WK 4 - Cryptography and Steganography Notes
Cryptography and Steganography Definitions
Encryption: The cryptographic transformation of plaintext to produce ciphertext.
Decryption: The cryptographic transformation of ciphertext to produce plaintext.
Plaintext: Data that can be viewed or used without a key, password, or decryption method (the original message).
Ciphertext: Data resulting from encryption, unreadable without a key, password, or decryption method (the unreadable message).
Cryptographic system: The specific method used for encryption and decryption.
Transposition: Rearranging the order of elements (e.g., ABCD becomes BDAC).
Substitution: Replacing elements with different ones (e.g., ABCD becomes EFGH).
Key: Information required to encrypt and/or decrypt data.
Steganography: Hiding a message in a way that its existence is hidden.
Encryption
Goal: Protect information by transforming it into an unreadable format.
Used to prevent information from falling into the wrong hands, ensuring data is only available to authorized people.
Encryption vs. Code:
Encryption transforms data using algorithms and keys.
Code substitutes words for other words (e.g., Navajo code talkers in WWII).
"dah-he-tih-hi" (hummingbird) substituted for "fighter plane."
"besh-lo" (iron fish) meant "submarine."
Goal of Cryptography and Steganography (CIA Triad)
Primarily focused on Confidentiality: Preventing unauthorized reading of information.
Steganography: Hides the existence of data by obscuring it.
Cryptography: Can also ensure Integrity.
Changes to the message render decryption unintelligible.
Requires an attacker to decrypt, modify, and re-encrypt the data.
History of Cryptography
Cryptography has existed for thousands of years.
General progression of cryptographic methods should be understood rather than specific dates.
How Encryption Works
Cryptographic process:
or
Success requires knowing the encryption method and key (if used).
Caesar Cipher Example:
Plaintext = "hello"
Encryption method = substitute letter with letter plus 3.
h → i → j → k
Deciphering:
Relatively easy to decipher due to letter frequency and common letter pairings (bigrams).
Modifying the cipher slightly can enhance security.
Modified Caesar Cipher Example:
Start with a shift of 3, then 4, then 5 (mod 26).
Plaintext = "hello"
Encryption method = substitute letter with letter + i, where i starts at 3 and increments 1 for each letter (mod 26).
More Definitions
Block Cipher:
Operates on a block of plaintext or ciphertext at a time.
Block size can vary (e.g., 64 bits, 256 bits, 1024 bits).
Pads data if there is not enough to complete a block.
Stream Cipher:
Operates on a single character, byte, or bit at a time.
Often uses the XOR function for encryption and decryption.
A special version of the stream cipher is a one-time pad.
Encryption Methods
Two broad categories:
Symmetric encryption
Asymmetric encryption
Symmetric Encryption:
The same key is used for both encryption and decryption (also called private key encryption).
Examples:
Data Encryption Standard (DES)
Loosely based on Lucifer, which used 128-bit keys.
NSA requested shortening the key length to 56 bits.
Triple-DES
Variant of DES with various modes and keys:
Advanced Encryption Standard (AES).
International Data Encryption Algorithm (IDEA).
Data Encryption Standard (DES) Properties
Block size: 64 bits.
Key size: 56 bits.
Drop bits: 8, 16, 24, 32, 40, 48, 56, 64.
Used for parity bits to ensure correct reading of previous 7 bits.
Keys were often loaded via paper tape readers, prone to errors.
Algorithm:
64-bit block is permutated.
64-bit block split into two 32-bit blocks.
Each sub-block combined with the key and processed 16 times (cycles).
Cycles include permutations, shifts, combinations (XOR), splits.
Substitutions are made by S-boxes.
Sub-blocks joined and sent through an inverse permutation process.
Types of Permutations
Basic permutations move bits or characters around.
Expansion permutations use some bits more than once to rearrange them.
Permuted choice moves some bits around and drops others.
Data Encryption Standard (DES) - Important takeaway
Familiarize yourself with types of operations in cryptographic systems.
Illustrates encryption and decryption algorithm complexity.
Data Encryption Standard (DES) - NSA Involvement
Some suspected NSA involvement in S-box design meant potential back door.
Later discovered that the S-boxes made DES resistant to differential cryptanalysis.
Data Encryption Standard (DES) - Concerns
Besides S-boxes, concerns were raised about:
Number of iterations (cycles).
Why only 16 cycles?
Wouldn't more cycles be better?
Key length.
The longer the key, the harder it is to crack a message.
The Lucifer algorithm was 128 bits.
DES is only 64 bits – with 56 key bits.
Cryptography often involves trade-offs between speed and security.
Compromises may be needed for usability.
Data Encryption Standard (DES) - Weaknesses
Weak keys:
Known keys weaken the algorithm.
e.g., keys where the shifted half is all 1s or all 0s.
Semi-weak keys:
Some keys have another key resulting in identical decryption.
Potential issues with S-Boxes:
Possible to produce same encrypted values after the first cycle with different inputs.
May indicate weakness.
Slow and only works on block sizes of 64 bits.
Key size is too small for power of today's computers
Exhaustive Key Search
Overall cryptographic system strength measured by time to do an exhaustive key space search.
Directly impacted by key length.
DES requires searches.
128 bits (or more) requires more time to crack than the remaining lifespan of our solar system.
Advanced Encryption Standard (AES)
Given the short key size of DES, a more modern system can complete an exhaustive search in less than 10 hours.
U.S. government called for a new encryption standard.
Requirements for AES Algorithm
Handle block size of 128 bits.
Handle key lengths of 128, 192, and 256 bits.
Algorithm Evaluation Criteria:
Security: Resistance to known cryptanalysis techniques, sound mathematical foundation, randomness of output
Cost: No licensing fees, no expensive hardware required.
Algorithm Characteristics: Efficiency in hardware and software, memory requirements, flexibility in key and block size, performance in various hardware such as smartcards.
AES Development Timeline
September 20, 1997: Call for algorithms.
August 20, 1998: 15 candidate algorithms named.
August 1999: NIST announced the 5 finalists: MARS, RC6, Rijndael, Serpent, and Twofish.
May 15, 2000: The period for public comments ends.
November 26, 2001: Rijndael becomes the basis of the AES.
June 2003: 192 or 256-bit key AES authorized for encrypting top-secret information.
Properties of Rijndael
Supported Key Sizes: 128, 192, 256 bits.
Support Block Sizes: 128, 192, 256 bits.
AES standard only indicates block size of 128 bits
Number of “rounds” based on block size and key size
If the key is 128, 192, 256 bits and block size is 128 bits, number of rounds of algorithm is 10, 12, 14
If the key is 128, 192, 256 bits and block size is 192 bits, number of rounds of algorithm is 12, 12, 14
If the key is 128, 192, 256 bits and block size is 256 bits, number of rounds of algorithm is 14, 14, 14
Rijndael Algorithm
Treat the block to be encrypted as a 4x4 matrix of single bytes, referred to as A.
Before the first round, A is XORed with .
Each round consists of 4 steps:
Byte substitution.
Row shift.
Column Mix.
XOR with the appropriate round key.
The last round does not perform the Column Mix.
Rijndael Algorithm - Byte Substitution
Take a single byte from the 4x4 matrix and convert it to the “new” value using table lookup.
The “new byte” goes into the same position in the matrix as the original byte.
Rijndael Algorithm – Row Shift
Each row of the 4x4 matrix is shifted “left” by a certain amount. (A permutation of the rows.)
Row 0 is shifted left 0 times.
Row 1 is shifted left 1 times.
Row 2 is shifted left 2 times.
Row 3 is shifted left 3 times.
Rijndael Algorithm - Column Mix
The mix is a linear transform done by treating the column as a polynomial over a Galois Field ().
This is then multiplied by the polynomial: .
Can also be considered as: , where:
M is a 32 x 32-bit matrix.
A is the 32 x 4 block being operated on.
Rijndael Algorithm – Round Key XOR
Each entry in the 4 x 4 matrix is XORed with the corresponding entry in the round key matrix.
Each entry in the key matrix is also 1 byte in size.
Rijndael Algorithm - Repetition
Repeat the process 9 to 13 more times depending on key and block size.
The operation on each byte can be performed in parallel.
The various operations can be performed using 4 table lookups, for a total table size of 1kB.
Decryption occurs by using inverse functions for the byte substitution, row shift, and column mixing.
These properties make Rijndael extremely fast for a cryptographic algorithm.
Comparison of DES and AES
Feature | DES | AES |
|---|---|---|
Date | 1976 | 1999 (submission) |
Block Size | 64 bits | 128 bits |
Key Length | 56 bits (in effect) | 128, 192, 256 (+) bits |
Encryption Primitives | Substitution, Permutation | Substitution, Shift, Bit Mix |
Cryptographic Design | Closed | Open |
Design Rationale | Secret | Open |
Selection Process | Secret | Open comment |
Source | IBM, Enhanced by NSA | Dutch Cryptographers |
Skipjack and Clipper Chip
Skipjack:
Developed by the NSA.
Used an 80-bit key.
Controversial encryption algorithm.
Allowed for key escrow – a “backdoor” that could allow decryption.
Backdoor used a separate mechanism called the Law Enforcement Access Field (LEAF).
Clipper Chip:
Integrated Skipjack algorithm.
Meant to help the FBI combat criminals using encryption.
Built in back door for law enforcement.
Used key escrow: the session key was held by a third-party for later release to law enforcement when needed.
The government tried to force this as a standard, but it was not widely accepted.
Skipjack and Clipper Chip Controversy:
Government tried to "outlaw" the use of any public encryption algorithm except Skipjack used by the Clipper chip.
This included a public relations campaign to gain acceptance of Clipper.
Would require a warrant to get the key held in escrow (similar to a warrant for a wiretap) so it wasn’t government intrusion 4
Critics argued that it wouldn't stop criminals and would allow the FBI to charge someone with a crime, even if they couldn’t read the (possibly) incriminating data.
Eventually, the idea met with opposition, and the government dropped it.
Issues with Symmetric Encryption
Problems:
The same key is used to encrypt and decrypt.
The shared key is more likely to be compromised.
It is possible to brute force short keys.
Certain keys are weak.
Different keys can produce identical ciphertext.
Distribution of keys is also difficult.
Large groups make this difficult.
This problem is called “key management.”
The method does not scale well.
The number of keys required for any two individuals to communicate securely is proportional to the square of the users.
Issues With Symmetric Encryption - Formula for the number of keys
The number of keys required can be visualized as a 2-dimensional matrix
Number of rows and columns is the number of users
Since the keys are symmetric, we can get rid of half the matrix (below the diagonal)
The key for User1 to User2 communication is the same as the User2 to User1 key
A user does not need a key for themselves, so we can also eliminate the diagonal
This gives us the formula for the number of keys as:
Number of Users | Unique Keys Needed |
|---|---|
2 | 1 |
3 | 3 |
4 | 6 |
5 | 10 |
10 | 45 |
100 | 4950 |
1000 | 499,500 |
100,000 | 4,999,950,000 |
1,000,000 | 499,999,500,000 |
34,734 | 603,208,011 UTSA Students Fall 2021 |
Asymmetric Algorithms
To address key management, asymmetric encryption was developed (also called public key cryptography).
Diffie-Hellman:
Developed the idea for public key cryptography in 1976.
Private Key: Known only to the owner.
Public Key: Can be known to others.
Public Key Algorithms:
RSA (Ron Rivest, Adi Shamir, and Leonard Adleman).
PGP (Pretty Good Privacy, developed by Phil Zimmerman).
Diffie-Hellman Method
\text{Ciphertext} = \text{Encrypt}(\text{Plaintext}, \text{public_key})
\text{Plaintext} = \text{Decrypt}(\text{Ciphertext}, \text{private_key})
Steps:
Each party creates their own private key.
Each party computes a public key using a mathematical function of the private key.
Public keys are exchanged.
The message key is computed from the other person's public key and your own private key.
Message key is the same on both sides given the mathematical properties of the key selection.
Public Key Algorithm Key Management
Public keys in this scheme are managed through public key infrastructure.
Key management systems allow users to lookup and retrieve public keys.
Greatly reduces the key management problem:
From:
To:
Example:
UTSA students in Fall 2021 (34,734 students).
Symmetric keys required: 603,208,011.
Asymmetric keys required: 69,468 (one public and one private for each student).
Almost a 99.99% reduction
Cryptographic Math
Developing algorithms for cryptographic systems is difficult.
Requires algorithms that are easy to verify (i.e., encrypt/decrypt) but are very difficult to brute-force.
The general approach is to use an NP-Complete problem.
NP-Complete: A special class of non-deterministic polynomial (NP) problems that suggests there is no "crack" or "shortcut" that will find an answer in less than exponential time.
Ex: If there are n keys, it cannot be cracked in less than operations.
Polynomial (P) problems have solutions that can run in a bounded polynomial function of the problem size.
Ex: If there are n keys, it could be cracked in or .
There is one unbreakable crypto method – the One-Time Pad (OTP).
NP-Complete Definitions
A problem is NP-complete when:
* the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.
* the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct.The name "NP-complete" is short for "nondeterministic polynomial-time complete".
Knapsack Problem is another example of a NP-Complete problem
Asymmetric Encryption - Remember:
Each user has a public key and a private key
They hold onto their private key – and keep it safe!
However, the public key can be made available to anyone
Other Uses of Cryptography
Digital Certificates:
Used to encode and verify messages.
Requires a Certificate Authority that creates a digital certificate based on a private key and other authentication information.
Implements the "trusted third party" concept.
X.509 is a popular standard for defining digital certificates
VPN (Virtual Private Network):
Connects geographically separate offices using public communication means.
Packets are usually "tunneled" – entire packet is encrypted and encapsulated in a new packet before sending.
Hardware or software based.
Sometimes integrated into firewalls.
Very good for mobile employees that need access to the company network
Transport Layer Security (TLS):
Replacement for SSL (Secure Sockets Layer) used in web transactions.
Uses Asymmetric encryption to exchange symmetric keys
Encryption is also increasingly being used in the offensive tools of cyberwarfare – such as malware
Public Key Infrastructure
Problem: How does Bob know that the public key he is using belongs to Alice?
Solution: Use a trusted third-party to verify Alice’s identity and digitally sign a certificate that binds her identity to that public key.
This is called a certificate authority (CA)
The infrastructure to support the hardware and software elements to make this solution workable is called public key infrastructure or PKI
Public Key Infrastructure- How it works:
Assume the CA has issued a self-signed certificate for itself (this creates the “root of trust”) with its public key
Alice and Bob agree to use the CA to verify their identities
Alice requests a public key certificate from the CA
The CA:
Verifies her identity
Computes a hash of the content that will make up her certificate
Signs the hash by using the private key that corresponds to the public key in the published CA certificate
Creates a new certificate by concatenating the certificate content and the signed hash
Makes the new certificate publicly available.
Bob:
Retrieves the certificate
Decrypts the signed hash by using the public key of the CA
Computes a new hash of the certificate content and compares the two hashes
If the hashes match the signature is verified
Bob uses Alice's verified public key to encrypt a message to her
Alice uses her private key to decrypt the message from Bob The certificate signing process enables Bob to verify that the public key was not tampered with or corrupted during transit Therefore he has some level of assurance/trust that the public key does belong to Alice
Operational Realities
Symmetric algorithms are fast but have the key distribution problem.
Asymmetric algorithms are slow but have a much easier key distribution problem.
Operational Solution: Use asymmetric algorithms to distribute symmetric keys for a single connection or transfer, then use faster symmetric encryption for data transfer.
One-Time Pad
Completely unbreakable encryption method (OTP).
Requirements:
The key must be at least as long as the plaintext.
The key must be random.
The key must never be reused in whole or in part.
The key must be kept completely secret by the communicating parties.
Randomness must be true randomness.
Worse key management problem than symmetric key encryption.
Not only do you need a key for every pair of users – the key has to be the length of every message you intend to send
One-Time Pad Example
Given the Cipher text:
gpprvynawosypzccup
If you use a key pad of:
zpdqbhhwfwshlgckbrasdfghjk
You will obtain the possible plain text:
"Hamburgers are tasty"
If you use a key pad of:
abcdefghijklmnopqrstuvwxyz
You will obtain the possible plain text:
"Go north to find money"
If the key is truly random, there is no way to know what the actual message is compared to any of the other possible messages
Other Concepts
COMSEC: Communications Security
Link Encryption: Encrypting information at the data link level as it is transmitted between two points within a network.
* Takes place in the lowest protocol layers (layers 1 and 2 in the OSI model).
* Plaintext in the host is encrypted when it leaves the host.
* It is decrypted at the next link (which may be a relay point).
* The information is then re-encrypted before it continues to the next linkEnd-to-end Encryption: Encryption takes place at the origin and decryption at the destination without intermediate (link) decryption
Onion Routing
A hybrid link encryption approach.
A routing onion (or just onion) is a data structureformed by 'wrapping' a plaintext message with successive layers of encryption, such that eachlayer can be 'unwrapped' (decrypted) like the layer of an onion by oneintermediary in a succession of intermediaries, with the originalplaintext message only being viewable by at most: the sender, the lastintermediary, and the recipient
Breaking Cryptography
Compromising a cryptographic scheme involves:
Inherent Weaknesses:
The human factor.
Somebody reveals the secret key.
Security of key and message.
Maintaining the secret key and decrypted message in a secure manner
Key length.
Short keys can be broken even with a good algorithm.
Algorithm (some algorithms are just not very secure).
It is very difficult to develop a secure algorithm
A weak algorithm can be insecure even with a long key
Technical Attacks:
Ciphertext only: The only thing available are copies of encrypted messages.
Known plaintext: The attacker has both the encrypted and unencrypted version of a message.
Chosen plaintext: The attacker has the ability to choose the text that will be encrypted and will then have both the plaintext and ciphertext versions.
Adaptive chosen plaintext: The attacker can choose multiple inputs to encrypt and can make small changes in successive messages to examine the changes in the resulting ciphertext.
Related Key Attacks: Analyzing ciphertext that had been encrypted with different but related keys
Breaking the Enigma
General Techniques involved the use of the known daily settings with different operators. Major details include the machines used to crack Enigma were known as bombes
Breaking Cryptography - Other Methods:
Brute Force: Simply attempt to use every possible key until you find the correct one
Acquire the Key: If you can obtain the key, there is no need to worry about trying to crack the algorithm
Ways to acquire the key include:
Attacking the algorithm: Attack the algorithm to
Cryptographic Hash Function
A cryptographic hash function (CHF) is a mathematical algorithm that maps data of an arbitrary size (often called the "message") to a bit array of a fixed size (the "hash value", "hash", or "message digest").
Important Properties:
Must be deterministic
quick to compute the hash value for any given message
it is infeasible to generate a message that yields a given hash value
it is infeasible to find two different messages with the same hash value
Random Number Generators
Useful in cryptography – especially for stream
ciphersTruly random is hard to do, so we usepseudorandom number generators (PNGs)
One method is a Linear CongruentialGenerator
Steganography
Steganography literally means “coveredwriting”
The practice of hiding a message in such amanner that its very existence is concealed
Done by embedding the message in somemedium such as a document, image, sound
recording, or video
Steganography- History
long history of steganography In theHistories of Herodotus (430 B.C.):
There are many other examples as time went on in history, examples as shaving the head of a messenger, tattoo the message on his head, then let his hair grow back. The message would then be hidden
Steganography- Examples:
Two ways of hiding the message "Pershing sails from N.Y. June 1" Example 1:
President's embargo ruling should have immediate notice. Grave situation affecting international law, statement foreshadows ruin ofmany neutrals. Yellow journals unifying national excitement immensely.
uses the first letter of each word to hide each letter of the message. It is pretty easy to spot. Example 2:
Apparently neutral's protest is thoroughly discounted and ignored. Isman hard hit. Blockade issue affects pretext forem bargo on byproducts, ejecting suets and vegetable oils.
Steganography- Common Method
The most common method used in steganography is to hide a message in a picture Any data file can potentially be used if there is any "slack space“ or hidden fields
For pictures, each pixel (picture element) is represented by 1 or more bytes
If the least significant bit is used to encode the message, small variations in the picture may occur but the message will be hidden inside
Steganography - Pay attention to Yellow Dot Code
Pay close attention to the “Yellow Dot Code” (printer steganography) The Yellow Dot Code may have been used to identify Reality Winner, an NSA contractor, who stole andshared classified documents
There are many online tools that allow you to hide a message in an image
Accountability in Cyberspace
Make a note of the three types of indicators for attribution (technical, political, clandestine) The same indicators that could attribute an attack could be used by a nation-state to impersonate another country ◦ A variant of a “false flag” operation
Anonymity Vs. Privacy
Privacy, according to the Merriam-Webster Dictionary, is“the state of being alone” or “the state of being away from other people.” It’s about being able to reach a place of sanctuary where one is free from unauthorizedintrusion or public attention.
Anonymity, as “the quality or state of being unknown to most people” or “the quality or state of being anonymous
The two are clearly different. Privacy is the ability control what one discloses to whom and when, while anonymity is about one’s interactions with an environment of which one is part, but which one does not own or control
Free Speech Issues
The issues around anonymity and privacy on the internet are not technical in nature ◦ They are in the legal and ethical realm. You think anonymity on the Internet should be protected
ACLU v. Miller, Northern District, Georgia, ACTION 1:96-cv-2475-MHS In ACLU v. Miller, the American Civil Liberties Union got an injunction against the enforcement of a Georgia statute that prohibited a person from falsely identifying herself while sending e-mail, posting on the Internet, and more (one of the problems with the statute was that it was too vague).
Talley v. California, 362 U.S. 60 (1960) This case dealt with a Los Angeles city ordinance which required distributors of leaflets to fully identify themselves and provide a mailing address.
McIntyre v. Ohio Elections Commission, Syllabus, US Supreme Court.
Does the U.S. Supreme Court have jurisdiction in cyberspace?
Anonymity and Attribution -
When a state decides to attack another state, it is not concerned solely with its relative power to its adversary. An attacking state is concerned with the power of its adversary and its ability to conduct an attack against an adversary while maintaining anonymity.
Anonymity and Attribution -
Anonymity in cyberspace in the initiation and implementation phases of an attack provides the freedom to maneuver.
Politics and Remaining Anonymous
If we follow the logic of Thomas Rid that 'history does not know acts of war without eventual attribution,' then do cyber attacks constitute political acts? With anonymity being a central feature that influences the success of cyber attacks, does anonymity remove the political aspect of attacks?
Attribution and Cyber Defense
An anonymous actor is one who avoids attribution. The ability for states to respond to cyber attacks and their perpetrators is an important aspect of cyber defense.
Attribution Can Be A Secondary Priority -
The scenario is one in which the previously laid groundwork for a coordinated attack against U.S. critical infrastructure begins to take down vital U.S. systems coinciding with a foreign policy flap occurring with China.
The Dark Web -
Surface Web: The Surface Web (also called the VisibleWeb, Clearnet, Indexed Web, Indexable Web orLightnet,) is that portion of the World Wide Web that is readily available to the general public and searchable with standard web search engines.
Deep Web: The deep web, invisible web, or hidden web are parts of the World WideWeb whose contents are not indexed by standardsearch engines for any reason. The opposite term to the deep web is the surface web.
The dark web forms a small part of the deep web, the part of the Web not indexed by search engines, although sometimes the term "deep web" is mistakenly used to refer specifically to the dark web.
The Dark Web Conceptually -
Conceptually, we can think of this as an iceberg While there are many services that are in “open view” there are far more that are not
The Dark Web -& legitimate individuals
The Dark Web has been around for decades and has many purposes (besides criminal)
It can allow legitimate individuals who need to remain anonymous (ex. intelligence agents) to communicate Can allow for debate on controversial topics without fear of retaliation
The Dark Web Timeline --
just get a feel for the timeline Also, note that Bitcoin was quickly adopted by sites on the Dark Web
Onion Routing-
Remember how onion routing works ◦ Onion routing is an hybrid link encryption approach