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.

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

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/

This is a great tip. I've been using it for a few years now to watch various lectures on youtube--especially mathematics. Professors lecturing mathematics tend to speak slowly since they don't want to say anything erroneous. Speeding them up is usually amazing. For youtube; open the javascript console in your browser and type '$('video').playbackRate = 2.5;'. I've found that each lecturer usually has their own magic number regarding speed--after watching someone for a few hours and varying the speed you can usually find it.

http://en.wikisource.org/wiki/Science_and_Hypothesis

http://en.wikisource.org/wiki/The_Measure_of_Time

English translations of Science and Hypothesis as well as The Measure of Time can be read here;

`http://en.wikisource.org/wiki/Science_and_Hypothesis',

`http://en.wikisource.org/wiki/The_Measure_of_Time'.

In French, most of Poincare's original works can be read here;

`http://henripoincarepapers.univ-lorraine.fr/bibliohp/index.p....

The comparisons between filesystem-level vs. block-level encryption that I've encountered usually make a common distinction; namely that file metadata is still present when only applying fs-level encryption. What are some attributes of fs-level encryption that would make it a superior choice over block-level?

Trying to hold on to worthless jobs is a terrible but popular idea.

It seems warm and fuzzy to think Sam, and the implicit company he keeps (the ultra rich)--who are "leveraging not only their abilities and luck" but already accrued wealth--can and will redistribute it. Anyone who wasn't born yesterday will simply laugh at this prospect.

I'm not sure why Sam feels the need to call what most of the world is doing worthless. I think it's crude and indicative of a narrow social and cultural experience (which surprises me considering his position).

Believe it or not, there are cultures and groups of people who do not revere technology the way most North Americans do.

Also, a good exercise for Sam (and others possessing a similar world view) might be to think about how many "worthless" people and jobs it takes to accomplish the things he does (including this blog post).

1. modularity (and now that they have added generative functors à la SML, you can have true abstraction)

Could you share some information regarding Haskell and it's 'modularity' problem (vs. the ML family of languages). I'm fond of the way SML projects can be structured. How are people solving this using Haskell? Are there any interesting solutions for creating modular Haskell application/system's I can see today?

Thanks for your comment.

Tcl/Tk is an often overlooked tool to quickly test UI ideas.

Check out `http://wiki.tcl.tk/' (which has lot's of good information).

Also learn some Tcl by reading the redis test suite here,

`https://github.com/antirez/redis/tree/unstable/tests'.

Thanks for sharing, and for anyone else reading you might also like the following book--`Modern Compiler Implementation in ML' by Appel. (http://www.cs.princeton.edu/~appel/modern/ml/)

The street became colder, short Russian summer moves for the winter. Brains cooled down a bit and began to think.

I've always anticipated winter with a similar sentiment--I like the way this was said.

Previously discussed here

`https://news.ycombinator.com/item?id=5872043'.

And links to the `greatest of the great' papers;

`https://news.ycombinator.com/item?id=5872310'.

For anyone interested, here is another paper concerning similar topics:

`Verification of a Cryptographic Primitive: SHA-256',

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

And don't forget about `CompCert C compiler',

http://compcert.inria.fr/compcert-C.html.

Or the `Vellvm' project,

http://www.cis.upenn.edu/~stevez/vellvm/.

Thanks for posting this; this is such a great interview.

I always find you can learn so much from an accomplished artist. They seem to know about everything!

This was one of my favourite parts ...

Yes, I use pencil first. With Genesis, because there was so much technical stuff that I had to do, especially drawing correct anatomy, I would often make a sketch first on a piece of scrap paper, try and get it right before I started penciling on the drawing paper. How’s this angle, his arm, and the guy’s holding a tool, how does that look? I used Muybridge’s Animal Locomotion, from the late 1800s. It includes hundreds of photos of naked people in action, really handy for any kind of cartoon work where you have to draw people realistically in different actions and poses. Like the scene where Jacob is wrestling with the angel; fortunately there were pages of photos in Muybridge’s book of men wrestling.

This made me immediately search google for 'Muybridge Animal Locomotion'. I had seen the galloping horse images before, but had no idea Muybridge published 700+ such studies in 1887. [0] UPenn has some of them archived digitally. [1]

[0] http://en.wikipedia.org/wiki/Eadweard_Muybridge [1] http://dla.library.upenn.edu/dla/archives/search.html?q=muyb...

Besides the paperlet, and Scott's new format for getting out his ideas -- I thought the rolling ball binary mechanical computer called the Digi-Comp II was pretty cool, and can actually be purchased as well. [0]

[0] http://www.evilmadscientist.com

This man was an absolute giant of design. (Along with his wife, who is also an amazing designer).

For those of you unfamiliar with his work. He created a lot iconic imagery -- including the signage and maps for the subway system in New York City.

A quick google search or visit to [0] will reveal his talent. Btw, I always thought this website was quite poorly designed considering the Vignelli's abilities.

[0] http://vignelli.com/home.html

Rest in peace Massimo!

What an amazing exchange of ideas;

Knuths response to Tarjans Q15 was particularly interesting since he was able to illustrate his insight with a concrete example;

Thus I think the present state of research in algorithm design misunderstands the true nature of efficiency. The literature exhibits a dangerous trend in contemporary views of what deserves to be published.

Another issue, when we come down to earth, is the efficiency of algorithms on real computers. As part of the Stanford GraphBase project I implemented four algorithms to compute minimum spanning trees of graphs, one of which was the very pretty method that you developed with Cheriton and Karp. Although I was expecting your method to be the winner, because it examines much of the data only half as often as the others, it actually came out two to three times worse than Kruskal's venerable method. Part of the reason was poor cache interaction, but the main cause was a large constant factor hidden by O notation.