[Cryptography] Non-Authenticated Key Agreement

[Bill Cox]

On Wed, Sep 23, 2015 at 11:56 AM, Kristian Gjøsteen <
kristian.gjosteen at math.ntnu.no> wrote:

> 23. sep. 2015 kl. 20.04 skrev Philipp Gühring <pg at futureware.at>:
> > Diffie-Hellman makes sure that both parties end up with a secure key d if
> > at least any one of them has a secure random number generator and follows
> > the protocol correctly.
>
> That is false.
>
> If Alice’ random number generator always outputs 3, Eve can easily deduce
> the shared secret, regardless of what Bob does.
>
> The correct statement is that the parties end up with a randomly chosen
> key if Bob (the responder) follows the protocol (with some minor additions
> to the textbook version). They end up with a randomly chosen key if Alice
> (the initiator) follows the protocol and Bob’s value is independent of
> Alice’ value. Note that «randomly chosen» is not the same as «secure».
>
> --
> Kristian Gjøsteen


It turns out that no public-key protocol can ever be designed that delivers
security in the face of a bad RNG on just one end.  This is another reason
that a good RNG is critical to security.

This is something I proved to myself a while back.  In general, if Eve can
predict any action Bob will take, because Bob has no actual source of
random behavior, then Even will know anything Bob knows as soon as he knows
it.  If Bob is a Turing machine with no random oracle, and Eve can see
initial state and all the input and output to Bob, she can simulate the
state machine on the inputs herself and know every bit of state Bob
contains.  Not good for Bob's privacy.

For Bob's internal state to diverge from what Eve can trivially predict,
Bob needs a random oracle.  I carry one in my pocket
<https://www.tindie.com/products/WaywardGeek/infinite-noise/>, just for fun.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150923/bd74fb2b/attachment.html>