Project topics and materials
Get Complete Project Material File(s) Now! »
The Solitaire Keystream Algorithm
Solitaire generates its keystream using a deck of cards. Each card in the deck (54 cards, including the 2 jokers) corresponds to a number 1 to 54. We could for instance use the bridge order of suits: clubs (1 – 13), diamonds (14 – 26), hearts (27 – 39), spades (40 – 52), Joker A = 53 and Joker B = 54. To initialize the deck, we have to arrange the cards in the initial configuration representing the initial state. The initial state in this instance corresponds to an element of the permutation group S54, meaning a state of 54 cards. It is recommended that the initializing state of the deck be randomly chosen in order to achieve a maximum of unpredictability. To produce a single output from the keystream algorithm, the following steps should be achieved:
1. Find the A joker and move it one card down. If the joker is the bottom card of the deck, move it just below the top card.
2. Find the B joker and move it two cards down. If the joker is the bottom card of the deck, move it just below the second card. If the joker is one up from the bottom card, move it just below the top card.
3. Perform a triple cut. That is, swap the cards above the first joker with the cards below the second joker.
4. Perform a count cut. That is, look at the bottom card and count down from the top card that number. Cut after the card that you counted down to, leaving the bottom card at the bottom position.
5. Find the output card (number). To do this, look at the top card. Count that number of cards from the top. The obtained card, is the output card. If the cards is a joker, restart Step 1.
A keystream of numbers can be generated by repeating the procedure above. Solitaire designer defines an optional input named passkey, which is used for scheduling the order of the deck. To obtain the same order of the deck, both communication parties should share the same passkey. The use of this input is like performing the four first steps of Solitaire, but instead of extracting an output number (Step 5), the Step 4 is performed another time, based on the first character of the passkey. These operations are repeated once for each character of the passkey. As stated before, Solitaire keystream is intended to be used as a PRNG for the KEDGEN2 protocol. Since an automated model checking tool will be used to verify the KEDGEN2 protocol (cf. Chapter 4) and this model uses a symbolic approach that could not deal with computational properties (i.e., the cryptographic primitives of the PRNG), it is crucial for us to study the probabilistic characteristics of Solitaire (see the following section), mainly the cycle length of the keys generations in order to adapt the protocol accordingly (the threshold length N). Finally, since a PRNG goal is to ensure the unpredictability of its generated outputs, the correctness of the PRNG can be measured with statistical tests that are applied to the output keystream (cf. Section 4.4).
Solitaire Model in Group Theory
One natural way of modeling the Solitaire keystream algorithm is to give a group theoretic point of view. This line of investigation was extensively used in algebraic cryptanalysis of the Advance Encryption Standard (AES) [42]. In [151], the authors also used this approach in their investigation of the Solitaire algorithm.In this theoretical framework, the state function F(t) at t’th keystream number generation step is an element of the permutation group Sn, where n is the number of cards in a deck. The state function F is composed of four transformations: F1, F2, F3, F4 which correspond to the four steps of the keystream algorithm. Clearly, if a cycle of length m exists, we would have S(t + m) = S(t), o(t + m) = o(t) from some t’th number onwards. Here, o(t) denotes the t’th number in the output keystream, and S(t) the corresponding Solitaire state. Thus, the task of detecting a cycle in the keystream is equivalent to finding a repetition of the Solitaire state at some regular time intervals. This approach turns out to be computationally feasible for us when the number of cards is less than 16 (i.e. n 16, including the jokers, cf. Section 3.4.3).
Let o(t) be a keystream element within a cycle, and S(t) the corresponding Solitaire state. The cycle length which contains o(t) is equal to the size of the orbit generated by < S(t) > acted under the transformation F. In [151], the authors gave some algebraic descriptions of the orbits generated by individual actions Fi. At present, a complete algebraic description of those orbits generated by < F = F1, F2, F3, F4 > does not exist in the literature. The best that is possible to do theoretically is to write down the trivial bound (i.e., the maximum cycle length is necessarily less than the group order |Sn| = n!). There are some evidences from our simulations shown in the next section, which suggest
that the orbit sizes are growing exponentially with respect to n.
Cycle Detection of Solitaire Keystream
The security of the Solitaire keystream based PRNG (to prevent key-recovery attacks) depends on the cycle length of a keystream. It is considered as secure if the best key recovery attack is computationally infeasible (requires a number of queries or a running time too large to make the attack practical). Thus, to make key recovery by exhaustive key search computationally hard, we should calculate the cycle value and prevent the adversary from reaching it. In this section, we propose a probabilistic cycle detection method. The principle of the cycle detection algorithm is: if a cycle of length m exists, we would have: S(t + m) = S(t), o(t + m) = o(t) from some t’th number onwards. Here S(t) denotes the state of keystream generation at t’th step, and o(t) the t’th number in a keystream output. For a fixed initial configuration, we could output S(t), o(t), t 1 in a given file. The cycle detection in Algorithm 1 takes a keystream as an input, and outputs a cycle length when it is found. We have implemented the algorithm in Perl, as Perl is extremely efficient in tasks such as line pattern grep, and pattern mining within a keystream file. The algorithm starts by randomly selecting a line L1 at position i1 where 1 i1 . Here, is an algorithm parameter that will be explained later. The algorithm then tries to pattern match among the rest of the lines, and finds L2, …,L at the positions i2, i3, …, i within the keystream, which are identical to L1, i.e. S(i1) = · · · = S(i) and o(i1) = · · · = o(i). The random selection step in Algorithm 1 is justified because any keystream number is equally likely to be in a cycle, cf. Section 3.4.1. The algorithm parameter is a stop counter, which stops the algorithm after number of matches are found. This parameter is designed to increase the algorithm efficiency, as now the algorithm may well terminate before the end of the keystream is reached. In fact, computation efficiency turns out to be crucial in exhaustive search scenarios as those explained in the cycle detection results.
Table of contents :
1 Introduction
1.1 Context and Motivation
1.2 Challenges
1.3 Contributions
1.4 Organization
I A Key Establishment and Derivation Protocol for Passive RFID Tags
2 State of the Art
2.1 EPC Gen2 Standard
2.1.1 Structure of the Electronic Product Code
2.1.2 Tag and Reader Communication
2.1.3 Flawed EPC Gen2 Security Model
2.2 Symmetric Cryptography
2.2.1 Security Goals
2.2.2 Symmetric Cryptography Primitives
2.3 Pseudo-Random Number Generators
2.3.1 Main Properties
2.3.2 Related Work on PRNGs for Constrained Devices
2.4 Key Establishment Protocols
2.4.1 Key Establishment Techniques
2.4.2 Related Work on Key Extablishment Protocols
2.5 Verification Approaches
2.5.1 Symbolic Approach
2.5.2 Automated Verification Techniques
3 KEDGEN2: A Key Establishment and Derivation Protocol
3.1 System Assumptions
3.1.1 Revised Security Model
3.1.2 Adversary Model
3.2 Targeted Security Properties
3.2.1 Mutual Authentication
3.2.2 Secrecy of the Master Key
3.2.3 Forward Secrecy
3.2.4 Backward Secrecy
3.3 The KEDGEN2 Protocol
3.3.1 Modeling the Key Generation Function
3.3.2 Protocol Components
3.3.3 Protocol Description
3.3.4 Security Mechanisms
3.4 Solitaire Keystream as a PRNG
3.4.1 The Solitaire Keystream Algorithm
3.4.2 Solitaire Model in Group Theory
3.4.3 Cycle Detection of Solitaire Keystream
3.4.4 The Solitaire Keystream Generator
4 Verifying the Security of the KEDGEN2 Protocol
4.1 Verifying the Security of KEDGEN2
4.1.1 Checking Tool
4.1.2 HLPSL Format
4.1.3 Output Format
4.1.4 Our HLPSL Specification
4.2 Evaluation Results of the KEDGEN2
4.2.1 Mutual Authentication
4.2.2 Secrecy of the Master Key
4.2.3 Forward Secrecy
4.2.4 Backward Secrecy
4.3 Comparative Discussion
4.4 Evaluation Results of the Solitaire PRNG
4.4.1 Statistical Testing Tool
4.4.2 Statistical Tests
4.4.3 Difference between original and adapted Solitaire version
II Privacy-enhanced RFID Middleware in the EPCglobal Networks
5 State of the Art
5.1 EPCglobal Network Architecture
5.1.1 EPCglobal Network Components
5.1.2 Intra and Inter Organizational Data Aggregation
5.2 The Filtering & Collection Middleware and its Interface
5.2.1 The EPCglobal Application Level Event Interface
5.2.2 Privacy Control Limitations in EPCglobal Specifications
5.2.3 Related Work on Middleware Implementations
5.3 Privacy Issues and Regulations
5.3.1 Privacy Approaches
5.3.2 Regulations and Guidelines Worldwide
5.4 The Privacy Model
5.4.1 The OrBAC Model
5.4.2 Privacy Contextual Management
6 Privacy-enhanced Control into the Filtering & Collection Middleware
6.1 Motivation
6.2 Introducing Privacy in the EPCglobal Middleware
6.2.1 Scenarios for Collecting Data
6.2.2 Privacy Dimensions in the Middleware
6.2.3 Privacy Dimensions in the Event Cycle Specification
6.3 Privacy Policy Specification
6.3.1 Motivating Scenario
6.3.2 The OrBAC Specification
6.4 Privacy-enhanced Filtering & Collection Middleware
6.4.1 Privacy Controller Activities
6.4.2 Privacy Control for Subscriptions
7 Platform and Implementation
7.1 The Fosstrak Platform
7.1.1 Fosstrak Middleware Modules
7.1.2 Fosstrak Event Cycle and Reports Generators
7.1.3 Sequence Diagram of Reports Generation
7.2 Privacy Controller Implementation in Fosstrak
7.2.1 Modifications in the Fosstrak Server and Client
7.2.2 Testing Scenario in a New Sequence Diagram of Reports Generation
7.2.3 Obtained Results
7.3 Performance Evaluation
8 Conclusion and Perspectives
8.1 Main Results
8.2 Perspectives
A The Block Cipher, a Pseudo-random Permutation
B EPC Data Representation
C The Correctness Criteria
D Deploying the Fosstrak ALE Middleware with the LLRP RFID Reader
E Résumé de la Thèse
List of Publications
Bibliography
