4
$\begingroup$

Assume an instantiation of AES-CTR like in the following picture:

AES-128 CTR

Some details on the input-values for keystream generation:

  • COUNT: a 32-bit value associated with the transmission mode
  • IV#1: a 5-bit value that can be assumed constant for a specified transmission
  • IV#2: a 1-bit value indicating the direction of the transmission
  • incr: a 64-bit value initialized to 0 and then incremented per standard $\bmod 2^{64}$ increment function.
  • cipher key: refers to ciphering key which is obviously not known

Assume that all those input values are not difficult to identify/guess as they are required to establish correct transmission and synchronization between the two communicating parties (e.g., direction, radio info, etc). We also assume that no pairs of ciphering keys and input values ($COUNT||IV\#1||IV\#2||0^{26}||incr$) are used. Is this a weak AES-CTR implementation, assuming one can obtain pairs of keystreams/input-values?

I guess we can say this implementation is malleable as any AES-CTR without authentication steps. Any other weaknesses?

$\endgroup$
9
  • $\begingroup$ Send the COUNT encrypted as the first plaintext block. $\endgroup$
    – kelalaka
    Oct 23, 2018 at 13:33
  • $\begingroup$ Thanks kelalaka. Can you elaborate on that? Is it safe to use the COUNT as input for the IV and as input for the plaintext? $\endgroup$
    – Jimakos
    Oct 23, 2018 at 14:23
  • 1
    $\begingroup$ I'm trying to saying that if the COUNT is just sent once per encryption session, then just encrypt it as $p_o,p_1,...,p_l$ where $p_1,...,p_l$ is your normal plaintext to encrypt and $p_o = COUNT$. That will give you just the same security as CTR mode. if you want append some randomness to the $p_0= COUNT\|random_c$ where $random_c$ is just 96 bits ramdom. $\endgroup$
    – kelalaka
    Oct 23, 2018 at 14:27
  • $\begingroup$ I thought about the randomness issue, but then I was wondering how I would synchronize this random value to the receiving side $\endgroup$
    – Jimakos
    Oct 23, 2018 at 14:37
  • 1
    $\begingroup$ @kelalaka: my reading is that, as often in AES-CTR, the 128-bit CTR has two concatenated parts (typically 64-bit each, as is the case here): an IV (here $\text{COUNT}\mathbin\|\text{IV}_1\mathbin\|\text{IV}_1\mathbin\|0^{26}$) that is assumed different from session to session, and an incremental counter (here $\text{incr}$) re-starting from zero at each session, and wide enough that it won't overlap. The combination insures the CTR value is never reused, and that's of paramount importance. $\endgroup$
    – fgrieu
    Oct 23, 2018 at 17:12

3 Answers 3

2
$\begingroup$

If the implementation ensures that no (COUNT, IV#1, IV#2) tuple can ever be used more than once, and if no tuple is ever used to generate more than 264+4 bytes of keystream output, then this scheme is as secure as any instantiation of AES-CTR can be. Of course, as CTR is not an authenticated encryption mode, it will still be malleable unless combined with a MAC.

Conversely, if an attacker can cause two plaintexts to be encrypted with the same COUNT, IV#1 and IV#2 values, then they can easily obtain the bitwise XOR of the plaintexts, which may be sufficient to at least partially recover the plaintexts themselves. In particular, if an attacker can cause a plaintext of their choosing (or at least known to them) to be encrypted with a chosen COUNT, IV#1 and IV#2, then they can fully decrypt any other plaintext (of equal or lower length) encrypted with those same values.

Your question does not contain enough information to let us tell which of these two scenarios applies, and so we cannot say whether this specific AES-CTR instantation is secure (in the usual IND-CPA sense one would expect of CTR mode) or not.

That said, the short length of IV#1 certainly raises some concern. You have not described exactly what constitutes a single "transmission" in this protocol, but whatever it is, there can be only 32 of them in this scheme before you'd need to rekey (assuming that nothing prevents two transmissions from using the same COUNT values). That seems like it might be a problem.

$\endgroup$
1
  • $\begingroup$ Thanks Ilmari. All of these input values concatenated constitute the input block to the algorithm. It just happens so that these fields bring some specific functionality with them to allow for correct transmission (for example the 1-bit IV is the direction of the transmission uplink/downlink or the 5-bit IV is called the bearer and has to do radio transmissions). The system is designed to avoid repetitions of COUNT/IVs/incr values under the same key. My concern was if this "easiness" for someone to monitor/guess the input parameters (apart from the key of course) may lead to a vulnerability. $\endgroup$
    – Jimakos
    Oct 23, 2018 at 14:16
1
$\begingroup$

Assume that all those input values are not difficult to identify/guess as they are required to establish correct transmission and synchronization between the two communicating parties.

If we assume that the key is secure then the mode of operation will also be secure for the security that it was designed to deliver. That the IV may be public is a common assumption: it does not in itself make the resulting cipher insecure.

Is this a weak AES-CTR implementation, assuming one can obtain pairs of keystreams/input-values?

It is hard to read what you mean here, but lets assume that:

  • keystreams means ciphertext;
  • input values means the components that make up the IV.

instead of the normal definition:

  • keystreams means the output of the block cipher that get XOR'ed with the plaintext
  • input values means the plaintext.

In that case the scheme would still offer confidentiality - presuming that there aren't any protocol or implementation mistakes.


Obviously if you do get access to part of the keystream generated by AES CTR - the part that gets XOR'ed with the plaintext - then you can decrypt that part of the plaintext, but not any other part of the plaintext.

You should only be able to get to parts of the keystream by either:

  1. knowing that part of the plaintext - this doesn't help the adversary because that part of the keystream is not linked to any other part of the keystream;

  2. knowing the key - this obviously breaks the cipher completely: once the key gets known all security assumptions are broken.

Note that the block cipher will protect the key. Furthermore the IV may be get known to an adversary. So knowing part of the key stream does not break security of CTR.

Knowing all of the keystream implies knowing all of the plaintext of a message or to know the AES key. In the first case no mode of operation can protect that particular message as the plaintext is already known. Other messages would still be secure. If the key gets known then the adversary can simply decrypt anything and all security is lost.

I guess we can say this implementation is malleable as any AES-CTR without authentication steps.

Of course it is malleable. There is nothing to authenticate the plaintext or ciphertext after all.

There aren't any other obvious attacks on CTR mode as long as the IV doesn't repeat or if the key gets known.

There is a copious amount of bits reserved for the counter, so it is clear that the message size is not an issue.


The IV seems to be build up well.

There is 32 bits space for a message counter. This allows for over four billion messages to be send before the counter starts to repeat. Do note that if the adversary can trigger messages to be send that this could become a problem: a computer can easily perform more than 4 billion calculations after all.

The transmission is identified by the next 5 bits and the direction in the one after. You could argue that those 6 bits should be before the message counter semantically, but in that case the 32 bit counter would not be 8 bit aligned, making the counter encoding non-trivial. There are obviously only 32 "transmission" connections possible. In general it is nicer to calculate a different key for each transmission and direction - but cryptographically speaking this is not required.

incr is the space reserved for the block counter used for CTR. It allows $2^{64}$ 16 byte blocks to be encrypted for each message. That should be plenty.

26 bits are left over. This is a bit weird: it would at least be easier to have IV1 and IV2 occupy their own byte. Now the least significant bits of the IV1 & IV2 byte must be set to zero and you have to shift the bits into place.


It is up to the protocol and protocol implementation to make sure that the IV doesn't repeat. The build up of the IV does seem to allow this.

Beware that counters are particularly dangerous to implement: a reset of the device should for instance not reset the counter value. If the implementation can be fooled to increase the counter if the transmission fails then the counter could easily cycle back to the starting value after $2^{32}$ tries.


TL;DR: this seems like a well thought out build up for the IV. If that IV is made sure not to repeat this scheme should deliver the security promised by CTR and AES.

$\endgroup$
1
  • $\begingroup$ Hi Maarten, sorry if I caused any misconception, I thought the diagram was clear. By pairs of input-values/keystreams I refer to my diagram, so keystream is the value that will be XORed with the plaintext and I'm not including of course the cipher key in the input parameters (those that constitute the IV as you mentioned). My concern is if by knowing the IV and a correspondig keystream and assuming that no repetition of IV exists under the same key, whether this can cause an issue. $\endgroup$
    – Jimakos
    Oct 23, 2018 at 14:21
0
$\begingroup$

Firstly, the construction that you described does not provide integrity. So as you say, the ciphertext is malleable.

As you suggest, if the sequence $\textrm{COUNT}||\textrm{IV}_1||\textrm{IV}_2||0^{26}||\textrm{incr}$ can be guessed by an attacker the construction is weak. An attacker with access to an oracle can recover/rebuild the stream and xor it with a given ciphertext and decrypt it.

More generally CTR mode produces a (very very) long pseudorandom key-dependent stream, and uses it to encrypt the plaintext XOR'ing the key-dependent stream with the plaintext. (this is very similar to the One Time Pad encryption, but with the random string generated by the AES)

Reusing the counter with the same key means re-generating the same key-dependent random string, breaking the OneTime property.

See also Why must IV/key-pairs not be reused in CTR mode?

You could probably give a look to the AES-SIV construction, SIV stands for Syntetic IV where the nonce is generated from the message itself, rather than being an explicit input into the algorithm. [See: RFC 5279 or original paper]

$\endgroup$
5
  • 1
    $\begingroup$ I don't see anything in the OP's question that would imply that an attacker could obtain the kind of oracle access necessary to get a duplicate keystream. Admittedly, the OP also doesn't explicitly say that it's not possible. Still, if properly implemented in a way that guarantees that no (COUNTER, IV1, IV2) tuple is ever reused, this scheme seems no less secure than any other instantiation of AES-CTR. $\endgroup$ Oct 23, 2018 at 13:39
  • $\begingroup$ I agree with you. I was only describing the weakness when an oracle is available. $\endgroup$
    – ddddavidee
    Oct 23, 2018 at 13:47
  • $\begingroup$ Thanks everyone for the comments. Some clarifications. The system is designed to avoid repetitions of COUNT/IVs/incr values under the same key, so there is no issue regarding OneTime property. My question had to do with the fact that all of these input values (obviously not the key) can be monitored by an attacker and hence wondering if this could lead to weaknesses. $\endgroup$
    – Jimakos
    Oct 23, 2018 at 14:10
  • $\begingroup$ @ddddavidee perhaps a bit naive, but would give an access to an oracle like that? How would that oracle look like? $\endgroup$
    – Jimakos
    Oct 23, 2018 at 15:22
  • $\begingroup$ An oracle is an abstract entity who can answer to some questions. That would be a system that knows the keys and an attacker can query asking for encryption of whatever message she wishes. Usually in cryptography an oracle is a black box machine executing cryptographic operations involving a secret. In this case it could be a server that encrypts whatever you send to it. $\endgroup$
    – ddddavidee
    Oct 23, 2018 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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