Live data from Hacker News

How do we know if a crypto function is correctly implemented?

rjlipton.wordpress.com

31–32 of 32 posts

Re: How do we know if a crypto function is correctly implemented?

#31
post #20

The rabbit hole goes deeper: how are you sure the compiler is correct? See the paper by John Regehr and his group: http://blog.regehr.org/archives/492 I'm not just saying this randomly in any subject that is concerned with correctness, as Regehr's work clearly shows that the places where compilers make the most mistakes are the places that cryptographic functions play in: numeric calculations at the boundaries of wha…

Turing award lecture by Ken Thompson, "Reflections on trusting trust".

Recommended if you haven't read it already.

https://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thomp...

Re: How do we know if a crypto function is correctly implemented?

#32

Possible and (relatively) easy. We write the formal definition of the function in Cryptol, and use the Cryptol toolset to compare it to our implementation. Cryptol[1] has the amazing ability to verify implementation equivalence between [a large class of] functions written in Cryptol, C, Java, Assembly or VHDL (as far as I recall). Of course this class of functions is not Turing Complete, but it's good enough to verif…

And then how do you know the formal definition you give to Cryptol is correct? How do you know that Cryptol correctly transforms the formal definition to a logic circuit? How do you know it correctly transforms your C/Java/Assembly/VHDL to a logic circuit?

Its a deep rabbit hole.

Post reply on HN