Editing Semantic security (section)

== The Role of Randomness in Semantic Security ==
Randomness plays a key role in [[cryptography]] by preventing attackers from detecting patterns in ciphertexts. In a semantically secure cryptosystem, encrypting the same plaintext multiple times should produce different ciphertexts.<ref name="HAC2">{{cite book |last1=Menezes |first1=Alfred |url=https://cacr.uwaterloo.ca/hac/ |title=Handbook of Applied Cryptography |last2=Van Oorschot |first2=Paul C. |last3=Vanstone |first3=Scott |publisher=CRC Press |year=1996 |access-date=}}</ref>

If encryption relies on predictable or weak randomness, it becomes easier to break.<ref name="HAC">{{cite book |last1=Menezes |first1=Alfred |url=https://cacr.uwaterloo.ca/hac/ |title=Handbook of Applied Cryptography |last2=Van Oorschot |first2=Paul C. |last3=Vanstone |first3=Scott |publisher=CRC Press |year=1996 |access-date=}}</ref> Poor randomness can lead to patterns that attackers can analyze, potentially allowing them to recover secret [[Key (cryptography)|keys]] or decrypt messages. Because of this, cryptographic systems must use strong and unpredictable random values to maintain security.<ref name="Katz">{{cite book |last1=Katz |first1=Jonathan |title=Introduction to Modern Cryptography: Principles and Protocols |last2=Lindell |first2=Yehuda |publisher=Chapman and Hall/CRC |year=2007 |isbn=978-1584885511}}</ref>

=== Why Randomness Is Important ===
Strong randomness is critical in:

* [[Key generation]] – Ensures cryptographic keys are unpredictable.<ref name="Katz2">{{cite book |last1=Katz |first1=Jonathan |title=Introduction to Modern Cryptography: Principles and Protocols |last2=Lindell |first2=Yehuda |publisher=Chapman and Hall/CRC |year=2007 |isbn=978-1584885511}}</ref>
* Nonce Selection – Reusing a nonce in [[AES-GCM]] or [[ElGamal encryption|ElGamal]] can break security.<ref name="Katz4">{{cite book |last1=Katz |first1=Jonathan |title=Introduction to Modern Cryptography: Principles and Protocols |last2=Lindell |first2=Yehuda |publisher=Chapman and Hall/CRC |year=2007 |isbn=978-1584885511}}</ref>
* [[Probabilistic encryption]] – Some schemes, like [[Goldwasser–Micali cryptosystem|Goldwasser–Micali]], rely on randomness to ensure ciphertexts are indistinguishable.<ref name="Katz4" />

=== Failures of Randomness in the Past ===
Several cryptographic failures have resulted from weak randomness, allowing attackers to break encryption.

==== Debian OpenSSL Vulnerability (2008) ====
An error in Debian’s [[OpenSSL]] removed entropy collection, producing a small set of predictable keys. Attackers could guess [[Secure Shell|SSH]] and [[Transport Layer Security|TLS]] keys, allowing unauthorized access.<ref>{{cite web |last=Bello |first=Luciano |date=2008-05-13 |title=Debian OpenSSL Predictable Random Number Generator |url=https://www.debian.org/security/2008/dsa-1571 |access-date= |publisher=Debian Security Advisory}}</ref>

==== Sony PlayStation 3 ECDSA Failure (2011) ====
Sony’s [[PlayStation 3]] misused the [[Elliptic Curve Digital Signature Algorithm]] (ECDSA) by reusing the same [[Cryptographic nonce|nonce]] - a random number used once in cryptographic signing - in multiple signatures. Since ECDSA relies on unique nonces for security, attackers recovered Sony’s private signing key, allowing them to sign unauthorized software.<ref>{{cite web |last=Schneier |first=Bruce |date=2011-01-06 |title=Sony PS3 Security Broken |url=https://www.schneier.com/blog/archives/2011/01/sony_ps3_securi.html |access-date= |publisher=Schneier on Security}}</ref>

==== ROCA Vulnerability (2017) ====
A flaw in [[Infineon Technologies|Infineon's]] [[RSA (cryptosystem)|RSA]] key generation created weak keys that attackers could efficiently factor. This vulnerability affected smart cards and [[Trusted Platform Module|Trusted Platform Modules]] (TPMs), requiring widespread key replacements.<ref>{{cite web |date=2017-10-17 |title=ROCA: Infineon TPM and Secure Element RSA Vulnerability Guidance |url=https://www.ncsc.gov.uk/guidance/roca-infineon-tpm-and-secure-element-rsa-vulnerability-guidance |access-date= |publisher=National Cyber Security Centre}}</ref>

=== How to Ensure Strong Randomness ===
To prevent such failures, cryptographic systems must generate unpredictable and high-quality random values.<ref name="NIST90A">{{cite web |date=2012-06-11 |title=Recommendation for Random Number Generation Using Deterministic Random Bit Generators |url=https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final |access-date= |publisher=National Institute of Standards and Technology (NIST)}}</ref>

==== Use of Cryptographically Secure Pseudorandom Number Generators (CSPRNGs) ====
CSPRNGs provide secure random numbers resistant to attacks. Common examples include:

* /dev/random and /dev/urandom (Unix)
* Windows CryptGenRandom
* NIST-approved DRBGs (Deterministic Random Bit Generators)<ref name="NIST90A" />

==== Entropy Collection ====
Secure randomness requires high entropy sources, such as:

* Hardware-based generators (e.g., Intel [[RDRAND]])<ref name="NIST90B">{{cite web |date=2018-01-10 |title=Recommendation for the Entropy Sources Used for Random Bit Generation |url=https://csrc.nist.gov/publications/detail/sp/800-90b/final |access-date= |publisher=National Institute of Standards and Technology (NIST)}}</ref>
* Physical sources, like keystroke timing<ref name="NIST90B" />
* Dedicated security hardware, including [[Hardware security module|HSMs]] and [[Trusted Platform Module|TPMs]]<ref name="NIST90B" />

==== Avoiding Deterministic Encryption Without Randomness ====
Some encryption schemes require added randomness to maintain security:

* [[RSA (cryptosystem)|RSA]] with [[Optimal asymmetric encryption padding|OAEP]] padding introduces randomness to prevent deterministic encryption.<ref name="NIST56B">{{cite web |date=2019-05-23 |title=Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography |url=https://csrc.nist.gov/publications/detail/sp/800-56b/rev-2/final |access-date= |publisher=National Institute of Standards and Technology (NIST)}}</ref>
* Unique nonces in [[AES-GCM]] and [[ElGamal encryption|ElGamal]] ensure encrypting the same message multiple times produces different ciphertexts.<ref name="NIST56B" />

==== Testing and Auditing Randomness ====
To verify randomness quality, cryptographic implementations should undergo:

* [[National Institute of Standards and Technology|NIST]] SP 800-90B randomness tests<ref name="NIST90B" />
* [[Diehard tests]]<ref name="NIST22">{{cite web |date=2010-04-01 |title=A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications |url=https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final |access-date= |publisher=National Institute of Standards and Technology (NIST)}}</ref>
* [[FIPS 140-2]] compliance checks<ref name="FIPS140">{{cite web |date=2002-05-25 |title=Security Requirements for Cryptographic Modules |url=https://csrc.nist.gov/publications/detail/fips/140/2/final |access-date= |publisher=National Institute of Standards and Technology (NIST)}}</ref>

Semantically secure encryption algorithms include [[Goldwasser-Micali cryptosystem|Goldwasser-Micali]], [[ElGamal encryption|ElGamal]] and [[Paillier]].  These schemes are considered [[provable security|provably secure]], as their semantic security can be reduced to solving some hard mathematical problem (e.g., [[Decisional Diffie-Hellman assumption|Decisional Diffie-Hellman]] or the [[Quadratic Residuosity Problem]]).  Other, semantically insecure algorithms such as [[RSA (algorithm)|RSA]], can be made semantically secure (under stronger assumptions) through the use of random encryption padding schemes such as [[Optimal Asymmetric Encryption Padding]] (OAEP).