Length of cryptographic keys Zdeněk Říha Security of RSA lWe choose randomly 2 primes and compute n and φ(n) : lp, q ln = p·q lφ(n) = (p-1)(q-1). l e is chosen such that gcd(e, φ(n)) = 1. lWe compute d = e-1 (mod φ(n)). lPublic key: n, e. Private parameters: p, q, d. Private key: d. lSecurity of RSA cryptosystem is based on the problem of factoring large numbers lIf public n can be factored into p and q, we can calculate φ(n) and derive d from e. lInteger factorization is taught at primary schools lBut when integers are very big it takes very long time even for fast computers to factor the number Computational Security lUnconditional vs. computational security lSecurity based on a hard problem lThe problem is solvable, but it takes impractically long time to solve lThe attacker cannot wait thousands/millions of years to break the encryption lOur expectations can change: lProgress in the speed of HW lProgress in the efficiency of algorithms History of RSA Security lRSA is considered secure lBut the key size does matter l1977: published in “Scientific American” lRSA-129 (129 decimal digits of modulus n) lChallenge of 100 dollars l40 quadrillion years estimated to factor … lFactored in 1994 l“The magic words are squeamish ossifrage.” History of RSA Security II l1999 l512 bit integer was factored l2005 l663 bit integer was factored lJanuary 2010 l768 bit integer was factored lFebruary 2020 l829 bit integer (RSA-250) was factored l l1024 bit integers are (probably) factorable at the moment by large organizations Security of RSA Source: P. Layland, RSA Security and Integer Factorization: The Thirty Years War from 1990 to 2020, IS2 2010, Praha Key size lAlgorithms are public & keys must be secret lKey must be large enough that a brute force attack is infeasible lDepending on the algorithm used it is common to have different key sizes for the same level of security lRepresenting the level of security – number of combinations needed for the brute force attack lE.g. 1024 bit RSA key equivalent to 80 bit symmetric encryption key Comparable strengths of cryptosystems Source: NIST SP800-57 Security strengths of hash functions Source: NIST SP800-57 Recommended key sizes Source: NIST SP800-57 Recommended key sizes Source: NIST SP800-57 “Acceptable” indicates that the algorithm or key length is not known to be insecure. “Deprecated” means that the use of an algorithm or key length that provides the indicated security strength may be used if risk is accepted “Legacy use” means that an algorithm or key length may be used because of its use in legacy applications “Disallowed” means that an algorithm or key length shall not be used for applying cryptographic protection. Crypto period Source: NIST SP800-57 Crypto period example Source: NIST SP800-57 Recommended crypto periods Source:NIST SP800-57 Recommended crypto periods Source:NIST SP800-57 ETSI recommendation (RSA) lSource: ETSI TS 119 312 V1.4.3 (2023-08) lRecommended key sizes for RSA for a resistance during X years lStarting date: 2023 ETSI recommendation (DSA) lSource: ETSI TS 119 312 V1.4.3 (2023-08) lRecommended key sizes for DSA lStarting date: 2023 l ETSI recommendation (ECDSA) lSource: ETSI TS 119 312 V1.4.3 (2023-08) lRecommended key sizes for ECDSA lStarting date: 2023 l ETSI recommendation (hash functions) lSource: ETSI TS 119 312 V1.4.3 (2023-08) lRecommended hash functions lStarting date: 2023 ETSI recommendation lSource: ETSI TS 119 312 V1.4.3 (2023-08) lRecommended signature suites lStarting date: 2023 l ICAO recommendation lInternational Civil Aviation Organization lElectronic passports lData signed by the issuing country to protect integrity lOne CA per country, certificates issued for entities producing passports (so called Document Signers). lStandard validity of passports: 10 years ICAO recommendations lRSA (UK, CZ, France, …) lPadding: PKCS#1 v1.5, PSS (recommended) lFor CA: min 3072 bits lFor DS: min 2048 bits lDSA lFor CA: min 3072/256 bits lFor DS: min 2048/224 bits lECDSA (Germany, Switzerland, …) lFor CA: min 256 bits lFor DS: min 224 bits lHash functions lSHA-1, SHA-2 Source: ICAO Doc. 9303 “Issuing States or organizations SHALL choose appropriate key lengths offering protection against attacks.” 8th edition of ICAO9303