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.
The problem is really much worse than this. You don't merely need a non-repeating nonce (the way you can get away with a GCM nonce that increments by 1 every session): you need an unbiased nonce.
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.
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?
It is not a common occurrence, but it does happen occasionally.
Once upon a time the best known way to compute discrete logarithms was Shanks's Baby-Step Giant-Step. This method begins by constructing a table of size sqrt(p), and then finds a logarithm in time sqrt(p) as well. But in 1978, Pollard came up with the rho algorithm, which did not require any storage beyond 2 group elements, and had the same asymptotic runtime! This method relies on collision-finding, and is still the best algorithm today---in a modified fashion to make it parallelizable---to attack elliptic curves.
Another example happened in integer factorization, but is more nuanced. In the early 1980s, the best known integer factorization algorithm to break semi-primes (i.e., RSA keys) was the quadratic sieve. Now, the quadratic sieve runs in time exp( sqrt( log n log log n ) ), but also requires storage proportional to the size of its factor base---exp( 1/2 sqrt( log n log log n ) ). Then in 1985 Lenstra came up with the elliptic curve method, which once again requires little storage and has the same asymptotic runtime as the quadratic sieve. In practice, however, the quadratic sieve will be faster for RSA numbers. And in 1990, the number field sieve improved the running time to something curve-based methods could not match.
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.
>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.
>A function f from a set X to a set Y is called a one-way function if f(x) is “easy” to compute for all x \in X but for “essentially all” elements y \in Im(f) it is “computationally infeasible” to find any x \in X such that f(x) = y. [0]
>1.16 Definition
>A trapdoor one-way function is a one-way function f : X -> Y with the additional property that given some extra information (called the trapdoor information) it becomes feasible to find for any given y \in Im(f), an x \in X such that f(x) = y. [0]
[0]; Menezes, A.; Oorschot, P. van; Vanstone, S. (2001). Handbook of Applied Cryptography (5th ed.). CRC Press.
Thanks for your comment. It brings up positive nostalgic memories for me. I grew up speaking, reading and writing three different languages, as well as constantly hearing another being yelled through the phone.
Not sure about the article; personally it's helped me be able to adapt quickly in lots of foreign places and realize that with a little time and enough "banging your head against a desk" anything can be understood (even Cyrillic alphabets).
Same here. Fluent in 4 languages.
For me the best advantage is not learning just the language, but the whole culture. If you can't laugh to comedy standup stars and understand the culture of other people, it really doesn't help much if you are fluent in one language or more. Languages also promote a more liberal worldview and more tolerance for others.
I agree with you - the moment you learn another language, you step outside the borders of your own culture, metaphysically, and are able to see things from a different perspective than what is normal. That's the value - and the liability - of language, in my opinion.
The world would be a better place if we all spoke more than just our mother-tongues ..
Here is a nice starting point for a generic rb tree structure in SML.
(* generic red-black-tree in Standard Jersey ML *)
type key = string
datatype color = R | B
datatype tree = E | T of (color * tree * key * tree)
fun rbmem (x, E) = false
| rbmem (x, T (_,a,y,b)) =
if x < y then rbmem (x,a)
else
if x > y then rbmem (x,b)
else
true
fun balance ( (B,T (R,T (R,a,x,b),y,c),z,d)
| (B,T (R,a,x,T (R,b,y,c)),z,d)
| (B,a,x,T (R,T (R,b,y,c),z,d))
| (B,a,x,T (R,b,y,T (R,c,z,d)))) = T (R,T (B,a,x,b),y,T (B,c,z,d))
| balance body = T body
fun insert (x,s) =
let fun ins E = T (R,E,x,E)
| ins (s as T (color,a,y,b)) =
if x < y then balance (color,(ins a),y,b)
else if x > y then balance (color,a,y,(ins b))
else s
val T (_,a,y,b) = ins s (* guaranteed to be non-empty *)
in T (B,a,y,b)
end
>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;
Observe that, Or, Which allows us to recover the private key x.Since,