Padding Question (Cramer-Shoup 98 Crypto System)

From: Oliver Moeller (omoeller_at_verify-it.de)
Date: 11/21/04


Date: 21 Nov 2004 12:40:36 -0800


Hello Crypto-Community.

I have a Java implementation of Cramer-Shoup 98 Crypto System (see links
below). Version 2.1 now guarantees to de-crypt to the original message by
introducing a safe way to pad the clear text message up to the required block
size.

They padding I chose is rather straightforward:

(I)
Always append a bit pattern of fixed (16 bits) length:
    1000 1000 1000 1000
The encryption does pad the message with a pattern (01|10)*[0]?, where
01 / 10 are picked uniformly random.

For n > 16 (realistic values are around 2000), this reduces the number of
messages from 2^n to (at least) 2^((n-16)/2).

Lets assume the somewhat "worst case":
The clear text message contains only 1 bit, the 'random' tail is of length
n-1. Then only the fraction 0.5*(n-17)/n of clear text messages have to be
considered in order to distinguish message '0' and message '1'.

This fraction is close to 0.5, so for practical matters this is not too bad.
In case of Cramer-Shoup, where a library of pre-computed cipher-texts do not
help (much), my claim is that this does not compromise security.

However, I have the feeling that there is a better way to do this.
My last lecture on Cryptography was in 2000, so I had a look at the omniscient
garbage dump for 'cryptographic padding' and found PKCS5:

(II)
## -- quote from http://www.chilkatsoft.com/faq/PKCS5_Padding.html
 PKCS#5 padding works as follows: the bytes remaining to fill a block are
 assigned a number, which is the number of bytes that were added to fill the
 block. For instance, if we have an 16-byte block, and only 11 bytes are
 filled, then we have 5 bytes to pad. Those 5 bytes are all assigned the value
 "5", for the 5 bytes of padding.

For the 1-bit example (assuming the attacker guesses that there is only 1
bit), it seems to be horribly bad (you can readily construct a library of
cipher-texts).

My Questions:
(1) Is (I) an acceptable way to pad?
(2) Is (II) PKCS5 better than padding with 10* ?
(3) Is there a suggested or even 'optimal' way to pad?

Thanks.

--
About the Java Implementation of Cramer-Shoup 98:
Though I do not assume this being a research topic, I'd like to point out some
(IMHO) interesting features of this implementation.
1. A Java front-end allows inclusion of the algorithm (and your public key) in
   a HTML page via an Applet. 
2. The same front-end can be used to encrypt/decrypt files from command line
3. The implementation is fairly small and can be realistically checked for
   correctness by manual code-inspection.
Resources:
A test suite for the implementation (including the key-generator) is
available. After un-zipping, call 'make' to generate a number of keys and test
proper en/de-cryption of random messages. This will abort if clear text
message and de-crypted cipher-text differ.
  http://www.verify-it.de/sub/testCrypter.zip
More information can be found at 
  http://www.verify-it.de/sub/cramer_shoup.html
References:
[CS98] Ronald Cramer and Victor Shoup: 
       A practical public key crypto system provably secure against adaptive
       chosen ciphertext attack. 
       in proceedings of Crypto 1998, LNCS 1462, p.13ff
- oli						       http://www.verify-it.de
*com-pu-ter*: device to enhance our capability to err. <omoeller@verify-it.de>


Relevant Pages

  • Re: Tom Clancy "Dead or Alive"
    ... hints but never fully describes the crypto system. ... the cipher is combined with steganography to hide the message ... many digits you want -- and use it for your new seed number. ... Biery grapped the legal pad on Hendley's desk and started writing: ...
    (sci.crypt)
  • Re: Tom Clancy "Dead or Alive"
    ... hints but never fully describes the crypto system. ... known crypto system as Clancy describes it. ... the cipher is combined with steganography to hide the message ... Biery grapped the legal pad on Hendley's desk and started writing: ...
    (sci.crypt)
  • Re: Tom Clancy "Dead or Alive"
    ... hints but never fully describes the crypto system. ... the cipher is combined with steganography to hide the message ... Biery grapped the legal pad on Hendley's desk and started writing: ... That's what was once called the pad or one-time-pad bit, ...
    (sci.crypt)
  • Re: One-Time Pad software?
    ... is larger than one piece of the pad. ... Any reasonable implementation of a one-time pad crypto would enforce ... is the currently guessed plain-text. ... block the key was generated from) with this guessed key, ...
    (Security-Basics)
  • Re: What is a "perfect secret" ?
    ... ]the "pad" or "confusion sequence" is unpredictable. ... ]All real implementations of the OTP are imperfect to ... ]of successful attack in the literature. ... ]and "proof" and related topics in my Crypto Glossary. ...
    (sci.crypt)