Disguising the Key length (Was...Has a change taken place in factoring RSA keys)

[Major Variola (ret)]

At 02:09 PM 11/10/03 -0500, Tyler Durden wrote:
>My first question is, how easy is it for them to estimate the key size
of an
>encrypted message?

Its not secret.  But lets look at twiddling what the message header
encodes.

Suppose you relabel a 2Kbit key as a 1Kbit.  Then what are the extra
bits for,
Eve will wonder.

Suppose you claim a 1Kbit RSA key is 2Kbits.
Now, the math works if you treat a 1Kbit key as 2Kbit.  But the
decrypt won't work unless the recipient modifies
the header to specify 1Kbit to ignore the fake extra key bits.  Which
requires a secure OOB channel, see below.


>Can they do this without actually "chewing" on the message for a while?
(ie,
>if it doesn't crack in x minutes then there's a 99% probability of the
key
>being Y in length...)

"How can you have any pudding if you don't eat your meat? "

Lets think about DES, which also has a publicly-visible keylength.
If you've run through *all* the 56 bit keys, and found
no solution, you know that either DES wasn't the algorithm (perhaps
3DES was, perhaps DES-X, perhaps Blowfish, AES, Skipjack, etc.
You need to reconfigure your FPGAs for each algorithm.)  And if you
haven't
run through all the keys, it could always be the *last* key you try.

So although given *large sets of messages* you can say that 99% would
have been cracked "by now", this kind of stats isn't really useful.
"Close" is for hand grenades, horseshoes, and proximity fuzes; there is
no "close" in crypto.

>Second question: Is it possible to make a message appear to have been
>encrypted with a shorter key than was actually used?

That would cause the decrypting code to truncate significant digits
which would not permit decryption.  Suppose you did this and the
recipient
fixed the length so it would work.  This wouldn't matter: Eve would
wonder what
all those extra random bits are for.

A better approach *might* be to lie about the symmetric encryption
you've
used.  Encrypt with AES-256, use RSA on that 256 bit key, but modify
the message to claim you've used AES-128 or 3DES.

However, this requires a secure out of band channel to communicate this
to
your recipient.  And if you have such a channel, you may as well give
them
a nonstandard S-box initialization (eg "e times your SSN number" vs.
"pi" in Blowfish) or a OTP.

---
A SAM a day keeps the invaders away.