Post by @hipsterelectron@circumstances.run

@hipsterelectron@circumstances.run 11 hr. ago

i'm heartbroken =',[ merkle how could you https://link.springer.com/content/pdf/10.1007/0-387-34805-0_40.pdf

While there has been a lively debate about the actual security level provided by DES[14.15,16,17] the fact remains that no major deviations from random behavior have been found.

shadow the hedgehog voice "what? this can't be....."

The existence of "random block ciphers" seems almost assured in some intuitive sense, and DES appears to be a reasonable approximation to one.

yeah that sounds good

84 Replies

4 Boosts

d@nny disc@

@hipsterelectron@circumstances.run 11 hr. ago

wow! this is easily one of the worst things i've ever read. worse than the incremental hashing paper and very directly says to put in secret information as a prefix to a message checksum

d@nny disc@

@hipsterelectron@circumstances.run 11 hr. ago

i totally assumed that was just a natural mistake anyone would make regard checksum security. nope! if this is actually a real paper he is on record telling you to put secret info in the prefix

d@nny disc@

@hipsterelectron@circumstances.run 11 hr. ago

another AWFUL one from mihir bellare https://cseweb.ucsd.edu/~mihir/papers/inchash.pdf

you might ask: didn't he already do an incremental hash paper? answer is: yes! this one has bad hashes instead of an incorrect usage of modular exponentiation

View (PDF)

d@nny disc@

@hipsterelectron@circumstances.run 11 hr. ago

i am kind of going mad with power though because you see there are very clearly two separate primitives at play for commutative (not order-dependent) and non-commutative (serial) data structures. and i have them both in my head now

~97 more replies

d@nny disc@

@hipsterelectron@circumstances.run 11 hr. ago

one of them is for parallel data, the other is for serial data. the first is not parallellizable, the second is fully parallelizable

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

somehow found this book when looking up the monster group https://archive.org/details/gdelsproof00nage/page/n133/mode/2up "Godel's Proof" by Ernest Nagel

https://en.wikipedia.org/wiki/Ernest_Nagel

it's kind of fascist but it's very compelling i couldn't stop reading

Ernest Nagel - Wikipedia

Internet Archive

Gödel's proof : Nagel, Ernest : Free Download, Borrow, and Streaming : Internet Archive

http://uf.catalog.fcla.edu/uf.jsp?st=UF020674712&ix=pm&I=0&V=D&pm=1

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

it does come out very strong against simulation of intelligence though. but i absolutely see why godel was possible to integrate into the number theoretic formal system without exploding it

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

https://en.wikipedia.org/wiki/Goldbach%27s_conjecture

that even integers are an infinite group and also that each of them can (probably) be represented as the sum of two primes is FUCKING ME UP FAM

Goldbach's conjecture - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

oh yeah and. i also learned about our boy lenstra https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm and now i see:

it's 1982. you are the US government. you have discovered a polynomial factoring method using lattices thanks to lenstra
it's 1985. you are still the US government. you have discovered an integer factoring method using elliptic curves thanks to lenstra

Factoring integers with elliptic curves | Scholarly Publications

Lenstra–Lenstra–Lovász lattice basis reduction algorithm - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

over the next 50 years, both elliptic curves and lattices would be advanced as cryptographic techniques. both of them are a component of cracking diffie-hellman

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

literally this is so absolutely 100% not serious https://en.wikipedia.org/wiki/Learning_with_errors#Public-key_cryptosystem

Learning with errors - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

hm. it's interesting how closely this mirrors the definition of "differential privacy"

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

so now i understand why they do so much fucking hashing

Like other PQC-KEM methods, Kyber makes extensive use of hashing internally. In Kyber's case, variants of Keccak (SHA-3/SHAKE) are used here, to generate pseudorandom numbers, among other things.[10]

literally the entire fucking "module learning with errors" problem is about sampling from random distributions gratuitously often so of course it's going to need an absurd degree of "randomness"

d@nny disc@

@hipsterelectron@circumstances.run 8 hr. ago

this is fucking my head up https://en.wikipedia.org/wiki/Transfinite_number

Any finite natural number can be used in at least two ways: as an ordinal and as a cardinal. Cardinal numbers specify the size of sets (e.g., a bag of five marbles), whereas ordinal numbers specify the order of a member within an ordered set[10]

Transfinite number - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

forgot about these https://en.wikipedia.org/wiki/Unum_(number_format)

Unum (number format) - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

oh hell yeah. i'm the world's biggest SHA-3 hater now

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

https://link.springer.com/content/pdf/10.1007/3-540-69710-1_5.pdf

this is the second draft from 1998, called PANAMA:

the buffer operates as a linear feedback shift register

bet? https://en.wikipedia.org/wiki/Linear-feedback_shift_register

The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the stream of values produced by the register is completely determined by its current (or previous) state. Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle.

View (PDF)

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

Panama has a low per-byte work factor while still claiming very high security.

it's literally a fucking CRC

The price paid for this is a relatively high fixed computational overhead for every execution of the hash function.

it's literally unkeyed. you have no excuse

This makes the Panama hash function less suited for the hashing of messages shorter than the equivalent of a typewritten page.

please do not try to check our randomness on a short stream

A typical application for Panama might be the encryption or decryption of video-rate data in conditional access applications (e.g. pay-TV).

please do use our guaranteed-to-recur-to-initial-state machine for high-rate data

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

RadioGatún is still a secure hash function;[2][3][4][5]

ok buddy

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

they describe how round 2 was different than round 1

https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09031.17

The round function in the mill is very similar to that of Panama, except that the indexes are taken modulo 19 (instead of modulo 17).

The Road from Panama to Keccak via RadioGatún

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

# Sponge functions?

they're trying so hard to make sponge functions a thing

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

literally you look this shit up https://en.wikipedia.org/wiki/Sponge_function

algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length.

ah so it's a turing machine. you're describing a turing machine

Sponge function - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

more specifically it's very obviously an attempt to dodge how finite-field diffie-hellman is still the best CSPRNG on the market

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

In the sponge construction, the input is applied to and the output is extracted from the same part of the state. This is in fact essential for the simplicity of the indifferentiability proof of the sponge construction

i'm no crypto genious but this sounds wrong

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

god fucking damn it. now i'm reading the maurer paper on indifferentiability and i feel this is just so obviously fucked now https://codeberg.org/cosmicexplorer/corporeal/src/branch/main/literature/maurer-indifferentiability-2003-161.pdf

The security of a cryptosystem C(S) involving a component S is typically proven by considering the cryptosystem C(T ) obtained from C(S) where the component S is replaced by an idealized component T.

yeah my cryptosystem would be soooooo secure if my components were replaced by spherical cows

The original system C(S) is secure if (a) the system C(T ) is secure, and (b) the component S is indistinguishable from T

see this is so clearly trying to pretend to be a polynomial-time reduction (WHICH DOES WORK!!!!) but it's WRONG

Cookie monster! (PDF)

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

omfg now read the very first line of SHA-3 explaining why they're sooooo spongey nao https://keccak.team/files/SpongeIndifferentiability.pdf

All cryptographic hash functions of any significance known today, i.e., MD4, MD5, the SHA and RIPEMD [15] families and several others, share the same design paradigm.

LMAO

They all consist of the iterated application of a compression
function.

NOT US!!! WE ARE THE BRAVE ONES WHO GO INTO BATTLE WITH ONLY A CRC

View (PDF)

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

During the last years, with
the recent collision attacks on SHA-1 as culminating point, it has become clear that designing a compression function that is both collision-resistant and efficient is not an easy task.

this is referring to the "compression function" that operates upon exactly one chunk of input at a time. it absolutely does NOT apply to generally "compressing" the bytes, since hash functions don't do that whatsoever.

but it sounds good right?

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

Moreover, weaknesses have been shown in the Merkle-Damgård construction itself.

gasp! not my Merkle-Damgård construct!!! anything but my Merkle-Damgård!!!!!

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

A well known example of such a weakness, discussed in [7], is the insecurity of the MAC function constructed from a Merkle-Damgård hash function by feeding the latter with the secret key followed by the message.

yeah cause it can leak the secret key not because it breaks the hash. this is SO unserious

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

also they keep getting Merkle-Damgård wrong in the text layer it's decomposed into like `a or some shit. lliterally could not be exerting less effort

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

wow i'm reading the maurer indifferentiability paper again and i cannot fucking believe this ever sounded good to me

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

Together with its derived notion of reducibility (Section 5), it will allow for exactly the same general statements about the security of cryptosystems as the conventional definitions.

this line is the killer. the incredibly vapid and confusing proofs that reduce to a confusing-but-standard framework? they are absolutely not fucking necessary. they're actively obfuscatory

general statements about the security of cryptosystems

you literally cannot do this. it is not something you can achieve

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

i really do wonder if several of the papers i've read today were composed with the authors like cackling over their incredibly mean-spirited april fool's day joke except people think this is real and they are gonna die

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

For each of these constructions they provide theorems stating that if the compression function is constructed using an ideal component, i.e., a finite input length (FIL) random oracle or an ideal block cipher (used as Davies-Meyer compression function), the hash function behaves as a random oracle [3] with output truncated to a fixed length.

literally "if it's ideal, then it would be literally random"

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

i can't fucking believe "random oracle" literally fucking means "totally random bitstream xD"

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

i'm gonna hate read the bellare random oracle paper that's ridiculous

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

wikipedia is blocking me from reading the page on random oracles

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

We argue that the random oracle model —where all parties have access to a public random oracle— provides a bridge between cryptographic theory and cryptographic practice.

bellare and rogaway are such absolute fuckboys

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

i liked a presentation rogaway gave to NIST a few years back and someone who i know is absolutely not a fed said he was a good guy so i guess i will have to tell them that is wrong

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

idk why they let me see those papers from the 1980s explaining how to use DH to do everything

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

Unfortunately, theoretical work often seems to gain provable security only at the cost of efficiency.

how are you being anti-intellectual while being cryptographic academics

This is due in part to the following. Theorists view certain primitives (e.g., one-way functions) as “basic”

one-way functions are bullshit, that's what merkle said about fucking DES. it's NP-completeness or go home

and build more powerful primitives (e.g., pseudorandom functions) out of them in inefficient ways;

i don't even know what a pseudorandom function is but i bet it sucks. also "inefficient"????? maybe yeah if you mean the BLAKE3 reference implementation

but in practice, powerful primitives are readily available and the so-called basic ones seem to be no easier to implement.

literally indistinguishable from LLM boosters

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

In fact theorists deny themselves the capabilities of practical primitives which satisfy not only the strongest kinds of assumptions they like to make, but even have strengths which have not been defined or formalized.

this is a crazy fucking thing to say. everyone in this field is first against the wall

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

In order to bring to practice some of the benefits of provable security,

in order to pretend like any of this is fucking real,

it makes sense to incorporate into our models objects which capture the properties that practical primitives really seem to possess,

it makes sense to sell snake oil

and view these objects as basic

and pretend this is all completely known and proven without dissent or controversy

even if the assumptions about them are, from a theoretical point of view, very strong.

thank you mr. president so strong

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

The idea is a simple one: namely, provide all parties —good and bad alike— with access to a (public) random oracle; prove correct a protocol in this model; then replace the random oracle by an object like a hash function. We stress that the proof is in the random oracle model and the last step is heuristic in nature.

literally the most cynical shit ever. worse than reading IETF bullshit

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

It is guided by many previous “unjustified” uses of hash functions.

i hate this so fucking much

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

Finally, we suggest constructions of hash functions which we believe
are appropriate to instantiate the random oracle.

finally, we have instantiated the random oracle, from hit sci-fi series "we made it up. you cannot instantiate the random oracle"

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

Theorists view a one-way function as a basic object and build pseudo-random functions from them.

literally they hate modular exponentiation so bad. it's the easiest fucking thing ever and anyone can do it

But in practice, as indicated by Luby and Rackoff [30, 31], the DES provides a pseudorandom function of 64 bits to 64 bits.

YOU CAN'T SAY THIS IN FUCKING 1993 LMAO

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

the other fucking diffie and hellman paper that wasn't the first one was literally describing how easy it would be to build and run a computer system to crack DES. that's not theoretical at all

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

If one is trying to design efficient protocols, it makes more sense to start off making strong, realistic assumptions about the primitives that will be used. Based on the paragraph above, a pseudorandom function on 64-bit strings is an excellent starting point. As we describe below, it seems reasonable to adopt even more generous assumptions.

yeah we should make it give us back free secrecy if the global active adversary says sorry

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

this is crazy

Consider first the map MD5. This function does not make a suitable replacement for a random
oracle since [41] has observed that for any x there is a y such that for any z, MD5(xyz) can be
easily computed given only |x|, MD5(x), and z.

i had to check the citation because there's no way they're actually trying to play with notation like MD5 and DH work the same way???

Structure like this shows up in applications; in particular, [41] points out that this means MD5(ax) cannot be used as a message authentication code of string x under key a.

yes, they literally actually are both using the "a" from DH while making it look like a multiplication, and adding insult to injury by actually referring to the very real issue of secret prefixes from any merkle-damgard construct

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

scheming..............complex integers where both components are bit strings, where the nonimaginary component represents the input message and the imaginary component represents the random state as a binary integer modulo some prime q

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

"gaussian integer" my ass https://en.wikipedia.org/wiki/Gaussian_integer

Gaussian integer - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

i have been thinking some pretty crazy things about the uniqueness of a prime factorization. you see, euclid in fact did not claim the uniqueness of a prime factorization. in fact, euclid was pretty specific that powers of primes were not distinguished at all.

Fundamental theorem of arithmetic - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

euclid definitely believed 1 to be a prime

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

i think failson gauss has fucked up number theory for centuries

Discussion

Discussion