1
$\begingroup$

I am following a document here about CTR mode of encryption. I have some point uncleared. At the part 1 Review of Counter-Mode Encryption. Operation.

To encrypt using CTR-mode encryption, one starts with a plaintext M (an arbitrary bit string), a key K, and a counter ctr , where ctr is an n-bit string. Let C be the XOR (excusive-or) of M and the first |M| bits of the pad EK(ctr) || EK(ctr+1) || EK(ctr+2)... The ciphertext is(ctr,C), or more generally, C together with something adequate to recover ctr.

To decrypt ciphertext (ctr;C) compute the plaintext M as the XOR of C and the first |C| bits of the pad EK(ctr) || EK(ctr+1) || EK(ctr+2)...

Therefore, decryption is the same as encryption with M and C interchanged

As I think, the pseudo code will be:

selectFirst(pad, plainText M){
    int n = length(M);
    return n first element of pad
    return firstElements(pad, n);
}

void ctr(){
    string M;
    key[16] K;
    n-bit-string ctr;
    pad = EK(ctr) || EK(ctr+1) || EK(ctr+2)...
    firstM = selectFirst(pad, M);
    C = xor(M, firstM);
}

EK (x) is encrypt x (using some algorithm such as AES) with key K. But I don't understand:

  1. what is ctr + 1, ctr+2...?
  2. Is EK(ctr) || EK(ctr+1) || EK(ctr+2)... an 'OR' operation? and what is its result?
  3. Is CTR mode one-time execution and not using loop?
$\endgroup$
3
$\begingroup$

what is ctr + 1, ctr+2...?

ctr is the first 128-bit input value processed by the block cipher, ctr+1 is this number incremented by 1, and so forth. In practice, ctr is generally a combination of a 96-bit nonce and a 32-bit incrementing counter.

Is EK(ctr) || EK(ctr+1) || EK(ctr+2)... an 'OR' operation? and what is its result?

No, || refers to concatenation in this example.

Is CTR mode one-time execution and not using loop?

No, CTR mode implementations almost always use a loop, and process in increments of a multiple of the block size.

$\endgroup$
  • $\begingroup$ Can you give me a pseudo code or CTR please, using above code? I am feeling confusing :) $\endgroup$ – Andiana Nov 29 '16 at 3:41
  • $\begingroup$ If ctr is a 128-bit input (for easy, think about a byte array), so "this number incremented by 1" is 129-bit input, right? Can you tell me where does the extra (+1, +2...) part come from and what are they, please? $\endgroup$ – Andiana Nov 29 '16 at 4:26
  • $\begingroup$ @Andiana: With the algorithm as written, (ctr+k) really is the value of ctr, plus the integer k, with conversion to integer and back in binary according to some specified endianness (usually big-endian), keeping as many low-order bits as there are in a block of the block cipher (e.g. 128 bits for AES-256). In practice, often ctr is chosen with its (say) 64 low-order bits at zero out of a 128-bit block, therefore (ctr+k) will fit a block until $2^{64+7}$ bits (2 zebibits) have been encrypted, which is more then enough in most applications. $\endgroup$ – fgrieu Nov 29 '16 at 6:29
  • $\begingroup$ I am viewing a CTR tutorial video here youtube.com/watch?v=6EbyCGrdKh8. ei = encrypt(i); //not ecrypt(ctr + i) ci = xor(ei, plainData[i]) Is it wrong? $\endgroup$ – Andiana Nov 29 '16 at 10:13
1
$\begingroup$

I suspect that more pseudo-code would not help much, since the details that you seem to be confused about are the kind that pseudo-code usually glosses over.

In particular:

  • In crypto and related fields, the $\|$ operator (sometimes written as || in ASCII) normally denotes string concatenation — not logical OR, as it does e.g. in the C language. Thus, e.g. $\text{"foo"} \,\|\, \text{"bar"} = \text{"foobar"}$.

  • The input to a block cipher is an $n$-bit block of binary data (where $n$ is the block size of the cipher, e.g. $n = 128$ for AES). Such a block can be naturally interpreted as an $n$-bit integer value, and when we apply an arithmetic operator like $+$ to such a block, this is exactly what we mean: interpret the bits in the block as an $n$-bit number and increment it.

    Of course, there are several possible ways to interpret a bit string as an integer, e.g. depending on endianness. The choice does not make any difference for the security of CTR mode, so theoretical descriptions generally don't mention it, but of course an actual interoperability standard does need to specify such details.

  • In your pseudocode, you don't have an explicit loop, but you do have the expression: $${\rm pad} = E_K({\rm ctr}) \,\|\, E_K({\rm ctr}+1) \,\|\, E_K({\rm ctr}+2) \,\|\, \dots.$$ To evaluate this expression, you'd need to call the block cipher encryption function $E$ several times and concatenate the results, which is something that you would, in practice, need to implement with a loop.

    Of course, in practice, you also need to determine when to stop appending more blocks to the pad — in a theoretical description, it's fine to just write "$\dots$" to imply that the pad can be extended indefinitely, but at least in most languages (functional languages with lazy evaluation, like Haskell, being perhaps the most notable potential exception) an actual implementation needs to specify an end to the loop. Of course, in practice this is simple enough: you stop when the pad is at least as long as the message.


Anyway, if you really want a pseudocode description of CTR mode encryption, here's how I'd write it:

function CTR_encrypt(message, key, IV):
    block := IV;
    pad := "";
    while length(pad) < length(message):
        pad := pad || block_cipher_encrypt(block, key);
        block := block + 1;
    pad := prefix(pad, length(message));
    return pad XOR message.

Here, message is an arbitary bit (or byte) string to be encrypted, key is a key suitable for the block cipher being used, and IV is the initial counter value, encoded as a single block cipher input block. The operator || denotes concatenation, and + denotes integer addition, as described above. The function prefix(string, length) returns the first length elements (bytes or bits or however you measure string length) of the string string, and the operator XOR denotes bitwise exclusive or.

A convenient feature of this implementation is that the exact same function can also be used for CTR mode decryption as well: if ciphertext = CTR_encrypt(message, key, IV), then message = CTR_encrypt(ciphertext, key, IV). Of course, to let the recipient decrypt the message, they must somehow know the correct IV; a common solution is for the sender to prepend the IV to the ciphertext, and for the recipient to remove the first cipher block from the ciphertext and use it as the IV to decrypt the rest.


Also note that, as Richie Frame notes in his answer, it's common to split the block cipher input for CTR mode into two parts: a fixed nonce string that's unique for each message, and a smaller block counter that always starts at zero for every new message. For example, for a cipher like AES with a 128-bit block size, we might use a 96-bit nonce and a 32-bit counter. This has a couple of practical advantages:

  • It simplifies the implementation, since most processors can easily do arithmetic on 32-bit integers, but fewer can natively handle 128-bit integers.

  • It provides a clear security criterion, namely that the CTR mode encryption scheme remains secure as long as no two messages encrypted with the same key ever use the same nonce, and as long as the counter never overflows (i.e. as long as no single message is longer than 232 blocks). With an arbitrary IV, it's much harder to provide such a simple sufficient criterion.

When used with a split nonce/counter like this, the pseudocode for CTR mode encryption (and decryption) would look like this:

function CTR_encrypt(message, key, nonce):
    counter := 0;
    pad := "";
    while length(pad) < length(message):
        block := nonce || number_to_bitstring(counter);
        pad := pad || block_cipher_encrypt(block, key);
        counter := counter + 1;  // throw error if this overflows!
    pad := prefix(pad, length(message));
    return pad XOR message.

One additional advantage is the we don't need to do any actual arithmetic on 128-bit bitstrings; rather, there's only a single place where we need to convert the 32-bit number counter into a 32-bit binary string, which I have marked with an explicit number_to_bitstring() function.


Ps. Of course, if the message string can be modified in place, a simple optimization would be not to store the full pad string, but simply to XOR each output of the block cipher directly with the corresponding block of the message string. Also, even if that is not possible or desirable, we should at least preallocate enough space for the entire pad string before the loop, since we know how long it will be.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I still have a confusing point, how can I plus an Integer to a string. Have I: Convert all chars of string to binary and concat them into a binary string, convert the int to binary string, sum up two binary strings, and convert it back to standard string? $\endgroup$ – Andiana Dec 1 '16 at 8:44
0
$\begingroup$

I think pseudo-code for a n-block cipher in counter mode could look like this:

#check if plaintext is multiple of the blocklength, if not pad

padding(plaintext M, blocklength n){
    if (M % n != 0) {
        pad(M)
    }
}


#run encryption on padded plaintext

ctr (Key K, Counter ctr, Paddedplaintext M){
    # number of plaintext blocks to encrypt
    number_of_blocks = M / n

    for i in number_of_blocks {
        #read n bits from padded plaintext
        block_i = M.read(n)

        #encrypt counter value with key K and XOR with n-bits of plaintext
        C_i = block_i XOR Encrypt(ctr, K)

        #update counter value
        ctr = ctr + 1
    }
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.