The Pure Crypto Project's Hash Function

[Eric Rescorla]

Ralf Senderek <ralf at senderek.de> writes:

> On 3 May 2003, Eric Rescorla wrote:
> 
> > Can you explain every single line of the modular exponentiation
> > routine you're using?
> 
> Yes, of course I can, otherwise the Pure Crypto Project would lack its
> second most important feature, clarity, security being the most important.
> Fortunately I have to explain only 10 lines of code:
> 
>           def ModExp (Base, Exp, Mod):
>                 Hash = 1
>                 X = Exp
>                 Factor = Base
> 
>                 while X > 0 :
>                       Remainder = X % 2
>                       X = X / 2
>                       if Remainder == 1:
>                                Hash = Hash * Factor % Mod
>                       Factor = Factor * Factor %  Mod
>                 return Hash
> 
>
> I have explained this sucessfully even to 18 year olds who wanted to
> learn about computer security. I will explain off-list on request.
This would be funny if it weren't sad. There's all this
code in the Python interpreter that is doing your modular
exponentiation for you that you haven't audited at all.

You might as well argue that using SSL is simple since all
you have to do in some APIs is do: open("https://blahblach").

> > Every single line of the compiler you're
> > using to compile the code?
> 
> No, I cannot. As I'm using bare multiplication and addition of long
> integers, I cannot rule out the possibility that the Python-interpreter
> executes some malicous code when multiplying x and y. But I don't have
> any reason to assume that.
Nor do you have any reason to assume that OpenSSL's SHA-1 code
has been botched but you seem quite ready to assume that.

> > The amount of math you would need to demonstrate the security
> > or insecurity of your hash algorithm is incredibly prohibitive,
> > and vastly larger than the amount of effort required to analyze the
> > C code in SHA-1.
> 
> I'm not sure, primes sometimes make an argument simple, please read
> my remarks on security.
I have. I'm not convinced.

Strangely enough, people have spent the past 20 years or so 
trying to decide if things like DH and DSA were secure and
we still find new stuff, despite primes "making things simple"
in those cases.

-Ekr



-- 
[Eric Rescorla                                   ekr at rtfm.com]
                http://www.rtfm.com/

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com