YAYERKA
Joined 16 years ago
Karma
750
Submissions
134
Member since
Sep 28
H
View on Hacker NewsRecent submissions
Comment · 10 years ago
I believe an natural segue here is to remind people about cryptopals (especially set 8). Ie., I don't have the chops and wouldn't attempt to writeup EC/DSA nonce bias and partial key exposure attacks better than you all--not to mention the challenges regarding GCM. Cheers.
Comment · 10 years ago
lordnacho, as tptacek wrote below (which also applies to DSA);
>a full repeat instantaneously destroys security with a single pair of signatures
Roughly--assuming ECDSA parameters (H,K,E,q,G)--where H is a hash function, E the Elliptic Curve over finite field K w/ point G of prime order q. Suppose two different messages m and m' have been signed with private key x using the same (non-ephemeral) random nonce value of k.
According to ECDSA Signing these messages m, m' become signatures (r,s), and (r',s') where;
r = r' = kG,
s = (H(m) + x*r)/k mod q,
s' = (H(m') + x*r)/k mod q.
(H(m) + x*r)/s = k = (H(m') + x*r)/s' mod q.
x*r(s' - s) = s*H(m') - s'*H(m) mod q.
Since,
x = s*H(m') - s'*H(m) / r*(s' - s) mod q.Comment · 11 years ago
>Ralf-Phillip Weinmann had a good Black Hat presentation about this bug class.
Comment · 11 years ago
Comment · 11 years ago
Following the "List of my papers" section from the "Number Theory" page
https://sites.google.com/site/jmptidcott2/nthy
>Some authors even applied the name "kangaroo" to any random walk in a cyclic group. This is zoologically absurd (a kangaroo cannot jump in one bound to another continent) - and mathematically confusing.
Spurred by this thread and especially after studying BSGS and the Pollard Rho for DLP set of algorithms more in depth over the last few days; I found his clarification and justification regarding the "taxonomy" of these methods entertaining and enlightening. Thanks again.
Comment · 11 years ago
My mistake; 1978 Pollard's Rho algorithm for DLP. Was looking at Pollard's Rho for integer factorization at the time. On that note; what a monster this Pollard character. Wonder what he is up to these days.
Comment · 11 years ago
Thanks for your response; 1971 Shanks' BSGS improvement to 1974 Pollard Rho for DLP is indeed a nice example.
Comment · 11 years ago
Thanks for posting; found many sections interesting especially 3.2;
>3.2. Does NSA have an $n^{1/3}$-algorithm for finding elliptic curve discrete logs? ...
In 2013 Bernstein and Lange described such an algorithm albeit with intractable pre-computation costs. [https://www.iacr.org/conferences/asiacrypt2013/slides/44.pdf]
In the paper Koblitz and Menezes say "it is conceivable that the NSA has found (or believes that there might exist) a similar algorithm that requires far less precomputation."
This made we wonder; are there any historic example(s) of an algorithm we have improved over time which lead to the side stepping of a previously unavoidable and large pre-computation?