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.
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() &gt; 0) {
        BigInteger[] qr = x.divideAndRemainder(u);
        x = qr[0];
        int c = qr[1].intValue();
        if (c &lt; 26) {
            c += 'a';
        } else if (c &lt; 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 &gt;= 0; i --) {
        int c = name.charAt(i);
        if (c &gt;= 'a' &amp;&amp; c &lt;= 'z') {
            c -= 'a';
        } else if (c &gt;= '0' &amp;&amp; c &lt;= '9') {
            c -= '0' - 26;
        } else if (c == '.') {
            c = 36;
        } else if (c == '-') {
            c = 37;
        } else {
            return null;
        }
        x = x.multiply(u).add(BigInteger.valueOf(c));
        z = z.multiply(u);
    }
    byte[] b = x.toByteArray();
    int encLen = z.subtract(BigInteger.ONE).bitLength() / 8;
    if (encLen &lt; 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.