The best cryptographic protocol ever!

Key exchanges

We recommend 2 safest algorithms

Matrix-based key exchange

Nowadays, it’s known that Diffie-Hellman (DH) key exchange is mathematically broken . To see how, let me describe the DH key exchange.

  1. Alice → Bob: xG
  2. Bob → Alice: yG
  3. The shared secret is y(xG)= xyG= x(yG).
  1. Alice → Bob: Ax
  2. Bob → Alice: yA
  • Quantum resistance matrix assumption (QRM): given matrix A and vector Ax, it’s impossible to compute x even with the help of quantum computers.
  • Theorem: Our matrix-based key exchange is safe against eavesdropping adversaries if QRM is true.
  • Proof: Only available in the extended version upon request.

Quantum key distribution (QKD)

QKD’s security doesn’t depend on the shaky ground of hard computational problems. Its security depends on quantum physics that no one understands, let alone breaks it. The core idea is that if the attacker (Eve) eavesdrops on the communication then both Alice and Bob can detect it based on the quantum measurement principle. Europe invested billions of dollars on QKD, so its security is guaranteed.

Digital signature

The drawback of the above key exchange protocols is that they’re unauthenticated. Therefore, we need a digital signature algorithm. Standard digital signatures such as ECDSA or Ed25519 are simple and not trendy, so we won’t use them.

  • Composition theorem: when we combine 2 safe protocols, the result is a safe protocol.

Quantum safe digital signature XMSS (eXtended Merkle Signature Scheme)

XMSS are standardized by both IETF and NIST, so its security is guaranteed. While XMSS is safe against quantum computers, it has a significant drawback. It’s stateful , i.e., it maintains state. No one likes states, so we will completely remove its state by keeping the secret key constant over time. This opens the door for distributed systems where sharing states is very difficult. By removing the state, we increase the speed by 128 times using 16 servers, each having 8 cores where parallelization is trivial.

BLS aggregate signatures

BLS signature is a pairing-based signature which uses the following beautiful property e(xP, yQ) = e(P, Q)^(xy). BLS aggregate signatures can combine millions of signatures into 1 short signature. Instead of keeping gigabytes of signatures, you can just store 1 single 48 byte aggregate signature. According to IRTF’s document, BLS signatures have no weaknesses. To add to the perfectness of BLS signatures, we will modify the pairing protocol to make it faster and constant-time. If we define e(P, Q) = 1 then e(P, Q)^(xy) = 1 for all x, y. Therefore, the pairing’s computation is super fast and constant-time.

Sign-sign algorithm

The sign-sign algorithm allows the combination of 2 signatures. It is simple yet elegant. To sign a message m, we first use XMSS to compute the signature y = XMSS(m). We then treat y as the input of BLS signature, i.e., we compute BLS(y). In summary, the signature is simply BLS(XMSS(m)). This algorithm is safe against quantum computers because XMSS is safe against quantum computers and it’s aggregable because BLS signatures are aggregable.

Transparent key server

Cryptographers often don’t discuss the important topic of key servers. We will avoid that mistake by specifying concrete key servers’ architecture. Google has a project called key transparency, but it’s not popular because it’s not transparent enough. We will define a fully transparent key management system. In fact, we will propose 2 key management systems.

RESTless key server

Our key server works all the time, it never stops and that’s why it’s called a restless server. It supports GET requests where everyone can retrieve the public keys and it supports POST requests where anyone can submit their public keys to the server. Therefore, this server is open, transparent and safe.

Blockchain-based key server

While the above RESTless server is awesome, it’s not safe against denial of service attack and censorship. We want a key server for everyone in the world, independent of geographic locations. Therefore, we propose using the block chain to store our public keys.

Side-channel protection

Standard cryptographic protocols don’t deal with key leakage problems and hence cause countless vulnerabilities. We propose 2 main enhancements.

Using leakage-resilient cryptography

Leakage-resilient cryptography is safe against “smartass” attackers. “Smartass” attackers are attackers who compromise the victim’s system, and have the capability to read the whole secret key, but the attackers don’t care, the attackers only read half of the secret key and run away. Using novel leakage-resilient cryptographic protocols, we don’t have to worry about smartass attackers anymore.

Constant-time signature verification

One of the forgotten problems in cryptography is constant-time signature verification. Traditional cryptography only cares about constant-time signing which leads to vulnerabilities in verification. Using our novel constant time mapping above, we can achieve this goal easily.

Compress-encrypt-compress algorithm

Cryptographers often don’t specify compression which causes significant bandwidth loss. We propose enhanced compression by compressing both the data and the ciphertext, i.e., to encrypt plaintext m, we do the following: compress(encrypt(compress(m))). This saves bandwidth and is super safe.

Record encryption

To encrypt a message, we will break the message into small 16Kb packets and encrypt each packet independently. This packet level’s stateless encryption is an enhancement over slow and cumbersome stateful encryption.

Replay attack protection

To avoid replay attack, we use Galois Counter Mode (GCM) encryption where the counter starts at 0. Both sides will keep increasing the counter and hence if the attacker replays the old packet with the old counter, we can detect it. We understand the expensiveness of key exchange, so when we resume a lost connection, we reuse the shared key, but reset the counter to 0.

Random number generator

Random number generator is crucial to security and hence we propose 2 enhancements.

Optimized modulo operation

Typically, the OS only allows us to generate random bytes. However, in practice, we need to generate a number in a specific range (0, x). By using optimized modulo operation (%), we can generate a random number in a range really fast by randomizing 8k bits and then % x.

Rejection sampling algorithm

Not all numbers are the same. For instance, 0 and 1 are guessable. Therefore we have a ban list of bad numbers and if the random number generators accidentally generates them, we will reject them.

Patent issue

I filed patents to protect intellectual property of my best cryptographic protocol. You can enjoy it, but you can’t use it in production without my explicit permission.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Quan Thoi Minh Nguyen

Quan Thoi Minh Nguyen

Senior security engineer. Formerly @Snap, @Google. Black Hat Speaker USA 2021, ASIA 2022. Personal account. https://github.com/cryptosubtlety