Subject: [Cfrg] Analysis of ipcrypt?

From: Paul Hoffman <[email-masked]>
Date: Thu, 22 Feb 2018 02:03:29 +0000

Greetings. ipcrypt is a format-preserving cipher for IPv4 addresses. It has a 32-bit blocksize for input and output, and 128-bit blocksize for the key. It was developed by Jean-Philippe Aumasson and is described at:
   https://github.com/veorq/ipcrypt
There doesn't appear to be any formal paper describing the algorithm, but the Python and Go code is trivial to follow.

This algorithm is now being considered by a few different projects that want to obfuscate IPv4 addresses. Has anyone analyzed the algorithm? I could not find analyses, but certainly could have missed them.

For a project I'm on, ipcrypt is attractive if an attacker cannot derive the 128-bit random key without a lot (maybe 2^80ish) effort. For cases in common use, assume that the attacker has 2^24 known plaintext/ciphertext pairs under a single 128-bit random key. For additional ciphertexts, how much effort must the attacker expend to get the key in order to decrypt additional unknown ciphertexts?

(Note that there are other options for this use case, which have different positive and negative features. What we'd like to know is how good is ipcrypt if we chose it.)

--Paul Hoffman

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Thu, 22 Feb 2018 06:55:17 +0000

Hi!

I designed ipcrypt as a low-security toy cipher to encrypt IPv4 addresses
for some log analysis application. It may be good enough for this purpose,
however it has very low security:

* because of 32-bit blocks, a chosen-plaintext codebook attack will work in
time 2^32 (or much less for specific IP ranges)

* known-plaintext codebook attacks will work similarly but in O(n log n),
or 2^37 (coupon collector problem)

* there is a generic ~2^16 distinguisher that works by looking for a
collision in a sequence of blocks

* worse, Jason just found a high-probability differential that seems
detectable with fewer than 2^24 chosen-plaintext pair, and which may speed
up key recovery

On Thu, 22 Feb 2018 at 03:03, Paul Hoffman <[email-masked]> wrote:

> Greetings. ipcrypt is a format-preserving cipher for IPv4 addresses. It
> has a 32-bit blocksize for input and output, and 128-bit blocksize for the
> key. It was developed by Jean-Philippe Aumasson and is described at:
> There doesn't appear to be any formal paper describing the algorithm, but
> the Python and Go code is trivial to follow.
>
> This algorithm is now being considered by a few different projects that
> want to obfuscate IPv4 addresses. Has anyone analyzed the algorithm? I
> could not find analyses, but certainly could have missed them.
>
> For a project I'm on, ipcrypt is attractive if an attacker cannot derive
> the 128-bit random key without a lot (maybe 2^80ish) effort. For cases in
> common use, assume that the attacker has 2^24 known plaintext/ciphertext
> pairs under a single 128-bit random key. For additional ciphertexts, how
> much effort must the attacker expend to get the key in order to decrypt
> additional unknown ciphertexts?
>
> (Note that there are other options for this use case, which have different
> positive and negative features. What we'd like to know is how good is
> ipcrypt if we chose it.)
>
> --Paul Hoffman_______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Jason A. Donenfeld" <[email-masked]>
Date: Thu, 22 Feb 2018 10:11:37 +0100

Hi Paul,

Found this last night shortly after you posted this message. The
attached program Samuel (CC'd) and I just drummed up may be cause for
concern. You may not want to use ipcrypt.

Regards,
Jason

---

From: Greg Rose <[email-masked]>
Date: Thu, 22 Feb 2018 06:11:38 -0800

I cooked up "skip32" for a similar purpose a decade or two ago. It's based on Skipjack. Googling for it just now, it appears to be the most widely-deployed cipher I worked on... lots of implementations.

Greg.

Phone/Signal:  +1 619 890 8236 
GPG/PGP:  1081A37C  232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

> On Feb 22, 2018, at 1:11 , Jason A. Donenfeld <[email-masked]> wrote:
> 
> Hi Paul,
> 
> <ipcrypt-broken.c>_______________________________________________
> Cfrg mailing list
> [email-masked]

---

From: Russ Housley <[email-masked]>
Date: Thu, 22 Feb 2018 18:30:36 -0500

Paul:

It sounds like you want a simple and straightforward way to obfuscate IPv4 addresses.

AES is very widely implemented.  You can find libraries for every platform.  So, something like this may do it for you:

	k = rand()  /* 128 bits; fresh key for each dataset */

	for each ipv4addr in dataset:
		plain = ipv4addr || ipv4addr || ipv4addr || ipv4addr
		obfuscated_ipv4addr = trunc32(AES_128_Encrypt(k, plain))

It is easy to go from 32-bit unsigned values to dotted notation and back if needed.

Russ

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 22 Feb 2018 15:58:49 -0800

> 		obfuscated_ipv4addr = trunc32(AES_128_Encrypt(k, plain))

This approach doesn't allow inverting the address if needed.  aiui, the
use case for ipcrypt and other format-preserving encryption is attack
detection and mitigation via anomaly detection, based on packet
captures, but with phased destruction of the IP addresses.

In this case, it's possible that the pcaps will persist for a while
longer (e.g. as inputs to statistical processing that provides baselines
for anomaly detection) than the IP address itself will need to be
available (e.g. for identifing a current attacking address).

            --dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 22 Feb 2018 16:06:22 -0800

On Thu 2018-02-22 06:11:38 -0800, Greg Rose wrote:
> I cooked up "skip32" for a similar purpose a decade or two ago. It's
> based on Skipjack. Googling for it just now, it appears to be the most
> widely-deployed cipher I worked on... lots of implementations.

yeah, skip32 is available all over the place, but...

> void
> skip32(BYTE key[10], BYTE buf[4], int encrypt)

80-bit keys don't seem appropriate for modern use, even for a 32-bit
format-preserving encryption (FPE) cipher.

NIST SP.800-38G identifies FF1 and FF3 as FPE options, both based on AES
with 128-bit or larger keys.

     --dkg

---

From: Greg Rose <[email-masked]>
Date: Thu, 22 Feb 2018 16:14:48 -0800

> On Feb 22, 2018, at 16:06 , Daniel Kahn Gillmor <[email-masked]> wrote:
> 

Anyone who wants to do 32-bit encryption with a key longer than 80 bits already needs to have their threat model reviewed ;-).

Greg.

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 23 Feb 2018 00:19:01 +0000

> Anyone who wants to do 32-bit encryption with a key longer than 80 bits already needs to have their threat model reviewed ;-).

OK, so please review what I said at the top of the thread:

The threat model then is that an attacker with 2^24 known plaintext/ciphertext pairs wants to determine the 128-bit random key that was used so that the attacker can de-anonymize addresses that are not in their current set.

Why is that threat model worth a smiley?

--Paul Hoffman

---

From: Martin Thomson <[email-masked]>
Date: Fri, 23 Feb 2018 11:46:23 +1100

Have you looked at FFX?  That has much stronger claims than those for
ipcrypt and it doesn't suffer the problem DKG described with Russ'
simple scheme.  It's a fair bit more computationally expensive though
- it uses a Feistel network with a decent number of iterations, which
means that the PRF (typically AES) needs to be run more often than you
might think.

On Thu, Feb 22, 2018 at 1:03 PM, Paul Hoffman <[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]

---

From: Greg Rose <[email-masked]>
Date: Thu, 22 Feb 2018 17:52:59 -0800

> On Feb 22, 2018, at 16:19 , Paul Hoffman <[email-masked]> wrote:
> 

I think J-P's earlier posting already described that he considered ipcrypt to be "a low-security toy cipher". He also very well spelled out the various generic attacks. You yourself said "2^80ish" work to recover the key. So my smiley was about the fact that recovering an 80-bit key in 2^80ish work is just as hard as recovering a 128- or 256-bit key in 2^80ish work. And it happened that I had an 80-bit key 32-bit block cipher lying around, so I mentioned it. I did not mean to give offense.

Greg.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 23 Feb 2018 06:53:27 +0000

I just looked at ipcrypt.

Obviously, a simple MITM attack would recover the key with 2^64 work (and a handful of known plaintexts/ciphertexts).

In addition, I believe I found a linear characteristic through the permutation; the bias is about 0.5 - 0.016.  This linear characteristic should (haven't verified) lead to something that recovers an outer round key (or, at least, places it within a 100 or so of potential values) with your 2^24 known plaintexts/ciphertexts and about 2^54 work (where 'work' is the equivalent of evaluating the cipher once).

I'm currently searching for more linear characteristics; that would drasticly improve this result.  However, even with what I have, this doesn't look good for this cipher.

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Paul Hoffman
> Sent: Thursday, February 22, 2018 7:19 PM
> To: Greg Rose <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [Cfrg] [Ext] Re: Analysis of ipcrypt?
> 
> > Anyone who wants to do 32-bit encryption with a key longer than 80 bits
> already needs to have their threat model reviewed ;-).
> 
> For a project I'm on, ipcrypt is attractive if an attacker cannot derive the 128-
> bit random key without a lot (maybe 2^80ish) effort. For cases in common
> use, assume that the attacker has 2^24 known plaintext/ciphertext pairs
> under a single 128-bit random key. For additional ciphertexts, how much
> effort must the attacker expend to get the key in order to decrypt additional
> unknown ciphertexts?
> 
> The threat model then is that an attacker with 2^24 known
> plaintext/ciphertext pairs wants to determine the 128-bit random key that
> was used so that the attacker can de-anonymize addresses that are not in
> their current set.
>

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Fri, 23 Feb 2018 14:25:57 +0000

Hi Paul,

Besides the particulars of the cipher, it is important to realize that deterministic encryption of addresses, or any other identifier, provides a limited amount of security against a dedicated attacker.  You surely know this already, but it is a point worth raising in this thread.  Deterministic encryption of addresses is worth using, in my opinion, but it is important that end users understand the limitations.

The best example of the security limitation is the following.   Suppose that you have a set of (source address, destination address, port, protocol, time) tuples for a corporation, where source addresses (but not destination addresses) have been anonymized through deterministic encryption of addresses.  Your goal is to find the traffic of the CEO, and you start by gathering intelligence about that individual (alma mater, state of origin, etc.) then construct a set of server addresses that the target is likely to visit.  With this data, you now have enough to achieve “robust deanonymization of large, sparse datasets” (as per Narayanan and Shmatikov).   If, on the other hand, the destination addresses are anonymized, the deanonymization challenge is harder (and the data set is less useful).  

For the record, I’ve used deterministic encryption of IPv4 addresses using a single AES-128 invocation, using the simple approach of padding out the 32-bit address to a 128-bit plaintext, then making room for the ciphertext.  In my application, the addresses are stored as JSON, so the expansion is not hard to accomodate.

best

David

---

From: Russ Housley <[email-masked]>
Date: Fri, 23 Feb 2018 12:05:42 -0500

> captures, but with phased destruction of the IP addresses.

Paul's description did not say that inversions was a requirement.  And, if you know the AES key, the work factor is _at_most_ 2^32 AES block operations.  That is within reach on my laptop.

The FF1 and FF3 solutions are fine solutions.  If the number of times that one has to remove the obfuscation is very low, then the lower encrypt cost of the above algorithm may be desirable.

Russ

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Sat, 24 Feb 2018 07:34:35 +0000

Seconding David. We're talking tokenization more than encryption. In the
context where I created ipcrypt we just needed to obfuscate the PII data
(such as IP addresses) in a deterministic and format-preserving way.

On Fri, Feb 23, 2018 at 3:26 PM David McGrew (mcgrew) <[email-masked]>
wrote:

> Hi Paul,
>
> Besides the particulars of the cipher, it is important to realize that
> deterministic encryption of addresses, or any other identifier, provides a
> limited amount of security against a dedicated attacker.  You surely know
> this already, but it is a point worth raising in this thread.
> Deterministic encryption of addresses is worth using, in my opinion, but it
> is important that end users understand the limitations.
>
> The best example of the security limitation is the following.   Suppose
> that you have a set of (source address, destination address, port,
> protocol, time) tuples for a corporation, where source addresses (but not
> destination addresses) have been anonymized through deterministic
> encryption of addresses.  Your goal is to find the traffic of the CEO, and
> you start by gathering intelligence about that individual (alma mater,
> state of origin, etc.) then construct a set of server addresses that the
> target is likely to visit.  With this data, you now have enough to achieve
> “robust deanonymization of large, sparse datasets” (as per Narayanan and
> Shmatikov).   If, on the other hand, the destination addresses are
> anonymized, the deanonymization challenge is harder (and the data set is
> less useful).
>
> For the record, I’ve used deterministic encryption of IPv4 addresses using
> a single AES-128 invocation, using the simple approach of padding out the
> 32-bit address to a 128-bit plaintext, then making room for the
> ciphertext.  In my application, the addresses are stored as JSON, so the
> expansion is not hard to accomodate.
>
> best
>
> David
>
>
> On 2/22/18, 7:19 PM, "Cfrg on behalf of Paul Hoffman" <
> [email-masked] on behalf of [email-masked]> wrote:
>

---

From: Greg Rose <[email-masked]>
Date: Sat, 24 Feb 2018 06:41:46 -0800

> On Feb 23, 2018, at 23:34 , Jean-Philippe Aumasson <[email-masked]> wrote:
> 
> Seconding David. We're talking tokenization more than encryption. In the context where I created ipcrypt we just needed to obfuscate the PII data (such as IP addresses) in a deterministic and format-preserving way.

Now I'm confused. Is there a requirement for invertability or not? The problem, if it isn't invertible, is that it will act as a hash, and you can expect collisions after only about 60k entries. Are there consequences to that?

Greg.

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Sat, 24 Feb 2018 14:51:00 +0000

In my use case it had to be 1-to-1.
On Sat, 24 Feb 2018 at 15:41, Greg Rose <[email-masked]> wrote:

> Now I'm confused. Is there a requirement for invertability or not? The
> problem, if it isn't invertible, is that it will act as a hash, and you can
> expect collisions after only about 60k entries. Are there consequences to
> that?
>
> Greg.

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 24 Feb 2018 15:31:06 +0000

> Now I'm confused. Is there a requirement for invertability or not? The problem, if it isn't invertible, is that it will act as a hash, and you can expect collisions after only about 60k entries. Ar…

This is a problem that is being debated by the users of the system.

- Invertability is a great feature if we can get it without concern that it lets an attacker with a lot of known pairs recover the key so they can then deanonymize all the pairs. 

- Non-invertable (current proposal is truncate32(AES128(32_bit_address, 128_bit_random_key))) causes collisions, but those collisions only affect researchers looking over a dataset who are trying to determine why party X sent a particular stream of messages. When there are collisions, two parties' streams get merged; however, with mix-and-truncate, there the attacker cannot determine the key from lots of known pairs.

There is a difficult balance: the party anonymizing the data has a much higher cost if the data is deanonymized than the benefit that is going to the party reading the data. One safe way to anonymize the addresses is to set them all to 0.0.0.0, but that makes them useless to the readers. The question is how far beyond that simple safe mechanism the anonymizing party should go, and at what cost. That's not a question that can be handled in CFRG (and it's not clear we will handle it well in the DNS operators fora).

--Paul Hoffman

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Sat, 24 Feb 2018 15:42:07 +0000

A “non-invertible” construction based on truncated AES will yield many
collisions if format-preserving (hashing to a 32-bit space), and it’ll
likely become partially invertible with sufficiently many known in-out
pairs.
On Sat, 24 Feb 2018 at 16:31, Paul Hoffman <[email-masked]> wrote:

> >> Seconding David. We're talking tokenization more than encryption. In
> the context where I created ipcrypt we just needed to obfuscate the PII
> data (such as IP addresses) in a deterministic and format-preserving way.
> >
> - Invertability is a great feature if we can get it without concern that
> it lets an attacker with a lot of known pairs recover the key so they can
> then deanonymize all the pairs.
>
> - Non-invertable (current proposal is truncate32(AES128(32_bit_address,
> 128_bit_random_key))) causes collisions, but those collisions only affect
> researchers looking over a dataset who are trying to determine why party X
> sent a particular stream of messages. When there are collisions, two
> parties' streams get merged; however, with mix-and-truncate, there the
> attacker cannot determine the key from lots of known pairs.
>
> There is a difficult balance: the party anonymizing the data has a much
> higher cost if the data is deanonymized than the benefit that is going to
> the party reading the data. One safe way to anonymize the addresses is to
> set them all to 0.0.0.0, but that makes them useless to the readers. The
> question is how far beyond that simple safe mechanism the anonymizing party
> should go, and at what cost. That's not a question that can be handled in
> CFRG (and it's not clear we will handle it well in the DNS operators fora).
>

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 24 Feb 2018 16:00:53 +0000

On Feb 24, 2018, at 7:42 AM, Jean-Philippe Aumasson <[email-masked]> wrote:
> 
> A “non-invertible” construction based on truncated AES will yield many collisions if format-preserving (hashing to a 32-bit space), and it’ll likely become partially invertible with sufficiently many known in-out pairs.

OK, then apologize for my ignorance. In truncate32(AES128(padded_32_bit_address, 128_bit_random_key)), are you saying that an attacker with lots of pairs can determine the key faster than if it was just AES128(padded_32_bit_address, 128_bit_random_key)?

--Paul Hoffman

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Sat, 24 Feb 2018 16:15:13 +0000

Sorry wasn't clear :)

I meant that, given the relatively small search space, collecting
input–output pairs and storing them in the table will allow an attack to
invert the mapping without knowing the key, if they can collect many such
pairs. For example, in an enterprise network the number of distinct IPs
observed is typically much less than 2^32.

On Sat, Feb 24, 2018 at 5:00 PM Paul Hoffman <[email-masked]> wrote:

> OK, then apologize for my ignorance. In
> truncate32(AES128(padded_32_bit_address, 128_bit_random_key)), are you
> saying that an attacker with lots of pairs can determine the key faster
> than if it was just AES128(padded_32_bit_address, 128_bit_random_key)?
>
> --Paul Hoffman

---

From: Tim Hollebeek <[email-masked]>
Date: Tue, 27 Feb 2018 19:37:42 +0000

Why use a low security toy cipher, when there are high security FPE algorithms available, which provide full strength and are reasonably efficient?  A number of them are being standardized as part of the work by ANSI ASC X9F1.

In particular, output sizes that are 2^n lead to very efficient implementations of most FPE algorithms.  They’re basically just Feistel structures over 32-bit blocks, using AES or something similar as the round function.

-Tim

From: Cfrg [mailto:[email-masked]] On Behalf Of Jean-Philippe Aumasson
Sent: Wednesday, February 21, 2018 11:55 PM
To: Paul Hoffman <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cfrg] Analysis of ipcrypt?

Hi!

I designed ipcrypt as a low-security toy cipher to encrypt IPv4 addresses for some log analysis application. It may be good enough for this purpose, however it has very low security:

* because of 32-bit blocks, a chosen-plaintext codebook attack will work in time 2^32 (or much less for specific IP ranges)

* known-plaintext codebook attacks will work similarly but in O(n log n), or 2^37 (coupon collector problem)

* there is a generic ~2^16 distinguisher that works by looking for a collision in a sequence of blocks

* worse, Jason just found a high-probability differential that seems detectable with fewer than 2^24 chosen-plaintext pair, and which may speed up key recovery

On Thu, 22 Feb 2018 at 03:03, Paul Hoffman <[email-masked] <mailto:[email-masked]> > wrote:

--Paul Hoffman_______________________________________________
Cfrg mailing list
[email-masked] <mailto:[email-masked]> 
https://www.irtf.org/mailman/listinfo/cfrg