Subject: [Cfrg] Big-key cryptography

From: Aaron Zauner <[email-masked]>
Date: Mon, 07 Dec 2015 01:27:44 +0100

Hi,

People that have read Rogaway's recent IACR Distinguished Lecture [0]
might have noticed (besides an amazing essay on crypto, ethics and
politics of course) that there's new work mentioned on something they
call 'Big-key cryptography'. Let me quote Verbatim:

```
Suppose you have a bigkey K. You want to use it for some protocol P that
has been designed to use a conventional-length key K. So choose a random
value R (maybe 256 bits) and hash it to get some number p of probes into
the bigkey:

i_1 = H(R, 1) i_2 = H(R, 2) ... i_p = H(R, p) .

Each probe i_j points into K: it’s a number between 1 and |K|. So you
grab the p bits at those locations and hash them, along with R, to get a
derived key K:

K = H'(R, K[i_1], . . . , K[i_p]) = XKEY(K, R) .

Where you would otherwise have used the protocol P with a shared key K,
you will now use P with a shared bigkey K, a freshly chosen R, this
determining the conventional key K = XKEY(K, R).

We show that derived-key K is indistinguishable from a uniformly random
key K0 even if the adversary gets R and can learn lots of information
about the bigkey K. The result is quantitative, measuring how good the
derived key is as a function of the length of the bigkey, the number of
bits leaked from it, the number of probes p, the length of R, and the
number of random-oracle calls.

[...]

I think that the subkey prediction problem, and the key-encapsulation
algorithm based on it, will give rise to nice means for
exfiltration-resistant authenticated-encryption and pseudorandom
generators. In general, I see bigkey cryptography as one tool that
cryptographers can contribute to make mass surveillance harder.
```

This seems to be a yet unpublished manuscript but I can think of quite a
few instances where this approach might come in handy for keys used in
various high-confidentiality protocols. What does CFRG think?

Thanks,
Aaron

[0] - http://web.cs.ucdavis.edu/~rogaway/papers/moral-fn.pdf p. 31-32

---

From: Dan Brown <[email-masked]>
Date: Mon, 7 Dec 2015 00:57:53 +0000

it looks interesting, but am so far having trouble with the threat model and actual proposal, though maybe others understood better than I did:

how realistic is this exfiltration adversary that the scheme aims to protect against? eg why not exfiltrate an inbox instead? if R is published, why not exfiltrate the p bits needed?

is there a bigkey per each pair of users, and how is it established? with small-key public keys?

  Original Message
From: Aaron Zauner
Sent: Sunday, December 6, 2015 7:28 PM
To: [email-masked]'
Subject: [Cfrg] Big-key cryptography

Hi,

```

[...]

Thanks,
Aaron

---

From: Natanael <[email-masked]>
Date: Mon, 7 Dec 2015 01:58:25 +0100

> various high-confidentiality protocols. What does CFRG think?

Looks like security-by-obesity extended from protected data using
all-or-nothing transforms to key material. I've seen similar methods
discussed before, but it is nice to see an actual proof for it when used
with key material.

And why not put this key material onto intentionally low-bandwith devices?
Like say putting some really big disk array holding your key material in a
well protected box, with the only external interface being an Arduino (or
maybe something tamper proof?) or similar very simple hardware? Could even
up the security against physical attacks by making it an m-of-n scheme with
multiple boxes physically spread out. Your only plausible attacks on it
would be outright theft or planting backdoors in the control / interface
chip.

http://ethanheilman.tumblr.com/post/28481738192/security-through-obesity
Discussion of that above link:
https://www.reddit.com/r/netsec/comments/xi587/a_look_at_securitythroughobesity/
https://stelfox.net/blog/2012/08/security-through-obesity/
https://www.reddit.com/r/netsec/comments/13mrle/new_developments_in_password_hashing_romporthard/

If you don't trust any HSM and need to generate shared key material between
two locations, this is one way to make your own.

---

From: Alexandre Anzala-Yamajako <[email-masked]>
Date: Mon, 7 Dec 2015 03:21:39 +0100

Isn't that a instance of cryptography in the Bounded Retrieval Model as
described by Alwen et al. in http://cims.nyu.edu/~wichs/BRMSurvey.pdf ?

---

From: Paul Grubbs <[email-masked]>
Date: Mon, 7 Dec 2015 10:28:41 -0800

Yes, Rogaway explicitly cites the BRM. He points out, though, that this may
be its most practical application thus far.

On Sun, Dec 6, 2015 at 6:21 PM, Alexandre Anzala-Yamajako <
[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Aaron Zauner <[email-masked]>
Date: Mon, 07 Dec 2015 23:40:43 +0100

Hi,

> how realistic is this exfiltration adversary that the scheme aims to protect against? eg why not exfiltrate an inbox instead? if R is published, why not exfiltrate the p bits needed?

Well, it depends on the setting of the protocol and actual setup of the
infrastructure, I guess. So that's a bit less academic. An example would
be an adversary that might have had point-in-time access to specific
infrastructure or might want to decrypt already stored communication
protected by the big key. Now extracting the key becomes the actual
problem It also depends on the levels of indirection in the protocol
and/or set-up.

What we've seen from the Snowden documents suggests that NSA isn't doing
a lot of real-world cryptanalysis (as in attacking specific ciphers and
crypto-schemes), they're stealing static keys from unencrypted sys-admin
e-mails, Telnet sessions, via server or client break-ins or the like.

Another message mentions how this could be used instead of HSMs, I've
had exactly the same idea when I've first read this text. But that's
just one useful instance.

> is there a bigkey per each pair of users, and how is it established? with small-key public keys?

It does not say. I've had similar thoughts though I'd rather have
someone with proper academic background in cryptography commenting -- or
better working/writing -- on this than myself (I'm just here to do the
plumbing).

Aaron

---

From: Dan Brown <[email-masked]>
Date: Tue, 8 Dec 2015 14:22:20 +0000

> -----Original Message-----
> From: Aaron Zauner [mailto:[email-masked]]
> 
> Dan Brown wrote:
> > it looks interesting, but am so far having trouble with the threat model
and
> > actual proposal, though maybe others understood better than I did:
> >
> > how realistic is this exfiltration adversary that the scheme aims to
protect
> > against? eg why not exfiltrate an inbox instead? ...
> 
> What we've seen from the Snowden documents suggests that 
perhaps exfiltrating large amounts of content data (e.g. said documents,
iow, said inbox) is just as realistic?

---

From: Aaron Zauner <[email-masked]>
Date: Tue, 08 Dec 2015 18:56:59 +0100

Hi Dan,

> iow, said inbox) is just as realistic?

Sure it is. Especially if you do it over a long period of time with low
bandwidth and the operator has no real monitoring in place. As an
engineer and operator I can tell you that in a 'properly' secured set-up
large data-exfil usually shows up on some form of detection mechanism.
But these exfiltrations are not nation state attackers but your average
cyber-criminal or script-kiddie and an adversary with the appropriate
amount of man-power and knowledge will certainly figure out some way to
do it if the environment allows for it:

There're very few organizations on the planet that have the capability
to preemptively collect this kind of data. I've been in and out of the
HPC business and been doing server deployments at scale for years now
and I can tell you that building appropriate data-centers, (near-time)
online storage facilities et cetera costs a *considerable* amount of
money and time. As does weaponized 0-day development. Every step we take
that makes decrypting already collected intelligence more difficult is a
good step as it increases the signal to noise ratio for these
organizations. And every step we take that causes more difficulty in key
extraction than just owning unpatched, unmonitored servers and clients
on the Internet or reading unencrypted e-mail from operators is also
good. It might cost us a bit of (cheap) disk space but them significant
monetary investment to take over infrastructure and exfiltrate data. And
then there's the possibility of detection, which they really do not
like. I think this is a good thing, others might disagree. It's not that
hard to figure out a way in which data-exfiltration will be detectable
from e.g. a 'big-key server'. How do you extract a multi-terabyte key
from highly monitored devices on a low-bandwidth connection? The chances
of detection increase significantly here as it not only takes longer to
extract but traffic flows might be visible to network security
operations in different places.

Aaron

---

From: Aaron Zauner <[email-masked]>
Date: Thu, 17 Dec 2015 21:13:08 +0100

Hi,

FYI: There's now also a recording available of Rogaway's lecture, in
which he also explains the threat model and philosophical background on
Big Key Cryptography and other anti-surveillance research that this
community should focus on (I think we're doing good work here in CFRG):
https://soundcloud.com/getur0/moral-crypto-asiacrypt

Aaron