YAYERKA

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.

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.

Observe that,

  (H(m) + x*r)/s = k = (H(m') + x*r)/s'  mod q.

Or,

  x*r(s' - s) = s*H(m') - s'*H(m)  mod q.

Which allows us to recover the private key x.

Since,

  x = s*H(m') - s'*H(m) / r*(s' - s)  mod q.

>Ralf-Phillip Weinmann had a good Black Hat presentation about this bug class.

https://www.youtube.com/watch?v=PqW8-MUu09c

https://comsecuris.com/research/slides-bignum-bhus2015.pdf

about the C; https://software.intel.com/sites/landingpage/IntrinsicsGuide...

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.

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.

Thanks for your response; 1971 Shanks' BSGS improvement to 1974 Pollard Rho for DLP is indeed a nice example.

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?

"Verification of a Cryptographic Primitive: SHA-256", Andrew Appel

https://www.cs.princeton.edu/~appel/papers/verif-sha.pdf

In a cryptographic context;

>1.12 Definition

>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.

For a slightly more mathematical introduction: https://www.youtube.com/watch?v=t3JzdKE-Fhs along with accompanying slides http://crypto.biu.ac.il/sites/default/files/3rd_BIU_Winter_S... both from ""3rd BIU Winter School on Cryptography: The basics of elliptic curves - Nigel Smart".

Here are links to the videos in a larger format;

# Opening Remarks with Alex Stamos

https://news.yahoo.com/video/yahoo-trust-unconference-alex-s...

# Trust and the Future of SV with Alex Stamos and Frank Chen

https://news.yahoo.com/video/yahoo-trust-unconference-firesi...

E2E Encryption with Yan Zhu

https://news.yahoo.com/video/yahoo-trust-unconference-e2e-en...

Zerocash with Zooko Wilcox-O’Hearn

https://news.yahoo.com/video/yahoo-trust-unconference-zeroca...

TLS with Adam Langley

https://news.yahoo.com/video/yahoo-trust-unconference-tls-ad...

Secure Messaging with Trevor Perrin

https://news.yahoo.com/video/yahoo-trust-unconference-secure...

Legislation and Let’s Encrypt with the EFF

https://news.yahoo.com/video/yahoo-trust-unconference-legisl...

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).

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

If your project can get away without having to build your own images; I would recommend Amazon Linux to anybody using EC2.

I've used Amazon Linux AMI's since 2012 on several different instances. At first `ps aux` you might think you are using *BSD!

Here are two useful links.

Regarding Amazon Linux AMI security updates; https://alas.aws.amazon.com/

FAQ; https://aws.amazon.com/amazon-linux-ami/faqs/