Should we do superencryption, and can we do it in a way that keeps the forgeability of the surrounding stuff about otrv4

[chelseakomlo]

I have some notes on this from meeting with Ian, will send out tomorrow.

[iapazmino]

I believe we said no PQ for now.
Should we close and reopen if needed in the future?

[tcz001]

adding a milestone here.

[olabini]

What is this????

[olabini]

Super encryption is not PQ.

[olabini]

And doesn't involve that decision at all.

[tcz001]

@olabini Where is the super-encryption published?

[olabini]

It's not.

[tcz001]

@olabini ok, could you please give some basic description about this?

[tcz001]

I saw this line in the Thoughts.md

"2048-bit mod p Diffie-Hellman" around the outside

What property is it trying to provide?

[chelseakomlo]

OTRv3 wraps the AKE with an unauthenticated DH exchange. Is this issue the investigation into whether we should do this for v4?

[olabini]

No. I explained this several times in the previous meetings. Noone listened?

[chelseakomlo]

I personally didn't understand when it was first explained. @olabini if you wouldn't mind pointing us in a direction for this, that would be helpful.

However, if this isn't a priority, we can wait on doing an investigation.

[tcz001]

To me, I didn't really catch all the Information when you mention
superencryption wrapping with an unauthentated diffie-hellman, and that
came when you also talked about postquantum resistance.

I think this is why Ivan and I both thought it's related with the PQ
decision, but turns out not (though in paper there's supersingular isogeny
DH for PQ suggested that made us confused).

But really I didn't mean to not listening to you, I apologize for repeat
this question. But I really don't know what it exactly means, I can't guess
this out, please point me to that Ola.

2016年9月16日 上午8:51，"Ola Bini" [email protected]写道：

No. I explained this several times in the previous meetings. Noone
listened?

—
You are receiving this because you modified the open/close state.
Reply to this email directly, view it on GitHub
#11 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/ABn5xPOIsaOBsZTF_L4yWB2DOJYbL-ptks5qqp74gaJpZM4J2NI7
.

[chelseakomlo]

Ok. So super encryption would be wrapping the message channel after the AKE has completed.

[claucece]

Usually, the outer-level encryption of a multiple encryption is called superencryption. We aim for: having an unauthenticated encrypted channel at the very beginning of the data exchange.

The reasons for using it are, as referenced in otr-dev:

1. Never have a packet on the network that is not encrypted or a key exchange.
2. Just to slightly hedge against elliptic curves being weaker than we think, or even to quantum computers with hundreds but not thousands of qubits, the whole OTRv4 protocol should have an outermost level encryption.

What will be used?
Unauthenticated 2048-bit mod p Diffie-Hellman. Using the order of 2048 as it is estimated that the pre-computation required for a 2048-bit prime is 10^9 more difficult than for 1024-bit primes. Vulnerable to man-in-the-middle-attack.
Comment: There is an interesting comment on OTR-dev meetings, suggesting the use of 3072 bit.

Important questions:

• How does this interact with the various deniability portions of the protocol? In an interactive setting, Spawn provides online repudiation for both parties. In non-interactive settings where the adversary is able to guarantee that the first message is honestly generated by the true I, Spawn does not provide online repudiation for R.
• How it will interact with the MAC keys? In OTRv3, revealing MAC keys means: Whenever you are about to forget either one of your old D-H key pairs, or one of your correspondent's old D-H public keys, take all of the receiving MAC keys that were generated by that key (note that there are up to two: the receiving MAC keys produced by the pairings of that key with each of two of the other side's keys; but note that you only need to take MAC keys that were actually used to verify a MAC on a message), and put them (as a set of concatenated 20-byte values) into the "Old MAC keys to be revealed" section of the next Data Message you send. This in done to allow the forgeability of OTR transcripts: once the MAC keys are revealed, anyone can modify an OTR message and still have it appear valid. But since we don't reveal the MAC keys until their corresponding pubkeys are being discarded, there is no danger of accepting a message as valid which uses a MAC key which has already been revealed.
  // With superencryption, we aim to keep the forgeability. Further revelation may be needed by double ratcheting. Problem is that the revelation of MAC keys will happen at the inner level and they will no longer be revealed at the outermost level. // Refer to #44

Todo:

• Define security of Diffie-Helmann vs Elliptic curves on PQ: Contrary to DH, elliptic curve cryptography is expected to be more vulnerable to an attack based on Shor's algorithm.
• Define forgeability: In a cryptographic digital signature or MAC system, digital signature forgery is the ability to create a pair consisting of a message, m, and a signature (or MAC), σ, that is valid for m, where m has not been signed in the past by the legitimate signer. There are three types of forgery: existential, selective, and universal.

[chelseakomlo]

Some of the questions we should answer are:

1. What additional security properties would this give us?
2. What additional complexity does it introduce?
3. Is adding this worth the additional complexity?

[chelseakomlo]

This paper talks about how textsecure achieves weaker deniability than OTR because it doesn't publish MAC keys: https://eprint.iacr.org/2014/904.pdf

OTR publishes MAC keys so anyone can forge the message.

In Textsecure, messages are encrypted using a symmetric primitive, so either side could have forged the entire transcript. So deniability relies on the fact that the other party could forge the entire transcript, not that anyone could have forged it.

Apparently, because the Textsecure server logs whom the messages are to and from, this breaks deniability for Textsecure in practice.

[chelseakomlo]

moxie0 posted a point about how wrapping OTR with an outer layer of encryption, even if unauthenticated, breaks deniability in practice:

https://whispersystems.org/blog/simplifying-otr-deniability/

What's more, since the initial OTR key exchange is signed and transmitted through an unobservable channel (an "outer" ephemeral key exchange), it's not actually possible for anyone to produce what appears to be a conversation with you. Only people you've actually had a conversation with are in possession of a signed ephemeral key from you, and are thus the only ones capable of producing plaintext messages attributed to you. Publishing old plaintext MAC keys in the clear does not substantially increase this set of people's ability to forge messages from you, since they are already in possession of the MAC keys.

[chelseakomlo]

https://blog.cryptographyengineering.com/2012/02/02/multiple-encryption/

[chelseakomlo]

Goals of superencryption:

1. Hedge against elliptic curves being weaker than we think
2. Add more time for quantum computers to catch up (DH will take more time than EC to break)

Considerations:

How does it interact with the various deniability portions of the protocol?

If we did superencryption, here is how we could do it:

Option 1: Everything is contained within the encrypted channel
So OTR messages would look like this:
{
Headers
Encrypted message
Current Ephemeral Key
MAC
Old MAC Keys
}
and then all of this would be encrypted by AES-CTR and sent over the network.

In doing this, we assume that the same security features are preserved to when there is no external encrypted channel. Therefore, the malleability of a message, the ability to forge a single message at any point in time during the conversation, etc all still holds.

Option 2: We publish MAC keys outside of the encrypted channel
So message sent over the network would look like this:
{
encrypted OTR packet (AES-CTR)
Old MAC Keys
}

In doing this option, we assume that deniability is improved by publishing MAC keys outside of encrypted channel.

Questions:

1. How does the ability for an attacker to forge a single message change with either option?
   (It seems that if we create an encrypted channel, we can only provide the security property that an attacker can forge an entire transcript, not a single message.)
2. Is doing superencryption preferable to just going with a PQ option?

[chelseakomlo]

The purpose of this is to describe where in the protocol we make choices to ensure deniability:

1. DAKE
   • We use NIZKPs for signatures
   • We use Dual-Receiver encryption for both sides to create a shared symmetric key

Wrapping this in an unauthenticated encrypted channel would not compromise the deniability features of either of these.

1. Data messaging
   • We publish MAC keys to make it very obvious that anyone could have interfered with the message. In order to forge a message, MAC keys are not enough as content keys are still needed: thus the only person that can forge is the other participant.

If we only sent an packet across the network that is encrypted by AES-CTR, someone would have needed to MITM the initial unauthenticated DH handshake to gain access to the inside channel.

[chelseakomlo]

Needing to MITM the initial DH handshake at the beginning of the protocol would break individual message deniability.

The argument against publishing MAC keys is similar- that it isn't a far stretch for someone to have access to the ciphertext of one message, and having the ability to control an endpoint. So we should think about this in regards to that argument. See here for more info: https://lists.cypherpunks.ca/pipermail/otr-dev/2013-July/001801.html

[claucece]

How slow will this be?

Generating prime numbers >= to 2048 bits takes a non-trivial amount of time, sometimes close to a minute. Refer to here. -Not the best source, I have to say-.

Also, from OTR-dev mailing list:

'The WPES 2004 paper states that under the current protocol a person can send and receive up to 18 messages per second (36 messages total) on a 450 mhz Pentium IIII. Thus, it would seem that even on a slow machine 2048 bit DH moduli wouldn't add a great deal of latency. 450 mhz
machines are also on the low end of what is generally used for desktops. Most PCs are 2-3 years old and 450 mhz processors are at least 4-5 if I remember correctly.' From here.

1. Add more time for quantum computers to catch up (DH will take more time than EC to break)

About elliptic curve:
The work of Proos and Zalka show how a quantum computer for breaking 2048-bit RSA requires roughly 4096 qubits, while a quantum computer to break the equivalently secure 224-bit Elliptic Curve Cryptography requires between 1300 and 1600 qubits.

About RSA, but relatable to Diffie-Hellman:
'Inherent in these anticipations is the well founded belief, thoroughly supported by experience, that if classical computing is all that’s available then RSA public key systems can be kept secure via increases of key number size no matter how much classical computers improve, because the magnitude of the computing effort needed to factor a large number N increases so very rapidly with increasing N.

Thus it is estimated that by 2009 a computer costing no more than $10 million will be able to factor RSA-309 in less than one month; correspondingly it is anticipated that by 2010 the standard (not merely ”extremely valuable”) RSA key number size will be 2048 binary digits, and by 2030 will be 3072 binary digits (corresponding to RSA-925).' Refer to this paper, page 6., by Edward Gerjuoy. Refer to this paper for attacks on DH less than 2048. '

1. Hedge against elliptic curves being weaker than we think

'The ~224-bit security level of curve448 is a trade-off between performance and paranoia. Large quantum computers, if ever created, will break both curve25519 and curve448, and reasonable projections of the abilities of classical computers conclude that curve25519 is perfectly safe. However, some designs have relaxed performance requirements and wish to hedge against some amount of analytical advance against elliptic curves and thus curve448 is also provided.' Refer here. Refer to this discussion too.

[chelseakomlo]

How the AKE would work? What it will look like with Spawn and initiating an unauthenticated DH exchange for data messages:

Interactive:

1. Alice sends {gDH^a, ψ1 = ("I"; gCS1^i)}. a is Alice's DH secret, gDH is the corresponding generator, gCS1 is the Cramer-Shoup generator.
   2, Bob sends {gDH^b, ψ2 = (“R”, γ, σ)}. b is Bob's DH secret, gDH is the corresponding generator, γ is DREnc, σ is Auth.

Non-interactive would be the same but the first step for the initiator would be stored in a central server.

[chelseakomlo]

How a data message flow would work:

(assuming the ratchet has already been initialized and an unauthenticated DH exchange has occured, both sides share a shared secret S)

EncDH and DecrDH can be AES-CTR.

1. Alice creates ciphertext EncDH(S, {ephemeral, ciphertext, MAC})
   Alice sends M1 = {ciphertext, old MAC key}
2. Bob receives M1
   Bob decrypts inner ciphertext DecrDH(S, M1 ciphertext)
   Bob validates the inner ciphertext and then decrypts using the double ratchet flow.

[chelseakomlo]

Using AES-CTR as it is malleable.

We use a malleable stream cipher so that any change to a bit in the ciphertext will correspond to a change to the corresponding bit in the plaintext.

[claucece]

4 scenarios:

Goal of adversary: Recover plain text.

Inner: encryption of message after double-ratcheting using ECDH.
Outer: encryption of message after AES-CTR using unauthenticated 2048 DH.

Inner broken: Elliptic Curve being not as secure as thought or Elliptic Curve vulnerable to an attack based on Shor's algorithm, which will take less time than DH.
Outer broken: vulnerability of DH to a man-in-the-middle attack or vulnerability of DH to an attack based on Shor's algorithm, which will take longer time than EC.

1. The inner is broken and the outer not.
   Case: A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits.
   Meaning: Mallory, an active attacker, will need a large n amount of time to break the DH outer layer, making this scenario secure (attacker cannot recover plaintext) until the n time have passed. DH will still protect the message even if EC is broken.
2. The inner is not broken, the outer is broken:
   Case 1: Mallory may establish two distinct key exchanges, one with Alice and the other with Bob, effectively masquerading as Alice to Bob, and vice versa, allowing her to decrypt, then re-encrypt, the messages passed between them. Note that Mallory must continue to be in the middle, transferring messages every time Alice and Bob communicate. If she is ever absent, her previous presence is then revealed to Alice and Bob. They will know that all of their private conversations had been intercepted and decoded by someone in the channel.
   Case 2: The DH key can broken on a quantum computer using around n qubits.
   Meaning: Mallory will still have to break the diffie hellman problem on EC or have the shared secrets in order to break EC. EC, therefore, remains with its same level of security (being perhaps not as secured as thought and vulnerable to a fast quantum attack) and, as a whole, the whole remain with the same security.
3. Both levels are broken:
   Case: A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits and a 2048 bit diffie hellman cryptographic key could be broken on a quantum computer using around n qubits.
   Meaning: Security is totally compromised.
4. None of them are broken:
   Case: EC are as secure as we thought and there is no quantum computers.
   Meaning: Security is not compromised in any way.

TODO: review all of these. Over these define where to reveal MAC keys.
Important comment here #44.

[chelseakomlo]

Thanks @claucece, I saw the same information in these papers:

https://otr.cypherpunks.ca/otr-wpes.pdf
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38a.pdf
http://www.cs.ru.nl/~rverdult/Introduction_to_Cryptanalysis-Attacking_Stream_Ciphers.pdf
https://tools.ietf.org/html/rfc3686#section-1

[chelseakomlo]

What is important to note about CTR mode is that the IV does not need to be unpredictable (unlike CBC) but it does need to be unique to each execution of the encryption operation (so we can use a counter). I am investigating whether this would be an issue for a long-lived conversation, as while we re-key on the inner layer, the outer layer would always use the same key.

[claucece]

@chelseakomlo I don't understand that... could you please elaborate? Thanks! :)

[chelseakomlo]

Sure! If we use the same key for AES-CTR across a long-lived conversation, we'll need to think through how to manage the IV.

I'm reading how this is implemented in other protocols, such as here:
https://tools.ietf.org/html/rfc6054
https://www.ietf.org/rfc/rfc4344.txt

Specifically: "All of the counter-based modes require that, if a single key is shared by multiple encryption engines, those engines must coordinate to ensure that every Initialization Vector (IV) used with that key is distinct. That is, for each key, no IV value can be used more than once."

Section B.2 of the NIST specification talks about how to choose initial counter blocks & maintaining state.

[chelseakomlo]

We need to model rekeying into this as well, per recommendation: "rekey at least once for every gigabyte of transmitted data." https://www.ietf.org/rfc/rfc4344.txt

[chelseakomlo]

Ok, here is the hard problem:

In OTR right now, we do:
ciphertext = Encr(plaintext, key)
mac = hmac(ciphertext, macKey)

Then, we publish the macKey. Because we use malleable encryption, anyone can then do:
forgedMac = hmac(forgedCiphertext, macKey)
and
validate(forgedCiphertext, forgedMac)
meaning that the sender has deniability on their message, because anyone can create an equally valid forged ciphertext.

With superencryption, the hard problem is preserving the property of doing
validate(forgedInnerCiphertext, forgedInnerMac)

Because we publish only the encrypted outerCiphertext, we cannot do:
forgedInnerCiphertext = Decr(forgedOuterCiphertext, unknownSecretKey)
validate(forgedInnerCiphertext, macInnerKey)
Because there is no way to know the forgedInnerCiphertext because we don't know the unknownSecretKey for the outer encryption level.

If we want superencryption, we will need to preserve OTR's message deniability. This means we need a solution where the innerCiphertext can be forged and validated without revealing it.

In OTR, we want messages to be forgeable. After the fact, anyone should be able to modify the ciphertext and it have it be able to be successfully validated. This forgeability property needs to continue to apply to the inner ciphertext, even when it isn't revealed externally.

[claucece]

// in progress
Ok, some thoughts we have with @tcz001:

1. CTR or other kind of block cipher modes of operation with malleability property will still need the forgeability of MAC in order to achieve perfect malleability of the ciphertext (since, otherwise, the MAC code will filter out this invalid ciphertext, even if it is MAC-then-encrypt, MAC-and-encrypt or encrypt-then-MAC).
2. Check if there is another block cipher modes of operation that will provide what we want.
3. Use DH2048 as defined in PQ in Nik's paper.

And approach that can work, but will not provide integrity (plaintext or ciphertext) of inner layer (c_1):

c_2 := Enc_2(k, (c_1: = Enc_1(k,m))) || MAC_2: This will provide ciphertext integrity of c_1, but no integrity of m. Nevertheless, c_2 can be malleable (due to CTR) with the forge of the MAC. Still, this seems to have a lot of problems... will this leak information about plaintext? TODO: check how this will fail, if it does.

1. How possible is to do a M-I-M?
2. If DH-2048 is broken.. how many problems will it make?
3. Problems with no PT integrity?
4. Chosen cipher text attack?

Questions to 4:

1. will it still be malleable?
   @chelseakomlo please, check :)

[tcz001]

Ola mentions some ideas:

First, what if we don't use AES-CTR but something else? Are there
other malleable symmetric schemes that have different properties when
used as super encryption?

Second, do we really need to do two rounds of AES-CTR? What if we use
the same approach Nik used in order to add post-quantum schemes in the
DAKE, but we instead use a classical DH 2048-bit group? In that case
we should theoretically get all the benefits of super encryption
without actually going through all the trouble.

[tcz001]

The second is feasible if we can find a way to handle performance issue better (cache table or only do it once in a conversation).
2048-DH can be an approach to start the DH which can increase the size of sharedsecret.
And then we may want every ratcheting can derive a new ephemeral 2048-bit secret efficiently, like using hash of the previous 2048-bit secret. (not necessary because Root key will be derived from this also)
We can use the 2048-bit DH sharedsecret only once, and then for ratcheting we use the ephemeral ECDH to derive keys for efficiency.

[claucece]

The last approach has being updated in the flow.

As Ola said, though, there are still things to consider:

I think the two biggest questions for an approach like this is whether
it makes sense to put it inside the AKE or outside it - and whether
it's safe to ignore ratcheting for it.