https://weakdh.org/ really cute shit
22
Replies
1
Boost
- INRIA Rocquencourt never signed off on this, that's where louis pouzin worked. note how the paper puts that first and marks it with a
*
- every fact that breathlessly took up the first 2.5 pages (and the last 2.5 pages) was known since hellman announced the attack himself and how to fix it by selecting an appropriate prime, something which requires no additional computational cost to do:
The new algorithm is least efficient when
p = 2p' + 1, wherep’is also prime.
this has not been broken
- the rest of it is just all TLS and IPSec vulnerabilities, all of which will of course remain true for all other protocols. a great way to "reset" the IETF's backdoor counter
- identifies NIST DSA as insecure--does not identify NIST as a problem despite literally spending another 2.5 pages screaming breathlessly about the NSA
this may have something to do with the johns hopkins and microsoft researchers listed. i have also literally never heard of these INRIA people before or even these INRIA sites before
(except Rocquencourt, which was fake and made up and had no representatives in the paper despite being the first location listed. and they didn't list microsoft in the pdf either)
- actively does incredibly wrong shit with asymptotic complexity:> Without better parameter choices, we resort to extrapolating from asymptotic complexity.
the parameter choices were prescribed in 1978, two years after diffie-hellman was published, but sure, let's do some asymptotic complexity with evil debate bros who want to kill people, why not
For the number field sieve, the complexity is
exp (k + o(1))(log N )1/3 (log log N )2/3),
that's still Omega(e^k) which is exponential
where
Nis the integer to factor or the prime modulus for discrete log,
that's literally not how it works. the chinese remainder theorem approach doesn't work on RSA's n = pq modulus and RSA is literally just diffie-hellman but worse for the actual asymmetric crypto part
and
kis an algorithm-specific constant. This formula is inherently imprecise, since theo(1)in the exponent can hide polynomial factors.
and they're lying about what's wrong, since as above exp(k) is exponential. really cute shit. go to hell
there has been zero progress on anything besides the completely fallacious "probabilistic algorithms" which were the reason quantum computing was "invented"
let's check back to page 2:
1 Recent spectacular advances in discrete log algorithms have resulted in a quasi-polynomial algorithm for small-characteristic fields [3], but these advances are not known to apply to the prime fields used in practice.
this is not trying to help anyone!!!!! this is misstating a factoring technique essentially solved in the year 1978 as if it were news and then replaying NIST and IETF vulns while not advising anyone on how to spot and avoid misuse!
i wonder how the researchers from johns hopkins and microsoft would advise the audience--oh:
Transition to elliptic curves.
not a single citation to how or why elliptic curves work better. not a single thing but the mention of the bernstein curve by name, without a link! god forbid someone cross-reference any claim whatsoever
looking on the wikipedia page for curve25519 states "Using a prime order subgroup prevents mounting a Pohlig–Hellman algorithm attack.[6]" and then [6] links to daniel jackoff bernstein's own paper, where he states:
Responsibilities of the user. The legitimate users are assumed to generate independent uniform random secret keys.
you know how that's done safely? diffie-hellman again!!!
Andrew C Yao, 1983: Theory and Applications of Trapdoor Functions
statistical cross-information is isomorphic to computational complexity means we can use complexity theory to address probabilistic arguments! of course people would take it the other way around but i'll link a sick thesis on how this is related to the q = 2p + 1 criterion
This means that a secret key
nis not used except to compute the public keyCurve25519(n, 9)and to compute the shared-secret hashH(Curve25519(n, q))givenq.
how is this fucking number 9 not the exact same thing as the oooooooo so scary points P and Q from DUAL_EC_DRBG, also first displayed by microsoft engineers at DEF CON?
(actually, what it should be interpreted as is the way ECC achieves smaller key sizes, if i understand correctly. it is not because it's magically safer. DH with q = 2p + 1 actually uses the whole prime field. it's not frivolous at all)
hellman wasn't fully sure on this point but what he did say was that primes of the form q = 2^m - 1 for some m if you can find them are even fucking better because you can losslessly transfer them to any m bit message
i don't know why number theorists and computer scientists aren't jumping out of their fucking seat at something that works in a machine numeral type because it's a prime number and just off of a power of two what else do you want
i'm asking because i haven't seen any cryptanalysis of this or other elliptic curve crypto and the arguments of security that go by key size alone are incredibly weak. this was something diffie called out in the 1976 paper as some bullshit that historians had found cardano (math fuckboy) would claim, incorrectly
the worst daniel on the planet called the one place in his official paper that claims to "specify" his elliptic curve "theorem 2.1", and then he immediately defined a function X_0 defined in terms of a secret inverse. is it a function of one or two variables daniel?
then he does his favorite thing which is telling you what cryptanalysis you're supposed to do. in this case the problem is fucking obvious because the lenstra method (linked later) through the chinese remainder theorem (he calls this "index calculus" in other work) very very specifically works to solve the discrete log problem based upon a fixed-size prime q.
it takes an attacker an IMMENSE amount of time to break one q = 2p + 1 and even using it takes a ton of time and that's why it was updated to use the new formula in 1978
so, of course, when daniel jackoff bernstein describes his discrete log cryptosystem based upon a fixed prime power, he says:
The attacker’s goal is to decrypt
or forge these messages.
that's not the concern people have with diffie-hellman. they're concerned about cracking long-lived private keys.
this is the real problem DH is protecting against, because the forge/decrypt problems are reduced to discrete log again, which can be proven in a tiny paper
and that's because it's actually possible for anyone to analyze what the fuck DH is doing whereas ECC security is based on an IBM guy saying "uhhhhh definitely can't happen" and then having okamoto hand their ass to them (paper later)
then he demonstrates how far the bar has fallen for cryptanalysis in government or academia:
One can improve speed by choosing functions at lower security levels; for example, dropping from 255 bits down to 160 bits. But—as discussed in Section 3—I can easily imagine an attacker with the resources to break a 160-bit elliptic curve in under a year.
again, curve25519 does not let you modify this at all. the prime field has been fixed since 2006.
it sure would be cool to be able to upgrade your security according to your computational resources while maintaining an exponential advantage in computing resources against the US government. if only there were a protocol that explicitly described creating a safe new prime q = 2p + 1 from the old prime p whenever you needed to increase a security level
now personally i still don't yet feel quite confident enough about the q = 2p + 1 criteria. if i understand this 1974 phd thesis from john dillon correctly, it produces sqrt(q) generating subgroups of minimum size sqrt(q),
...based upon a remarkably well-documented and easy-to-follow argument that doesn't require pulling in other fields of math beyond matrix multiplication and group theory
[unlike every elliptic curve and lattice cryptosystem from this fucking millennium]
if you've ever played around with the differences between prime numbers you might have found these kinds of relations described as "difference sets" (which are shown to represent hadamard matrices, which represent a transformation of a binary vector in 2m bits). this stuff should actually be taught to undergrads and made free online
but the bar is so much higher for "literally doing an exponent in a number system that just requires carrying over machine arithmetic" than any crypto introduced since the USA PATRIOT act. it sucks seeing what i've seen before in software getting replicated in mathware.
not getting stuck with whatever RSA security gives you for prime numbers and also having actually auditable cryptographic methods is just incredibly valuable. did you know DH is how double ratchet works
if elliptic curve crypto was capable of anything more meaningful than obfuscating things we would know it. it took 10 years for miller and koblitz (i'm not linking their papers, they actively left me understanding less than before i started) to decide ECC crypto is totally real, we promise!
and then they stated without any proof that it's not susceptible to the still-exponential attack from lenstra (whose paper in 1982 was the same year as ECC crypto came out which claimed to be safe against it)
