Re: PKI for very short (32bit) messages

From: Joonas Lehtinen (jole_at_jole.fi)
Date: 03/31/04 

Date: 31 Mar 2004 00:23:41 -0800

> > Are there any public key methods for encryption of very short
> > (32-bit) messages (..)
> > The goal is to distribute public key for large number of
> > (insecure) recipients that should be fairly sure that the
> > 32-bit messages sent to these recipients over a long period
> > of time originate from the holder of the private key.
> This is public key signature, not encryption.

True, but unfortunately my application has very strict constraints for
message length (32bits). For this reason, encrypted message could be
used for both originator validation and as data carrier. For example,
we could send one bit of data by defining that all hight 31 bits must
be 0 and the recipient can read the message payload from the lowest
bit and check that decrypted message has all higher bits set to 0. Of
course this would imply that a message could not be accepted twice as
then the attacker could just memorize the messages used for sending 0
and 1 messages. Still, for this application it is enough to send such
a message just once (the recipient can use some other validation
bit-configuration each time).

> The size of RSA-processed cyphertext or signature is at least
> about as big as the module (tricks exists to gain just a few bits).
> The size of the plaintext is at most about as big as the module,
> with no minimum (adding random data to the plaintext solves the
> plaintext enumeration.

This is a real problem - for 32bit messages it would only require some
16gigs of space to create map of all possible messages. Also creation
of such map would not be too hard to achieve for possessor of public
key. Just "decrypt" all possible bit-combimations and save the
compinations for locations pointed by the descrypted plaintext. If it
would be possible to increase the message size by, say 16bits, this
attach would become impractical as the size of the map would increase
to 48 * 2^48 bits = ~1500 terabytes.

> Any public key encryption (or signature) scheme must markedly
> expand a short (32 bits) message; else it is trivialy vulnerable
> to enumeration.

If the enumeration can be considered impractical (by increasing
message lenght a bit), are there any methods of keeping the encrypted
message short while using long keys? I would guess that for 48bit
messages enumeration is not viable attack, but if the keysize is also
48bits, factorization of ECC keys might not take too much time.

- Joonas

Relevant Pages

  • Re: PGP scripting...
    ... If we keep both private and public key secret, ... > Asymmetric bulk encryption can also be used with a random initialization ... > key that makes brute-force chosen plaintext attacks unreasonable, ... >>>for encryption of bulk data. ...
    (SecProg)
  • Re: PGP scripting...
    ... first proposal: use symmetric encryption ... Attack: repeat the encryption for possible plain texts. ... Either the software decrypts with the vendor's public key ... >>key that makes brute-force chosen plaintext attacks unreasonable, ...
    (SecProg)
  • RE: PGP scripting...
    ... Asymmetric encryption is also valuable for bulk encryption in a scenario ... Either the software decrypts with the vendor's public key ... > transform the entire ciphertext message with the potential key until you ... > key that makes brute-force chosen plaintext attacks unreasonable, ...
    (SecProg)
  • Re: Encrypted network communication
    ... Bob) communicate over an insecure channel. ... This type of encryption uses a single shared, ... Secret-key encryption algorithms use a single secret key to encrypt and ... unauthorized users and a public key that can be made public to anyone. ...
    (microsoft.public.dotnet.languages.csharp)
  • RE: PGP scripting...
    ... cryptosystems, ... In these systems divulging your private key compromises the public ... Here is a quick over view of the public key encryption routines (the ...
    (SecProg)