[curves] encoding points -> bitstrings: indistinguishability, PAKE?

[Joe]

On 6/24/21 3:50 AM, Trevor Perrin wrote:
> On Wed, Jun 23, 2021 at 4:43 PM Joe <joe at celo.io> wrote:
>>
>> On 6/24/21 1:30 AM, Joe wrote:
>>> You probably want a PRP (or key-wide block cipher) to avoid scenarios
>>> where flipping individual bits lead to weird corner cases. At the very
>>> least an attacker could structure their key such that e.g. two guesses
>>> would decode to related keys, which weakens the properties of your EKE
>>> PAKE ever so slightly (no longer one guess per interaction).
> 
> 
> Trying to write down security goals for a simplified EKE:
> 
>    Alice -> Bob: Encrypt(password, Encode(g^a))
>    Alice <- Bob: g^b, Hash(g^ab)
> 
> where Hash() is modelled as a random oracle, and Hash(g^ab) provides
> key confirmation.
> 
> Something like this?

Here Alice gains confidence Bob guessed the password, but Bob has no 
confidence or ack that Alice knew it. You can run the protocol in 
parallel, but then you have to watch out for Alice sending Bob his own key.

If Alice aborts the protocol after seeing Bob's wrong Hash(g^ab) then 
Alice reveals to not just Bob, but to wiretapping third parties too, 
that Bob's attempt was wrong. Likely not a concern.

Hash(g^ab) is vulnerable to stupid things like Bob sending "g^b = 0" and 
a fixed Hash without knowing the password at all. Should probably be 
handled in the implementation somehow, but that means we still need to 
decide how to handle bad inputs. If Bob's key is also decoded then it is 
harder for Bob to inject bad stuff to pin the DH result.

>   (a) A malicious Alice can't produce an initial message and two
> passwords which decode this message to two different public values
> A1=g^a1 and A2=g^a2 for which Alice knows a1 and a2; because then she
> could check two passwords against Bob's response.
>   (b) A malicious Bob, given any valid initial message, can't produce a
> password for which the initial message fails to decrypt or decode,
> because then he could rule out that password.
> 
> I think (b) is easy to check, so the risk with Encrypt()=XOR of
> Hash(password) is about (a):  maybe Alice could find two DH public
> values whose encodings have some XOR difference, and for which she
> knows the discrete log?

Yes, but this would also be an issue with a 256 bit block width since 
the attacker can spend a great deal of time offline preparing it such 
that the decryption of their chosen keypair resulted in the two 
representations from Elligator. I don't see an easy way to fix that; 
perhaps multiple keys and an n-way diffie-hellman or something like that 
would make it harder.

The XOR thing would make this possible for interactive MITM where Alice 
would still be able to complete the protocol run, oblivious to the 
attack, but where the MITM learns that their bit-flip worked, which 
partitions the key space of the shared secret. After enough repeated 
runs with the same password, the MITM obtains the password (a bit like 
the WPA-EKE attack I described earlier).

Both are a bit far-fetched and likely not a problem in a real-world 
settings, but interesting threat models to think about.

> If we can't rule that out via some assumption about the encoding, I
> wonder what is the simplest encryption construct that rules that out.
> 
> Interesting topic, will think more...
> 

I think those properties make sense. I found it helpful when modelling 
to remember to add messages from both parties (likely outcome of a key 
exchange); such messages are important because they can (sometimes) 
serve as reveals:

In the protocol described above, if Alice sends
Encrypt("hello", KDF("msg1", Hash(g^ab)))
after Bob sent the wrong Hash(g^ab), Bob gains an offline oracle for 
trial decryption, so it's important to abort the protocol run there.