[OTR-dev] DSA, RSA, ECDSA, etc

[Jacob Appelbaum]

Nate Lawson:
> 
> On Sep 24, 2012, at 1:31 PM, Adam Langley wrote:
> 
>> On Mon, Sep 24, 2012 at 4:06 PM, Jacob Appelbaum
>> <jacob at appelbaum.net> wrote:
>>> r? Not k? What happens if k repeats?
>> 
>> Ed25519 is a Schnorr signature based system and so the variable
>> names are slightly different. It has the same RNG problem as
>> (EC)DSA however and Ed25519 solves it with deterministic
>> signatures. Since (EC)DSA generally has non-deterministic
>> signatures, I'd recommend maintaining that property in any generic
>> implementation: i.e. hash in the private key, message and entropy
>> to generate k. That's what we do in Google systems.
>> 
>>> But what is the right way to ensure that k has some safety
>>> without being weaker by being predictable? I imagine a lot of OTR
>>> conversations start with pretty well known plaintext such as "hi"
>>> or "hello" or some variant.
>> 
>> In OTR the data that is signed includes the two, ephemeral, DH
>> public keys, not any user message. Therefore a deterministic
>> signature shouldn't be problem because the signed data is random.
> 
> Jake, I appreciate your care in reviewing OTR for these kinds of
> robustness issues. 

I have to admit, I never would have considered it had I not read your
blog, so hey, thanks. :)

> I think providing "defense in depth" for PRNG
> implementations and their input entropy is often overlooked.

Agreed - the lesson of the Debian bug is that we have bugs we cannot see
and later, we will feel their impact _if we're lucky_ enough to know.

> 
> I generally favor keeping PRNG components independent and combining
> their final output. For example, you might take /dev/urandom output,
> the hash of the message, a timestamp, the last nonce, and the DH
> publicly exchanged values (e.g., g^x and g^y, NOT the key 'x' itself
> or the g^xy session key aka 's'). All of these would be hashed to
> create the nonce.
> 

That seems reasonable. What would you suggest for the actual hashing?

OTR already uses SHA256 - I think we can ensure that we will always have
SHA256 around in libgcrypt. Shall I use that and call it a day?

> The general idea is that complete failure of any one (or possibly
> more) inputs should not destroy your application's security. If
> /dev/urandom becomes 0 and the timestamp repeats, you still have a
> unique and unpredictable nonce for a given pair of users for each
> unique message at a given index in this conversation.
> 

That is exactly the property that I would like for this extended dsa
sign() function. :)

> I think something like this should be done in addition Adam's point
> that the DH public values are part of the message. It doesn't hurt to
> duplicate the use of them in this way, feeding directly into the
> nonce creation instead of implicitly by being part of the message
> itself. If someone changes the message format, these kinds of
> implicit contracts have a chance of being forgotten.
> 

Absolutely.

> Anyway, you should carefully review how this nonce is created and not
> throw in the kitchen sink. I'm happy to see a specific proposal.
> 

I'll start working on a patch; it seems like any other proposal wouldn't
be very specific. :)

All the best,
Jake