Understanding Multiple Right-Hand Sides in Linear Algebra

Exploring the concept of Multiple Right-Hand Sides (MRHS) in linear algebra, we delve into normal linear operations, algebraic attack conversions, and known plaintext-ciphertext pair attacks. Discover the significance of MRHS and its applications in solving systems of polynomial equations.

• Linear Algebra
• Multiple Right-Hand Sides
• Algebraic Attack
• Systems of Equations
• Matrix Form

lamberto Follow

Uploaded on Sep 10, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Abusing Linear Algebra with Multiple Right-Hand Sides John-Petter Indr y 1

2. Multiple Right-Hand Sides (MRHS) uses normal linear operations ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 Some important operations: ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 Addition Row swap Linear dependency Consistent vs inconsistent 0 = 0 : Consistent 0 = 1 : Inconsistent 2

3. As we have 52 variables in 96 rows, we will use Algebraic Normal Form (ANF) instead of Matrix Form ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 ?0 + ?3 + ?6 ?1 + ?4 + ?7 ?2 + ?5 + ?8 ?0 + ?3 + ?6 ?1 + ?4 + ?7 ?2 + ?5 + ?8 ?0 + ?3 + ?6 ?1 + ?4 + ?7 ?2 + ?5 + ?8 ?2 + ?5 + ?8= 0?0 + 0?1 + ?2 + 0?3 + 0?4 + ?5 + 0?6 + 0?7 + ?8 3

4. MRHS is a known plaintext-ciphertext pair attack, meaning we know the plaintext that created the ciphertext Known Known Want to know! 4

5. The first step of an algebraic attack is to convert the cipher into a system of polynomial equations 5

6. The first step of an algebraic attack is to convert the cipher into a system of polynomial equations ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?? ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?? 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 6

7. The first step of an algebraic attack is to convert the cipher into a system of polynomial equations 7

8. The first step of an algebraic attack is to convert the cipher into a system of polynomial equations 8

9. By combining the input and output to an Sbox into a matrix, we can use the definition of the Sbox to find the ? vector(s) (the RHS) a15 + a3 + a0 + k20 + k4 a15 + a12 + a13 + a1 +a0 + k21 + k5 a13 + a2 + a1 + k22 + k6 a14 + a3 + a2 + k23 + k7 a20 a21 a22 a23 = 0 = 0 = 0 = 0 = 0 = 1 = 1 = 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 9

10. By combining the input and output to an Sbox into a matrix, we can use the definition of the Sbox to find the ? vector(s) a15 + a3 + a0 + k20 + k4 a15 + a12 + a13 + a1 +a0 + k21 + k5 a13 + a2 + a1 + k22 + k6 a14 + a3 + a2 + k23 + k7 a20 a21 a22 a23 = 0 = 0 = 0 = 0 = 0 = 1 = 1 = 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 a15 + a12 + a3 + k16 +k0 a15 + a12 + a13 + a0 + k17 +k1 a14 + a13 + a1 + k18 +k2 a15 + a14 + a2 + k19 +k3 a16 a17 a18 a19 = 0 = 0 = 0 = 0 = 0 = 1 = 1 = 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 10

11. The Shard is the basic building block of MRHS A ? = ?0, ?1?2, ?3, , ?? a15 + a3 + a0 + k20 + k4 a15 + a12 + a13 + a1 +a0 + k21 + k5 a13 + a2 + a1 + k22 + k6 a14 + a3 + a2 + k23 + k7 a20 a21 a22 a23 = 0 = 0 = 0 = 0 = 0 = 1 = 1 = 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 NOT a matrix! It s a set of vectors, all valid solutions for this shard 11

12. The second stage is of algebraic cryptanalysis to solve this system of equations LHS: Stack on top of each other a15 + a12 + a3 + k16 +k0 a15 + a12 + a13 + a0 + k17 +k1 a14 + a13 + a1 + k18 +k2 a15 + a14 + a2 + k19 +k3 a16 a17 a18 a19 a15 + a3 + a0 + k20 + k4 a15 + a12 + a13 + a1 +a0 + k21 + k5 a13 + a2 + a1 + k22 + k6 a14 + a3 + a2 + k23 + k7 a20 a21 a22 a23 12

13. The second stage is of algebraic cryptanalysis to solve this system of equations a15 + a12 + a3 + k16 +k0 a15 + a12 + a13 + a0 + k17 +k1 a14 + a13 + a1 + k18 +k2 a15 + a14 + a2 + k19 +k3 a16 a17 a18 a19 a15 + a3 + a0 + k20 + k4 a15 + a12 + a13 + a1 +a0 + k21 + k5 a13 + a2 + a1 + k22 + k6 a14 + a3 + a2 + k23 + k7 a20 a21 a22 a23 13

14. In order to preserve the solution space, each vector in the first shards RHS must be combined with each vector in the second s RHS 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 14

15. Finding the solution to the system as a whole then becomes an iterative process of gluing and resolving linear dependencies Remember, all the normal Linear Algebra operations are available For the LHS, as long as they are within the same shard, the operations behave as normal/expected For the RHS, we treat each individual vector as a ? vector, and the operations behave as normal/expected Any ? vector which is inconsistent with the system, is removed: This one cannot be a solution to the full system 15

16. Finding the variables values is then equal to a lookup in the system of linear equations: A ? = ? ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?15 ??,16 ??,17 ??,18 ??,19 ??,20 ??,21 ??,22 ??,? ??,? = , , ??,0 ??,1 ??,2 ??,3 ??,4 ??,5 ??,6 ??,15 ??,0 ??,1 ??,2 ??,3 ??,4 ??,5 ??,6 ??,15 = = = = = = = = = = = = = = = , , All remaining vectors are a solution to the final system Due to false positives, there may be more than one remaining vector Other aspects of the cipher may allow for more than one solution , , ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?? ??,16 ??,17 ??,18 ??,19 ??,20 ??,21 ??,22 Questions? 16

17. Today, we no longer actively use MRHS. Instead we use Compressed Right-Hand Sides (CRHS) With CRHS The RHS is instead represented as a Binary Decision Diagram Not only drops rows, but also columns Still issues with memory Brand new CRHS tool almost done, paper in the works 17

18. Some results, 16 bit systems 18