https://weakdh.org/ really cute shit
37
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)
i absolutely 100000% believe we should be able to prove P < NP based upon the discrete log problem. fucks me up how suddenly doing math right was considered harmful when it turns out math is literally not on the side of evildoers
it's 40 years of diffie-hellman this year!!!
so the idea that by the year 2006 for curve25519 and certainly 2015 when matthew d green from johns hopkins university thought it was safe to start blatantly lying about asymptotic analysis upsets me greatly.
standards would have dropped so precipitously that you can claim your elliptic curve method is safe against the probabilistic methods (which never worked against diffie-hellman q = 2p + 1) and then not even prove it safe against probabilistic methods (which are literally still exponential-time and exponential-memory, since 1978) is crazy
i definitely liked these two papers on ECC (from 2/3 of the same authors each time, both of whom i don't even like):
It was learned from the hybrid system that the elliptic curve computations, especially over nonsupersingular curves, were I/O intensive.
this is their description of creating a custom FPGA system just to do ECC with.
recall this term "supersingular".
then:
The main result of the paper is to demonstrate
the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying finite field. For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time
now keep in mind that probabilistic algorithms aren't real, and okamoto is the only one i like at all among those three and i wish i could apply to study under him somehow.
but, under their own criteria of what makes ECC fast to implement, it is reducible to discrete log. so is it a faster discrete log? do we even know that it's faster? we'll have to see, won't we?
but it does at least shed light on how complex the analysis of groups becomes when you have to factor polynomials in finite fields ON TOP OF THE DISCRETE LOG PROBLEM which is NOT an easy thing to do at all, JUST to get to the point where you can even ANALYZE A DAMN THING!
math works like other secure code! complexity is not safe!
with ECC i'm pretty confident you literally don't have "n bits of security" at all anymore (which is often a lie, but can be real for q = 2p + 1 diffie-hellman). i have not found a single thing to support that they manage to create new subgroups out of nowhere that give them more security in fewer bits!
meanwhile there is a whole separate theory about using discrete log as an actually secure CSPRNG, because the problem of guessing a hidden state is actually so much easier when it's also reducible to complexity theory
(i'm still not quite sure about that part yet, btw. i need to understand the q = 2p + 1 transformation better but i believe it is correct that you should be able to extract log q bits per exponentiation and you should be able to do that sqrt(q) times. but this is where the trail goes cold)
(like people say you can pull log q bits there are papers on it but i don't just trust anything i read because it says diffie-hellman on it)
but i cannot tell you how my jaw dropped to learn elliptic curves and lattices are quite literally the two components of the techniques used against discrete log in diffie-hellman. very literally
this is the one i found most useful to understand it (this is not the quadratic/number field sieve method, btw, that just runs to factor your q - 1 afaict):
A.K. Lenstra, H.W. Lenstra, Jr., L. Lovasz: Factoring Polynomials with Rational Coefficients
there's a book by lenstra on the number field sieve with a surprise visit by daniel jackoff bernstein in the credits but i haven't read it because i don't really care that much and as far as i'm aware you can in fact just delegate to the hardness of discrete log and feel satisfied that you are not going to die horribly. ECC does not give you that