Skip to main content

Questions tagged [algebraic-attack]

An algebraic attack is a method of cryptanalysis against a cipher 1)expressing the cipher operations as a system of equations. 2)substituting in known data for some of the variables. 3)solving for the key.

Filter by
Sorted by
Tagged with
1 vote
1 answer
95 views

Is it possible to break a DSA with k that increases statically?

I am currently studying cryptography. I came across this problem: I had an exercise that as a vulnerability had that k is generated every 10 seconds: ...
Edoardo's user avatar
  • 11
1 vote
1 answer
107 views

How does big Galois groups yield better security in NTRU Prime?

I'm still kinda new to Galois theory so I apologize if this question is very obvious to some people. Basically I'm reading this paper by the NTRU Prime team and in section 2.5 it's explaining how ...
faust's user avatar
  • 13
1 vote
1 answer
38 views

Data fingerprint using multiple multilinear polynomials

Related to this question. I'm trying to find a way to use this fingerprint system without a second pre-image attack. Assume I have a set of elements $V = [v_0, v_1, v_2]$ in $\mathbb{F}_p$. Assume the ...
vimwitch's user avatar
  • 139
2 votes
2 answers
1k views

Time Complexity of Exhaustive Search Algorithm

I have the sets $S_1=\{2,10,20,6\}$ and $S_2=\{25,26,20\}$ and I want to find which numbers sum to make 32. This is very easy by inspection; 6 and 26. It seems similar to the Knapsack problem, but I ...
MeBadMaths's user avatar
0 votes
1 answer
222 views

Finding Multiplicative Inverse In Field

Consider the finite set Z_257 of non-negative integers less than 257. The number 257 is a prime, so Z_257 forms a field with addition and multiplication mod 257. How can I use the Extended Euclidean ...
hollyjolly's user avatar
1 vote
1 answer
98 views

DH: Is it possible to solve for A private if all other variables are known with 90-bit modulus

$g^{ab} \pmod{p} = B^a \pmod{p}$ where all variables are known except $a$. In this case, I have an equivalent value for $a'*b'$, but this is not the same as the real values of $a*b$ due to the modulus....
Tom Smith's user avatar
1 vote
0 answers
70 views

Help on Algebraic Side Channel Attacks

I am a master student in computer security, I am preparing a dissertation thesis in the theme is: Algebraic cryptanalys by auxiliary channels, I need reference on this theme (book, thesis, ...), and ...
Frih Osmane's user avatar
1 vote
0 answers
114 views

Symbolic computation in finite fields [closed]

What I want to know is how to perform symbolic finite field computations in SAGE math? Such computations are required in building algebraic models for cryptanalysis. To explain this mathematically ...
Viren Sule's user avatar
0 votes
0 answers
54 views

Symbolic models and security under algebraic attacks

It seems that algebraic attacks against cipher algorithms have not succeeded in practically breaking ciphers. The reason primarily is that the algebraic models of ciphers under with a known plaintext ...
Viren Sule's user avatar
4 votes
2 answers
1k views

What is linearization attack

I know that In cryptography, the linearization attack is a method of cryptanalysis for block ciphers I am looking for an example of linearization attack couldn't find it online Could anyone ...
user avatar
4 votes
0 answers
248 views

Solving not so much overdetermined system of multivariate polynomial equations

I'm studying algorithms solving multivariate equations. I'm stuck in solving overdetermined set of quadratic equations. Concretely, with the number $n$ of variables, the number of equations is $m=\...
wooa0923's user avatar
  • 173
2 votes
1 answer
100 views

What is the difference between the 23 bi-affine and the 39 fully quadratic equations of the rijndael sbox?

In Cryptanalysis of Block Ciphers with Overdefined Systems of Equations Nicolas Courtois and Josef Pieprzyk define 23 so called bi-affine equations (in Appendix A of the paper) between the input x and ...
ph_0's user avatar
  • 145
2 votes
0 answers
203 views

How can the Rijndael SBox be written as a linearized polynomial?

In Cryptanalysis of Block Ciphers with Overdefined Systems of Equations Nicolas Courtois and Josef Pieprzyk state (in Appendix A) that the Rijndael SBox can be written as a "linearized polynomial" $S(...
ph_0's user avatar
  • 145
3 votes
1 answer
1k views

Degree vs index of regularity

I'm studying the multivariate cryptography and specifically attacks using Groebner basis. On the complexity of such direct attacks, it is well-known that the most important parameter is the degree of ...
wooa0923's user avatar
  • 173
2 votes
0 answers
78 views

Algebraic Attack on Mix Mode Modular Arithmetic

I have a toy cipher that comprises of Mix Mode Modular Arithmetic (bit similar to IDEA including, Addition Modulo $2^{n}$ , Multiplication Modulo $2^{n}$ , Subtraction Modulo $2^{n}$ and circular ...
R. Sam's user avatar
  • 389
2 votes
0 answers
106 views

Using XL Algorithm to solve overdetermined systems, simple example required

Can someone give an example of how the XL algorithm is used to solve an overdetermined system as apposed to just a general case? I have a fairly good understanding of how steps of the algorithm work, ...
d_s_m's user avatar
  • 33
3 votes
1 answer
387 views

Need an XL Algorithm example

could anyone give me a small example with actual numbers and variables over a finite field of how the XL algorithm is used to solve overdetermined systems? And the steps involved. I understand the ...
Guneet SIngh Uppal's user avatar
4 votes
0 answers
123 views

Сryptanalysis of Hill's method [closed]

The brutal ciphertext is given. The text volume is more than 6000 characters. It is known that the text is encrypted with a 7x7 matrix. Unknown key and plaintext. Is it possible to crack this code? ...
DisplayName's user avatar
4 votes
2 answers
307 views

(Impossibility of?) Associative Pseudorandom Permutation

I'm not sure whether this had been a long-standing open problem in cryptography. Definition An associative pseudorandom permutation $f(k,m)$ is a permutation such that: $f(k_1, f(k_2, m)) = f(f(...
DannyNiu's user avatar
  • 9,451
1 vote
0 answers
84 views

Are low degree I/O relations in AES possible?

If I restrict the degree of each monomial to say 4 or 5 at maximum. Is it then actually possible to write down the I/O relations for an AES S-box?
Riddhi Ghosal's user avatar
2 votes
0 answers
76 views

Can someone help me understand how to get the I/O relation equations in DES S- boxes

I am referring to the equations that have been discussed in Nicolas T. Courtois and Gregory V. Bard's Algebraic Cryptanalysis of the Data Encryption Standard (in proceedings of Cryptography and Coding ...
Riddhi Ghosal's user avatar
15 votes
4 answers
3k views

Generate ANF from SBox

Given an SBox, how can I generate its component equations (in ANF)? For example, let's say I have this SBox: 6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11 Then, the equations are: $y_0 = x_1 ...
hola's user avatar
  • 603
3 votes
1 answer
283 views

Function to polynomial equation in GF(2)

Let F(a,b,c,d,e) be a function that returns the ith bit of 0x3A5C742E, where ...
mapjoe's user avatar
  • 33
1 vote
0 answers
334 views

Algebraic Attacks against ARX

I have not seen much about algebraic attacks against ARX ciphers. How would ARX ciphers compare in algebraic security to AES or Present or Simon?
user3201068's user avatar
4 votes
2 answers
3k views

Issue implementing Pollard's Rho for discrete logarithms

I've been trying to implement Pollard's Rho recently. The original idea was to implement the code in several languages and put it up for everyone to see for educational purposes. I first took to ...
cheater's user avatar
  • 143
1 vote
1 answer
170 views

Derive $x$ when given $g,g^x$ and $g^{(1/x)}$?

If an adversary has access to the generator g of a group G and is given access to $g^{x}$ and $g^{(1/x)}$, will it make it any easier to derive the value of $x$ compared to when he had access to only $...
chisky's user avatar
  • 123
1 vote
1 answer
140 views

Difference of full codebook and non full codebook

While reading a paper about Dynamic cube attack, I saw two terms: full-codebook and non-full-codebook attacks. What do they mean? What is the difference? Regards
Saeidmscs's user avatar
  • 119
8 votes
1 answer
7k views

Small subgroup confinement attack on Diffie-Hellman

I am trying to understand the small subgroup confinement attack on the Diffie-Hellman algorithm. I will present the attack and try to explain why it works. Small subgroup confinement attack on the ...
Raoul722's user avatar
  • 2,836
3 votes
1 answer
142 views

Algebraic cryptanalysis on public-key schemes

The book Algebraic Cryptanalysis (Bard, G.V.; Springer, 2009) speaks about transforming a symmetric scheme into a system of polynomial equations and solving these equations to break the scheme. But ...
Marcellus's user avatar
  • 264
2 votes
1 answer
705 views

algebraic attacks for mixed operations (mod 2 and mod 256) [closed]

If a cipher has mixed operations, e.g $\oplus$ (addition mod $2$), and addition modulo $2^8$. How we we going to express them mathematically? Thanks in advance!
meta_warrior's user avatar
11 votes
2 answers
1k views

Evaluating Algebraic Complexity of a S-box

While studying the design and the desirable properties of an AES S-box , I came to know that Algebraic Complexity is also an important property of an S-box which is usually considered while evaluating ...
m2n's user avatar
  • 111
26 votes
4 answers
7k views

How Brittle Are LCG-Cracking Techniques?

There are published techniques for cracking LCGs, but to my eye those techniques seem very brittle — very minor changes can add nonlinearity that renders techniques like the LLL algorithm unusable. ...
Charphacy's user avatar
  • 546
4 votes
1 answer
131 views

What is the Geometric Generalised T' Method?

This page by Nicolas T. Courtois mentions Geometric Generalised T' Method. It is described as an advanced geometric algorithm, never published, for finding extra linearly independent equations at ...
max taldykin's user avatar
6 votes
1 answer
593 views

How do you find the inverse degree of a hash function?

I am trying to learn cryptanalysis on the Keccak hash function. One of the papers on zero sum distinguishers talks about Keccak having inverse degree of 3. I am unable to figure this out: how do you ...
Soham's user avatar
  • 255
4 votes
2 answers
2k views

DSA signatures with related k and unknown payloads

Suppose that we are given DSA parameters $p$, $q$, $g$, a public key $y = g^x$, and two signatures $(r_1,s_1)$ and $(r_2,s_2)$. We are told that $(r_1,s_1)$ and $(r_2,s_2)$ were produced by related ...
Gilles 'SO- stop being evil''s user avatar
4 votes
1 answer
4k views

Attack on DSA with signatures made with k, k+1, k+2

For homework, I'm asked to find the private key, $x$, in a DSA digital signature scheme. In the particular instance, we are given the parameters $p$, $q$ and $g$, the public key $g^x$, 3 messages $(...
user1136342's user avatar
7 votes
1 answer
832 views

Is SHA-1 still practically secure under specific scenarios?

It is conjectured that SHA-1 has been broken from the "research" perspective, but not in the real world; that is, there exists an algebraic attack that explores weaknesses on its algebraic ...
curious's user avatar
  • 6,200
5 votes
2 answers
354 views

Determine complexity of a SAT problem

Is there a standard way to determine a complexity of the specified SAT problem? I'm researching algebraic cryptanalysis and came to solving multivariate quadratic equation systems using CryptoMiniSat. ...
rkiyanchuk's user avatar
2 votes
1 answer
150 views

Is it possible to spoof an identity cert modulus?

I was looking at FOAF+SSL and wondering if its possible to spoof the modulus of the browser certificate so that the FOAF and browser certificate's modulus match?
Tyler Gillies's user avatar
3 votes
2 answers
265 views

Background for modular arithmetic function

I'm investigating this function: $a := ((b\cdot c) \bmod k) - (b \cdot c)/k$ where $/$ indicates integer division. Two things I've noticed: It's equivalent to multiplying a·b, and then ...
S. Robert James's user avatar
12 votes
1 answer
1k views

XSL on serpent and rijndael - which is most affected?

So I've often looked at serpent and thought it was a very strong contender in AES. Not so long ago I was looking for evidence as to why it didn't beat rijndael. So far, the closest I've got answering ...
user avatar
15 votes
2 answers
874 views

Why is there an enormous difference between SAT solvers?

SAT solvers are very important in algebraic attacks, for example walksat and minisat. However, when solving the benchmark problems available here there is an enormous performance difference between ...
ir01's user avatar
  • 4,022
7 votes
2 answers
345 views

Are there any tools for expressing the cipher operations as a system of equations?

The first step In Algebraic-attack is expressing the cipher operations as a system of equations. Is there an automated tool to do this?
ir01's user avatar
  • 4,022