Models of Cryptography Security Proof

---

An important property of cryptographic algorithms is the proof of security.

• 2 classes of models:
  • Unconditional security
    • aka information-theoretic security
    • a system is secure against attackers with unlimited computing resources (memory space and time)
  • Computational security
    • refers to the amount of computational resources needed to break an algorithm using the best known attack
    • most algorithms fall here
    • computationally secure algorithm is any algorithm that cannot be broken using reasonable computing resources

Computational Infeasibility

An attack is computationally infeasible if the required amount of resources is beyond the capacity of any attacker.

• governments could be an exception
• currently, an attack that requires operations is considered computationally infeasible
• the strength level of 80 bits is no longer considered secure
  • i.e. the required number of operations is of at least

Information-theoretic secure cipher is a cipher is that cannot be broken even if the adversary has unlimited computation resources.

Provable Security

• no cryptographic algorithm has been proven to be entirely secure
• but under specific and restrictive conditions, an algorithm can be declared secure
  • since the key space is finite,
    • the probability to recover a secret key is not 0
  • some plaintexts have a format known to attackers
    • so they can infer, using traffic analysis, information that could help break the algorithm
• thus, security of a cryptographic algorithm is based on a probabilistic approach, not on a formal proof
• In practice, given a cryptographic algorithm and cryptanalysts,
  • if none can break it after a long time using reasonable computational resources
  • then the algorithm can be reasonable assumed to be secure
• after publication of a vulnerability, an algorithm should stop being used immediately

Quote

“Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that himself can’t break. It’s not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. And the only way to prove that is to subject the algorithm to years of analysis by the best cryptographer around”

– Brice Schneier

Lifecycle of a Cryptographic Algorithm

1. A talented cryptograph publishes a new algorithm
   • believes it is secure
   • other cryptanalysts see this as a challenge
2. Cryptanalysts deeply analyze the robustness of the algorithm regarding known attacks
3. When a vulnerability is discovered, the algorithm is updated, and a new version is published
4. If the weakness is critical (no patch exists without major redesign), the algorithm is deprecated