#Cryptography #Lesson #Adversaries #Games
Welcome to cryptography lesson number two in this lesson we will be covering adversaries and games in order to show how cryptographic schemes can be analyzed to introduce us to adversaries and games let’s take a look at a short puzzle do you remember block ciphers from
Lesson 1 block ciphers take in a key and a plaintext message and use these values to generate an invertible ciphertext we previously looked at you could find the plaintext or ciphertext with knowledge of the key value now we will attempt to guess the key given a plaintext and the
Corresponding output ciphertext for this puzzle we will make it easy and show you the inside of the block cipher in use if you recall it is exactly the block cipher described in lesson 1 in this case the double carrots to the right mean that each character in the message
Is shifted to the right alphabetically K times we will also tell you that the key can only take on the values 0 1 2 or 3 can you guess the key for the following plaintext ciphertext pairs for the given examples the input characters are shifted to the right by 1 in all cases
Thus the key was 1 this puzzle is very similar to the key recovery game used to analyze the security of block ciphers in cryptography games are used to test how strong various cryptographic elements are then adversaries are challenged to win these games if an adversary can win
A game with a high probability then the strength of the cryptographic element is questionable in the previous puzzle the game was to determine the key given multiple plaintext ciphertext pairs and when shown the block cipher code you acted as the adversary by attempting to break the security of the scheme overall
Now let’s take a look how formal cryptographic games are organized to do this we will be going over an actual cryptographic game the key recovery game for a block cipher e the title for this game which indicates something about the purpose is kr sub e or key recovery
Against e every game begins with an initialize procedure which performs tasks one time and sets the scene for the game in this case the initialized procedure selects a que bit key at random where each of the K bits are either a 0 or a 1 it then sets a
Variable I which will be used as a counter to 0 as you can see initialize is typically used to set constant values that will be used for the duration of the game if any values are returned from the procedure then the adversary has access to them however in the case of
This game initialize does not return anything so the adversary does not get any extra information additionally every game has a finalized procedure which checks to see if an adversary has won the game or not this procedure is typically called once at the end of the game here the finalized procedure takes
In a guess at what the adversary believes to be the key this is K Prime the rest of the finalized code sets a win to true initially then it checks to see if the adversary of selected key will work to properly decode a set of messages which have been stored
Internally in the game if the key does not work correctly or if the stored messages are repeats the adversary will lose the game otherwise the finalized procedure will return that the adversary won the game in any given game there may also be zero or more Oracle procedures these are procedures which adversaries
Are allowed to call one or more times over the duration of the game these procedures typically reveal some information about the cryptographic scheme which is being analyzed that one could expect a real adversary to get their hands on easily in this case the Oracle procedure FN allows an adversary
To pass in a message and receive the corresponding ciphertext to that message the internals of this procedure do some bookkeeping to ensure that the adversary does not simply continue calling the Oracle on the same message then the block cipher is called using the secret key and the message that the adversary
Chose because the procedure returns CI we know that the adversary now has access to that ciphertext value finally every game has a formula associated with it that can be used to calculate the probability of success or the advantage of an adversary if the advantage is high or close to one
The adversary will win most of the time and the scheme is probably insecure if the adversary’s advantage is low or close to zero this generally shows a more secure scheme for this game the adversary is advantage for the key recovery game against a block cipher e is simply the same as the probability
The adversary a will win the game against the block cipher if the adversary always wins the advantage will be won if the adversary wins only half the time the advantage will be one-half and if the adversary never wins the advantage is zero now that the key recovery game has been explained let’s
Take a look at how an adversary might work to beat this game here you can see the code for adversary a using an exhaustive key search technique we will not dive too deep into the details of this adversaries code but we will go over what it does at a high level
Remember that because the initialized procedure did not return any values the adversary does not take in any inputs the first line of the adversary code does the following for Q queries it selects a message which is simply some binary representation of the number of the query it then calls the Oracle
Procedures for each of these queries passing in a message and storing the resulting ciphertext value the second part of the code is where this adversary gets the name exhaustive key search because we know that the keys are K bits long the adversary tries every possible
Key of that bit length for each key it checks if all the queries from the first part of the code work with the specified key that is it checks every possible key against a set of known plaintext ciphertext pairs when a key is found which works for all of the pairs then
The adversary knows which block cipher key to pass to the finalized procedure in order to win this code will return an advantage of one in all cases because every possible key is checked the correct result is guaranteed to come along eventually adversaries to these types of games as well as the calculated
Advantages of these adversaries are used to analyze cryptographic schemes if an adversary can be created for a game such as key recovery with a high advantage then the scheme we are investigating may not be secure or strong enough in the given example where the adversary used exhaustive key search
There is no obvious way to reduce the adversaries advantage however this does not necessarily mean that block ciphers are insecure since we can reason that if the number of possible keys is extremely large then the adversary cannot check all values in a reasonable amount of time thus we have learned something
Regarding the necessary key length of a block cipher new games can then be developed and analyzed to check the security of other aspects of these cryptographic schemes to review in this lesson we have learned that games adversaries and advantages are tools which are commonly used to test the security of cryptographic schemes the
Initialize and finalize procedures of a game are generally called once at the beginning and end of any given game Oracle’s are procedures which adversaries may typically use multiple times and any values returned from the initialize or Oracle procedures are available for use by the adversary hopefully you have grasped the gist of
How games and adversaries can be used in the field of cryptography see you in the next lesson
0 Comments