Category Archives: Cryptography

Black Hat 2023 Day 1

Posted on by
Reply
  1. Introduction (J. MOSS)

Jeff MOSS (Founder of DefCon and Black Hat) highlighted some points:

  • AI is about using predictions. 
  • AI brings new issues with Intellectual Properties.   He cited the example of Zoom™ that just decided that all our interactions could be used for their ML training.
  • Need for authentic data.

The current ML models are insecure, but people trust them.  Labs had LLMs available for many years but kept them.  With OpenAI going public, it started the race.

She presents trends for enterprise:

  • Enterprise’s answer to ChatGPT is Machine Learning as a Service (MLaaS).  But these services are not secure.
  • The next generation should be multi-modal models (using audio, image, video, text…).  More potent than monomodal ones such as LLMs.
  • Autonomous agent mixes the data collection of LLM and takes decisions and actions.  These models will need secure authorized access to enterprise data.  Unfortunately, their actions are non-deterministic.
  • Data security for training is critical.  It is even more challenging when using real-time data.

She pointed to an interesting paper about poisoning multi-modal data via image or sound.

Often, the power LED is more or less at the entry of the power supply circuit.  Thus, intensity is correlated to the consumption.

They recorded only the image of the LED to see the effect of the rolling shutter.  Thus, they increase the sampling rate on the LED with the same video frequency.  This is a clever, “cheap” trick.

To attack ECDSA, they used the Minerva attack (2020)

Conclusion: They turned timing attacks into a power attack.  The attacks need two conditions:

  1. The implementation must be prone to some side-channel timing attack.
  2. The target must have a power LED in a simple setting, such as a smart card reader, or USB speakers. 

Despite these limitations, it is clever.

Once more, users trust AI blindly.

The global environment is complex and extends further than ML code.

All traditional security issues are still present, such as dependency injection.

The current systems are not secure against adversarial examples.  They may not even present the same robustness of all data points.

Explainability is insufficient if it is not trustworthy.  Furthermore, the fairness and trustworthiness of the entity using the explanation are essential.

The Multi-Party Computation (MPC) Lindel17 specifies that all further interactions should be blocked when a finalized signature fails.  In other words, the wallet should be blocked.  They found a way to exfiltrate the part key if the wallet is not blocked (it was the case for several wallets)

In the case of GG18 and GG20, they gained the full key by zeroing the ZKP using the CRT (Chinese Remainder Theorem) and choosing a small factor prime.

Conclusion: Adding ZKP in protocols to ensure that some design hypotheses are enforced.

They created H26forge to create vulnerable H264 content.  They attack the semantics out of its specified range.  Decoders may not test all of them.  The tool helps with handling the creation of forged H264. 

Conclusion

This may be devastating if combined with fuzzing.

Enforce the limits in the code.

If the EKU (extended key use) is not properly verified for its purpose, bingo.

Some tested implementations failed the verification.  The speaker forged the signing tools to accept domain-validated certificates for signing code.

Politically correct but not really informative.

IS RSA2048 broken?

Posted on by
Reply

Recently, an academic paper from a large team of Chinese researchers made the headlines of the specialized press [1].  Reporters claimed that “small” quantum computers may break RSA2048.  Breaking RSA2048 may need only 372 qubits.  Qubits are similar to bits in the quantum domain.  IBM already proposes Osprey: a 433-qubit chip.  So, is RSA2048 dead?

The security of RSA relies on the assumption that factorizing the product of two large prime numbers is extremely difficult.  It is assumed currently that conventional computers cannot solve this problem.  Recent studies showed that, in theory, quantum computers may succeed.

The paper is not for the faint heart.  Its summary is as follows:

Shor’s algorithm has seriously challenged information security based on public key cryptosystems.  However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities.  Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA).  The number of qubits required is O(logN/loglog N), which is sublinear in the bit length of the integer $N$, making it the most qubit-saving factorization algorithm to date.  We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device.  We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm.  Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.

As mentioned, RSA’s security assumes it is tough to factorize the product of two very large prime numbers.  The researchers use Schnorr’s algorithm [2] to factor these large numbers rather than the Schor one.  On the one hand, the Schor algorithm requires millions of qubits, but it is a theoretically proven solution.  Unfortunately, it is out of the current feasibility realm.  On the other hand, Schnorr’s algorithm seems not yet to be a proven solution at a large scale.  The expected speed-up using quantum computing is highly controversial and not demonstrated.  The paper stays in the realm of unproven expectations.

The consensus seems to be that the threat is not yet here.  Following is a list of posts of people who know far better than me:

  • [3] highlights one crucial point (present in all papers): It should be pointed out that the quantum speed-up of the algorithm is unclear due to the ambiguous convergence of QAOA.  In other words, the paper does not demonstrate that it is faster than Schor’s.  Scott is a quantum computing expert.
  • [4] highlights that the paper never claims to be faster.  It omits “running time”; what is merely claimed is that the quantum circuit is very small.
  • [5] Bruce Schneier reminds that Schnorr’s paper works well for small moduli, but does not scale well for larger prime numbers.
  • [6] highlights that the quantum computer should have a 99.999% fidelity.  This would require a NISQ computer with gate level fidelities of 99.999%.  That level is more than two orders of magnitude better than the best machines we have today. 

Conclusion

Keep calm.  RSA 2048 is still safe for many years.  Nevertheless, it is key to be aware of the latest progress of post-quantum cryptography.  Do we have to switch to post-quantum cryptography?  Not right now, especially if you do not handle secrets that have to last for many decades.

Reference

[1]          B. Yan et al., “Factoring integers with sublinear resources on a superconducting quantum processor.” arXiv, Dec. 23, 2022.   Available: http://arxiv.org/abs/2212.12372

[2]          C. P. Schnorr, “Fast Factoring Integers by SVP Algorithms, corrected.” 2021.  Available: https://eprint.iacr.org/2021/933

[3]          S. Aaronson, “Cargo Cult Quantum Factoring,” Shtetl-Optimized, Jan. 04, 2023.  https://scottaaronson.blog/?p=6957

[4]          “Paper claims to break RSA-2048 with only 372 physical quibits.” https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/AkfdRQS4yoY/m/3plDftUEAgAJ .

[5]          “Breaking RSA with a Quantum Computer – Schneier on Security.” https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html

[6]          dougfinke, “Quantum Experts Debunk China Quantum Factoring Claims,” Quantum Computing Report, Jan. 06, 2023.  https://quantumcomputingreport.com/quantum-experts-debunk-china-quantum-factoring-claims

NIST selected the post-quantum cryptosystems

Posted on by
Reply

Post-quantum cryptography encompasses the algorithms that are allegedly immune to quantum computing.  In 2017, NIST initiated the process of selecting and standardizing a set of post-quantum cryptosystems. In 2020, NIST started the third round with 15 remaining candidates.

NIST announced the four winners.  CRYSTALS-KYBER is the new key establishment protocol for post-quantum. 

“Among its advantages are comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation. ”

CRYSTALS-DILITHIUM, Falcon, and SPHINCS+ are the new digital signature systems.

“ Reviewers noted the high efficiency of the first two, and NIST recommends CRYSTALS-Dilithium as the primary algorithm, with FALCON for applications that need smaller signatures than Dilithium can provide. The third, SPHINCS+, is somewhat larger and slower than the other two, but it is valuable as a backup for one chief reason: It is based on a different math approach than all three of NIST’s other selections.”

Interestingly, version 9.0 of OpenSSH proposes a post-quantum algorithm.  It is NTRU prime and not CRYSTALS-KYBER.

OpenSSH prepares post-quantum

Posted on by
Reply

For several years, cryptography has studied the implication of the rise of quantum computation.  Once fully operational, with enough qubits, error-free, and keeping quantum states long enough, quantum computing will break prime number factor-based cryptosystems (such as RSA) and Elliptic Curve Cryptography by quickly finding the private keys.

Thus, in 2017, NIST initiated selecting and standardizing a set of post-quantum cryptosystems.

OpenSSH just released version 9.0.  And it adds the support of a post-quantum cryptosystem.  To be precise:

Quoting

use the hybrid Streamlined NTRU Prime + x25519 key exchange method by default (“sntrup761x25519-sha512@openssh.com”). The NTRU algorithm is believed to resist attacks enabled by future quantum computers and is paired with the X25519 ECDH key exchange (the previous default) as a backstop against any weaknesses in NTRU Prime that may be discovered in the future.  The combination ensures that the hybrid exchange offers at least as good security as the status quo.

NTRU Prime is one of the nine remaining candidates in the NIST selection process.   OpenSSH chose one without waiting for the NIST final selection. 

Breaching the Samsung S9 Keystore

Posted on by
Reply

Most Android devices implement an Android Hardware-backed Keystore.  The Rich Execution Environment (REE) applications, i.e., the unsecure ones, use a hardware root of trust and an application in the Trusted Execution Environment (TEE).  Usually, as all the cryptographic operations occur only in the trusted part, these keys should be safe.

Three researchers from the Tel-Aviv university demonstrated that it is not necessarily the case.  ARM’s TrustZone is one of the most used TEEs.  Each vendor must write its own Trusted Application (TA) that executes in the TrustZone for its key store.  The researchers reverse-engineered the Samsung implementation for S8, S9, S20, and S21.  They succeeded in breaching the keys protected by the key store.

The breach is not due to a vulnerability in TrustZone.  It is due to design errors in the TA.

When REE requests to generate a new key, the TA returns a wrapped key, i.e., a key encrypted with a key stored in the root of trust.  In a simplified explanation, the wrapped key is the newly generated key AES-CGM-encrypted with an IV provided by the REE application and a Hardware-Derived Key (HDK) derived from some information supplied by the REE application and the hardware root of trust key.

 In other words, the REE application provides the IV and some data that generate the HDK.  AES-CGM is a stream cipher (uses AES CTR), and thus it is sensitive to IV reuse.  With a streamcipher, you must never reuse an IV with the same key.  Else, it is easy to retrieve the encrypted message with a known ciphertext.  In this case, the attacker has access to the IV used to encrypt the wrapped key and can provide the same `seed` for generating the HDK.   Game over!

In S20 and S21, the key derivation function adds some randomness for each new HDK.  The attacker cannot anymore generate the same HDK.  Unfortunately, the S20 andS21 TA contains the old derivation function.  The researchers found a way to downgrade to the S9 HDK.  Once more, game over!

Lessons:

  1. Never reuse an IV with a streamcipher.  Do not trust the user to generate a new IV, do it yourself.
  2. A Trusted Execution Environment does not protect from a weak/wicked “trusted” application. 
  3. If not necessary, remove all unused software from the implementation.  You reduce the attack surface.

Reference

A. Shakevsky, E. Ronen, and A. Wool, “Trust Dies in Darkness: Shedding Light on Samsung’s TrustZone Keymaster Design,” 208, 2022.  Available: http://eprint.iacr.org/2022/208

Quantum what?

Posted on by
2

Quantum what?

Quantum computing, quantum cryptography, and post-quantum cryptography: these terms are confusing.  This post attempts to clarify them and draws the relationship between them.

Quantum computing is the set of technologies that use quantum-mechanical phenomena to perform computing.  Quantum computing uses qubits rather than bits.  Where one bit of conventional computing has one of the two possible states “0” or “1”, a qubit has a set of independent states simultaneously via superposition.  Furthermore, entangled qubits behave together in non-conventional ways (for instance, immediate synchronization independent from the distance separating the two qubits).

These properties allow solving some classes of problems, many orders faster than conventional computing.  In 1994, Peter Shor published “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” [1].  His algorithm solves the prime factorization and discrete logarithm hard problems.  Prime factorization is the foundation of cryptosystems such as Diffie Hellman (DH) and RSA.  Discrete logarithms are the foundation of elliptic curve cryptosystems (ECC). In 1996, Lov Grover published “A fast quantum mechanical algorithm for database search” [2].  His algorithm inverts one-way functions in  time.  It applies to symmetric ciphers and cryptographic hashes.

Whenever quantum computing is operational, accurate, and with enough qubits, these algorithms and their enhancements will impact traditional cryptography.  To mitigate Grover’s algorithm, the size of symmetric keys and hashes has to increase.  For instance, AES will need at least 256-bit keys. Shor’s algorithm annihilates the security of prime factorization or discrete logarithm-based cryptosystems.  In other words, DH, RSA, and ECC will not be secure anymore.

Post-quantum cryptography encompasses the algorithms that are allegedly immune against quantum computing.   There are mainly four categories of algorithms.

  • Hash-based signatures; It uses the current hash algorithms, and its security is well understood. The size of the public key is far larger and usable only once. 
  • Code-based encryption;  It uses sophisticated error-correcting codes.  The McEliece’s scheme was first proposed in 1978 [3] and has not been broken since. 
  • Lattice-based encryption is the most efficient and promising solution.  It allows encryption, digital signatures, and fully homomorphic encryption.
  • Multi-variate Quadratic Equations seem the less promising path.  All proposed schemes are currently broken. 

It is wise to strengthen post-quantum cryptography to be ready whenever this threat is active.  NIST estimates that a 1 billion $ quantum computer may break RSA 2048 keys in a matter of hours.   A future post will explore more in detail post-quantum cryptography.

Quantum cryptography or Quantum Key Distribution (QKD) sends over information, including a secret key, using photons over a line between Alice and Bob.  Once Bob received the secret key, Alice and Bob use it to encrypt and decrypt via traditional symmetric cryptosystems their messages.  This key distribution is very similar to many current systems.  Nevertheless, due to the Heisenberg’s principle, if Eve eavesdrops the QKD, she alters the secret key.  Thus, Alice and Bob know they are eavesdropped, offering higher security.  The obvious limitation is that it can only be used in point to point communications.  The first QKDs were designed in the 80s.

Hoping that this post shed some light, I wish you a happy new year.

References

[1]          P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Comput., vol. 26, no. 5, pp. 1484–1509, Oct. 1997, doi: 10.1137/S0097539795293172.

[2]          L. K. Grover, “A fast quantum mechanical algorithm for database search,” ArXivquant-Ph9605043, Nov. 1996.

[3]          R. McEliece, “A public-key cryptosystem based on algebraic coding theory,” NASA, DSN 42-44, 1978.

White box cryptography: an open challenge

Posted on by
2

The ideal implementation of a cryptographic algorithm would be such that even if the attacker would have the source code and would entirely control the platform, she would not be able to retrieve the secret key. In 2002, Stanley Chow and his colleagues proposed a new concept coined the white-box cryptography. The threat model of white-box attack assumes that the attacker has full access to the encryption software and entirely controls the execution platform. White-box cryptography attempts to protect the keys even under such a hostile threat model. The main idea is to create a functionally equivalent implementation of the encryption or decryption algorithm that uses only look-up tables. Corresponding look-up tables, with the corresponding hard-coded secret key, replace the S-boxes, Feistel boxes and XOR functions usually employed by symmetric cryptography. Then, the look-up tables are further randomized. In theory, the randomization hides the hard-coded key. White box cryptography is a difficult challenge for skilled reverse engineers.

Abundant cryptographic analysis has demonstrated that these constructions are not theoretically secure. Nevertheless, well-crafted real implementations may resist reverse engineering. Many vendors offer such white-box cryptography for AES. The issue is how do you know whether an implementation is robust. Securing white-box cryptography is a lot of black magic. Currently, the only solutions are either reverse-engineer it yourself or trust your supplier blindly.

Fortunately, the European-funded research project ECRYPT launches an exciting challenge: The WhiBox contest. It is a capture the flag challenge dedicated to white-box cryptography. Developers are encouraged to post AES-128 white-box implementation as a C source code. Attackers are invited to break the challenge, i.e., extract the encryption key.

The contest starts on May 15 and ends August 31. The winners, i.e., the implementation that resisted the longest, and the attacker who broke the “strongest” implementation, during the rump session of CHES 2017.

This initiative is interesting. It will be a benchmark of state of the art in this obscure field. Of course, it will have value only if enough skilled attackers will answer the challenge. I expect some success. It reminds the challenges to evaluate oracle attacks for digital video watermarking (BOWS and BOWS2). BOWS demonstrated the risk associated with the access to a watermark detector.

We will follow this challenge. Will commercial solutions dare to submit implementations? Winning this challenge would be a feather in their hat.

 

Reference:

    Chow, S., Eisen, P., Johnson, H., Oorschot, P.C. van: A White-Box DES Implementation for DRM Applications. In: Feigenbaum, J. (ed.) Digital Rights Management. pp. 1–15. Springer Berlin Heidelberg (2003).