[Cfrg] On using ROs for analyzing randomness extraction functions

[David Wagner <daw at cs.berkeley.edu>]

Jack Lloyd writes:
>David Wagner writes:
>> there do exist (contrived-looking)
>> trapdoor permutations that interact with SHA256 badly enough to make
>> "hash-then-sign" insecure with those trapdoor permutations.
>
>Could you provide a reference to or sketch of what such a function might look
>like? I gave it a bit of thought and couldn't see any way of creating a
>trapdoor such as you describe, so now I'm curious.

Hmm.  Here's a boring one.  Let (d,n) be a RSA private key.
    Trapdoor(X):
    1. If X=SHA256(0), output d.
    2. Otherwise, output X^d mod n.
Note that Sign(M) = Trapdoor(SHA256(M)) is insecure in the real world
(just ask for a signature on the all-zeros message), but Sign(M) =
Trapdoor(H(M)) is secure in the random oracle model.

Ok, I told you it wasn't very interesting.

(Well, strictly speaking you need to use this in a full domain hash
mode, so let me assume you do so: e.g., use SHA256(0,M)||SHA256(1,M)||..
instead of SHA256(M), and so on.  That's just a distracting detail.)

(Strictly speaking, the above isn't a permutation, but I think one can
patch it up to make a permutation without too much work, if you care.)

In this example, it is obvious that Trapdoor() is "not independent" of
the hash function SHA256, which should immediately make one extremely
suspicious about the possibility of "bad interactions" between Trapdoor()
and SHA256.  Thus in this case, despite the fact that hash-then-sign
with Trapdoor() is secure in the random oracle model, I doubt that anyone
would be fooled into using Trapdoor() in practice.

Alternatively, one can say that it is a modelling mistake to leave
Trapdoor() exactly as is when transitioning to the random oracle model.
One might suggest instead that the call to SHA256 in Trapdoor() should be
replaced by a call to the random oracle H.  Then it would become clear in
the random oracle model that the signature scheme is insecure.  However,
this just pushes around the burden of proving "no bad interactions" from
the interpretation to the modelling stage.  One can come up with variants
of Trapdoor() where the computation of SHA256 is obfuscated enough that
it would be hard to recognize it for what it is during the modelling stage.

I'm making this up off the top of my head, so I hope I'm getting this
all right.  I _think_ I've got the essentials correct, but you can
double check.

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg