January 06, 2017

Real World Crypto 2017

Nothing beats a cold bottle of Duvel. Except, maybe, three days chock full of real world crypto in NYC. Lucky for me, I’m sitting in EWR sipping on that beer and editing my notes taken from such an occasion. I’m talking, of course, about Real World Crypto 2017. This was the first year I attended the conference and it did not disappoint. There were talks on a variety of topics, including TLS attacks and engineering, end-to-end encryption and messaging, isogeny-based elliptic curve crypto, post-quantum cryptography and quantum computing, embedded crypto protocol frameworks, enhancements to fundamental protocols in used today (e.g., DNS and NTP), and secure multi-party computation. And that’s only naming a few. In an effort to capture my experience at the conference, I took notes on as many talks as possible. These notes are below as well as on Github. I tried to include pointers to relevant papers and source code repositories when available.

One thing is clear: if my reading list wasn’t backed up enough due to the holidays, it’s now overflowing with new material to read and review. So, at least for me, RWC will have an impact long even after the closing ceremony.

Alright, enough with the babbling. Here are the notes. By the way, if any talk particularly piqueues your interest, I highly recommend you check out the recorded videos made available online. Enjoy.

Session 1: TLS Engineering

Software engineering and OpenSSL is not an oxymoron

  • Post-Heartbleed: more sponsors and F2F developer meetings
  • Increased focus on testing (up to 57% coverage), regular (and planned) releases, and increased transparency
  • Removed dozens of outdated platforms and trimmed dead or unneeded code
  • Closed old bugs and asked originators to reopen them on Github if they’re still relevant
  • TLS 1.3 fixed delivery date in Q1 2017

Project Wycheproof - Scaling crypto testing

  • Google depends (partly) on third party crypto libraries (OpenSSL, OpenJDK, Bouncy Castle, etc.) [?]
    • APIS (AEAD, MAC, PKE, DS) are build on these libraries
  • Motivation: need common framework for testing third party libraries for known bugs
  • Wycheproof:
    • 80+ unit tests
    • Out-of-box runners for libraries
  • Notable bugs discovered: key recovery in OpenJDK’s DSA and Bouncy Castle’s ECDHC
  • Common crypto interfaces for C++, Python, Go, Javascript, Java, etc. are desperately needed
  • Sensible interfaces are also needed:
    • Allow effortless switching algorithms adhering to the same interface
    • Show crypto properties in the code [?]
    • Never ask user to provide critical input

X.509 in Practice (It’s worse than you think)

  • TLS phishing is on the rise, but still rather small (in the 100s per day [?])
  • Certificate sharing (across banks) is still prevalent – what happens when keys need to change (see Heartbleed)?
    • Some banks just had their certificates, with the same key, re-signed
  • Poor certificate algorithms (MD5 and SHA1), keys (RSA 1024 bits), versions (< V3), etc. are still problematic
  • Downgrading happened without switching of certificate providers – so why did the downgrades occur in reaction to Heartbleed et al?

Is Crypto Software Safe Yet?

(Review of some attacks in go-jose and Bouncy Castle)

##Session 2: Crypto for Internet Protocols

NSEC5: Provably Preventing DNSSEC Zone Enumerationasd

  • Relevant links:
    • http://www.cs.bu.edu/~goldbe/papers/nsec5.pdf
    • http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6924218
  • Offline zone enumeration requires online crypto
  • NSEC: sign the gaps
  • NSEC3: hash domains and sign the gaps offline
  • NSEC3-WL: hash domains, sign the gaps online
  • NSEC5 = NSEC3-WL with a VRF instead of standard H (hash function)
    • A VRF is a publicly keyed hash function – compute with a secret key and verify with a public key
    • VRF proofs must be provided with the NSEC5 records
  • Replay attacks are not possible since the signature and VRF proof are computed based on the query (must include a nonce?)
  • Preventing replays of pre-NSEC5 records is not possible beyond standard TTL and NSEC record lifetime enforcement

Cryptographically Securing the Network Time Protocol

  • Relevant references:
    • https://tools.ietf.org/html/draft-ietf-ntp-network-time-security-15
    • https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_dowling.pdf
    • https://tools.ietf.org/html/draft-dfranke-ntp-data-minimization-01
    • https://roughtime.googlesource.com/roughtime
    • https://github.com/dfoxfranke/nts
  • (NTP overview)
  • Symmetric authenticaton (for NTP) uses prefix-key MD5 (MD5(K   M)) – length extension attacks not really a concern
  • NTP servers have an exceptionally large number of clients
    • Stateless query processing is a must
  • NTS approach: use (D)TLS to create a session, export keys, and use them to AEAD-encrypt request and response
  • Some properties of TLS are problematic from a privacy perspective (tickets, e.g.), but that will be addressed with TLS 1.3

##Session 3: Quantum and Post-Quantum

The physics of building a quantum computer

  • (quantum computing overview)
  • Google’s using superconductors to build Qbits
  • [see slides]

NIST’s Post-Quantum Cryptography Project

  • Relevant links:
    • http://csrc.nist.gov/groups/ST/post-quantum-crypto/
  • Full transition to PQC may take > 10 years
  • Current outlook:
    • Speed looks good
    • Key sizes may increases (significantly)
    • Signature sizes can be large
    • Possible increase in ciphertext sizes
    • industry impact assessment must be done now

Cryptographic Suite for Algebraic Lattices — CRYSTAL


##Session 4: Post-Quantum Crypto

Practical post-quantum key exchange from both ideal and generic lattices

  • Relevant papers and links:    - NTRU, Regev ‘05 (LWE assumption), etc. [see the slides]
    • https://eprint.iacr.org/2016/659.pdf
    • https://openquantumsafe.org/
    • https://eprint.iacr.org/2016/1017.pdf
    • https://github.com/lwe-frodo
  • PQC breaks standard KEX protocols and requires longer key and digest sizes for symmetric encryption and hashing, respectively
    • Relevant to TLS, since KEX breakage gives an attacker the ability to decrypt logged traffic
  • Frodo is based on LWE security
    • Matrices are random
  • New Hope is based on Ring-LWE
    • Ring-LWE saves computation since each row in the matrix is a cyclic shift of the one above
    • Matrices are cyclic
    • S -> C: AX + E    - C -> S: YA + E*
      • shared secret is derived from the MSBs of (YAX + YE)
      • A is generated randomly (from PRG), X,E are sampled from Gaussian noise with paramter \sigma
  • Matrix generation can be done at random, which is different from parameter generation for DH-like KEXs where the group structure matters (i.e., we must use safe primes)
  • KEX is parametered by (coefficient) modulus q, (matrix) dimension n, and the distribution for small matrices
  • Recommended parameters:    - Frodo: q = 2^15, n = 752, table distribution => quantum security: 130 bits
    • NewHope: q = 12289, n = 1024, binominal distribution => quantum security: 255 bits
  • Network complexity:
    • Frodo: ~22 KiB
    • NewHope: ~4 KiB
  • Processing complexity:
    • Frodo: 1.4ms
    • NewHope: 0.2ms

Supersingular Isogeny Diffie-Hellman

  • Some ECC benefits:
    • Factoring and primality proving
    • Small and fast KEX
    • Digital signatures
    • Pairings: ID-based crypto, proxy re-encryption, etc.
  • (did not easily follow the rest)

##Session 5: Embedded Crypto

The Strobe protocol framework

  • Relevant links:
    • https://moderncrypto.org/mail-archive/noise/2015/000220.html
    • https://strobe.sourceforge.io/
    • https://strobe.sourceforge.io/papers/strobe-latest.pdf
  • Protocol framework with embedded focus: simple protocols and handshakes, e.g., encrypt, MAC, hash, sign, etc.
  • Goals: simple and easy to analyze, non-terrible performance
  • Use: when best practices (TLS and IPsec) don’t work due to diverse reqiuirements:
    • public key encryption and auth. algorithms
    • different or odd message flow
    • code size and memory requirements
      • these all tend to yield custom protocols!
  • Modern solution (for auth.): hash everything (input to protocol, e.g. messages sent and received)
    • TLS 1.3, Noise, BLINKER, etc.
  • STROBE sits in the middle and “hashes all the things” -> goal is to make the output look like a RO
  • Can use it to build FHMQV-C
  • Operations: key, AD, PRF, send clear, rcv clear, send enc, recv enc, send MAC, verify MAC, rachet [see slides for flow]
  • Implementation is based on duplex sponge operation
    • state is divided into a rate and capacity    - rate is XOR’d with inputs for operations
    • capacity is kept separate (internal) as stream-cipher-like key material for the operations
  • RO behavior: input is all previous operations, including the operation type and data, as well as the intended use of the output
  • Duplex sponge gives RO behavior, but does not yield parsability. Metadata operations are used to disambiguate outputs:
    • Metadata AD/CLR/ENC before each operation
    • Can be (tag, length) of protocol framing
  • Future work: implement existing protocols using Strobe

FourQ based cryptography for high performance and low power applications

  • Relevant links:
    • https://tools.ietf.org/html/draft-ladd-cfrg-4q-00
    • https://www.microsoft.com/en-us/research/project/fourqlib/
  • Curve25519 and Ed448-Goldilocks were selected as CFRG-approved curves
  • FourQ is a newer variant that builds on improvements in the literature
  • Performance: speedup ratio ranging from 2.4-2.9x compared to Curve25519 on varying platforms
  • Some properties:
    • Fastest ECC addition laws which are complete on the curve
  • SchnorrQ is the signature variant of FourQ
    • i.e., closely follows the EdDSA spec, but uses FourQ
  • [read the paper(s) for more details]

##Session 6: MPC

High-Throughput Secure 3PC for Semi-Honest and Malicious Adversaries - Breaking the Billion-Gate per Second Barrier

  • Primary metrics for MPC are latency and throughput
    • Low latency: garbled circuits are standard since they have a small number of rounds, but the circuits are large
    • High throughput: the secret-sharing approach is standard since it has low bandwidth and simple computations
  • “Protocols for malicious security are orders of magnitude more expensive than those for semi-honest security”
  • Contribution: design secure against semi-honest adv that requires only 1 bit per AND gate (and XORs are free)
    • e.g., with a three-server cluster of servers with 20 cores each, connected over a 10 Gbps LAN, a total of 7B AND gates (=1.3 million AES operations) can be computed per second
  • Adapted a Kerberos implementation to use MPC to split credentials
    • Results: single-core = 3k logins per second, 20 cores = 41k logins per second
  • Malicious security preview: generate a huge number of multiplication triples and check them [no details given – see paper]
  • Performance:
    • exceeds 1.1B AND gates/second (215k AES operations/second) at high throughput design using the same cluster as above
    • offline/online variant: 2.1B AND gates/second
  • Design is fully parallelizable, so adding more servers leads to a linear increase in the throughput

Secure Multiparty Computation at Google

  • Semihonest model can be OK => bound behavior by contracts or other external means
  • In practice, cost is the primary factor, not speed
    • Computation clusters are shared by multiple applications, links suffer from contention, and network costs therefore increase
  • Challenges in practice:
    • Consumer devices can’t communicate directly
    • Consumer devices have different cost metrics (e.g., power consumption == battery life)
    • Consumer devices fail!
    • Consumer devices can be malicious (think the Sybil attack – https://www.freehaven.net/anonbib/cache/sybil.pdf)
    • Non-colluding service providers are not impossible (it has been done)
  • Prevention of clients maliciously inserting garbage in the aggregation step is dealt with by (a) acknowleding that it’s an open problem and (b) attempting to distinguish random garbage from the legitimate model (didn’t follow the latter one – OTP’d data is indistinguishable from random)

Privacy-Preserving Classification on Deep Neural Network

  • Relevant links:
    • https://www.microsoft.com/en-us/research/wp-content/uploads/2016/04/CryptonetsTechReport.pdf
  • Privacy-preserving classification:
    • Client gets output from neural network and the server gets nothing.
    • Assume that the server’s net is trained
  • Enabling technology: HE -> complexity (efficiency) is proportional to the number of non-linear layers times the multplicative depth of the non-linear layer [in the network]
  • Server privacy is not defined (the client is not disallowed to learn information from the server about the model) – is it a requirement?

##Session 7: Applications and Lawsuits

Challenges of E2E Encryption in Facebook Messenger [Jon Millican]

  • E2E requirements:
    • perfect forward secrecy
    • (consistent and) verifiable identities
    • account-based access control of messages
  • Translation:
    • consistent and verifiable identities
    • no message history on new devices
    • need for “fat clients” that can do crypto
    • account data is isolated in storage
  • Implementations today: WhatsApp, SIgnal, Viber, and soon Allo
    • All of which are indexed by phone numbers and have “static” endpoints
  • Messenger choices:
    • off-the-shelf crypto
    • single- or multi-device per thread [?]
    • single-device per account
    • end-to-end protocol: signal (double rachet)
    • abuse reporting via message franking => use onion HMAC to prove that the infrastructure sends messages between peers
      • server doesn’t see plaintext unless a message is explicitly reported
    • attachments:
      • data encrypted with AES-GCM using random key (k)
      • uploaded to FB to return ID i and authorization tag a
      • peers transfer (k, i, a) from messenger and retrieve data from FB
    • secure storage: FB-provided account key is used to derive: storage keys [private and thread storage keys], message data, and auth keys
      • not forward-secure?
  • Future work and challenges:
    • Desire accessible authentication without a trusted party, CA, etc. [missed some – see slides]
    • Multi-device management: how are devices enrolled and dis-enrolled, and under what circumstances does each happen? How are these operations trusted?
    • Usability

Memories for Your Eyes Only

  • Possible solutions for memory encryption:
    • PW-based key: too weak (dict. attacks)
    • 128-bit entropy key: no usability
    • Per-device key: no mobility
    • ..
  • Solution: password-protected secret sharing [give and take]
  • Give and take:
    • Give: user creates and gives key to the servers
    • Take: when opening MEO, user takes key from the servers
    • User contributes its pin in the “give and take”
  • GT Protocol #1:
    • U -> S: authenticates to S “first factor”
    • S -> U: gets short-term session cert., and a random nonce N (S remembers N)
    • U inserts P=PIN locally
    • U generates tokens ENC = H1(N, P), AUT = H2(N, P), where H1 and H2 are KDFs
    • U uses master key M to derive T1 = AES(ENC, M), T2 = AUT [is AUTH the authentication tag, or the KDF output from above?]
    • U -> KS: certifies self to KS: gives T1,T2 to KS
    • Secret Sharing: T1,T2 at KS, P at U, N at S
  • GT Protocol #2:
    • U -> S: authenticates to S
    • S -> U: nonce N, short-lived cert., and signed challenge (Ch, Sig(Ch))
    • U inserts P to re-generated ENC and AUT
    • U -> KS: cerifies self to KS, uses Resp = AES(T2 = AUT, Ch), to answer signed challenge, present (Ch, Sig(Ch), Resp)
    • SK checks session-cert, Sig(Ch), and that Resp is right
    • SK -> U: if correct, sends T1
    • U takes T1, and with key ENC decrypts key M
  • Security depends on key and nonce separation between S and KS
  • Summary: combines authentication, signing, secret sharing, PBKDF (H1 and H2)
  • Extensions: PIN and key changes (rotations) are possible, could explore Shamir-like secret sharing in the future
  • Concern: if S and KS collude, they can bruteforce the PIN.


  • US law says no one should use technology to get access to copyrighted material (e.g., dencrypt this material) without the approval of the copyright owner(s).
  • US law says no one can manufacture, import or provide to public traffic in technology-related devices or services.
  • Some people got in a lot of problems (e.g., jail time) for breaking DCMA.
  • Summary is available in a paper called “Unintended Consequences Report” (https://www.eff.org/deeplinks/2008/10/dmca-ten-years-unintended-consequences).
  • Exception: results can be presented with the intention to advance crypto systems, i.e., “solely for the purpose of good-faith security research.” This is valid till end of 2018.
  • Some concerns: this law contradicts with the first amendment. Why?
    • Code is speech.
    • DMCA 1201 restricts research and discussion of research.
    • Circumvention is a “necessary predicate” to speech.
    • DMCA 1201 bans far more speech than necessary because it’s not tie to illegal behavior.
  • DCMA 1201 doesn’t accommodate fair use and is overboard.

Lightning Talks

  • https://www.coreinfrastructure.org/ for funding of open-source projects.

##Session 8: Key Exchange and Secure Messaging Protocols

Message Encryption

  • Relevant links:
    • https://whispersystems.org/docs/specifications/xeddsa/
    • https://whispersystems.org/docs/specifications/x3dh/
    • https://whispersystems.org/docs/specifications/doubleratchet/
  • (Overview of crypto for message encryption from early 20th century to now)
  • A variety of approaches to securely serve keys: trusted directories, transparent key servers (CONIKS), OOB “secret tokens” (key IDs), etc.
  • Encryption, not authentication, is now the new base model for messaging systems
    • “this model reflects the world changing” - Trevor
    • encryption should be the foundation for systems with authentication built on top
  • AtE vs EtA (examples):
    • Military vs consumer (general population)
    • Single root of trust vs diverse trust
    • Symmetric crypto vs public key crypto
    • Radio vs servers
  • Modern protocols, e.g., OTR, Signal, TextSecure, use DH KEXs with racheting to move FS properties forward with time (i.e., as messages are sent and received)
  • Protocol stack:
    • 2-party -> multi-party -> multi-device
  • Question: what is the right security model for symmetric-key message encryption systems (sponge, HKDF interaction/mixing, …)?

A Formal Security Analysis of the Signal Messaging Protocol

  • Relevant links:
    • https://eprint.iacr.org/2016/1013.pdf
    • https://eprint.iacr.org/2016/221.pdf
    • https://eprint.iacr.org/2003/031.pdf
    • https://tools.ietf.org/html/rfc6189
  • Forward-secrecy: compromise does not harm secrecy of past events [TLS 1.3]
    • Adv must compromise long-term keys and be an active MitM attacker
  • Post-compromise security (PCS): compromise does not harm secrecy of future events [Signal?]
    • This is only possible if there is some shared state
    • State is used to “recover” from the compromise
    • Adv must compromise long-term secrets, immediately attack, and the continue attacking to maintain access
  • Signal security model:
    • Adv has full network control
    • PFS
    • Key compromise impersonation attacks
    • Some (but not all) random numbers can be compromised
    • PCS
  • Question: Does ZRTP enable or provide ZRTP (https://tools.ietf.org/html/rfc6189#section-15.1)

0-RTT Key Exchange with Full Forward Secrecy

  • Relevant links:
    • puncturable FS
    • forward secure PKE
  • Problems with 0-RTT KEX:
    • Replay attacks (!)
    • No forward secrecy
  • Main idea: Puncutrable forward-secret encryption yields forward secret 0-RTT KEX
  • Building block: puncturable forward-secrecy key encapsulation (PFSKEM)
  • From a PFSKEM, build a 0-RTT KEX
  • General idea:
    • PKE encrypt from Alice to Bob
    • Bob decrypts and then punctures the secret key for the given ciphertext
    • Secret keys advance using FS PKE tree scheme
  • Properties: forward secure with replay attack prevention
  • DoS: can adv force ciphertext puncturing? No, since puncturing ciphertexts only happens after a successful decryption
  • Q: how would this work with distributed servers that don’t have shared state? (TLS tickets solve this problem) load balancing could be done by partitioning the ciphertext space and using that to direct to servers
    • this is not so great for geographically distributed servers

Towards 5G Authenticated Key-Exchange: the security and privacy of the AKA Protocol

  • AKA and 3G/4G networks:
    • Communication as a service for mobile users
    • Service probided by servers
  • AKA protocol: 3-party protocol in which the server acts as proxy between the client and operator
  • Q: how can authentication work without client secrets?
    • Server used as a proxy and does only identity management
  • Protocol structure
    • C-S: perform authentication
    • S-O: fetch authentication vectors
    • C-S: challenge-response for each auth. vector
    • C-S: TMSI re-allocation [does this fix the privacy problem?]
  • Q: is AKA appropriate for 5G networks? No…

##Session 9: Passwords and Authentication

Is Password InSecurity Inevitable? Cryptographic Enhancements to Password Protocols

  • Relevant links:
    • http://webee.technion.ac.il/~hugo/rwc17.html
    • https://www.leakedsource.com/
    • https://pdfs.semanticscholar.org/447e/3968f7547fb3d6506fb063d591a111608f91.pdf
    • http://eprint.iacr.org/2016/144.pdf
  • Building block: oblivious PRF
  • Motivation: Offline attacks upon server compromise are unavoidable
  • Goal: make unavoidable exhaustive attacks ineffective
  • Use password manager to remove human memory burden
    • Passwords are encrypted under a single master password
    • Leakage is reduced to the master password – hopefully this is high entropy and cannot be leaked (online?)
  • Dream password store:
    • All passwords kept in a password store in user’s device
    • User memorizes a single master PW
    • All passwords are independent and random [information theoretic randomness]
    • Leaking a password leaks nothjing of other passwords
      • Information stored in device is indepent of user’s
      • Ciphertext master password is never entered into the device
  • SPHINX: a password store that perfectly hides from itself (no exaggeration)
  • PRF-based solution:
    • rwd (random password) = PRK(K_d, pwd url) [pseudorandom]
      • Offline attacks are infeasible
    • K_d is a device key on user’s phone
      • Independent of master PWD and RWD’s
      • Learning K_d leaks nothing of the master pwd
    • pwd is entered into the device
      • Problem: this is in the clear in the system!
      • Solution: use an Oblivious PRF (OPRF)
  • Use OPRF with one-time key to encrypt PWD (master) from device to phone, and the phone sends the encrypted PRF value back
    • Client encrypts PWD and then decrypts the PRF value from the OPRF
    • PWD (master) hjidden over the wire and from the device (phone)
  • OPRF computation: OPRF(K_d, pwd) = (H(pwd))^{K_d}
  • Can work with any client-server password protocol
  • Security properties:
    • Device compromise: unconditional secure (online-only attack)
    • Network attacks: unconditional secure (due to OTP)
    • No PKI needed
    • Offline dictionary attacks: infeasible
  • Password-protected secret sharing (PPSS):
    • init: user secret shares a secret among n servers; forgest secret and keeps a single password
    • retreival: user contacts (t + 1) servers, authenticates using the single password, and reconstructs the secret
    • adv: breaking into t servers yields nothing about secret or password
  • [see references for the efficient PPSS construction and the Single-Server PAKE protocol]

Towards a Theory of Data-Independent Memory Hard Functions

  • scrypt is not data independent and therefore may be vulnerable to SCAs (e.g., cache timing)
  • MHFs should therefore not depend on the secret input
  • pebbling arguments help show memory hardness
    • put a pebble on a node when it’s in memory
    • remove a pebble when it must be dropped from memory
    • can only pebble a node if it’s inputs are in memory
  • Claim: space-time complexity is not appropriate for password hashing
    • Reason: ST complexity can scale badly in the number of evaluations of a function, for parallel computations
    • Therefore we need the notion of cumulative complexity (sum of all pebbling steps as a function of time)
  • [see references for depth robustness and pebbling connection]

The memory-hardness of Scrypt

  • Relevant links:
    • https://tools.ietf.org/html/rfc7914
    • http://www.tarsnap.com/scrypt/scrypt.pdf
    • http://eprint.iacr.org/2016/989
  • [battery depleted; see slides for details]

Solving the Cloudflare CAPTCHA

  • Relevant links:
    • https://github.com/cloudflare/challenge-bypass-specification/blob/master/captcha-bypass-internet-draft.txt
  • Cloudflare == value-added request routing
    • Tries to differentiate between real humans and bots
    • CAPTCHAs are served to disambiguate
  • Tor browsing obscures signals that indicate whether or not requests come from a human
    • All requests look indistinguishable – so what are some appropriate signals?
  • IP reputation (of exit nodes) matters most – traffic from exits get CAPTCHAs
  • Thus, Tor users get a lot of CAPTCHAs, and that’s terrible for usability
  • Solution: use blind signatures to generate “human-proof” tokens

##Session 10: Implementations

Security assessment of software security: A closer look at white-box cryptographic implementations

  • Relevant links:
    • http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7676183
    • http://tigress.cs.arizona.edu/img/eurocrypt-2016.pdf
    • http://eprint.iacr.org/2016/203.pdf
    • https://github.com/SideChannelMarvels/Tracer
  • Whitebox (r.e. software): adversary owns the device running the software (maybe it’s the user)
    • A system secure in this model is called a “whitebox implementation”
  • Goal: prevent key exfiltration from the owner or user
  • Historical use case == DRM, recent trend: host card emulation (HCE) to communicate using NFC
    • Protection of the secret key is done with a white-box implementation
  • Why not use normal crypto software code?
    • Entropy attacks (scanning memory for high entropy bits)
    • S-box blanking attacks (see slides)
  • Theoretical whitebox implementation is possible => one big lookup table [that includes the key] (2^{92} TB storage)
    • Networks of tables can be used to reduce the size
  • Differential correlation attacks (DCA, the software analog to DPA), is the automated attack that can be used on implementations
  • Software control flow trace should mask algorithm details (i.e., there should be no side channel leaks)
    • Visualizing traces can help distinguish algorithm details, e.g., 9+1 rounds for AES
    • Unrolling and other techniques to unify the implementation help
  • Existing WB encodings (see slides) do adequately hide correlations
  • Open question: how does WB crypto empower or protect the user (hint: it doesn’t)?

Erasing secrets from RAM

  • Relevant links:
    • https://github.com/lmrs2/secretgrind
    • https://www.cl.cam.ac.uk/~lmrs2/
  • Primary concern: compiler optimizations removing seemingly unnecessary code, e.g., memset(buffer, 0, sizeof(buffer))
  • Approach: use static and dynamic code analysis
  • Some results:
    • IO API caching optimizations can cause memory to not be cleared
      • e.g., reading from a PEM file and then zeroing the buffer won’t erase the memory -> it may still be cached by the API [?]
    • Formatting functions prone to leaving copies of sensitive data on the stack
    • Recursive functions prone to leaving residual sensitive data on the stack
    • [see slides for more examples]
  • Modified LLVM compiler to automaitcally erase used stack and registers upon returning from functions annotated by developers as sensitive
  • Implemented new versions for key functions, e.g., memset

##Session 11: TPMs and Chips

Direct Anonymous Attestation and TPM 2.0: Getting Provably-Secure Crypto into the Real-World

  • Standard certificates for remote attestation make them linkable and reveal TMP’s IDs
  • Direct Anonymous Attestation (DAA): unforgeability, anonymity & unlinkability, non-frameability [12 years ago in ‘04]
  • DAA history:
    • Simulation-based definitions:
      • BCC04: no output signatures (verification was interactive), prohibits working with signatures in practice
      • CMS09: output signatures = random values, not realizible by any construction
      • CDL16a: current authors
    • Gmae-based definitions:
      • BCL09: trivially forgeable scheme, no property for non-frameability
      • BL10: extend BCL09 with non-frameability and sig-based recovation, same unforgeability flaw as BCL09
      • BFG+13: for pre-DAAA where TPM and host are one party, does not cover corruption
  • DAA overview:
    • TPM gets secret attestation key, which is blindly signed by issuer with membership credential
    • Provides NIZK proof to verifier that the key is signed
  • TPM 2.0 interface: create, hash, commit, sign
  • TPM 2.0 interfaces provide static DH oracle -> can be abused by corrupt host to simplify DL problem (128-bit security to 85-bit curve for 256-bit BN curve)
  • Approach: add bind function to set cleared points, which limits the points at which commit can be evaluated
  • Alternative: commit funciton accepts string from which point is derived (as opposed to directly accepting point), and remove the bind function
  • Problem: adding TPM commands is not trivial

DPA Resistance for Real People

  • Typical countermeasures: obfuscation, leak reduction, balanced HW/SW, dynamic differential logics, incorporate randomness, add amplitude and temporal noise, etc.
    • These assume that one can control the algorithm implemented
  • What about protocol level CM against DPA?
    • problem: protocols may allow attacked unlimited traces with a fixed key
    • solution: build protocols that survive this leakage
      • design crypto with realistic assumptions about the HW
      • hardware has to be fairly good, but assured to leak
      • … re-key often [using tree-based KDF]
  • Challenge and response: Given K_root, traverse tree using F0() and F1() [which are two OWFs with low bounded leakage implementations] to get the path to a leaf, and provide the response as (K_root, path)
    • No matter how many times the keytree is traversed, no key is involved in more than <height> operations
  • Use the key tree approach with two hashes H0 and H1 (instead of F0 and F1) for DPA-safe KDF
    • [see slides for the AE protocol based on the key trees]
  • TVLA: test-vector leakage assessment using statistical (Welch’s) t-tests

##Session 12: Searching on Encrypted Data

What Else is Revealed by Order-Revealing Encryption

  • Relevant links:
    • https://eprint.iacr.org/2016/786.pdf
  • ORE is a generalized version of OPE, which is an encryption scheme such that Enc(x) < Enc(y) if x < y
  • Contribution: attacks on multiple (correlated) columns that are ORE-protected
    • Possible to attack multiple columns even when an individual column is impossible to attack
    • Attacks on ORE-protected data that is not uniform
  • Chosen-plaintext attacks on ORE can reveal the original plaintext (via binary search)
  • Non-interactive ideal ORE is only possible by IO (indist. obfuscation) and multilinear maps
    • Interactive protocols can be used for the data
  • Leaky ORE: ORE + extra info revealed -> extra info obviously depends on the construction
    • Fast blockc ipher based constructions are possible
    • Extra info includes: some plaintext bits, statistics, etc.
  • Security: one-wayness notions for ORE are proved when the input data are random
  • General observation: correlation among columns leaks more information than what is revealed by a single column

Breaking Web Applications Built On Top of Encrypted Data

  • Proxy re-encryption can be used to translate encrypted search tokens from one “policy” to another
  • Types of threats: snapshot passive (weak) and persistent passive (continually eavesdropping), and active
  • Attacks on mylar do not use data access patterns or timing information – they use metadata about documents, clients, and access control relationships
    • Searches increasingly reveal plaintext
  • Recovering a search keyword token allows one to perform a dictionary attack to retrieve access to otherwise protected documents
  • Mylar reveals order of keywords in a document in addition to whether a document matches
  • OXT is a system that enables keyword search without PRE
  • User must necessarily see metadata to decide whether or not it should accept the share

Building web applications on top of encrypted data

  • Active attacker prevention:
    • No tampering with client
    • No tampering with data and query results
    • Hide metadata
    • Hide access patterns
    • Hide operations performed, timing, runtime, data size, structure, etc.
  • Actual systems: Mylar, Verena, and (soon) Opaque

Session 13: TLS Attacks

PRNG Failures and TLS Vulnerabilities in the Wild

  • Relevant links:
    • https://github.com/davidmcgrew/joy
  • Multisession memory requires a great deal of memory
    • PRNG should have a large set of states, but if it has a weak set of states, then collisions can be found by observing Sqrt(N) [birthday bound] states
  • Virtual machines: snapshot and clone for autoscaling
    • Volume snapshot: image of bootable disk, boot latency, not vulnerable
    • Full snapshot: image of RAM+disk, no boot latency, vulnerable!
      • … due to storing random seeds
  • TLS model [Time Random ClientKeyExchange]:
    • Entropy -> PRNG -> Nonce generator -> Random -> RSA/(EC)DH -> ClientKeyExchange
    • Clock -> Time
  • Full snapshot copies RAM, including PRNG state, which feeds nonce generation and RSA/(EC)DH
  • Crypto attacks:
    • Cut and paste attacks work in sessions with the same encryption/authentication keys
    • Private key recovery for (EC)DSA –> deterministic DSA looks even better
      • Or mix PRF(message) into entropy prior to signature
  • Passive network crypto visibility can help detect collisions – multisession monitoring is needed
  • Use a robust AEAD such as AES-GCM-SIV, otherwise it must be tested

Concerto: A Methodology Towards Reproducible Analyses of TLS Datasets

  • Relevant links:
    • https://github.com/ANSSI-FR/concerto
    • https://github.com/ANSSI-FR/parsifal
  • [presentation of data – see slides for details]

Productizing TLS Attacks: The Rupture API

  • Relevant links:
    • https://ruptureit.com/
    • https://github.com/dionyziz/rupture/
  • [description of BREACH and the Rupture attack framework]