RE: PGP scripting...

From: Jason Coombs (jasoncat_private)
Date: Thu Jan 23 2003 - 16:22:18 PST

  • Next message: Alex Russell: "Re: Standards for developing secure software"

    Interesting discussion -- just a point of clarity:
    
    Glynn Clements wrote:
    > To take an extreme (and somewhat contrived) example, suppose that you
    > know that the message will either be "The deal is on" or "The deal is
    > off"; although the message would occupy at least 112 bits as ASCII,
    > you only really have one bit of data, and you would only have to
    > encrypt the two candidate messages to determine which one was actually
    > sent.
    
    Previously Andre Marien stated:
    > If there are n possible messgaes, it only takes at most n trials to
    > decrypt the message, no matter your key size(if the encrypting key is
    > known; typically it is the public key and it is known)
    
    If the public key used to perform the encryption is known, then it only
    takes at most n trials to decrypt a message encrypted with that public key.
    Without the public key, you're still stuck brute-forcing the key length
    because the RSA algorithm does not result in predictable placement of
    ciphertext bits that correspond to the plaintext "n" or "f" -- you can't
    just ignore the rest of the cryptographic transformation and concentrate on
    scanning a single byte until it comes up "n" or "f" and then attempt to
    transform the entire ciphertext message with the potential key until you
    find the right one.
    
    You can mount a chosen plaintext attack with "The deal is on" and one in
    parallel with "The deal is off", but since you don't know the key your
    attack is going to take a very long time and span a good deal of the
    available key space.
    
    Asymmetric bulk encryption can also be used with a random initialization
    vector the same way that IVs are used in symmetric bulk encryption with
    feedback modes like Cipher Block Chaining. You then have a secret session
    key (the IV) that makes brute-force chosen plaintext attacks unreasonable,
    while preserving the feature of practical unrecoverability of the plaintext
    in the event that the secret session key is captured along with the
    ciphertext. It is arguably more difficult for an adversary to capture [the
    private key from an asymmetric key pair AND the IV AND the ciphertext] than
    it is to capture [the symmetric secret key AND the IV and the ciphertext] --
    for the simple reason that at the point of encryption the softwre that
    implements the asymmetric bulk cipher is never in possession of the private
    key necessary for decryption.
    
    Jason Coombs
    jasoncat_private
    
    -----Original Message-----
    From: Glynn Clements [mailto:glynn.clementsat_private]
    Sent: Wednesday, January 22, 2003 10:06 AM
    To: Beatie, Breck (ISSMountain View)
    Cc: secprogat_private; Andre Marien
    Subject: RE: PGP scripting...
    
    
    
    Beatie, Breck (ISSMountain View) wrote:
    
    > > Please do not use public key encryption for bulk data, even if
    > > you accept the long times. It is a bad idea. If there are n
    > > possible messgaes, it only takes at most n trials to decrypt
    > > the message, no matter your key size (if the encrypting key is known;
    > > typically it is the public key and it is known).
    > > This problem is justification in itself to have a two stage system
    > > for encryption of bulk data.
    > > (there is someone at counterpane that can explain it in more detail ;-)
    >
    > I'm not sure I understand the point of this message.  It seems that
    > you are saying that you can figure out the cleartext message by taking
    > the n possible cleartext messages and encrypting with the known public
    > key until you find the cipher text.  That much makes sense, but since
    > we were talking about encryption of bulk data it seems that the number
    > of possible messages would be VERY large and such an approach would
    > not be workable.
    >
    > It seems that your comment would even argue AGAINST the "two stage"
    > system that you're talking about.  The total number of possible symmetric
    > keys would be much less than the total number of possible messages.
    >
    > But then I'm a bit of a crypto ignoramus.  If you (or someone) would
    > elaborate a bit I would be grateful.
    
    I think that you're misinterpreting the term "bulk data" slightly;
    it is referring to the actual plaintext (subject to any
    transformations such as compression), not necessarily to a *large*
    amount of data.
    
    The context may greatly reduce the set of possible plaintexts, even
    below the size of a symmetric key. Suppose that you can guess almost
    the entire plaintext (e.g. because it's generated automatically by a
    specific piece of software), and the only thing which you *can't*
    guess is a very small section e.g. a credit card number, you could
    attempt a brute-force search of all plausible credit card numbers,
    which is likely to be easier than brute-forcing a 128-bit symmetric
    key.
    
    To take an extreme (and somewhat contrived) example, suppose that you
    know that the message will either be "The deal is on" or "The deal is
    off"; although the message would occupy at least 112 bits as ASCII,
    you only really have one bit of data, and you would only have to
    encrypt the two candidate messages to determine which one was actually
    sent.
    
    In short, with the two-stage approach, you have a fixed lower bound on
    the number of possible plaintexts, and for a 128-bit key, this is well
    beyond brute-force viability with current hardware, even for the NSA.
    OTOH, directly encrypting the plaintext provides no such lower bound.
    
    --
    Glynn Clements <glynn.clementsat_private>
    



    This archive was generated by hypermail 2b30 : Thu Jan 23 2003 - 16:39:34 PST