# How can I encrypt + authenticate short strings into similar short ciphertexts?

I wish to manipulate short ASCII strings (namely unpredictable domain names) into a form which cryptographically assures authenticity and confidentiality, for use in the local part of email addresses. Furthermore, the resulting email addresses should be valid according to most address validators (including the many many non-standards compliant ones).

I therefore envisage that the resulting ciphertext must be as compact as possible (many validators have arbitrarily short length restrictions) once it is encoded using a very restricted subset of ASCII characters (probably just [a-z0-9\.\-], since many email address validators do not properly accept quoted/escaped characters and may erroneously transform the address in such a way that character case is lost). Most ciphers that I've tried produce far too much ciphertext to meet these requirements.

As an aside, it may be interesting to note that my proposed encoding uses the same alphabet as the plaintext.

A given plaintext should always produce the same ciphertext (when using the same key), so there should be no random component here.

Strong authenticity is more important than strong confidentiality, but a mere encoding will not provide sufficient confidentiality. There is no particular requirement for asymmetric ciphers. For the sake of argument, assume unlimited computational resources are available to perform encryption/decryption.

Suggestions for possible ciphers and/or encoding schemes would be most welcome.

-

## migrated from stackoverflow.comOct 17 '11 at 17:17

This question came from our site for professional and enthusiast programmers.

You need something like format-preserving encryption, probably together with an authentication tag. –  Paŭlo Ebermann Oct 17 '11 at 14:37
Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. –  Paŭlo Ebermann Oct 17 '11 at 20:53

First, convert the string which is to be encrypted into a sequence of bytes. UTF-8 is easy enough; you may reduce the size a bit, depending on what you know on the input strings (e.g. if the strings are domain names, they are ASCII-compatible, so you need only 7 bits per character -- actually a bit less). For the rest of this post, we need to assume that the encoding does not yield any byte of numerical value zero (which is true of both ASCII and UTF-8, if the source string does not have any embedded zero).

Once you have $d$ bytes, append at least $m$ bytes of value 0. This is the authenticity check: an attacker will have at a probability of at most $2^{-8m}$ to produce what will look like a "valid" encrypted string. This is a trade-off: a higher $m$ makes life more difficult for the attacker, but costs you space.

Let $n = d + m$. You now have a sequence of $n$ bytes (note: you can "round up" the size by adding some extra zeros beyond the $m$ zeros). Encrypt that sequence of $n$ bytes into another sequence of $n$ bytes by applying a block cipher with blocks of $n$ bytes (see below). This must be a single application of the cipher, no chaining mode, no IV.

Finally, represent the resulting $n$ bytes as a sequence of characters in your destination alphabet. Since you want to stick to 38 characters (lowercase letters, digits, dot and dash), this means interpreting the $n$ bytes as an integer, and converting it to base 38. In Java, this would may like this:

/*
* WARNING: this code is completely untested, I write it "on-the-go". I have not
* tried to run or even compile it. It is also grossly inefficient (although it
* should be fast enough for most applications).
*
* convertToName() converts a sequence of bytes (normally the output of the
* encryption function) into a string suitable for being the local part of an
* email address. convertFromName() does the opposite (or returns null on
* invalidly encoded string).
*/

static String convertToName(byte[] enc)
{
StringBuilder sb = new StringBuilder();
BigInteger z = BigInteger.ONE
.shiftLeft(enc.length * 8)
.subtract(BigInteger.ONE);
BigInteger x = new BigInteger(1, enc);
BigInteger u = BigInteger.valueOf(38);
while (z.signum() > 0) {
BigInteger[] qr = x.divideAndRemainder(u);
x = qr[0];
int c = qr[1].intValue();
if (c < 26) {
c += 'a';
} else if (c < 36) {
c += '0' - 26;
} else {
c = (c == 36) ? '.' : '-';
}
sb.append((char)c);
z = z.divide(u);
}
return sb.toString();
}

static byte[] convertFromName(String name)
{
BigInteger u = BigInteger.valueOf(38);
BigInteger x = BigInteger.ZERO;
BigInteger z = BigInteger.ONE;
for (int i = name.length() - 1; i >= 0; i --) {
int c = name.charAt(i);
if (c >= 'a' && c <= 'z') {
c -= 'a';
} else if (c >= '0' && c <= '9') {
c -= '0' - 26;
} else if (c == '.') {
c = 36;
} else if (c == '-') {
c = 37;
} else {
return null;
}
z = z.multiply(u);
}
byte[] b = x.toByteArray();
int encLen = z.subtract(BigInteger.ONE).bitLength() / 8;
if (encLen < b) {
byte[] enc = new byte[encLen];
System.arraycopy(b, b.length - encLen, enc, 0, encLen);
return enc;
} else if (encLen == b) {
return b;
} else {
byte[] enc = new byte[encLen];
System.arraycopy(b, 0, enc, encLen - b.length, encLen);
return enc;
}
}


When decrypted, you call convertFromName(), and reject if you get null; otherwise, you should have a sequence of $n$ bytes, which you then decrypt with the block cipher. You check that there are at least $m$ zeros at the end of the decrypted block (that's the authenticity check), and finally decode the string using whatever convention you used in the first place (e.g. UTF-8).

All of the above is just encoding and decoding things. Remains "only" the yummy part: the block cipher. What you need is a pseudo-random permutation of the space of $n$-byte values, selected by a key which you use to encrypt and decrypt.

For $n = 8$ you can use Triple-DES. For $n = 16$, no hesitation, use AES. For larger blocks, there is no completely established rock solid standard, but for $n = 32$ you can have a look at Rijndael: the original Rijndael is defined over blocks of 128, 192 and 256 bits, with keys of 128, 192 or 256 bits (AES is Rijndael with 128-bit blocks, but the versions with larger blocks, while not being "the AES" per se, are considered reasonably robust nonetheless). For larger blocks, see Threefish, which is very new (this is not a good thing for a cryptographic algorithm) and received only limited attention as a block cipher, but goes up to 1024-bit blocks (that's for $n = 128$).

The idea would be the following: in the conversion above, you add enough extra zeros (beyond the $m$ zeros for the integrity check) to reach the next $n$ for which you have a suitable block cipher in the list given above.

On a general basis, you may want to implement "Format Preserving Encryption", e.g. using the Thorp shuffle as described by Morris, Rogaway and Stegers. This could allow you to have a "block cipher" for any $n$, without having to round up to the next value for which there is a suitable conventional block cipher. This is a mixed blessing, though: by keeping $n$ as is without ever adding more zeros than the initial $m$, you are effectively leaking the original length of the plaintext string. By making sure that $n$ is always one of $\{8,16,32,64,128\}$, you are masking part of that information while keeping your "local names" small when possible.

Numerical application: with $m = 3$ (the attacker has only one chance in 16777216 to create an invalid string which will be accepted by the check on $m$ zeros), input strings ("domain names") will yield output strings ("local names for email addresses") of the following length:

• if $d \leq 5$, you uses 3DES and get strings of 13 characters;
• if $5 \lt d \leq 13$, you use AES and get strings of 25 characters;
• if $13 \lt d \leq 29$, you use a cipher with 256-bit blocks, and get strings of 49 characters;
• if $29 \lt d \leq 61$, you use a cipher with 512-bit blocks, and get strings of 98 characters.

If you use UTF-8 encoding, $d = 13$ means 13 characters for input. But if you assume that input strings consist only of ASCII characters with codes from 33 to 126 inclusive (no control character, no space), you can store 15 characters in 13 bytes.

-
It feels to me that a sequence of $m$ zeroes provides relatively weak authentication, especially considering that strong authentication is of greater priority than strong confidentiality. I propose instead appending a separation marker (perhaps ASCII US 0x1f) followed by e.g. the first $m-1$ characters of an HMAC, such as MD5(plaintext + key). Indeed, if the authentication code is of a fixed length, it could prefix the plaintext and avoid having the separation marker at all. Otherwise your scheme feels good, albeit the resulting strings may be longer than many validators will accept. –  eggyal Oct 17 '11 at 22:12
Theoretically, the $m$ zeros provide "perfect" authentication (i.e. attack works with probability at most $2^{-8m}$) as long as the block cipher is indistinguishable from a random permutation -- a property which you need anyway for proper encryption in this setup. Using the first $m$ bytes of HMAC instead of $m$ zeros does not buy you much here, except perhaps a warm feeling of safety (but HMAC will not harm either, so go for it if you need it to sleep at night -- make sure to use a key distinct from the one for encryption, though). –  Thomas Pornin Oct 17 '11 at 22:19
My leaning towards HMAC came from an earlier thought to only encrypt the domain and add an HMAC in the clear for authentication, intended to reduce the length of the result if encoding the ciphertext resulted in a string of greater length than the plaintext (as it does here). Perhaps it would also be useful to compress the plaintext, e.g. encode TLDs, many popular SLDs and common letter combinations and express the remainder in base 38? I fear space really is of the essence, as some validators will reject an address with as few as 30 characters - including the remainder of the email address! –  eggyal Oct 17 '11 at 22:35
Actually, UTF-8 might need more than one byte per character (for all outside of ASCII). So the last paragraph should start with be "if you use an one-byte encoding". –  Paŭlo Ebermann Oct 17 '11 at 22:43
@eggyal You might want to use some (standard or custom) compression algorithm before adding the zeros (or the MAC) and applying the encryption. deflate (which is used in gzip and zip, for example) can work with a dictionary of common byte sequences to increase compression ratio. –  Paŭlo Ebermann Oct 17 '11 at 22:47