wondering the secret message number

[liting zhang]

Dear, all

 

Will someone please show us in what kind of current applications the secret message number is used, and how?

 

Should this number be shared between the communicating parties in advance? 

 

 

Or the sender may have to choose and use it in the encryption, and finally send out by hiding it in the ciphertext. Then, what benefits can the receiver obtain?

 

Thanks a lot.

 

 

Liting Zhang

[D. J. Bernstein]

Here's a sequence of three illustrative cipher examples, with security
failures in the first two. I'll take AES modes, but similar comments
apply to integrated ciphers; what matters here is the data flow.

First example: Classic CBC converts a plaintext message (p0,p1,...) into

n, c0 = AES_k(p0+n), c1 = AES_k(p1+c0), c2 = AES_k(p2+c1), ...

which is a security disaster if n is a counter. The cryptographers are
relying critically on the user to provide a random n for each message.
(Note that the CAESAR draft call specifically says "ciphers should not
ask users to choose message numbers randomly".)

Cryptographers then add a stateless authenticator (say HMAC) into the
plaintext or ciphertext to build an authenticated cipher---but this does
nothing to stop the simplest type of forgery, namely a replay. The
cryptographers are relying critically on the user to incorporate some
counter into the authentication (via plaintext or "associated data") and
to check that the counter is larger than the largest previous
authenticated counter.

In theory there's no reason that users can't do these things, but in the
real world users get them wrong much more often than cryptographers do.
(For example, ssh seems to allow trivial packet replays after 2^32
packets.) Even if they're done correctly, there's an obvious cost in
bandwidth and performance from having both an n for the CBC mode and a
separate counter embedded into the plaintext. There's also a missed
opportunity to protect against denial of service: better crypto can

* throw away replays immediately and
* throw away all other forgeries after verification,

but with this cipher replays aren't thrown away until after the
cryptography has spent all the time to verify _and_ decrypt them.
Encrypt-then-MAC ciphers are often claimed to allow fast rejection of
forgeries, but this claim is simply wrong for ciphers of the type shown
here---it's based on the erroneous view that a replay is not a forgery.

Second example: Modern CBC, at only slightly more expense, sends

n, c0 = AES_k(p0+AES_j(n)), c1 = AES_k(p1+c0), c2 = AES_k(p2+c1), ...

using an extra key j to encrypt n. Suddenly there's no need for n to be
a random number---a counter is safe. There's no need for a separate
anti-replay counter embedded into the plaintext.

On the other hand, this is suddenly exposing information that wasn't so
obviously exposed before: each message says how many messages came
earlier. Theoretical security models typically conclude that this isn't
a problem since they assume that the attacker sees the complete history
of all messages anyway---but the reality is more complicated:

* Maybe the attacker is seeing only occasional packets, and maybe the
user doesn't want those to give away the exact number of preceding
and intermediate packets.

* Maybe the user finds it convenient to use a high-resolution
monotonic clock as a message number, and doesn't want to have this
clock data leaked to attackers. Actual CPU clocks aren't exactly
real time---the difference shows temperature, which shows load,
even load from nearby CPU cores that shouldn't be talking to the
network.

* Maybe the user wants to reuse some source of unique data from
earlier in the protocol, and doesn't want to expose that data to
the attacker.

* Maybe the user is encoding messages inside a cover channel to
circumvent censorship, and wants the whole sequence of messages to
be indistinguishable from uniform random strings.

* Maybe the user simply thinks that encrypting everything is the
correct default.

I wouldn't say that a failure of message-number confidentiality is as
severe as the failures in the first example, but I also wouldn't dismiss
a security problem on the basis of the inability of some oversimplified
theoretical model to express the problem.

Third example: Users who are concerned about the above exposure of n can
simply encrypt it, again with only slightly more expense:

AES_i(n), c0 = AES_k(p0+AES_j(n)), c1 = AES_k(p1+c0), c2 = AES_k(p2+c1), ...

Probably this isn't the optimal overhead---it's just an example of how
users react when ciphers aren't solving their problems, although I'm
probably being too optimistic in assuming that the users will take an
independent key for this encryption.

I've heard increasingly frequent discussions of message-number
confidentality. Apparently some cipher designers are thinking about the
requirements, and presumably coming up with something much better than
this third example. Of course, cipher designers who aren't interested
can simply specify a length of 0 for the secret message number.

http://eprint.iacr.org/2013/242 says that allowing secret message
numbers has a cost in "familiarity" and "minimalism" and "conceptual
complexity". But

* stopping replays is a real security requirement; and
* protecting the confidentiality of message numbers is, at least for
some users, a real security requirement.

Ignoring these requirements doesn't make them go away. Ciphers that fail
to solve the problems simply force users to deploy their own solutions,
producing a complicated, fragile system, whereas it's relatively easy to
integrate solutions directly into the ciphers. Saying that encrypting
message numbers has a cost in "complexity" is like saying that
encrypting variable-length messages has a cost in "complexity"---well,
yes, it does have a cost, but that's what users need.

I find it quite strange to see a call for "minimalism" from people who
keep writing definitions that treat associated data separately from
plaintext. It's clearly more "minimal" for the cryptographer to allow
just plaintext, and to tell the user to put a hash of the associated
data into the plaintext. Sure, this means some extra cost in bandwidth
and computation, but these costs aren't more severe than the costs and
security problems described above, so anyone who advocates burying the
latter under "minimalism" should also advocate burying the former.

Security goals: Allowing a secret message number---and in particular
allowing _both_ a secret message number and a public message number, as
the CAESAR draft call does---creates possibilities of different security
levels for

(1) protection no matter how users choose secret and public message
numbers;
(2) protection if users never repeat the concatenation of secret
message number and public message number;
(3) protection if users never repeat the secret message number;
(4) protection if users never repeat the public message number;
(5) protection if users never repeat the secret message number _and_
never repeat the public message number.

Obviously 1=>2, 2=>3, 2=>4, 3=>5, and 4=>5. If secret message numbers
aren't allowed then 3 and 5 are vacuous while 2 and 4 are equivalent;
2/4 then match the standard definition in the literature while 1 is the
extra robustness considered in a few papers. Allowing secret message
numbers forces 2 and 4 to split, so the CAESAR draft call is careful to
specify 2 (not 4) as the minimum security level, while also allowing 1
(and intermediate possibilities such as the "almost foolproof" McOE):

Security goals: ... This section must clearly state either
* that users are required to treat the concatenation of the private
message number and the public message number as a nonce, i.e., that
the cipher may lose all integrity and confidentiality if the
legitimate key holder uses the same (private message number,public
message number) pair to encrypt two different (plaintext,additional
data) pairs under the same key; or
* that the cipher is designed to provide the maximum possible
robustness against message-number reuse, i.e., that the cipher
maintains full integrity and confidentiality, except for leaking
collisions of (plaintext,additional data,private message
number,public message number) via collisions of ciphertexts; or
* that the cipher is designed to provide some intermediate level of
robustness against message-number reuse, in which case this section
must specify what that level of robustness is.

The rules allow designers to build a cipher that encrypts _part_ of a
nonce, and that (as usual) requires the user to avoid repeating nonces,
but they don't allow the cipher to lose security if the user repeats
just the encrypted part (or just the unencrypted part) of the nonce
while the other part changes. It's not clear that there's any demand for
ciphers that encrypt _part_ of a nonce without encrypting the whole
thing, but there's also no obvious reason to prohibit it.

http://eprint.iacr.org/2013/242 says that adding a secret message number
allows "inequivalent definitions"---well, yes, 2 and 4 are different---
and that 2 and 1 are the "basic goals"---well, yes, that's what the
draft CAESAR call already said. http://eprint.iacr.org/2013/242 is wrong
in saying that the draft call allows 3, 4, or 5.

liting zhang writes:
> Will someone please show us in what kind of current applications the secret
> message number is used, and how?

As the call says, many existing applications use "96-bit or 104-bit
public message numbers" and "0-bit secret message numbers", i.e., no
secret message number.

On the other hand, if you run TCP packets in standard "tunnel mode"
through an IPsec VPN then IPsec will encrypt not just the plaintext that
TCP is carrying but also the TCP message number ("sequence number").
IPsec then adds its own message number on the outside---which leaks less
information than TCP message numbers when multiple TCP connections are
sent through the same tunnel, but also is clearly not a great solution.

> Should this number be shared between the communicating parties in
> advance?

The secret message number is communicated inside the ciphertext: "It
must be possible to recover the plaintext and the secret message number
from the ciphertext, associated data, public message number, and key."
This is also stated in the API.

> Or the sender may have to choose and use it in the encryption, and
> finally send out by hiding it in the ciphertext. Then, what benefits
> can the receiver obtain?

See above.

---Dan