3.7 Understand methods of cryptanalytic attacks

  • Brute force
  • Ciphertext only
  • Known plaintext
  • Frequency analysis
  • Chosen ciphertext
  • Implementation attacks
  • Side-channel
  • Fault injection
  • Timing
  • Man-in-the-Middle (MITM)
  • Pass the hash
  • Kerberos exploitation
  • Ransomware

.  Some of the cryptanalysis attacks include

  • Birthday.  Consider a set of values (not necessarily unique values), .  In any set , the possibility that at least two values are identical is .  If we have a set of two values, then the possibility that they are identical is .  As the set grows, the possibility that two entries will be identical also grows.  This idea came from the fact that in a room of 30 people, there is at least a 50% chance that two of them share a birthday.

    We can use this property to crack a hash function.  It is possible to find two different values that have the same hash.
  • Known Plain Text/Cipher Text.  If the hacker can intercept a portion of the plain text communication and the corresponding portion of the cipher, he can use cryptanalysis to decrypt the algorithm.  The hacker does not require the entire communication, only a portion.  Good encryption algorithms can mitigate this threat because they use large keys.  Once the algorithm and key are known, the hacker will be able to read future communications.

  • Cipher Text Only Attack.  It is difficult to reverse a good algorithm when we only know the cipher text.  The resulting ciphertext of a good algorithm is supposed to be random.  When it is not random, then we can apply frequency analysis.

  • Frequency Analysis.  Since certain characters are more common, a hacker can intercept the cyphertext and run a frequency analysis.  Consider that the letter e is the most common letter and the least common letter is q.  If our algorithm substitutes the letter b for the letter e, the most common letter in our cyphertext will be b.  The hacker can determine that the letter b in the cyphertext is actually e.  From there, he can guess some smaller words that may have the letter e at the end and reverse a few of the substitutions.  Eventually, the hacker can reverse the entire algorithm.

    If the hacker has access to the algorithm, he can send in many plaintexts and receive the corresponding ciphertexts.  If the algorithm is simple, then it is trivial to reverse it.  If the algorithm is secure, then it is practically impossible.

  • Chosen Ciphertext.  If a hacker has access, he can send in many ciphertexts into the decryption engine and obtain the corresponding plain texts.  He can then compare the plaintexts to the ciphertexts and look for patterns.  Some algorithms such as RSA-OAEP are known to be secure against the attack.

  • Rainbow Tables.  Recall that it is bad security practice to store passwords in plain text.  Passwords are typically hashed, and the hash is stored (the hash is not reversible). 

    But a hacker could generate a dictionary of passwords (common and uncommon) and calculate the corresponding hash for each one.  This dictionary is known as a rainbow table.  The hacker could then steal a hashed value and look up the corresponding password.

    Rainbow tables are readily available on the internet for passwords up to eight characters (every possible combination!) and rainbow tables of even longer passwords can be computed.

    To prevent the use of rainbow table attacks, modern password hash functions incorporate a ‘salt’.  The salt is a random set of characters appended to the end of each password before the hash is calculated.  The hash and the salt are stored in plain text.  If the hash database is compromised, the hacker would have to regenerate each rainbow table incorporating the salt into every password to make any sense of it.  This would be practically impossible.

  • Dictionary.  A Dictionary attack uses a list of predetermined passwords and brute force to guess the password.  The dictionary could consist of common words in the English language, especially common passwords such as “password”, “12345678”, and “abcd”.

    A hacker could create a custom dictionary based on the user account that he is trying to hack into.  For example, the dictionary could be customized to include the names of the user’s children, pets, vehicles, etc..

    Many organizations force users to choose complex passwords.  Password complexity could include

    • Not reusing a password

    • Including upper case letters, lower case letters, numbers, and special characters

    • Ensuring that the password meets a minimum length

    • Not using a person’s name, address, or username in the password

Yet, it is still possible to create a custom dictionary based on the password complexity requirements.  For example, if the user’s password was ‘donkey’, then a complicated password might be ‘D0nkey!’.  Users tend to substitute @ for a, 0 for o, 1 for l, and so forth in a predictable manner.

A dictionary attack can be prevented by limiting the amount of password attempts a user has before his account is locked out.  Of course, the dictionary attack could occur offline, or the hacker may have a way to bypass the incorrect password attempt count.

  • Brute Force.  A brute force attack is like a dictionary attack, except that the hacker attempts every password combination possible (based on the character set), starting from the letter a and working his way up until the password is guessed.  For example, the hacker will guess the password ‘sdfsfgdgsdfsdfd’, and then the next password would be ‘sdfsfgdgsdfsdfe

    The length of time for a brute force attack to be successful depends on the computing power available (how many passwords can be attempted every second) and the length of the password (how many passwords need to be attempted).

    An online brute force attack occurs against a live computer.  For example, consider Active Directory, a Microsoft system that stores user accounts on a central server.  When a user attempts to log in to an Active Directory-based computer, the computer validates the login credentials with the server.  On a successful login, the computer caches the correct credentials on the local computer.  If the computer is later offline (or off the local network), the user can still log in (the computer validates the login with the cached credentials).

    • In an online attack, the hacker would brute force the computer’s login while it is connected to the Active Directory server.  This attack would likely be unsuccessful because the server would notice the incorrect logins and disable the account.

    • In an offline attack, the hacker would brute force the computer’s login while it is not connected to the Active Directory server.  This attack may or may not be successful depending on the length and complexity of the password.

How to prevent

  • Offline attacks can’t be prevented.  Where possible, secure equipment so that it is not stolen.  Stolen equipment is more susceptible to offline attacks.

    • Enforce stronger password requirements (including special characters, numbers, upper/lower case letters).

    • Enforce a timer that delays the entry of passwords.  This can be accomplished at the software or hardware level, by hashing the password multiple times.

    • Offline data can be encrypted with a strong algorithm that takes several seconds to validate the password.  This would be a minor inconvenience to a user entering an incorrect password but would substantially slow down a brute force attack.

  • Implementation Attack.  Even if the algorithm is secure and the key is long enough, the cryptography can be broken if the implementation is weak.  A cryptography algorithm does not exist in a vacuum.  It must be installed as part of a software application or on some hardware.  If the software or hardware is not secure, then it can be exploited.

    For example, your web browser supports SSL or TLS for encryption.  When developers wrote the code for your web browser, they implemented SSL or TLS.  Rather than reinvent the wheel, they most likely took an open source library that provided the encryption functions and pasted it in.

    If your web browser has bugs, or if the library has bugs, then a hacker could exploit them to obtain your data, even if the algorithm is secure.

    The analogy is that we install a secure lock on our door, but don’t put enough screws to hold in.  A thief won’t be able to pick the lock but can loosen it and then the lock falls off.

    Some common implementation weaknesses

    • We use a version of an algorithm that is weak

    • We use a strong algorithm, but a weak key

    • We use an algorithm that requires random numbers, but we don’t generate the numbers randomly

    • We use an algorithm that we think is strong (and that people in the security community think is strong), but it contains a hidden backdoor

    • We use elliptic curve cryptography, but we don’t use a strong curve

  • Side Channel Attack.  A side-channel attack is a type of implementation attack.  We can monitor a system to see how it behaves.  These types of attacks are complicated and use expensive equipment.  Some side channel attacks

    • Monitor the power consumption of a processor.  We can create a graph of the power consumption to analyse the encryption and decryption process.

      Smart cards are vulnerable to power consumption attacks.  A smart card will draw different amounts of power depending on whether it is processing a 0 or a 1 in the algorithm.  If we monitor the power consumption (and we can do so by tampering with the power supply), we can read the key.

    • Monitor the electromagnetic radiation.  We can create a graph of the radiation produced by the processor to analyse the encryption and decryption process.

      The computer will emit different types of radiation depending on whether the processor is using a 0 or a 1.  RSA and many other asymmetric algorithms are vulnerable.

    • Monitor the sound produced by the processor.

    • Cold boot attack.  The processor may store unencrypted data or the encryption / decryption keys in the RAM.  If we shut off the computer and quickly cool down the RAM, we might be able to read the unencrypted data for up to five minutes.

    • Fault Injection.  A fault injection happens when we stress the encryption circuitry enough.  Some ways that we can stress it

      • High temperature

      • High or low voltage

      • High or low current

      • Overclocking

      • Introducing an electric or magnetic field

      • Radiation

The stress will cause the processor to output inaccurate data, which we can analyse to determine the contents of the memory.  If we are lucky, we might stress the processor enough to give up its encryption keys.

This is a good attack against the iPhone’s secure enclave processor.  But it requires us to physically access the chip and remove the coating to expose the internal components.

  • Timing.  A timing attack is a type of side channel attack where we analyse the amount of time it takes a processor to execute encryption and decryption operations.  If we are precise enough with our measurements, we can determine the contents of those operations.

    It is difficult to design an algorithm that is not vulnerable to timing attacks because the processor ultimately decides how to execute each step of the algorithm, and the execution time usually depends on the complexity of the data.  Also, many developers try to optimize their algorithms so that they execute as quickly as possible, because this conserves system resources.

    We must try to implement constant-time functions.  A constant-time function is a function that takes the same amount of time to execute, regardless of the underlying data.  This is easier said than done

  • Man-In-The-Middle.  As mentioned earlier, if the communication is encrypted and uses public key cryptography (such as Apple iMessage), a man-in-the-middle attack is more difficult.  Users encrypt messages with public keys (which they obtain from a central directory).  If Alice wants to send a message to Bob, she obtains Bob’s public key from Apple, encrypts the message, and sends it to Bob.  Bob uses his private key (which only he knows) to decrypt the message.  Eve can intercept the message

    • She generates her own public and private keys

    • She hacks into the central directory and changes Bob’s public key to her own.  She copies Bob’s public key

    • When Alice queries the directory, she receives what she thinks is Bob’s public key (but is in fact Eve’s public key)

    • Alice encrypts the message with Eve’s public key and sends the message to Eve (thinking that she is sending it to Bob)

    • Eve decrypts the message, reads it, and then encrypts it with Bob’s public key

    • Eve sends the message to Bob

    • Bob receives the message, thinking it came from Alice and decrypts it with his own private key

    • Eve does the same thing with Alice’s public key so that she can intercept messages that Bob is sending to Alice

  • Pass the Hash.  Remember that it is a bad security practice to store a password in plain text.  Instead, we hash the password and store the hash.  When a user attempts to log in, we hash the password he entered and compare it with the one on file.  If the hash is stolen, a hacker will only see the hash and not the original password.

    But a hacker can capture the hash that was used in the authentication or registration process.  The hacker then injects the hash into a website or Windows process to gain access to the computer, without ever knowing the password.

  • Kerberos.  Kerberos is a protocol that allows clients and servers to authenticate with each other and prove their identities.  The Kerberos protocol protects against eavesdropping and replay attacks.  Kerberos uses UDP port 88.  Kerberos provides encryption over an unsecure network.

    All versions of Windows including Windows 2000 and later use Kerberos for authentication by default (although other protocols can be used).  Kerberos is used to join a client to a Windows domain.

    Most common versions of UNIX also use Kerberos.

    If a client wishes to connect, the following procedure is followed. 

    • The client calls the Authentication Server (AS) to obtain authentication. 

    • The authentication server takes the client’s username and sends it to another server called the Key Distribution Center (KDC). 

    • The KDC runs a service known as the Ticket-Granting Service (TGS), which maintains a secret key. 

    • The KDC issues a ticket known as the Ticket-Granting Ticket (TGT) and encrypts it with the secret key. 

    • The encrypted key is sent back to the client.

How it actually works

  • A user would like to log in to a Windows machine, with a username and password.  Even on a corporate network, the password should not be sent to the server (domain controller) in plain text.

    • The user enters his username and password

    • The Windows machine encrypts/hashes the password

    • The client sends the user ID to the authentication server (in plain text).

    • The Authentication Server verifies that the username is in the database.  If the user is in the database, the AS creates a secret key from the hash of the user’s password stored in the database and returns to the client the following messages

    • A TGS Session Key, which is encrypted with the newly created secret key (Message A)

    • A TGT, which includes an expiry date, the client’s network address, all encrypted with the TGS’s secret key (Message B)

    • The client takes the TGS Session Key and decrypts it with the hash of the password entered earlier.  If the client entered the wrong password, then the client will be unable to decrypt the TGS Session Key, and the user will have to try again.

    • The client uses the decrypted TGS Session Key to communicate with the TGS

When the user is requesting additional services

  • Client sends additional messages to TGS

    • Message C is the TGT from Message B and the ID number for the requested service

    • Message D is the authenticator (client ID and time stamp), encrypted with the Client/TGS

    • TGS obtains Message B from Message C and decrypts it (Only TGS has the encryption key for Message B).  TGS uses this to decrypt Message D.

    • If the Client ID in Message C and Message D match, then the client is authenticated

    • TGS sends additional messages

      • Message E is the Client-to-Server Ticket, which includes the client ID, network address, and expiry, encrypted using the service’s secret key

      • Message F is the Client/Server Session Key, encrypted with the Client/TGS Session Key

    • The client takes Message E and Message F and uses them to authenticate with the Service Server

    • The client sends

      • Message E from before

      • Message G, which is an authenticator, including the client ID, and timestamp

    • The SS decrypts Message E with its own secret key and obtains the Client/Server session Key.  It uses this key to decrypt Message G.  If they match, then the client is authenticated with the service

    • The SS sends Message H to the client, which includes the timestamp in Message E, encrypted with the Client/Server Session Key

    • The client decrypts Message H.  If the timestamp on Message H is correct, then the client knows it can trust the server.  A rogue agent could issue a fake message but would not be able to match the timestamp.

The encrypted key will expire, but if the user is logged in, the key will renew (the client will automatically contact the server and obtain an updated key).

To communicate with another node, the ticket is sent back to the service.    The TGS verifies that the user is permitted to access the service and then sends the ticket to the Service Server (SS).

Kerberos has a single point of failure, which is the authentication server. 

Kerberos also requires the clients, servers, and services to be responsive (since timestamps must match on all devices).  That means that all devices must have synchronized clocks.  If a client/server issues a ticket/message with a timestamp that doesn’t match due to a clock that is out of sync, then the system will fail.  Clocks must not be more than five minutes apart.

We can steal a Kerberos ticket or TGT from a user’s device by dumping its credentials and then try to gain access to other resources

  • A Silver Ticket is used to generate tickets that access external resources

    • A Golden Ticket allows us to grant a TGT for any Active Directory Key Distribution Service

We can also create tickets using other types of information such as hashes.

  • Ransomware.  Ransomware is not really a cryptographic attack except that the hacker will use cryptography to lock up all of your data.

  • Rubber Hose.  If you beat somebody with a rubber hose, they might give you the secrets.  This does not involve cryptanalysis but is very effective.  If that person is responsible for implementing the cryptography, and you have a big enough hose, you can force them to implement a weak algorithm.