Key Cracking: Brute Force

Learning Goals

• Brute-force attack exposing the weaknesses of basic encryption
• Importance of the strength of a cipher's algorithm and the secret key

Description

Being a rudimentary cipher, Caesar cipher is easily susceptible to a host of attacks. The Caesar cipher has a very small key space, as there are only so many single shift values that can be chosen even moving into ASCII characters. Therefore, it is trivial for a computer program (or even humans) to explore the key space and find out the encryption key.

In this unit, we demonstrate Caesar cipher's weaknesses and provide solutions.

Glossary

• brute-force attack
• key space
• character encoding

Required/Authorized Commands

• listen
• set key
• encrypt
• decrypt
• encrypt++
• speck encrypt

Activities

• Discussing Key Cracking
  • Frequency Analysis: in a longer message especially, by examining how often letters come up in the encrypted text and comparing it to the data of percent likelihood for a particular letter to be used in English words, we can make educated guesses on decryption. This can be assisted by examining either spaces between words that have been encrypted or, if you can still see the spaces as plain text, by considering the length of common words for the particular application ("set" and "speed" in particular for the robots).
  • Brute Force: alternatively, we can just go through all possible key values looking for a decrypted text that is what we'd expect to see (such as "set speed")
  • Character Encoding: utilizes the ASCII table
• Brute Force in Action
  • By this point, students might have already discovered that given the limited set of shift values in the ASCII implementation of the cipher, they can break each other's encryption by brute-forcing the key.
  • One option is a partially known plain-text attack
    • Capture the encrypted command
    • Cycle through all the shift values until you get a sensible text
    • Use that value to encrypt messages and attack the robot
  • The other option is to encrypt your command with different shift values and query the server until a true acknowledgment is received from the server. This would mean that the key had been discovered.
• Mitigation Strategies
  • There are different strategies to protect against brute force attacks to a good extent.
    • Increased key space by using encrypt++ and multiple keys at once
    • Reducing the key lifetime by changing it automatically and frequently during operation
    • Basically, any other improvements to the cipher used and quality of encryption
• Example: Shift Array
  • A simple way of enforcing the Caesar cipher that we have is to modify it to use a list of shift values. Instead of shifting all the characters by a constant shift value, we will loop through a series of shift values and shift each character differently, making the search space for a brute force attack much bigger. The longer the list of shift values, the harder it would be to crack. Incorporating this technique means that a dumb brute-force attack in NetsBlox would take long enough to make it infeasible.

Next Steps

• Other simple ciphers
• Frequency analysis
• Known plain-text attack