Threats

Vulnerabilities in networks, applications, and services are being identified and exploited everyday. Weaknesses in both cryptographic algorithms and their implementations can allow attackers to gain the "keys to the kingdom" so to speak.  That is, with a stolen or deciphered private key, there is little standing in the way of an attacker from gaining unauthorized access to an exposed network service, or decrypting confidential network traffic. 

A recently discovered critical vulnerability tracked as CVE-2024-31497 in PuTTY, the most popular Windows SSH client threatens to expose the victim's private key used to authenticate to network services. Considering the prevalence of SSH as a remote access tool for critical systems, the vulnerability in PuTTY represents a serious threat to many organizations globally. 

The CVE-2024-31497 security flaw stems from a weakness in PuTTY's Elliptic Curve Digital Signature Algorithm (ECDSA); specifically its nonce generation. The first 9 bits of each nonce are consistently zero, drastically reducing the entropy and therefore the algorithm's cryptographic resilience. Researchers ultimately determined that CVE-2024-31497 allows an attacker to recover a user's NIST P-521 secret key with possession of about 60 digital signatures. This is seriously bad news for organizations around the world, especially considering that the ECDSA signatures required for an attack may already be available to attackers in GitHub commit histories. This puts publicly shared "open source" repositories at risk of supply chain chain attacks if the package maintainer was using PuTTY or its command line tool Pageant.  

In this article we will enrich our understanding of how Cryptanalysis attacks are classified and how they stack up against each other in terms of evidencing a particular encryption scheme's resilience. 

What is Cryptanalysis?

Cryptanalysis is the practice and study of methods for understanding, examining, and breaking ciphers and cryptographic systems. Historically linked with codebreaking, as seen during wartime intelligence efforts like those at Bletchley Park in World War II, modern cryptanalysis includes a broad array of techniques used to breach cryptographic security systems.

The primary goal of cryptanalysis is not always to break a cipher outright, but also to find weaknesses in encryption methods that could theoretically reduce their strength. This includes assessing how long and under what conditions a cryptographic method or algorithm might resist various types of attacks before being cracked.

The Strength Of Various Cryptanalysis Attacks

Organizations like NIST and ISO set minimum standards for which cryptographic algorithms are considered strong and secure. For example, NIST FIPS 140-2 defines security requirements for cryptographic modules validated via the Cryptographic Module Validation Program (CMVP), including testing for various types of unforgeability. These advisories are based on evaluations of algorithms to determine their strength against various types of attacks and their suitability for practical use. 

These terms defined below are essential in academic research to classify the security properties of cryptographic schemes and used in formal security proofs to show that an algorithm meets specific security criteria under defined assumptions. Most recently, these attack classifications have been applied to quantum cryptography. Each level of security is crucial for different applications and environments, depending on the risk and the potential damage an attacker could cause by breaking the signature scheme.

The classifications of cryptanalysis attack and validation as follows:

• UUF-CMA (Universal Unforgeability under Chosen-Message Attack): The attacker can request signatures on messages of their choosing and aims to prove the ability to universally forge signatures for arbitrary messages at will. UUF-CMA means that the security of the signature scheme is such that the attacker cannot forge a valid signature for any message, even if they have had the opportunity to request signatures on messages of their choosing. This is the strongest validation of an encryption scheme.

• SUF-CMA (Selective Unforgeability under Chosen-Message Attack): The attacker chooses a specific message upfront, requests signatures for other messages of their choice, and tries to forge a signature for the initially chosen message. This level of security is violated if the attacker, after choosing their desired message and receiving other signed messages, can forge a signature for their chosen message. This model is more restrictive than UUF-CMA because the attacker has a specific target message and thus technically it provides less security assurances.

• EUF-CMA (Existential Unforgeability under Chosen-Message Attack): The attacker can request signatures on messages of their choosing and must attempt to forge a signature on any message not in their set of chosen signed messages. Still very strong, but it only requires the attacker to produce one valid forged signature on any message not previously signed.

• UUF-KMA (Universal Unforgeability under Known-Message Attack): In this attack scenario, the attacker is given access to a set of valid message-signature pairs. The goal is to produce a valid signature on any new message, which was not part of the initial set. A signature scheme is vulnerable under UUF-KMA if an attacker can forge a signature for any single message at all after observing some valid signatures.

• SUF-KMA (Selective Unforgeability under Known-Message Attack): SUF-KMA attacks are similar to UUF-KMA; the attacker has several valid message-signature pairs. The goal here, however, is to forge a signature for a specific message chosen by the attacker beforehand. The scheme fails this test if the attacker can forge a signature on a pre-selected, specific message after observing valid signatures. 

• EUF-KMA (Existential Unforgeability under Known-Message Attack): The attacker, given valid message-signature pairs, needs to produce a valid signature on at least one new message, not necessarily chosen in advance. This could be any message that wasn't in the original set. This is the weakest form of security under KMA. The scheme is compromised if the attacker can find any new message that they can validly sign. 

Here are some additional cryptographic attack classifications:

• No-Message Attack (NMA): In a no-message attack, the adversary only has access to the public key of the cryptographic system. They do not have access to any signatures or signed messages. The adversary's goal is to forge a valid signature for at least one message using only the public key information.

• Random message attack (RMA): Adversary can obtain signatures for random messages (not in the control of the adversary).  They do not have control over which messages have been digitally signed and do not know the contents of the messages. 

Conclusion

In this article, we've explored the intricate world of cryptanalysis and its implications on cybersecurity. Cryptanalysis, the art and science of breaking cryptographic systems, serves as both a defensive tool for identifying potential vulnerabilities and an offensive measure that could potentially be exploited by attackers, especially sophisticated nation-state threat actors and other well funded Advanced Persistent Threats (APT).