Principles of Cryptography and Data Security
In this week's summary, we delve into the fundamentals of cryptography, encryption schemes, authentication, privacy, integrity, and more. Explore the workings of secret-key and public-key cryptography systems to secure data at rest and in motion effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Information and Communications Technology ICT 4680 Principles of Cryptography Week 10 Summary
Information and Communications Technology This week, we summarize all we have learned over the past few weeks in this term and use the learning to see how we can secure data at rest and in motion. The securing of data is going to be done by you you will research how to apply the learning
Information and Communications Technology Alice wants to send Bob a secret message. Encryption Schemes c = E(m,k) m = D(c,k) c They agree in advance on 3 components: Encryption algorithm: E Decryption algorithm: D Secret key: k To encrypt plaintext m, Alice sends c = E(m,k) to Bob. To decrypt a cyphertext c, Bob computes m = D(c,k). A scheme is valid if m =m Intuitively, a scheme is secure if eavesdropper can not learn m from c.
Information and Communications Technology General Requirements Authentication: The sender knows that the message is going to the intended recipient; and the recipient knows that the message was sent by the proper sender. Privacy: The message is secret: only the sender and the intended recipient know its contents. Integrity: The message was not modified (intentionally or accidentally) while in transit. Non-repudiation: The author of the message cannot later deny having sent the message. Cryptographic techniques can be used to satisfy the above requirements.
Information and Communications Technology How Does It Work? An ordinary message (the plaintext) is processed by an encryption algorithm to produce a scrambled message (the ciphertext). The receiver then uses a matching decryption algorithm to recover the plaintext from the ciphertext. There would be no security if these algorithms were known to everyone. Hence, there is an additional piece of input data called a key. The key is secret, even though many people may know the algorithms. The idea is the same as that of combination locks: Many people may use locks with the same design, but each one chooses a different combination (i.e., a different key).
Information and Communications Technology Two Basic Types Secret-key (or symmetric) cryptography: Both encryption and decryption operations use the same key. Secret-key systems have been around for many hundreds of years. Public-key (or asymmetric) cryptography: Public-key systems use different keys for the encryption and decryption operations. One key can be made public while the other key is kept secret (and is called private key). Recent invention (dating from mid 1970s). Can grow more easily to worldwide scale and more easily permit unaffiliated persons to communicate securely. Can be used to provide digital signatures (to be discussed more later).
Information and Communications Technology Symmetric Cryptography Ciphertext The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog AxCv;5bmEseTfid3)fGs mWe#4^,sdgfMwir3:dkJ eTsY8R\s@!q3% Plaintext input Plaintext output Encryption Decryption Same key (shared secret)
Information and Communications Technology Asymmetric Cryptography Plaintext input Plaintext output Ciphertext The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog Py75c%bn&*)9|fDe^bD Faq#xzjFr@g5=&nmdFg$ 5knvMd rkvegMs Encryption Decryption Different keys public private Public key Private key
Information and Communications Technology Practical Use In practice, cryptographic systems often use both secret-key and public-key cryptography together. Since secret-key algorithms are usually faster, it is more efficient to use a secret-key algorithm to encrypt the actual data. The system first generates a (random) key for the secret-key algorithm. The system then encrypts that key using the public-key algorithm. The receiver first decrypts the secret key using the public-key algorithm, and then decrypts the data using that newly decrypted key.
Information and Communications Technology Main Components There are 4 main components in the use of cryptography for any practical systems: cryptosystems, modes, protocols, and key management. The term cryptosystems refers to the cryptographic algorithms and their characteristics. Modes refers to how the cryptographic algorithms are initialized and used to manage messages that are longer than a single block. Protocols refers to the ways in which cryptographic algorithms are composed and applied to real problems (e.g., the securing of a communication channel or information in a database). Very important for e-commerce because they are used for protecting content as well as for payment systems. Key management refers to the essential problems of creating, distributing, storing, and updating keys. Since modern cryptographic algorithms and protocols are very strong, key management is a tempting target for attackers.
Information and Communications Technology Cryptographic Strength One way to attack a cryptosystem is to try all possible keys to decrypt a message (exhaustive search or brute force attack). There must be enough possible keys to make this attack computationally infeasible. The Data Encryption Standard (DES) in 1977 uses 56-bit keys. There are 256 possible keys (or 72.1 x 1015 different keys), which seems sufficiently large. Several years ago, Digital Equipment Corporation built a chip capable of 16,000,000 DES operations per second. If one were to build a machine with 1000 such chips, a 56-bit key DES encrypted message could be broken in less than 8 weeks!
Information and Communications Technology Key Length Given a reasonably strong algorithm, how well the data is protected depends largely on the length of the encryption key. An encrypted message must remain secret during the useful life of the information. Financial credentials must remain secret beyond their validity period. Contract bids must remain secret beyond the contract award. Editorial material must remain secret until published. Confidential personal information must remain secret beyond the lifetime of the person. The value of the information in the encrypted message governs the resources used to attack it. An attacker would be foolish to spend $1 million to obtain information worth $1 thousand. He may spend $1 million to obtain a secret worth $2 million.
Information and Communications Technology Key Length (cont.) Today, it is common to use 128/256-bit keys for symmetric algorithms, both for communication security and for the security of data to be protected for 20 years. The current recommendation for asymmetric algorithms is to use a minimum length of 2048 (2K) bits (or 4096(4K) bits) for especially sensitive applications or long-term key.
Information and Communications Technology Key Updates The longer a key has been in used, the greater the chance that it is discovered by subterfuge (rather than by brute force attack). Hence, keys need to be updated from time to time. It is important to note that changing a key does not increase the time that an attacker will need to break it using brute force attack. However, changing a key will limit the amount of information revealed if any particular key is discovered. Example: If the encryption key is changed every month, then only one month s worth of information is lost if a key is discovered.
Information and Communications Technology Secret-Key (Symmetric) Cryptography
Information and Communications Technology Overview The message (plaintext) is encrypted into ciphertext using a key. The resulting ciphertext is sent to the recipient, who will decrypt it using the same key. Hence, the same key must be known to both parties. The best known secret-key system is the Advanced Encryption Standard (AES). Receiver Sender Plaintext ciphertext Plaintext Decrypt Encrypt Key Key
Information and Communications Technology Overview (cont.) Privacy is achieved because only those who know the key can encrypt or decrypt messages. Authentication can be achieved if separate keys are used for each pair of communicating parties. Integrity can be achieved if a message integrity code (MIC) is added to the message. An MIC is a cryptographic checksum assigned to a file and used to test the file later to verify that the data contained in the file has not been maliciously changed. Non-repudiation is not achieved because either the sender or the intended recipient could have created the message. Example: Bob and Alice communicate using secret-key cryptography. First, they must agree on a key, which only they will know and which they will keep secret from all others. Now, they each can encrypt messages to the other using the common key.
Information and Communications Technology Block Ciphers and Stream Ciphers Block cipher algorithm takes a fixed-length block of plaintext (64 or 128 bits) and encrypts it with the key to produce a fixed-length block of ciphertext . Disadvantage: One may notice that certain ciphertext blocks are repeated and will therefore know that the corresponding plaintext blocks are also repeated. To combat this problem, an initialization vector (IV) is pre-pended to the message and then encrypted. Then, the first block of ciphertext is exclusive-OR ed with the second block of plaintext and then encrypted, and so on. The IV is different for each message. This technique is called cipher block chaining (CBC). Stream cipher algorithm uses the key to produce a pseudorandom key stream, which is exclusive- OR ed with the plaintext to produce the ciphertext. Disadvantage: Simple cipher algorithm produces the same key stream with each new message. To prevent this problem, the IV and the key are used to initialize the key stream generator so that it produces a different sequence for each message.
Information and Communications Technology Secret-Key Cryptosystems Data Encryption Standard (DES): DES is a block cipher algorithm that uses a 56-bit key to encrypt a 64-bit plaintext block into a 64-bit ciphertext block. The most common mode of operation of DES is CBC: Each output block of ciphertext is exclusive-ORed with the next plaintext block to form the next input to the DES algorithm. This process begins with a 64-bit IV. Disadvantage: Its 56-bit key length is too small to resist brute force attacks by modern computers. Triple DES: Uses three 56-bit DES keys to encrypt each block. The data block is encrypted with the first key, then run in decryption mode with the second key, and finally encrypted again with the third key. If all the three keys are chosen to be the same then Triple DES reduces to ordinary DES. In its three-key mode, Triple DES requires a 168-bit key.
Information and Communications Technology Secret-Key Cryptosystems (cont.) Blowfish: A block cipher algorithm using variable key lengths, designed by Bruce Schneier. Freely available and very fast, running nearly 3 times faster than DES. Widely used in file encryption applications for personal computers. The key length is variable from 32 bits to 448 bits, making it interesting for variable security applications. Advanced Encryption Standard (AES): AES is an effort of the National Institute of Standard and Technology (NIST) to develop and standardize a replacement for DES. AES uses Rijndael algorithm, which is an iterated block cipher algorithm whose block length and key length can be independently set to 128 bits, 192 bits, or 256 bits. AES is a good choice for new applications, because it is standard, it is receiving careful study by cryptographers, and it continues to resist attacks.
Information and Communications Technology Public-Key (Asymmetric) Cryptography
Information and Communications Technology Overview In an asymmetric cryptosystem, the encryption key is different from the decryption key. Each participant creates his own pair of keys: One is called the public key and is distributed freely. The other is called the private key and is kept secret. Either key may be used for encryption or for decryption, but the private key should never be revealed to anyone. The best-known public-key cryptosystem is RSA, named after its inventors: Rivest, Shamir, and Adleman. Sender Receiver Plaintext ciphertext Plaintext Decrypt Encrypt Decryption Key Encryption Key
Information and Communications Technology Overview (cont.) Bob and Alice communicates using public-key cryptography. First, Bob and Alice each create a key pair (public key and private key). Next, they publish their respective public keys in the town directory. If Bob wants to send Alice a message, he encrypts the message using Alice s public key. The ciphertext can be read only by Alice, because only Alice knows her own private key. Alice decrypts the message using her private key, revealing the original message.
Information and Communications Technology Overview (cont.) Authentication problem: How can Alice tell if the message is really from Bob? Answer: Bob applies his digital signature to the message. Bob can do so by encrypting the message using his own private key, creating a signed message. Of course, anyone can decrypt this signed message by using Bob s public key. The signed message is not secret, but only Bob could have sent it, because only Bob knows his private key. Solution to the authentication problem: Bob first signs his message using his private key. He then encrypts this signed message using Alice s public key. Then only Alice can decrypt this message. Once she has, she can verify (by using Bob s public key) that Bob indeed sent the message.
Information and Communications Technology Overview (cont.) Another problem (security of the key directory): When Bob sends a message to Alice, he looks up Alice s public key in the directory. Suppose someone has substituted his own public key with Alice s public key in the directory. So Bob will unwittingly encrypt his message using not Alice s public key, but the public key of someone else. Solution: Public-key certificates. A public key certificate is a document containing a name and the corresponding public key, signed by a trusted certificate authority. Suppose the town clerk is operating as a certificate authority. When Alice first creates her public key, she appears in person before the clerk with a document attesting that the public key is really hers. The clerk then signs the document with her private key. The resulting signed document becomes a public- key certificate. Anyone can verify the clerk s signature using the clerk s public key. Once Alice has a certificate, she can place it in the directory. Bob then can be assured that the key he uses to send messages to Alice is really Alice s public key.
Information and Communications Technology Overview (cont.) Certificate authorities (CA) are often organized in a hierarchy (similar to DNS). Higher-level certificate authorities sign certificates for lower-level authorities. The certificate authority at the top of the hierarchy is called the root, and its public key is called the root key. A hierarchy of certificate authorities together with the widespread use of public-key certificates constitute a public-key infrastructure (PKI).
Information and Communications Technology The RSA Algorithm The best-known public-key cryptosystem is RSA, whose algorithm is as follows: Bob chooses two distinct large primes p and q and computes n = pq. Bob chooses the encryption key e such that the greatest common divisor gcd(e, (p 1)(q 1)) = 1. Bob then computes the decryption key d with de = 1 (mod(p -1)(q 1)) (read: de is congruent to 1 mod (p 1)(q 1)). Bob makes n and e public, and keeps p, q, and d secret. Alice writes her message as a number m. If m is greater than n, she will break the message into blocks, each of which is less than n. For simplicity, let us assume for now that m < n. Alice will encrypt message m as c = me (mod n) and sends the ciphertext c to Bob. Bob decrypts c by computing m = cd (mod n). 1. 2. 3. 4. 5. 6. 7.
Information and Communications Technology The RSA Algorithm (cont.) Recall the definition of congruence: Let a, b, n be integers with n being nonzero. We say that a = b (mod n) (read: a is congruent to b mod n) if (a b) is a multiple (positive or negative) of n, that is a = b + kn for some integer k (positive, negative or zero). Examples: 32 = 7 (mod 5), -12 = 37 (mod 7), 17 = 17 (mod 13) A text message can be written as a number using some numbering scheme to number the letters. If we number a = 01, b = 02, c = 03, , z = 26 then the message cat can be written as the number m = 30120. Proof of the algorithm (i.e., why m = cd (mod n)?) can be found in any standard cryptography textbook
Information and Communications Technology Modes When the message to be encrypted is longer than the block length of the cipher, it is necessary to execute the algorithm several times and to combine the results in some way. The method of combination is called the mode of operation. We shall look at the Electronic Codebook (ECB)Mode and the Cipher Block Chaining (CBC) Mode. There are also other modes such as Cipher Feedback Mode, Output Feedback Mode etc., whose details can be found in reference [1].
Information and Communications Technology Electronic Codebook (ECB) Mode The encryption algorithm is applied independently to each block of the message. Disadvantages: The same input block is always encrypted as the same ciphertext block. An attacker can substitute blocks to alter part of a message (e.g., changing payment amount by substituting the block where the amount appears). Plaintext 1 Plaintext 2 Encrypt (key) Encrypt (key) Ciphertext 2 Ciphertext 1 Decrypt (key) Decrypt (key) Plaintext 1 Plaintext 2
Information and Communications Technology Cipher Block Chaining (CBC) Mode Plaintext 1 Plaintext 2 Each plaintext block is exclusive-ORed with the preceding ciphertext block before the plaintext is encrypted. The process is bootstrapped using an initialization vector (IV). IV + + Encrypt (key) Encrypt (key) Ciphertext 2 Ciphertext 1 Decrypt (key) Decrypt (key) IV + + Plaintext 1 Plaintext 2
Information and Communications Technology CBC Mode (cont.) In CBC mode, each block of plaintext is scrambled by XOR with a block of ciphertext. Because these ciphertext blocks are different, if the same plaintext block occurs in multiple places, it will be encrypted into different ciphertext blocks. The IV provides this function for the first plaintext block. The IV must be random and different for each message, but it doesn t need to be secret. The IV is often transmitted in the clear as the first part of the message. CBC mode also makes the overall message more resistant to tampering. If an attacker switches blocks around, duplicates blocks, or substitutes old blocks in new messages, the chaining that occurs during decryption will result in the output plaintext being gibberish.
Information and Communications Technology Protocols A protocol is a series of steps taken to accomplish a task. This is similar to the definition of an algorithm, but we use algorithm to refer to the attainment of internal, mathematical results such as encrypting a block we use protocol to refer to the attainment of user-visible results such as secret communication and digital signatures.
Information and Communications Technology Communications: Session Keys A session key is a cryptographic key adopted for use for a particular message or during a particular session of communications. Session keys are used for two reasons: 1. To achieve greater performance: Usually a communications system will use a relatively low-performance public-key cryptosystem to communicate a session key. The session key is then used in a high-performance secret-key cryptosystem to encrypt the bulk volume of message data. To limit the amount of data encrypted with the master key. Because only the session key is encrypted by the master key, the attacker cannot exploit statistical properties of the actual message to assist in the attack on the master key. 2.
Information and Communications Technology Communications: Data Compression Data compression refers to the problem of encoding a message in the minimum amount of space. In order to do this, data compression algorithms (e.g., ZIP and COMPRESS) exploit statistical properties of the source file to encode the same information with fewer bits. In general, it is not possible to compress an encrypted message, because a good encryption algorithm should destroy the statistical properties that a compression algorithm can exploit. However, it is possible to encrypt a compressed message. Compressing a file before encrypting it may slightly improve security, because compression algorithms reduce the redundancy that may be exploited during cryptanalysis.
Information and Communications Technology Digital Signatures A digital signature is an information block attached to a message that could have been created only by a particular individual. One can use public-key cryptography to produce a digital signature by creating a message digest of the message and encrypting the message digest with one s private key. Anyone can validate a signature using the corresponding public key.
Information and Communications Technology Key Management Key management is the tempting target for attackers (because modern cryptographic algorithms, modes and protocols are strong). Key management consists of Key generation Key storage Key distribution Key destruction
Information and Communications Technology Digital Signatures. Electronically sign documents in unforgeable way. Zero-knowledge proofs. Alice proves to Bob that she earns <$50K without Bob learning her income. Privacy-preserving data mining. Bob holds DB. Alice gets answer to one query, without Bob knowing what she asked. Playing poker over the net. Alice, Bob, Carol and David can play poker over the net without trusting each other or any central server. Distributed systems. Distribute sensitive data to 7 servers s.t. as long as <3 are broken, no harm to security occurs. Electronic auctions. Can run auctions s.t. no one (even not seller) learns anything other than winning party and bid. 38
Information and Communications Technology Cryptography and Security A chain is only as strong as it s weakest link The more complex the algorithm, the greater the chance of hidden bugs Even with perfect cryptography, a memory hole or other OS and application errors can cause data leakage or even allow outright theft There is no avoiding the human element Then we have key storage and other protection issues how does one overcome those?
