Detecting attempts to decrypt with incorrect secret key in OWASP ESAPI

[Kevin W. Wall]

Hi all,

I was referred to this site by a former colleague who thought this
is something that someone with professional cryptanalysis experience should
comment on. Also, I apologize in advance for the length of this
post (especially since it's my first one). Just trying to be thorough.

I have been working with Jeff Williams, Jim Manico and others on the OWASP ESAPI
Java implementation (http://www.esapi.org). Work is underway for the 2.0
release.

I am re-implementing the somewhat "broken" symmetric encryption / decryption
mechanisms implemented in the earlier 1.x versions that only supported ECB
cipher mode, restricted encryption and decryption operations to the use
of a single encryption key, and used whatever the default padding scheme
was for whatever JCE provider that happened to be used. As such, this is
still very much a work in progress, but rather than risk fouling up
encryption in the 2.0 release as well, I wanted to gather some input
that we are on the right track. Since this work is for a free open source
project (developed under the BSD license), I'm hoping that one of you
on this list will take some time to address my questions.

In OWASP ESAPI Java 2.0, I started out by deprecating the older methods that
only supported ECB mode and used the provider's default padding scheme (which
can vary, depending on JCE provider).

The new default for the new encryption / decryption methods is to be
128-bit AES/CBC/PKCS5Padding and use of a random IV. (There is some
thought on my part to not allow different cipher modes or padding
schemes, but I go back and forth on this. (Certainly if someone
tries to use something like OFB we'll at least probably long a
warning that there's some chance that the same IV could be reused
even though it is chosen randomly.)

But for the remainder of this discussion, you can assume some suitably
strong cipher algorithm and key size >= 128 bits with encryption using
CBC cipher mode and PKCS5Padding. (Eventually we may allow others, but
for now, that is probably sufficient and certainly a big improvement over
only supporting ECB mode.)

Based on experience at my day job, what I have found is when you try to
decrypt something using PKCS5Padding using the wrong secret key, about
99.9% of the time you will get a BadPaddingException in Java and about
the other .1% of the time you just get random garbage back for the plaintext.
This is bad because if one is performing _manual_ key change operations
(which many small IT shops using OWASP ESAPI will likely do for PCI DSS
compliance reasons), then one could end up storing the resulting (incorrect)
plaintext value and not discovering the error until much further downstream
making and/or at a much later time. This makes the error very hard to
troubleshoot as it typically will a long ways away in both code space
and timeline away from the true root cause of the problem.

I would like to be able to support such key change operations for ESAPI in
a way that one has a much higher probability of detecting that decryptions
using the incorrect secret key that do NOT result in a BadPaddingException
have a much higher probability of being detected. Unfortunately, since
this is generally reusable class library I can make no assumptions about
the original plaintext. Specifically, it might not be text in the conventional
sense at all, but rather it could be something like another random secret key
that someone encrypted, etc. (key wrapping notwithstanding, but it is not
currently supported in ESAPI 2.0).

For ESAPI Java 2.0, I've created a serializable CipherText class that
contains everything one generally needs to know to perform the decryption
operation. That is, the CipherText object contains things like the
the specification cipher transformation used to encrypt it, the IV used
(unless ECB mode), and the raw ciphertext value as a byte array.

My first thought was to also include a digital signature that was created
along the lines one of these (note: here 'DSig(msg)' includes both the
hashing and private key signature operations and probably would use DSA
since it is not subject to any US export regulations):

    DSig( IV + secretKey )	// I explain below why IV is included
or
    DSig( IV + plaintext )	// '+' is just the usual byte concatenation

signed by the encrypter's private key. The decrypting side would then validate
the digital signature using the encrypter's public key and only use the
plaintext value if the digital signature was valid. If I were to do this,
I might also add the encrypter's identity or alias as part of the CipherText
class, although in most of the simple cases, it should be obvious based on
from whom one is receiving the encrypted data.

However, the main problem with using digital signatures is the performance
hit. In my day job, I have made two observations involving encryption:

    1) If you wish to ensure that application developers use solid
       algorithms such as AES, you must ensure that the encryption and
       decryption operations are sufficiently fast not to cause a
       bottleneck even when millions of encryptions are done.
    2) Approximately 90+% of the encryption that occurs deals with the
       plaintext being very short (usually ASCII, occasionally EBCDIC)
       string data such as SSNs, CC#s, bank account information, etc. (This
       is driven by regulatory and compliance issues.)

Because of these two observations I am concerned that the digital signature
operation and its corresponding validation will had significant processing
overhead relative to the actual encryption / decryption operations.

Thus I'd prefer something lighter weight than digital signatures to
accomplish more or less the same thing.

I have considered using an HMAC-SHA1 as a keyless MIC to do this,
using something like:

	MIC = HMAC-SHA1( nonce, IV + secretKey )
or
	MIC = HMAC-SHA1( nonce, IV + plaintext )

and then also include the random nonce and the MIC itself in the CipherText
class so it can be validated later by the decrypter, with the understanding
that the plaintext resulting from the decryption operation should only be
used if the MIC can be properly validated. (Probably an exception would
be thrown if the dsig was not valid so there would be no choice.)

However, I am not a cryptanalyst so I am not sure how secure this is (if at
all). My intuition tells me that it's not as good as using a DSig, but it
should be significantly faster (or if not, rather than using an HMAC,
alternatively just using something like SHA-256 and prepending the nonce
to the rest).

Note that I am now writing this ESAPI Java crypto code so that one has the
choice of not doing these MIC calculations at all simply by setting a
property in ESAPI.properties, but I have made to made the default to have it
enabled to do this calculation in the encryption and validate it during the
decryption.

On why I included the IV in the MIC (or DSig) calculations...
=============================================================
The ESAPI default will be to use a random IV appropriate for the cipher
whenever that cipher mode requires an IV. Thus in the minimalist case, someone
who needs to persist the ciphertext (say in a DB) will need to store the
IV+ciphertext. There is a method on CipherText to return the base64-encoded
IV+ciphertext byte array, like it is done in W3C's XML Encrypt specification.

I added the random IV into the MIC (or DSig) calculation in part to add
to the entropy and in part to be able to detect attempts of an adversary
to change the IV to something of their liking.

In the DSig case, it serves more or less as a nonce (with the assumption
that because it's a ciphertext block size of random bytes it is unlikely
to be repeated). It probably isn't as useful for a MIC calculation, but
figured it couldn't hurt since byte concatenation is cheap.

I had considered using something without the nonce like

	MIC = HMAC-SHA1( IV, plaintext )

but since I was already uneasy about using a MIC in the first place, I decided
to do it the way shown above with an additional random nonce thinking I can
ensure that the nonce is randomly chosen and sufficiently large (e.g.,
say 160-bits or longer, independent of the cipher algorithm's block size).

The second reason I added the IV into the mix is because I figured that this
would make it possible to detect an adversary tampering with the IV.
(Well, it would for the DSig for sure; perhaps less so for the plaintext version
of the MIC if it is possible for the adversary to do any type of chosen
plaintext attack.)

The reason that I want to be able to detect this is because I read somewhere
in a paper by some cryptographer (maybe David Wagner, but am not sure)
that there were some esoteric cryptographic attacks that could leak a few
bits of the secret key or something if an adversary could get someone to attempt
to decrypt some ciphertext using IVs that the adversary could manipulate.
(I think maybe this had to do with IPSec but don't recall exactly as it's
been several years ago.) But in a nutshell, I was hoping that including the
IV would have the secondary benefit of preventing these types of attacks.
[Note: Any references to papers referencing something like this would be
appreciated.]

So, having provided all of that background, in summary, here are my
three questions:
    1) Is using either of these MIC calculations cryptographically secure?
    2) If answer to #1, is 'yes', which one is "safer" / more secure?
    3) If answer to #1 is 'no', do you have any suggestions less
       computationally expensive then digital signatures that would
       allow us to detect attempts to decrypt with the incorrect secret
       key and/or an adversary attempting to alter the IV prior to the
       decryption.

Thanks in advance to all who respond,
-kevin--
Kevin W. Wall
"The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents."        -- Nathaniel Borenstein, co-creator of MIME

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com