Questions tagged [cryptanalysis]

Analysis of individual security aspects of a cipher or algorithm, not the security of a cipher or algorithm in general (which would lean towards “algorithm-design”).

186 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13
votes
0answers
189 views

Space complexity of quantum collision search?

Is there a known way to reduce the space complexity of quantum collision search (PDF) beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below ...
10
votes
0answers
246 views

Do trinomials weaken the Alternating Step Generator?

The Alternating Step Generator was proposed by Christoph G. Günther: Alternating step generators controlled by de Bruijn sequences, in proceedings of Eurocrypt 1987. It's perhaps the conceptually ...
8
votes
0answers
74 views

Do CCM and EAX provide key commitment?

In an interesting paper called "Partitioning Oracle Attacks" by Julia Len, Paul Grubbs & Thomas Ristenpart an attack is presented on 1.5 pass AEAD schemes that utilize GMAC (GCM, AES-GCM,...
7
votes
0answers
177 views

Which is the smallest safe elliptic curve (bit-length)?

At https://safecurves.cr.yp.to/ some elliptic curves are listed which passed certain security tests. The smallest bit-length of a safe curve listed there is 221 bits. At wiki page discrete logarithm ...
7
votes
0answers
104 views

FPE current state of art for “small” domains

Is there any survey with the state of art treatment of format-preserving encryption for small domains (i.e. 2^20 for example)? I believe that Stalling's and Rogaway's surveys are out of date due to ...
6
votes
0answers
118 views

Parameters for high density SIS

I am considering the SIS problem of finding $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}_q^{n\times m}$, $Ax=0$ and $\lVert x\rVert < \beta$ for some $p$-norm and bound $\beta < q$. ...
6
votes
0answers
271 views

Index calculus over elliptic curve over function field

According to my understanding there are some pretty solid seeming roadblocks to carrying out an index calculus on an elliptic curve over a finite field. The general strategy is to take points over $E(\...
6
votes
0answers
617 views

Is this PRG secure?

$G$ is a secure PRG in range $\{0,1\}^n\rightarrow\{0,1\}^{n+1}$. Let us define $G'(S)=G(S\oplus G(S)_{1,...,n})$, s.t. $G(S)_{1,...,n}$ is the first n bits of $G(S)$. Is $G'(S)$ a secure PRG? ...
5
votes
0answers
106 views

search of patterns in key schedules

I am developing a new key schedule, and there is this article (Enhanced Key Expansion for AES-256 by Using Even-Odd Method) where the authors also propose a new algorithm and one of the objectives is ...
5
votes
0answers
326 views

Statistical saturation attack on block ciphers

I was wondering if anyone around here could give me some explanation on this type of attacks. Pretty much the only thing that I could find is A Statistical Saturation Attack against the Block Cipher ...
4
votes
0answers
68 views

Help with cryptanalysis of branching in schemes based on Multivariate Public Key Cryptography

I'm familiarized with the structure of branching found in Multivariate Cryptography, as it allows us to partition a $n$-tuple over $F_{q}$ into a $k$-tuple where the $i$-th element is in $F_{q^{\...
4
votes
0answers
158 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=\...
4
votes
0answers
114 views

What is the probability equation of rotational cryptanalysis on modulo multiplication?

The answer in this question defined how to calculate the probability of rotational cryptanalysis on modulo multiplication $\odot$. This paper defined an algebraic equation of how to calculate the ...
4
votes
0answers
307 views

Encrypt using ECDH with two different EC public keys, minimizing payload size

Let's say Alice has the private EC keys $a$ and $b$, with a base point of prime order $G$. Alice computes the corresponding public keys $A = aG$ and $B = bG$, and sends them to Bob. Bob now wants to ...
4
votes
0answers
152 views

AES-256 9 round related key attack - getting possible state differences

I'm trying to implement related key attack on 9 round AES256, described here: Biryukov, Dunkelman, Keller, Khovratovich, Shamir, but I am stuck at the very beginning with Observation A, used to ...
4
votes
0answers
146 views

Privacy of Multiplication of Shamir Shared Secrets with an Active Adversary Where Final Result is Revealed to a Third Party Over a Secure Channel

I have the following question related to the privacy of multiplication of Shamir Shared Secrets: Suppose we have two secrets, a and b, shared by a Shamir Secret Sharing Scheme in a (k,n) ...
4
votes
0answers
190 views

Differential Path Search of a Block Cipher

Camellia Design and Analysis document refers to a paper: [24] M. Matsui, "Differential Path Search of the Block Cipher E2," (in Japanese), Technical report of IE- ICE, ISEC99-19, pp.57-64, The ...
4
votes
0answers
280 views

How to modify the Socialist Millionaire Protocol to be symmetric.

In the Socialist Millionaire Protocol, the roles of Alice and Bob are almost symmetric. By this I mean they do almost the same thing, until the very last step. In the final step, both parties check a ...
4
votes
0answers
143 views

How to overcome issues with big ciphers? E.g. with small vs. big Vigenére Ciphers

I understand that bigger ciphers show more recurring patterns and therefore should be easier (or at least faster) to decrypt as you'll have a better statistical analysis, being However, if we use an ...
4
votes
0answers
161 views

Using machine-learning techniques for data-dependent operations in ciphers

From 'Methods of Symmetric Cryptanalysis' by Dmitry Khovratovich, The data-dependent operations are one of the most controversial design concepts. We say that an operation is data-dependent, if it ...
4
votes
0answers
507 views

Using the same private key for two ECC key pairs

Let $(d_1,Q_1)$ and $(d_2,Q_2)$ be ECC key pairs over two different elliptic curves (say NIST P-224 and NIST P-256). According to the Elliptic Curve Discrete Logarithm Problem (ECDLP), if the private ...
3
votes
0answers
539 views

Identifying correct cipher

I am trying to decrypt a text(~900 characters) and I started with the assumption that its a Vigenère cipher as the one of the identifier tool identified it as Vigenère cipher and also the Index of ...
3
votes
0answers
142 views

Understanding Linear Cryptanalysis

I'm reading about the linear cryptanalysis of an SPN and I have some questions about the practicality of this. The example I'm looking at is from 3.3.3 of Stinson's Book and I believe the same example ...
3
votes
0answers
137 views

Solving LPN using algorithm for syndrome decoding

Given an algorithm $A_D$ which solves an instance of the decoding problem $e \in \mathbb{F}_2^n$ in time $T_D$ given a parity check matrix $H \in \mathbb{F}_2^{(n-k)\times n}$ and a syndrome $s \in \...
3
votes
0answers
114 views

Breaking RC5 without rotations

I'm trying to follow Schneier's self-study course in cryptanalysis and am ashamed to say I am stuck on the very first problem of breaking 8-round RC5 without any rotations (i.e. just XOR and modular ...
3
votes
0answers
57 views

Finding maximal $n$-affine subset

We obtained $l$ vectors $B_i$ of $c$ bits $b_{i,j}$. These are an altered form of vectors $A_i$ where the last $n$ bits of each $A_i$ are an affine function of the other bits of that $A_i$. We want ...
3
votes
0answers
137 views

Old French Cipher w/ Text Hidden In Drawing

I'm trying to find a cipher challenge I saw a few years back, it was an old drawing (I think 1800's or earlier) with clouds and stars on it and French text was hidden in the image. Does anyone happen ...
3
votes
0answers
73 views

OAEP Cryptanalysis with broken hash

Keeping OAEP Cryptanalysis in mind, about the inability to get to $M_1$ or $M_2$ given $\operatorname{OAEP}(M_1) \oplus \operatorname{OAEP}(M_2)$. Would it be possible to get to $M_1$ or $M_2$, given ...
3
votes
0answers
224 views

Breaking an addition-based cipher with two ciphertexts but no known plaintext

I'm attempting to break a system which uses decryption code functionally equivalent to the following: ...
3
votes
0answers
194 views

In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$

In the NTRU cryptosystem, it is suggested to take $N$ prime. I want to understand why. In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (...
3
votes
0answers
168 views

Are analog quantum computers a threat to RSA and DLP?

We already know that D-WAVE's "quantum computers" can't really run the Shor's algorithm, because the way they're built doesn't qualify them as universal quantum computers. Now researchers actually ...
3
votes
0answers
85 views

On a proposition in NTRU original paper: $\gamma_1 |f|_2 |g|_2 \leq |f \circledast g|_\infty \leq \gamma_2 |f|_2 |g|_2$

In the original paper of NTRU cryptosystem, we have the following proposition (that is said to be suggested by Don Coppersmith): For any $\epsilon > 0$, there are constants $\gamma_1,\gamma_2 &...
3
votes
0answers
661 views

Is there any analysis of freebsd's “geli” encrypted geometry provider?

I've done a few obvious searches on google and google scholar and not turned up any security analysis of FreeBSD's geli. Is there some out there, or has it gone unanalyzed since its introduction ...
3
votes
0answers
213 views

Security of stream cipher based on Matrix multiplication GF(256) with randomized padding

The actual question is stated at the end of the text. Suppose you have a (grossly inefficient) confidentiality stream cipher with the following components: The keyed function $F_k:\{0,1\}^{8n}\mapsto\...
2
votes
0answers
53 views

Howgrave-Graham lattice attack on NTRU

I am lookin for a good example to illustrate this attack on NTRU using low parameters but I failed to do that, The attack consist to use LLL reduction on A basis of NTRU Lattice, let us use the column ...
2
votes
0answers
39 views

How is the 'Algebraic Degree' calculated in the paper about analysing the white-box AES(Chow et al. 2002) by exploiting internal collisions?

This paper proposed a new attack on the initial white-box AES implementation of Chow et al. In order to determine the good solution, we use the particular structure of the function $S_{0}$. $S^{-1} \...
2
votes
0answers
46 views

Fisher Yates on “faulted” random number generator cryptanalysis

For the sake of curiosity and fun, i have implemented a C# program that operate as deck dealer on 40 cards deck (following the Fisher Yates shuffeling algorithm https://en.wikipedia.org/wiki/Fisher%E2%...
2
votes
0answers
31 views

Unknown bit in the output of encryption of data using SIMECK32 cipher?

How is the unknown bits (annotated by red arrow in figure below) come in the OUTPUT after round 1 and round 2 ? Following is the pictorial representation of SIMECK round function operation. Ref: ...
2
votes
0answers
44 views

what if the S-boxes in DES were “optimal”

if we assume that the s-boxes in DES were optimal. that is for each s-box, every cell in the DDT equals to 4. is there a differential characteristic in a good probability?
2
votes
0answers
56 views

Why is it bad to encrypt the same message M with the same key K in both CTR and CBC modes of operation?

It is apparently not good - more precisely it is not secure - to encrypt the same data message M using the same cryptographic K with a block cipher (e.g. AES, but this is not relevant) in both CTR and ...
2
votes
0answers
80 views

Using Viterbi algorithm to decrypt Vernam cipher

I'm reading a book on cryptography and it mentions the Viterbi algorithm being used to decrypt Vernam cipher if the same key is used multiple times. According to the book the Viterbi algorithm takes ...
2
votes
0answers
87 views

Enhancing Differential-Linear Cryptanalysis

I'm studying Differential-Linear Cryptanalysis, and I'm trying to understand the context from the article Enhancing Differential-Linear Cryptanalysis by Eli Biham et al. There are some difficult ...
2
votes
0answers
111 views

A proposal for randomization of Niederreiter cryptosystem

The Niederreiter cryptosystem is a public key cryptosystem using Goppa code. Unfortunately it it is insecure unless it is a binary code. So I thought I could insert random linear codes into randomly ...
2
votes
0answers
128 views

Security of an Elliptic Curve Public Key with a “Small” x-coordinate

Consider an elliptic curve over a finite field $F_p$ with $p$ prime and order $n$. Let $Q$ be a generator for the field. Given a public key point $P = aQ$, suppose we have an algorithm that finds an ...
2
votes
0answers
118 views

Recover all keys on differential cryptanalysis

I am practically implementing differential cryptanalysis on a cipher from the book "the block cipher companion" . I am successful to get the last key $k_5$. Just to say some words about the ...
2
votes
0answers
421 views

How can I determine the Hill cipher key in this case?

I have been struggling with a Hill cipher problem for many days, without any luck. I have the following ciphertext, which I know is an encrypted excerpt from an Edgar Allan Poe story: ...
2
votes
0answers
86 views

Hamming Weight of Solutions to the Frobenius Equation

My area of research is algorithms for calculating optimal addition chains. I have a new high performance algorithm that at its core benefits from estimating the number of set bits ($v(n)$ Hamming ...
2
votes
0answers
69 views

Why commutativity gives an invariant subspace?

In A Generic Approach to Invariant Subspace Attacks the authors defined an invariant subspace as: $$F(u + A) = v + A$$ Where $F:\mathbb{F}_2^n \to \mathbb{F}_2^n$,$u, v \in \mathbb{F}_2^n$, and $A$ ...
2
votes
0answers
83 views

Differential analysis tools for cryptographic hash function

Is there any software tools available for conducting differential analysis test on cryptographic hash functions? If so, suggest few of them
2
votes
0answers
155 views

Efficient way of knowing large factors of $\phi(n)$ given small prime factors and $n$

Knowing large prime factor$(r > n^{1/4})$ of $\phi(n)$ can easily factorize n and hence learn $\phi(n)$. If we have knowledge on all small prime factors $(2< r_i << n^{1/4})$ of $\phi(n)$...