Re: PGP Lame question

Milan VXdgsvt <milan_vxdgsvt@seznam.cz> wrote:
>> If I can get you to encrypt the message m+SHA1(m), the ciphertext
>> would be CBC-AES(k,m+SHA1(m)+SHA1(m+SHA1(m))). If I am a bit careful
>> with the message length, I can shave off the final two blocks of
>> the ciphertext and get CBC-AES(k,m+SHA1(m)).
>
>Well, not very useful, but neither nice. I'm beginning to see why
>homebrew crypto does no good.

If you consider CBC-AES(k,m+SHA1(m)) vs. c1=CBC-AES(k1,m),
c=c1+HMAC-SHA1(k2,c1), you see that both schemes have approximately
the same cost, the latter is always secure, while the former has
security problems. The choice is easy.

>> If this is AES applied to SHA1 truncated to 128 bits, it has only
>> 64 bits of security against a chosen message attack.
>
>I guess it's always at most (half the length of MAC) bits of security.

What I had in mind is: find two colliding messages M1 and M2. Obtain
AES(SHA1(M1)), and you have found AES(SHA1(M2)). So it is a chosen
message attack creating a usable forgery with 2^64 work. For a good
MAC you would expect roughly 2^128 work. (For instance, in HMAC,
such collision attacks do not work.)

Therefore, encrypting an unkeyed hash is not that good. Encrypting
certain keyed hashes is ok, I think, and the keyed hash functions
required for that kind of thing can be very fast.

>I was interested if the goals
>
>1) B can be sure the message is from A,
>2) A can deny knowing B,
>3) No one else can read or forge or modify M,
>4) The protocol has single round between A and B,
>
>when
> the message can be intercepted, but the sender is unknown,
>
>can be satisfied at all.

I do not immediately see why not.

Perhaps this could be described as an authenticated key transport
scheme where the recipient can forge encapsulations to himself.
(That is generally considered a bad property in a scheme, but in
this case it is a desired property.)

>b) my scheme could satisfy them
> Sending: S + CTR-AES(R,M) + MAC(R, CTR-AES(R,M))
> Where as before S := Sign_privA( Crypt_pubB( R ))
> and CTR is always initialized to 0

Let me add a couple of hash functions and spell things out in
detail.

Alice's public and private keys are (n_a,e_a) and (n_a,d_a), Bob's
public and private keys are (n_b,e_b) and (n_b,d_b). Assume that
n_b < n_a < C*n_b for some small C. (We can ensure this by using
different sender and receiver keys, which would anyway be a good
idea.)

To encrypt a message, choose a random number R in Z_{n_b}, compute

        c0 = (R^e_b mod n_b)^d_a mod n_a
        k1 = h1(R)
        k2 = h2(R)
        c1 = Enc(k1,m)
        c2 = Mac(k2,c1)

        c = c0 || c1 || c2 .

To decrypt a ciphertext, split it into c0', c1', c2', and compute

        R' = (c0'^e_a mod n_a)^d_b mod n_b
        k1' = h1(R')
        k2' = h2(R')
                        if c2' != Mac(k2',c1) then stop
        m = Dec(k1',c1')

To forge a ciphertext, Bob chooses a random c0'' in Z_{n_a} such
that c0''^e_a mod n_a < n_b.

        R'' = (c0''^e_a mod n_a)^d_b mod n_b
        k1'' = h1(R'')
        k2'' = h2(R'')
        c1'' = Enc(k1'',m)
        c2'' = Mac(k2'',c1'')

        c = c0'' || c1'' || c2''

Here's an attack on confidentiality: Eve has the public and private
keys (n_e,e_e) and (n_e,d_e). Eve sees the ciphertext c0 || c1 ||
c2 sent to Bob which she knows is from Alice. First she computes

        c0''' = (c0^e_a mod n_a)^d_e mod n_e .

Then she sends the ciphertext c''' = c0''' || c1 || c2 to Bob along
with the cover story:

        Dear Bob,
        I planned to send a very important and very secret message
        to someone you don't know. But unfortunately, I made a big
        mistake. I think I encrypted the message to you, not to the
        intended recipient (I am such a klutz with computer stuff,
        you know). But after I encrypted the message, I deleted it.
        So now I really, really need your help. I need you to decrypt
        this message and send me the result, but please, please,
        please, since you are a kind gentleman, do not look at the
        message. Delete it and the ciphertext afterwards. Thank
        you oh so very much, signed Eve.

Bob is of course a gentleman and does as requested, and Eve breaks
the confidentiality of the message.

A good system ought to refuse to decrypt the message when Bob tries
to decrypt.

Seeing if it is possible to protect against such attacks and still
preserve your properties may lead you somewhere.

-- 
Kristian Gjøsteen