4
$\begingroup$

A sender wants to transmit an ultra secret code $M$ which could be either 'go', 'stop' or 'wait'. This could be any selection of code words really and adopted for any use such as transmitting short commands or short status messages. The code list could also be specific or relevant to a current mission/objective. A limited number of code words will make things a lot faster for the recipient however. I will try explain:

  • Both sender and recipient know the valid code list $L$ and share a random 256 bit key $K$ beforehand. This exchange is out of scope.

  • Let $H$ be a secure hash function with an output of 256 bits which also claims to be a secure MAC in the format of $H$($K$ | $M$). Skein and possibly a few others fit this criteria.

  • Sender generates a random 256 bit nonce $N$ per transmission.

  • Sender generates a MAC tag $T$ by calculating $H$($K$ | $N$ | $M$);

  • Sender sends $N$ | $T$ in the clear to the recipient.

The recipient tries each message in the code list with the nonce and key to try get a match with the sent MAC tag and thus decipher the message:

function(K, L, N, T) {
   foreach M in L {
      if (T equals H(K | N | M)) {
         return M
      }
   }
   return invalid
}

You will note there is no separate MAC tag sent to authenticate the nonce and MAC tag sent in the clear. Because there are only 3 valid codes, there are only 3 possible MACs considered valid by the recipient. This increases the attacker's chance of a creating a forgery to 2^256 / 3 = 2^254 but this is still comfortably secure. You could in fact have 1000 code words and the security would still be adequate at 2^246. However shorter code lists would be better to prevent a DOS type attack when an attacker sends fake transmissions causing excess MAC validation work for the receiver. For longer code lists, perhaps a separate MAC of the $N$ and $T$ would fix that.

From what I can ascertain, only the recipient should know the true message. An attacker can if they do a brute force of the key space (2^256 difficulty) or break the hash function. There is practically no chance of the receiver interpreting the transmitted code incorrectly because the odds of a valid code word producing the same MAC tag is extremely unlikely due to the collision resistance of the hash function.

Can a secret message be securely transmitted, authenticated and read like this?

$\endgroup$
5
  • 1
    $\begingroup$ If the code word count is limited enough there are more simple options, such as using AES_CTR and the block counter being the codeword. The sent message would be 28 bytes, you have $2^{32}$ options for code words, and you only need to decrypt once (no more DOS) $\endgroup$ Nov 21, 2014 at 11:37
  • $\begingroup$ @Richie Frame, but is AES_CTR considered a secure MAC? Otherwise you would need more bytes for a MAC tag too. $\endgroup$
    – ushadm
    Nov 21, 2014 at 11:55
  • 1
    $\begingroup$ it is a secure block cipher, CTR in this case is the same as N | AES_ECB(N | M), and even if the attacker knows N, he does not know the key to the block cipher. If you want to encode the secret inside the MAC of a different message, then this can also be used, and you encrypt the actual MAC with AES_CTR under the super secret key $\endgroup$ Nov 21, 2014 at 11:58
  • $\begingroup$ @Richie, sounds more complicated. The advantage with my scheme is you could encode messages of variable length and it produces a fixed output ciphertext and MAC in one. I don't think AES can do that, can it? $\endgroup$
    – ushadm
    Nov 30, 2014 at 1:06
  • $\begingroup$ Your scheme does not produce ciphertext, mine does not produce a MAC. And yes, you can encode larger messages, but as you said your messages will probably be less than 8-bits in size $\endgroup$ Nov 30, 2014 at 9:45

2 Answers 2

2
$\begingroup$

There are two parts to this proposal: the use of a code book and a scheme to send short confidential and authenticated messages utilising an existing shared symmetric key.

A code book can be used alone to provide a degree of confidentiality, or can be used to ascribe specific pre-agreed meanings to short messages, in combination with any scheme for sending those short messages. The rest of this answer focuses on the use of a MAC for sending such short messages.

Short answer: yes, this scheme preserves confidentiality and integrity of messages.

Pre-image resistance of the secure hash function ensures confidentiality of the message (in conjunction with an appropriately strong key).

The use of a nonce ensures that an eavesdropper can't tell whether a genuine message is the same as any previous messages.

The properties of a MAC prevent forgeries or manipulated messages being accepted.

Note that this system does not protect against replay attacks or message re-ordering attacks, i.e. it can't be used as a generic secure channel. Once an attacker has observed a message, they can replay the message and the recipient cannot differentiate between a replayed message and a fresh message. If the recipient were to record all valid nonce-message pairs they could detect replays, but not out-of-order messages.

This use of a MAC isn't a standard way to build a secure messaging system, so shouldn't be used for production systems. Practically, it has very large message expansion (256 bit ciphertext + 256 bit nonce per ~10 bit data transferred = ~500bit overhead per 10 bit message). An example of a standardised alternative is GCM, which is more size-efficient (96bit nonce + up to 128bit tag = up to 224bit fixed overhead per any length of message) as well as supporting very long messages.

$\endgroup$
13
  • $\begingroup$ Thank you for your answer. I was mainly just asking about the confidentiality and authentication as I was considering using it in a channel which is already protected against reordering or replaying attacks. Anyway one could easily send a sequence number with each message. Or check for repeated nonces, then use a timestamp as well to reject messages outside of a valid time window or that have been reordered. $\endgroup$
    – ushadm
    Nov 30, 2014 at 0:56
  • $\begingroup$ has massive message expansion (384 bit ciphertext incl nonce per ~10 bit message) Well actually it's 512 bit ciphertext including the nonce. Point is, the message can be any length and it would produce the same length ciphertext. As long as the sender and receiver agree on the code book in advance, they can send entire sentences e.g. 'Attack these coordinates', followed by 'Latitude', '127', '134', '233', 'Longitude', '222', '321', '12', 'Time', '14', '45'. Or 'Wait until midnight' etc. $\endgroup$
    – ushadm
    Nov 30, 2014 at 1:00
  • $\begingroup$ Thanks, fixed the length. The actual data sent is of very restricted size, which is what I am referring to by 'message'. How this message is interpreted is up to the system it exists in as you point out. I wouldn't recommend using this non-standard approach - I've updated my answer to reflect this. $\endgroup$
    – Michael
    Nov 30, 2014 at 9:06
  • $\begingroup$ I'm not really interested in your "recommendations". I asked a specific question about whether it was secure or not. It does appear to be secure regardless of whether or not it's considered "standard" or inefficient. $\endgroup$
    – ushadm
    Dec 1, 2014 at 7:59
  • $\begingroup$ I notice you decided to use a 96 bit GCM tag to compare it. This lowers the security and is not secure against a quantum computer. Let's compare apples to apples for a minute. If you paired the AES CTR mode cipher with HMAC-SHA256 and a message of the same length, my scheme is actually more efficient in terms of ciphertext length. For an arbitrary length, let's say 200 bit message, my scheme would total 512 bits. That is a fixed length for any message size. For your CTR mode scheme you have 256 bit nonce + ciphertext + padding + 256 bit MAC. That would be 712 bits or more. $\endgroup$
    – ushadm
    Dec 1, 2014 at 8:10
1
$\begingroup$

Yes, I don't see why this scheme would not be secure. It uses a MAC over known data - protected against replay. If that data is received or calculated locally shouldn't matter.

But as you already showed yourself, you bring down the security of the tag with the amount of bits required to calculate the options. So in the end you could as well just CTR-encrypt the $m$ bits of the message $M$ and create a tag value $t$ that is $m$ bits shorter in size.

There is already have a nonce (which is unnecessarily large) and shared secret in the protocol, so there is nothing preventing the use of AES-CTR within the scheme. The only disadvantage of this scheme is that you may loose one bit of space (as you will require two bits to encode a value with 3 possibilities).

$\endgroup$

Your Answer

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

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