Real World Crypto 2021 - Session 12: Crypto for the Cloud


Prev | Up | Next

Session video

Kenny Patterson (ETH Zurich) / SWiSSSE: System-Wide Security for Searchable Symmetric Encryption / paper video slides

There’s a github repo

Searchable Encryption: how do you permit keyword searching over a corpus of encrypted documents?

Symmetric: they’re only allowing use of symmetric techniques, for efficiency.

Server might have a search index, a keyvalue store, where PRF(search keyword)->Enc(matching doc ids). All value entries have same size to avoid attacks like freq analysis, so all doc id lists are padded to max size. Client makes search, gets back enc doc IDs, then goes and requests docs by enc id.

The system security is good at hiding keywords used in search in part one (hitting seach index) but breaks down if someone can analyse traffic in requesting docs by enc docid, as frequency analysis is possible there.

SWiSSSE is designed to prevent that kind of leakage. It addresses the second freq analysis attack by padding stores out with fake keywords, fake documents, and mixing up of server’s data returned in various reads. Clients maintain a stash that is used to mix things up over time and write back to the server (didn’t quite get this part).

The more you want to reduce leakage, the more padding must approach worst-case, and that consumes many resources

Their reference impl server uses Redis. PRF = HMAC-SHA256 and Enc = AES-GCM

Sophie Schmieg (Google ISE-Crypto) / What’s In A Key? In Band Key Negotiation and How To Avoid It / paper video

(Unfortunately the audio in this talk had a really bad echo).

How many days since a jwt alg none vulnerability?

In JWT, the ‘alg’ field, can be (legitimately) set to ‘none’. The problem isn’t this so much as that there is an ‘alg’ field at all!

This allows someone to switch ‘alg’ to a symmetric scheme, after which if a client provides their public key it’d be misinterpreted as symmetric key material. Then anyone could mint a valid token without a problem. The key ID ‘kid’ field can be similarly attacked - switch out a real key for one the attacker controls.

These sorts of issues are seen elsewhere, not just JWT. It’s a result of attaching to the ciphertext metadata that dictates what’s needed to authenticate and decrypt.
Similar vuln was found in AWS S3 Client-Side Encryption library (CVE-2020-9812)

Tink Keys: In Google’s Tink API they’ve ensured these sorts of vulnerabilities are avoided. The metadata is embedded into the key itself. Key rotation is supported via keysets. You can tell a Google product that uses Tink as keys are expressed in B64 and it’s always start with ‘A’ (this is 01, from the key format’s leading version field). There follows the key ID to identify the key to be used in the keyset.


  1. never trust the ciphertext!
  2. ensure key metadata is part of the key itself - i.e. algo type, algo’s required params
  3. key IDs can’t be authenticated as they must be attached to a ciphertext, so key IDs should only be meaningful within a keyset, and should be equally trusted.

Paul Grubbs (Uni Michigan) / Pancake: Frequency Smoothing for Encrypted Data Stores / paper video

Many apps are transitioning their data storage requirements to cloud-hosted data stores. Those data stores (e.g. AWS S3, ElastiCache) should not necessarily be trusted.

Apps may encrypt their key-value pairs for security

e.g. on medical data, indexed by patient condition - the cloud provider doesn’t know which patient or specifically which condition, but could obtain independently from medical literature the prevalence of conditions. Then with frequency analysis of the data accesses made, work out which PRF(K) is which medical condition. This has been seen in practice.

Existing solutions:

Pancake introduces a trusted proxy on client side, which smoothes the accesses being made by the client, so that access patterns to the server appear to be uniformly random. Trhoughput is 100x higher than ORAM.

Possible approaches to smoothing:

Pancake is a mix of the two above.

Challenge is to ensure adversary can’t distinguish real and fake accesses by e.g. timing analysis.

They’ve achieved max 3x bandwidth and 2x storage overhead.