class: big, middle # ECE 7420 / ENGI 9823: Security .title[ .lecture[Lecture 10:] .title[Cryptography] ] --- # Today ### Intro to cryptography ### Classical cryptography --- ## Κρυπτογραφία -- (cryptography) -- #### κρυπτός -- : hidden, secret -- #### γράφειν -- : writing -- <img src="https://assets.atlasobscura.com/media/W1siZiIsInVwbG9hZHMvYXNzZXRzLzI5MmE1OWE0YTVhMzUwMTE4N19HZXR0eUltYWdlcy01MTU1NDMwMjIuanBnIl0sWyJwIiwiY29udmVydCIsIi1hdXRvLW9yaWVudCAiXSxbInAiLCJ0aHVtYiIsIjEwMjR4NjgyKzArOTAiXSxbInAiLCJjb252ZXJ0IiwiLXF1YWxpdHkgODEgLWF1dG8tb3JpZW50Il0sWyJwIiwidGh1bWIiLCIxMjgweD4iXV0/GettyImages-515543022.jpg" align="right" width="350"/> * in general: transforming a _message_ using _secret knowledge_ ??? This famous photograph of US POWs in North Korea is an example of something that bears a hidden meaning to those with secret (or at least not-ubiquitous) knowledge. This photo was staged to show how happy captured US sailors were supposed to be in their new homes, but there is a hidden [digital message](http://www.usspueblo.org/Prisoners/The_Digit_Affair.html)... -- * in more technical terms: _plaintext_ &#8644; _ciphertext_ using a _key_&ast; .footnote[ &ast; Not _all_ cryptograhic operations require a key, but we'll start with those that do. ] --- # Security goals | | | |:-|:-| | Confidentiality | | Integrity | | Availability | | Authentication | | Authorization | | Accountability | --- # Security goals | | | |:-|:-| | **Confidentiality** | Encryption | **Integrity** | MACs, signatures | ~~Availability~~ | | **Authentication** | Password hashing | ~~Authorization~~ | | ~~Accountability~~ | ??? Cryptography is a useful mechanism that can be **part of a solution** that achieves security goals. -- #### Cryptography is a useful tool... -- but it's _just_ a tool ??? As [Peter Neumann said](http://www.nytimes.com/2001/02/20/science/20CODE.html): > If you think cryptography is the answer to your problem, then you don't know what your problem is. Cryptography doesn't solve problems by itself. Encrypting a network packet doesn't secure the hosts doing the communication. Putting a contract on a blockchain won't stop people from breaking their word. A secure system is much more than just cryptography. However, cryptography is an important _part_ of most secure systems. --- # Classical Cryptography ??? _Classical cryptography_ refers to everything from the classical era (hence the Greek name!) up to the 20th Century. _Modern cryptography_ is based on mathematical problems like the discrete logarithm problem — we'll talk about such things we get to public-key cryptography. In between, there's some awkwardness where different experts may disagree on definitions. Modern block ciphers aren't modern enough for some people, but they're definititely not classical either. I would suggest that you think of classical cryptography as **cryptography before computers** (very broadly defined) and modern cryptography as **cryptography based on math problems and applied computer science**. However, don't be surprised if you encounter someone who doesn't think that definition is "pure" enough. 😉 -- ### Substitution Cipher * replace each symbol in the plaintext with a corresponding ciphertext symbol -- <img src="hello-3.png" width="300" align="right"/> #### Example: Caesar cipher * "shift" each letter by **three** (the _key_) * _vini vidi vici_ &rarr; _ylql ylgl ylfl_ --- # More classical cryptography ### Transposition Cipher * divide messages into blocks * transpose characters within blocks * _newfoundland_ &rarr; _newf_ _ound_ _land_ &rarr; _wnfe_ _nodu_ _nlda_ with key 2413 (1 &rarr; 2, 2 &rarr; 4, 3 &rarr; 1, 4 &rarr; 3) -- ### Clearly not great... but why not? ??? If you don't know the key to such a transposition cipher, what might you try in order to find it? --- # Cryptanalysis -- * given some plaintext and/or ciphertext, find the key -- * find a fatal flaw ("break") that subverts a cryptosystem -- #### Most fundamental example: exhaustive key search * given some ciphertext (_ylql ylgl ylfl_), try all possible key values -- * 1 &rarr; _xkpk xkek xkek_ -- , 2 &rarr; _wjoj wjej wjdj_ -- , 3 &rarr; _vini vidi vici_ -- * possible if correct plaintext is **distinguishable** -- , easy if some P/C pairs are known -- (yes, this is actually possible!) ??? It might seem unlikely that an attacker would have access to all details of the system, plus plaintext and ciphertext pairs, but it's actually not. In WWII, British codebreaking was sometimes aided by feeding specific plaintexts to the German enemy via a process called ["gardening"](https://en.wikipedia.org/wiki/Gardening_(cryptanalysis)) (laying sea mines in specific locations to create minesweeping messages). --- # Kerckhoffs's principle(s) -- > 1. The system must be practically, if not mathematically, indecipherable; > 2. It should not require secrecy, and **it should not be a problem if it falls into enemy hands**; > 3. It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will; [...] .footnote[ Translation from the French from [Wikipedia](https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle) ] ??? Kerchoffs had six principles, including that "it must be applicable to telegraph communications", but we're less interested in those. One key principle that we _are_ still interested in is the second one: the security of a system **should not depend on the adversary being ignorant of its details**. This is commonly mis-stated as, "the design should be public", but that's not quite what Kerchoffs said. Rather, the principle is that your security shouldn't **depend on the design being secret**. --- # Exhaustive key search -- * Caesar-style _shift cipher_: 26 possible keys (well, really 25) -- * Modern AES-128 cipher: $2^{128}$ keys -- — could take awhile! -- - 10,000 CPUs checking one key / ns -- - $10^4 \textrm{CPU} \times 10^9 \frac{\textrm{key}}{\textrm{CPU} \cdot s} \times 10^{4.9} \frac{s}{d} = 10^{17.9} \frac{\textrm{key}}{d} = 2^{59.5} \frac{\textrm{key}}{d}$ -- - need $2^{67.5}$ days -- , i.e., 209 Edays -- / 572 Pyears -- / 63.5 Msols -- * Lesson: make the search space large! --- # Cryptanalysis assumptions ### Various attack models: -- * ciphertext-only (COA) ??? In a ciphertext-only attack, the adversary can break your cryptosystem **using nothing but ciphertext**. This is the **strongest form of attack**, so to say that a cryptosystem can withstand it **don't impress me much**. -- * known-plaintext (KPA) ??? In a known-plaintext attack, the adversary is assumed to **have access to plaintext/ciphertext pairs**. -- * chosen-plaintext (CPA, CPA2) ??? In a chosen-plaintext attack, the adversary is assumed to **be able to make you encrypt plaintexts of their choosing** (like "gardening" in WWII, but much more direct / less costly). -- * chosen-ciphertext (CCA, CCA2) ??? Finally, in a chosen-ciphertext attack, the adversary is assumed to **be able to make you decrypt ciphertexts they give you**. --- # Frequency analysis -- ### Example of a ciphertext-only attack -- * don't know the plaintext -- * know something _about_ the plaintext -- : symbol frequencies -- * English: 12% e, 9% t, etc., common groupings: the, an, qu... -- #### Exercise: decode shift-enciphered ciphertext via frequency analysis hijstcih hdbtixbth tcrdst pcs strdst bthhpvth --- class: big, middle The End.