Why DDH is easy if a pairing function exists? When I look at some demos which demonstrate that DDH is easy if a pairing function $e$ exists, I usually see if $e(g,g^c)=e(g^a,g^b)$. Then we can know that $g^c=g^{ab}$, but why is this so? How do we remove the $e$? Let's imagine this is a symmetric-key cypher problem and $e:G_1 \times G_1 \rightarrow G_2$.

For example: here.

You don't 'remove the e', instead, you use the mathematical properties of it.

e satistifies the identities:

$$e(a^x, b) = e(a, b)^x$$

$$e(a, b^y) = e(a, b)^y$$

for any $a, b, x, y$

We also assume that the pairing is nontrivial (that is, $e(g,g) \ne 1$); typically, we further assume that $g$ generates a prime order group, this implies that $e(g,g)$ generates a group of the same order.

So, we have $e(g, g^c) = e(g, g)^c$ (second identity).

We also have $e(g^a, g^b) = e(g, g^b)^a = e(g, g)^{ab}$ (first and second identities).

So, if we have $e(g, g)^c = e(g, g)^{ab}$, because we know that the group generated by $e(g, g)$ and $g$ are isomorphic (even if we cannot compute that isomorphism in the $e(g,g)$ to $g$ direction; that's because all prime order groups of the same prime order are isomorphic), we then have $g^c = g^{ab}$


Would the ability to efficiently find Discrete Logs have any impact on the security of RSA? This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.

RSA labs makes a similar statement:

  The discrete logarithm problem bears the same relation to these systems as factoring does to the RSA system: the security of these systems rests on the assumption that discrete logarithms are difficult to compute.

Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

If you had a discrete log oracle could you use it to attack RSA?

There is a reduction from DL to RSA if the DL oracle accepts composite modulus. For prime modulus, a reduction is not known. I copied the following from this wikipedia page with minor edits.

Let $n = p\,q$ be an RSA modulus.

Generate random integer $a$ co-prime to $n$ and a random integer $x$ taken in an interval much larger than $n$, say $[1,1000n]$.
Compute $b = a^x \bmod n$ but don't tell $x$ to the 'discrete log oracle'.
Instead ask it to find the discrete log of $b \bmod n$ (to base $a$). Let the value returned by the oracle be $y$.
If $y$ is a solution, then so is $y\pm\varphi(n)$ where $\varphi$ is Euler's totient function, and $0<\varphi(n)<n$. It follows there are at least $1000$ solutions $y$ that lie in the interval of $1000\,n$ integers from which we picked $x$ uniformly at random, thus the oracle has probability $\le\frac1{1000}$ of finding $x$. There is thus a high probability that $y\neq x$. If so, $|x-y|$ will be a multiple of the order of $a$, which can easily be used to factor $n$. I will not go to the details of factoring once (a multiple of) the order of $a$ is known (since this is a well known method, also used in Shor's algorithm). If we are unlucky and $x=y$, then we start over.


Noise NK1 pattern identity hiding In the official documentation for the Noise Framework there is a section with an overview of the identity hiding for each pattern. The numbering of properties there, obviously, from weaker properties to strong ones, and the last property is:

  An active attacker who pretends to be the initiator and records a single protocol run can then check candidates for the responder's public key.

The NK1 pattern has this property.

NK1 pattern itself
  <- s
  ...
  -> e
  <- e, ee, es
  ->

What does this property mean?

What mean check candidates for the responder's public key?
How can recording a single run of a protocol help this? (preferably with an example)
Why is this property the latest in the list (i.e. supposedly the strongest)?

(here is not any tag related to Noise Framework, this is strange)

Let's break apart the property description:

An active attacker

So an attacker who can both read and create packets on the network

who pretends to be the initiator

In the NK1 handshake, the initiator is anonymous, so it's not really pretending to be the initiator, it is an anonymous initiator like any other NK1 initiator

and records a single protocol run

This just means they remember every message sent and received. You need to do this to analyze the packets later! I'll give the analysis you do below.

can then check candidates for the responder's public key.

You explicitly ask about this part in your question. The responder's public key, whose identity you're trying to hide, is never transmitted in this protocol, so you won't be able to ever see or directly decrypt it. In order to learn the responder's public key, you can only check if a guess you have for the public key is valid. You could enumerate the entire public key space, but it's so infeasibly large you'd never find it. But if you think the responder might use a specific public key (its identity), say because you know a certain service uses that public key, you could check if your guess is right. That's what this part of the identity hiding property is all about.
How would you do this? The crucial bit here is that 2 Diffie-Hellman operations are done here: ee and es. For ee, you are the initiator and the server transmits it's "e", so you can do this DH easily. For es, you supplied the "e", but want to make guesses about "s". The implicit (possibly empty) transport message after the "es" token has a MAC whose key is derived from ee and es; so if you can guess the responder's public key "s", and you use it and it successfully validates the MAC sent, then you know your guess was right.
Finally, this property is last in the list because it was added last; deferred handshakes (like NK1) were added later. It's not the strongest identity hiding level, 8 is.


Is the HMAC of a broken hash such as MD2, MD5, SHA1 etc, also broken? As we know, MD5 and SHA1 (to some extent) are broken, and older algorithms like SHA0 or MD4 and MD2 are very broken.
Does this also imply that the corresponding HMACs are also broken?
Obviously nobody should use e.g. HMAC_MD4 anymore. But I'm just trying to understand the underlying security risk from a theoretical point of view.
Is it feasible to generate a collision for something like HMAC_MD2 or HMAC_MD5?

In 2006, Mihir Bellare, in their article

New Proofs for NMAC and HMAC: Security without Collision-Resistance

proved that if the compression function is a PRF then HMAC is a PRF ( this is a short story, see below).
As a result, HMAC like HMAC-MD5 does not suffer the weaknesses of MD5. However, still prefer HMAC-SHA256 or KMAC of the SHA-3 series. Keep yourself away from MD5 and SHA-1.

However, the story is not finished There:
In 2006, Jongsung Kim, Alex Biryukov, Bart Preneel, and Seokhie Hong showed that they can distinguish HMAC if instantiated with reduced versions of MD5 and SHA-1 or instantiated full versions of HAVAL, MD4, and SHA-0 from a random function or HMAC with a random function.
In 2012, Koblitz–Menezes published a paper Another look at HMAC ( from the abstract);

First, we describe a security issue that arises because of
inconsistencies in the standards and the published literature regarding keylength. We prove a separation result between two versions of HMAC, which we denote $\operatorname{HMAC}^{std}$ and $\operatorname{HMAC}^{Bel}$, the former being the real-world version standardized by Bellare et al. in 1997 and the latter being the version described in Bellare’s proof of security
in his Crypto 2006 paper.
Second, we describe how $\operatorname{HMAC}^{NIST}$ (the FIPS version
standardized by NIST), while provably secure (in the single-user setting), succumbs to a practical attack in the multi-user setting.
Third, we describe a fundamental defect from a practice-oriented standpoint in Bellare’s 2006 security result for HMAC, and
show that because of this defect his proof gives a security guarantee that is of little value in practice.
We give a new proof of NMAC security that gives a stronger result
for NMAC and HMAC and we discuss why even this stronger result by itself fails to give convincing assurance of HMAC security.

from conclusion;

When HMAC is used with a hash function that is not collision-resistant, confidence in its security cannot come from the proof in [1] – or even from our proof in §10 – but rather must be based upon the large number of person-years that engineers and cryptanalysts have devoted to testing it. This is especially the case in an application
where one needs pseudorandomness and where short-term security is not enough.

There is a slide from Bernstein that covers the brawl around the above paper

2012 - The HMAC brawl


Using Optimal Prime Field in ECC "Optimal Prime Field is a family of 'low-weight' prime fields that allow for efficient software implementation of all operations requiring a modular reduction, in particular the field-multiplication. More formally, an OPF is a finite field defined by a prime of the form p = u · 2^k + v, whereby the two coefficients u and v are “small” (in relation to 2^k)".
Eg: p = 0xCD3E000000000000000000000000000000000001
Only the 4 MSB words are non-zero and rest are always zero, except the last bit.
I have read in the literature, OPF can be clubbed with ECC to speed up the computation involved. However, wouldn't a 160bit OPF with hamming weight 16bit used as key, make it vulnerable to brute force attack. I couldn't find any mention of it in literature. Please comment.

Preliminary: the present answer assumes an Elliptic Curve group of order $n$ built on a prime field of order $p$, with one of $p$ or $n$ a 160-bit prime of the form in the question (rather $p$, which will give the most computational benefit, and is close to common practice). Choosing "public key $P$ as $p*G$ where $p$ is an Optimal prime" is not proper, and not considered.
Rather yes: ECC cryptography would be dangerously close to being vulnerable to brute force attack.
That's because the order $n$ of the Elliptic Curve group would be at most roughly $2^{160}$ (due to Hasse's bound when the 160-bit prime is $p$), thus vulnerable to a generic Pollard's rho attack with cost about $2^{160/2}=2^{80}$ field operations, e.g. recovering a private key from a public key. Further, that attack is not too difficult to parallelize. That's not entirely out of reach for well funded adversaries.
However, the largest similar attack publicly performed (by Nov. 2020) seems to be against secp112r1, requiring about $2^{56}$ field operations, that is about $2^{25}$ less work than for the above. See Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, and Peter L. Montgomery's Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles using Sloppy Reduction, in International Journal of Applied Cryptography, 2012.
Thus for a 160-bit prime, a similar attack would be worth publication in the applied cryptography field. And in the unlikely cases that it it required sizably less than $2^{80}$ field operations, or less than $2^{25}$ more computing power than the secp112r1 attack on any given sufficiently flexible hardware, that would be a major theoretical breakthrough.

Update per comment: I fixed the above to use proper notation for $p$ and $n$. Yes proper ECC on a 160-bit prime field is not publicly broken in practice so far. Yes a 256-bit OPF $p$ would be on par with current practice: common curves such as secp256k1 and Ed25519 use primes of the form $2^{256}-2^{32}-977$ or $2^{255}-19$, which is similar to the question's OPF. Beware however that what matters to security is (half) the number of bits of the highest prime factor of $n$ (that is $n$ if it is prime), which depends on $p$ and other curve parameters. And there are other complex considerations in choosing an ECC curve, that I do not master, see safecurves.


Textbook RSA Attacks Given textbook RSA encryption, if an attacker obtains the ciphertext and has the public key that was used, can he or she decrypt said ciphertext without calculating the private key?

Without any additional knowledge? No.

The problem here is, that this understanding of security is wrong / too weak. Ciphertext-only attacks is the weakest kind of attack model, which is only relevant for classical ciphers any more.

To consider a cryptosystem secure today, it has to resist the much stronger attacks, most commonly the chosen-plaintext attacks and (in the case of public key crypto) chosen ciphertext attack. And on the other hand, we also don't require the attacker to decrypt the actual message. We consider the system broken if the attacker can distinguish messages already, for instance  ciphertext indistinguishability.

  ... without calculating the private key?

If the attack goal would be decryption, the only known way is to break the private key. It is unknown, if the RSA problem and the factorization problem are equivalent or not. And if we had an algorithm which could decrypt but not calculate the private key, this question would be solved.


SIKE/SIDH algorithm 6 I was recently reading this paper on SIKE and I'm trying to understand the details of the implementation.

I've noticed the point tripling algorithm (algorithm 6) was already described in a different paper.
Nevertheless, the SIKE paper uses a slightly different algorithm for calculating [3]P. I've quickly checked - it seems to me that both algorithms give different result (am I wrong?).
Any idea why the algorithm from SIKE spec is preferred over the algorithm from the other paper. Is it somehow faster?

Not a complete answer, just trying to shed some of your doubts.

  I've noticed the point tripling algorithm (algorithm 6) was already described in a different paper. Nevertheless, the SIKE paper uses a slightly different algorithm for calculating [3]P.

Although the official dates may indicate that the SIKE spec was published after the Faz-Hernández, López, Ochoa-Jiménez, Rodríguez-Henríquez paper (let's call it FLOR), the two were really being written about at the same time, so it's completely possible that we missed some optimizations.

As far as I can remember (speaking only for myself), the Montgomery ladder algorithm in FLOR had been previously presented at a conference, so we included it in the spec, but we did not know about the tripling formula at the moment of writing.

  I've quickly checked - it seems to me that both algorithms give different result (am I wrong?).

I haven't checked, but it is completely possible that the two formulas give different, projectively equivalent, coordinates.

  Any idea why the algorithm from SIKE spec is preferred over the algorithm from the other paper. Is it somehow faster?

Probably not faster, since FLOR explicitly say their formula is. However you have to follow the spec if you want to implement SIKE. It is important for the KEM that algorithm isogen returns exactly what's expected from the spec, and not something that is only projectively equivalent; so you cannot replace another formula inside the algorithm, unless the output is equal.

If it is confirmed that the FLOR formula is the best available formula, we may  update the spec at the next round of the NIST competition.


Twofish vs. Serpent vs. AES (or a combo) I've seen some posts and info online, but they are from 2009, 2010, 2011 or 2012, which is 3-6 years ago, which is a very long time. So I'm looking for an up-to-date answer about which of these is the safest encryption to be used, or rather most unbreakable? Particularly interested in encryption programs, so performance would also interest me, not only security.

I think things have changed since Snowden's postings, though then again - I know that a file encrypted with some sort of TrueCrypt algorithms remains uncracked after a few years of trying in the FBI.

So, having that in mind, I'd like to know more about it all so that I would be able to choose the right algorithm for me.

None of Twofish, Serpent and AES are currently known as broken, so as far as security is concerned, you can use any of them. AES has a slight advantage because it's very widely used, so if it gets broken you're more likely to hear about it and get relevant software updates quickly.
The Snowden postings haven't changed much as far as cryptography usage is concerned. They confirmed what was generally suspected before, which is that the generally-accepted cryptographic primitives are safe even from NSA-level adversaries¹; it's the systems and sometimes the protocols that are insecure. What's important is not your choice of primitive (as long as it's one of the generally-accepted ones, e.g. one approved by a NIST standard), but your choice of software.
AES has the advantage that high-end x86 and ARM CPUs include hardware acceleration for it.
If you're a user of cryptography, as opposed to an implementer of software like GPG, keep in mind that if you're typing the letters A-E-S into your code, you're doing it wrong.
¹  You might consider Dual_EC_DRBG to be an exception, but few people used it because it had no obvious security benefit, and its potential to be backdoored was known, and it was slow.


Non-Linearity of an Sbox Non-Linearity of an Sbox affects its resistance towards Linear Cryptanalysis. What happens, if an Sbox has low non-linearity (specially with respect to Linear Cryptanalysis)?

Consider a linear 8-bit s-box $S$:

$$
c=S\cdot p,
$$

where $c$ and $p$ are 8-bit vectors, and thus $S$ is an $8\times8$ matrix. This means we can pick 64 different s-boxes in our design. This already gives an intuition on one weakness: there are $8!$ permutations for 8 bits, but we limit our design to "just" 64 of them.

Now on to the fun stuff: differential cryptanalysis. Linear s-boxes have the nice property that for ciphertexts $c, c'$ and their respective plaintexts $p, p'$:

$$
c\oplus c' = S\cdot p \oplus S\cdot p' = S\cdot (p \oplus p'),
$$

which is a very much unwanted property of linear s-boxes. In usual symmetric cipher design, a non-linear s-box is the main element to counter this kind of differential cryptanalysis.

For what it's worth, the same can be said about affine s-boxes ($c=S\cdot p \oplus b$ for fixed $b$).

Now consider (simplified) AES, where the s-box is constructed as some form of inversion (technically a multiplicative inverse in the Rijndael finite field):

$$
c\oplus c' = p^{-1} \oplus p^{-1} \neq (p\oplus p')^{-1}
$$

Here, the $(\cdot)^{-1}$ operator is not distributive, hence, this simplified attack does not hold.

Linear cryptanalysis uses a linear approximation of the s-box. It tries to "model" the $(\cdot)^{-1}$ operator (or the s-box of the studied cipher) as a linear map $S$, such that usually (with high probability) bits from plaintext map on ciphertext bits using this linear model.

If such a model can be found with a high bias, we may be able to distinguish ciphertexts, or even derive (part of) the used key.

AES is designed to be highly non-linear, exactly to resist this kind of attack; the multiplicative inverse is said to be highly non-linear.


Doubts regarding implementing AES-128 bit algorithm in my IOT system I want to implement AES-128 in my IoT network which consists of a Master device which runs Linux on it and slave devices which are 8-bit micro-controllers that periodically transmit data packets to the master.

I read about the AES/Rijndael algorithm and liked it.

The only questions I have are:-

What should I set my IV to be ?
What should be the key value?

Can the key value be a random value chosen by me or it has to come from a specific source?

What should I set my IV to be ?

For any decent mode of operation, like AES-EAX or AES-CCM you want to not re-use a key-IV pair. That is different keys with the same IV is fine as is the same key with different IVs and different keys with different IVs. Beyond that if you can enforce the above restriction with a counter (or domain-separated counters, e.g. $2^{32}$ unique prefixes for the devices which independently count from $0$ up with their prefix) that is fine, if you can't then you probably want to just generate the IVs at random if possible.

You may want to note that CBC is not a decent mode of operation, forcing you to use unpredictable IVs.

  What should be the key value ?

Keys should ideally be generated such that they are indistinguishable from random strings of the same length. This may involve a key-exchange (using symmetric or asymmetric cryptography) or other methods of key-derivation (e.g. using a password or key-based key deriviation function like Argon2 or HKDF).

In your specific scenario one idea would be let the master have a secret key $K$ and each device having a unique serial number. Then on deployment you use HKDF to derive two keys for each device using its serial number and the data flow direction and store the keys on the device. Then when you get a packet, you can simply re-derive and / or cache the specific keys on your master device.

One final warning: You really don't want to implement AES (or maybe even the mode) yourself because that's quite hard to do securely and with good performance. You really want to use a library for that instead, e.g. BearSSL or mbedTLS.

Oh and if you are doing transport encryption you probably want to consider using TLS (for TCP-like transport guarantees) or DTLS (for UDP-like transport guarantees) with pre-shared keys which handles all the encryption and authentication and IV management for you if you just supply it the shared key (only one this time, it will derive its own for each traffic direction).


Can you decrypt with 1 round key? If one has the last round key in an SP or Feistel network (the 16th round key in DES for example), would that someone be able to decrypt the rest of the encryption?

It depends on the block cipher in question - specifically its key schedule. Knowing any round key of AES-128 would let you calculate the key, because the schedule is reversible. OTOH, e.g. TEA would retain secrecy of most of the key and might remain secure, because its round keys are small enough parts of the key.

In the case of DES, it is weak enough to be decryptable regardless of any information. However, knowing a round key would make it trivial, since every round key reveals 48/56 key bits, leaving only 8 bits to be brute forced.


Complexity of computing zk-SNARK Proofs Disclaimer: I have no background in cryptography, and everything I'm asking about is what I've learnt from last couple of days of frantic reading on this topic. Any help is much appreciated.

Q: What does the computational complexity of generating a zkSNARK proof and verifying it scale with?

Specifically, how many bilinear pairings, curve point additions and scalar multiplications are involved in generating and verifying a proof? Are these linear in the number of constraints in the system?

Here, I can see that there each verification requires the verifier to compute $11$ curve pairings, $3*m$ scalar multiplications, and $3(m+1)$ curve point additions. First of all, is my understanding correct? Second, what is $m$? Is that the number of constraints? Third, how can I similarly calculate the number of pairings, additions and multiplications that the prover has to compute if I know the number of constraints?

Its depend on the protocol used. The last and more efficient is Groth16 that use only 3 curve points in its proofs. You can see the size of the keys and the  the proofs in the table 2 of Groth's paper. The computation complexity of the pairing depends of whats curve is used. In general ZoKrates/Ethereum and ZCash use the bn256 curve paramters and the pairing algorithm used in their package (at least in the golang's one) is the algorithm 1 of the miller ate pairings.

You see zk-SNARK is an amalgamation of various works and its complexity depends on the implementation that is evolving day to day.


Message space in security definitions What is the message space in the following example and how does a message space relate to a security definition?

I mean, what difference does it make to such a definition if your message space is $\{0,1\}^n$ or if it is $\{0,1\}$?

  We say $(\mathsf{K},\mathsf{E},\mathsf{D})$ is $(t,\epsilon)$-IND-CPA secure if for all $t$-bounded adversaries Adv:

  $|\mathrm{Pr}[ (pk,sk)←\mathsf{K}(1^n); (m_0,m_1)←\mathrm{Adv}(pk);c ← \mathsf{E}_{pk}(m_0): \mathrm{Adv}(c) = 1]$
  $-\mathrm{Pr}[(pk,sk)←\mathsf{K}(1^n); (m_0,m_1)←\mathrm{Adv}(pk); c←\mathsf{E}_{pk}(m_1): \mathrm{Adv}(c) = 1 ]| \leq ε$

  where Adv outputs $|m_0|=|m_1|$

In your formula, $n$ appears to relate to the key space, not the message space.

The message space does not intervene in the definition of IND-CPA, and that's a good thing because practical message spaces consist in messages which "make sense" in a given context. There are situations where the attacker already guesses quite a lot of the attacked message, and the message space size (as in "number of distinct values that the message may meaningfully assume") can shrink down to 2 (e.g. if the attacker tries to guess a yes/no answer). So whatever security definition you use must be able to cope with very small message spaces.

The formula you quote is the translation of the following thought experiment:

A key pair is generated, with a given "size parameter" $n$ (e.g. we do RSA, with a 1024-bit key). The public key is made public, i.e. the adversary can see it.
The adversary produces two messages $m_0$ and $m_1$ of his choosing, from the set of message values that the encryption scheme can process (e.g. with RSA, a 1024-bit key, and PKCS#1 v1.5 padding, $m_0$ and $m_1$ must be sequences of bytes no longer than 117 bytes).
We choose at random one of the two messages, encrypt it, and give it back to the adversary.
The adversary must now guess which of the two messages we encrypted.

If we do this many times, we can compute the average success of the attacker. If the encryption system is "perfect", the adversary can do no better than a random binary choice. But we give him some CPU power (the $t$ parameter) and he can use that to try to guess the private key, so the attacker can always guess correctly a bit more often than incorrectly. The   $ε$ value is a measure of that "bit more".

Specifically, in the formula, the first probability says how often the adversary gets it wrong when he answers "1", and the second how often he gets it right. The difference between the two probabilities should be no more than $ε$. Note that if the adversary cannot guess right substantially more often than half the time, he cannot guess right substantially less often than half the time either (otherwise, he could just systematically reverse his answer; a compass which always points South is quite useful once you know it).

"CPA" means "Chosen-Plaintext Attack": in the thought experiment, the adversary can choose $m_0$ and $m_1$ as he wishes to, and can do it again for each attack instance.


question about curve secp112r1 In SEC 2: Recommended Elliptic Curve Domain Parameters curve secp112r1 has $0xDB7C2ABF62E35E668076BEAD208B$ as the order of the finite field and as the $a$ coefficient in the equation $y^2 =x^3 +ax +b$. Wouldn't that essentially make the $a$ coefficient $0$? If so then why not just say that that's what the coefficient is?

secp192k1 has $0$ as coefficients so it's not like there's not precedent for a coefficient of $0$.

You misread the parameters: $p$ is $$\mathrm{0xDB7C2ABF62E35E668076BEAD208B} \text,$$ but $a$ is $$\mathrm{0xDB7C2ABF62E35E668076BEAD208\underline{\mathbf8}}$$
which is $-3$ $\bmod p$!


Resolution plan

$N$ is a composite with no trival factor, and our plan will be:

Find what's missing in $r$ (14 decimal digits) from what's known, the values of $N$, $g$, $h$, and the relation $g^r\equiv h\pmod N$, using a minor variation of the baby-step giant-step Discrete Log algorithm.
Similarly find the missing decimal digits in $s$.
Raising $g^r\equiv h\pmod N$ to the power $s$ then substituting $h^s\equiv g\pmod N$ gives $g^{r\cdot s}\equiv g\pmod N$. Hence $r\cdot s-1$, which we now can compute, is a multiple of the order of $g$, and thus has a fair chance to be a multiple of $\varphi(N)/2$.
Note: That's not sure! In the preparatory problem $g$ is of order $\varphi(N)/2$, and it's at best reasonable to hope that in the full problem that order is $\varphi(N)/2$ or $\varphi(N)$. However, if $g$ has been randomly selected, its order likely is a multiple of $\varphi(N)/c$ for some small $c$ dividing $\varphi(N)$, and $c$ can be searched.
Factor $N$ from its value and that of the multiple of $\varphi(N)/2$ just obtained.

Finding the full $r$ with baby-step giant-step

We are working in base $b$ and missing digits of $r$ at index $i$ in set $\Bbb M$ (starting at index 0 on the right), and can write $\displaystyle r=\hat r+\sum_{i\in\Bbb M}x_i\,b^i$ with unknowns $x_i\in[0,b)$. Here $b=10$, $\hat r$ is obtained by replacing @ with 0 in the given form of $r$, and the 14 indexes of the @ starting from the right are $\Bbb M=\{16,106,116,126,137,146,154,163,172,181,191,201,212,229\}$.

We split $\Bbb M$ about evenly into disjoint subsets $\Bbb U$ and $\Bbb V$ and rewrite $g^r\equiv h\pmod N$ as

$$\begin{array}{llll}
g^r&\equiv&h&\pmod N\\
g^{\left(\hat r+\displaystyle\sum_{i\in\Bbb M}x_i\,b^i\right)}&\equiv&h&\pmod N\\\\
g^{\hat r}\cdot\displaystyle\prod_{i\in\Bbb M}\left(g^{(b^i)}\right)^{x_i}&\equiv&h&\pmod N\\
g^{\hat r}\cdot\displaystyle\prod_{i\in\Bbb U}\left(g^{(b^i)}\right)^{x_i}&\equiv&h\cdot\displaystyle\prod_{i\in\Bbb V}\left(g^{(-b^i)}\right)^{x_i}&\pmod N
\end{array}$$

We pre-compute $g^{-1}\bmod N$ (using e.g. the half-extended Euclidean algorithm), and $\left(g^{-1}\right)^{(b^i)}\bmod N$ for ${i\in\Bbb V}$, then can sequentially compute and store in a data structure allowing fast search all $b^{|\Bbb V|}$ values of $\displaystyle\left(h\cdot\prod_{i\in\Bbb V}\left(g^{(-b^i)}\right)^{x_i}\right)\bmod N$ (alongside the matching tuple of $x_i$ for $i\in\Bbb V$). We start from $h$ for all $x_i=0$ with ${i\in\Bbb V}$ and perform one modular multiplication for each other (we need $|\Bbb V|$ intermediary variables, including $h$).

We pre-compute $g^{\hat r}\bmod N$ and the $g^{(b^i)}\bmod N$ for ${i\in\Bbb U}$, and sequentially compute and search in said data structure $g^{\hat r}\cdot\displaystyle\left(\prod_{i\in\Bbb U}\left(g^{(b^i)}\right)^{x_i}\right)\bmod N$. We start from $g^{\hat r}\bmod N$ for all $x_i=0$ with ${i\in\Bbb U}$ and perform one modular multiplication for each other (we need $|\Bbb U|$ intermediary variables, including $g^{\hat r}$). When we get a match, that gives us all the $x_i\in\Bbb M$ (those from $\Bbb V$ come from the data structure, those from $\Bbb U$ are the one which led to the match), hence the full $r$.

The worst case computing effort is dominated by about $2\,b^{|\Bbb M|/2}$ (here 20,000,000) modular multiplications modulo $N$ (here, costing about $2\,\lceil(\log_2N)/32+1\rceil^2<1500$ elementary multiplications of 32-bit variables and additions of the 64-bit result using schoolbook algorithms). We are talking minutes of runtime, and less than 3 Megabytes of memory (and by making $|\Bbb V|$ one smaller, we reduce memory requirement by a factor $b$, at the expense of runtime).


How to use proof of lack of knowledge? This is a purely hypothetical example but is provable ignorance useful in cryptography?

For example, let's say I have a trapdoor collision resistant function. I know the trapdoor and therefore some $x_0 \neq x_1$ such that $f(x_0) = f(x_1)$. This is however, hard to find. If someone proves they know $x_0$, I can conclude that they do not know $x_1$.

Is there any context where more complicated versions of such problems is useful?

In general, you cannot prove lack of knowledge, because even if you did know something you shouldn't, you can always pretend that you don't know it and carry out the proof as if you didn't know it.

For your specific example, consider how the prover would know $x_0$.  Did you tell them what it is?  If so, that proves nothing, since they would then know $x_0$ even if they had also learned $x_1$ from somewhere else.

Conversely, if your function $f$ is collision resistant without the trapdoor, but is not injective (i.e. potential collisions do exist), then it must also be preimage resistant.  Thus, finding $x_0$ from $y = f(x_0)$ is (at least) as hard as finding $x_1$.  Thus, paradoxically, the prover exhibiting $x_0$ would in fact be evidence that they can find preimages for $f$, and thus can probably find $x_1$ as well.


GCM decryption and clear text processing When using GCM mode decryption, is it necessary to wait for the decryption to complete, (and thus being able to see if the integrity of cipher text is OK) before beginning processing the clear text output, or is it possible to begin processing the clear text in parallel without any risk, regarding chosen cipher text and timing attacks? (Of course, I understand that the clear text would have to be discarded anyway, if the integrity of ciphertext appeared to be bad)

TL;DR: no you should not process GCM decrypted data before the authentication tag has been verified.

GCM mode simply uses counter (CTR or SIC) mode as cipher. For the 12 byte IV you just have to create a counter by adding bytes 00000002 and start decrypting using the given key. You can see a decryption example here. It would be easy to create an example that starts at a different offset in the ciphertext / plaintext as well.

When you process the decrypted data without authentication you will expose yourself to timing attacks and plaintext oracle attacks. Any state that you keep that depends on the plaintext can be altered by an adversary; adversary can flip any bit of plaintext for unauthenticated ciphertext in CTR mode by flipping the ciphertext bit at the same offset.

How badly you are exposed depends of course on the plaintext processing used. I would not underestimate the risk though, even simple decoding of Unicode (UTF-8) characters could leak information. It could also be possible for an adversary to change the state of your service and then try to prevent rollback (e.g. by turning off the power).

You could possibly write the decrypted plaintext to a temporary file. Then you could copy the file to the final destination once the authentication has succeeded. This kind of processing can be performed without too much risk as the contents of the plaintext shouldn't influence the processing of the bytes.

Commonly this issue is sidestepped by encrypting the plaintext in chunks, verifying the authentication tag for each chunk. Note that you would need some kind of protocol to disallow reordering of the chunks - you could use the IV for that. Obviously this also requires additional space to store the authentication tag for each chunk.

And obviously these kind of changes to the protocol need to be performed during encryption; it doesn't influence existing ciphertext.

GCM mode is basically encrypt-then-MAC, where the MAC is generally faster than the CTR mode decryption. In principle it is therefore possible to verify the MAC before decryption. So in principle you could verify and then perform stream decryption, processing the bytes on the go. You would need a specialized implementation for this.

Unfortunately, passing over the same bytes twice could significantly slow down operation as well. In general you are better off trying to speed up GCM decryption in general and cache the results. You could however use this complicated scheme for memory-starved environments.


Is it theoretically possible for the output of SHAKE to be an infinite concatenation of the same 512-bit block? Let $X$ denote a particular 512-bit sequence.
Let $A,B,C$ denote sequences of bits such that:
$$len(X || A) = len(X || B) = len(X || C) = 1600$$

$$\operatorname{Keccak-}f(X||A) = X||B$$
$$\operatorname{Keccak-}f(X||B) = X||C$$
$$\operatorname{Keccak-}f(X||C) = X||A$$

then we have a loop, so the output of SHAKE (if my understanding of how the sponge construction works is correct and if $X||A$ happens to be the state which was output after xoring the final block of input) is nothing but an infinite concatenation of the same 512-bit block. Is it possible?

Minor correction: SHAKE generates either 1088 or 1344 bits per squeeze; not 512.  So, the example you give will give a repeating pattern, but it'd be either 3264 or 4032 bits long, not 512.

Other than that, yes, that is possible, as far as we know.  In fact, a far more likely repeat is:

$$\operatorname{Keccak-}f(A||X) = A||X$$

This would give a repeating pattern of 1088 or 1344 bits long.

In addition, not only is this possible, there's a good likelihood that there actually is such a $A || X$ pattern.  Such a $A || X$ is known as a fixed point of the permutation; a random permutation has at least one fixed point with probability approximately $1 - 1/e \approx 0.6321$; assuming that $\operatorname{Keccak-}f$ does, in fact, act like a random permutation, then it's more likely than not that there is such a fixed point.


Zodiac unsolved 340 cipher decryption in 2020 This is a rather general question, but I'd really appreciate your (experts, in my view) opinion on this subject.
I was wondering if, using current tech like machine learning, quantum computers and ultrafast GPUs, are we anywhere closer to deciphering the (in)famous 340-sign Zodiac letter which he sent to the press in November 1969?
I can't understand why it isn't as simple as sifting thorugh random substitution-decrypted combinations of plaintext and employing properly trained NLP neural net to select only these outputs that have the highest rating in terms of grammatical and semantic correctness also taking into account the timeframe (late 60s, early 70s frequently used words) as well as context (Zodiac was a serial killer).
I'm not thinking of trivial word salad pseudo-solutions but possible plaintext which would be deemed to convey coherent message via correct language-specific sentence building rules/structures.

It seems this is now cracked, see for example here.


Is there a security proof for the Triple-DES construction in the ideal cipher model? Suppose one has an ideal block cipher

$E \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^k \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \;\;\;$ and $\;\;\; D \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^k \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w$.

One can obviously follow the Triple-DES construction with that block cipher and keying option $n$, to get the block ciphers

$\operatorname{enc}_n \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^{(4-n)\cdot k} \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \;\;\;$ and $\;\;\; \operatorname{dec}_n \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^{(4-n)\cdot k} \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w$.

One can easily show that is takes $\:$$\Theta$$\left(2^k\right)\:$ queries to $E$ and $D$ to break the security of $E\hspace{.02 in}$.

Regardless of which keying option is used, $\:\operatorname{enc}_n\:$ will be at least that secure.

For $\:n\in \{\hspace{-0.02 in}1,\hspace{-0.02 in}2\hspace{-0.02 in}\}$, is it known that $\:\operatorname{enc}_n\:$ will be a PRP family against adversaries that can make significantly more than $2^k$ queries to $E$ and $D\hspace{.03 in}$?

Yes.  The following papers should be exactly what you are looking for.

The following paper shows that the answer is "Yes" and provides evidence that 3-key Triple DES is more secure than single DES:

Code-Based Game-Playing Proofs and the Security of Triple Encryption.
Mihir Bellare, Phillip Rogaway.  IACR ePrint 2004/331.  (Full version of a paper published at Eurocrypt 2006.)

They show that, in the ideal cipher model, the adversary must make more than about $2^{78}$ chosen-plaintext/ciphertext queries to have a reasonable chance at distinguishing 3-key Triple DES from a random permutation.  This not too far off from the best known attack on 3-key Triple DES (which requires about $2^{90}$ queries), and shows that 3-key Triple DES is significantly more secure than single DES (again, in the ideal cipher model).

There is prior work by Aiello et al. that analyzes 2-key Triple DES in the ideal cipher; see the related work section of the Bellare et al. paper for a citation and discussion.

There is also subsequent work that re-proves the result on 3-key Triple DES in a simpler form, and analyzes 5DES and longer cascades as well:

Cascade Encryption Revisited.
Peter Gazi, Ueli Maurer.  Asiacrypt 2009.


curve25519 weak points for contributory behaviour The Diffie-Hellman on curve25519 is usually calculated using the base point $(9,…)$ which induces a cyclic subgroup of $G:=\{\infty\}\cup(E(F_{p^2})\cap(F_p\times F_p))$ with index 8, i.e. there is a prime $p_1$ such that $|G|=8p_1$ and the order of $(9,…)$ is $p_1$. An attacker does not have to use a multiple of $(9,…)$ though and can even choose an element in the twist group $T:=\{\infty\}\cup(E(F_{p^2})\cap(F_p\times \sqrt 2 F_p))$ which has order $|T|=4p_2$ for a prime $p_2$.

Contributory behaviour (afaik) describes the property that none of the participants of the Diffie-Hellman exchange can force the outcome to be one of a small set of values. Such a property is for example interesting to defend against something like the triple handshake attack. The website on curve25519 lists 12 values to reject to assure contributory behaviour.

I understand where eleven of these come from, namely the elements of the subgroups of order 8 and 4 of $G$ and $T$ respectively. As they both share the same identity element ($\infty$) there are $8+4-1=11$ of those elements.

(If an element is not in those subgroups of order 8 and 4, then its order is $\geq \min(p_1,p_2)$ and thus the set of possible values that result out of the multiplication with the private scalar of the other party is large.)

Which of the 12 elements listed on the website is not one of the above eleven and why is it there?

There are actually only 5 unique $x$-coordinates one needs to be concerned about:

$(0, \ldots)$
$(1, \ldots)$
$(-1, \ldots)$
$(x_1, \ldots)$
$(x_2, \ldots)$,

where

$$\begin{eqnarray}
x_1 =& 393823572354896145817230607815530211125 \\
     & 29911719440698176882885853963445705823
\end{eqnarray}
$$
and
$$\begin{eqnarray}
x_2 =& 32560625091655743179598362635611063129 \\
     & 4008115727848805560023387167927233504
\end{eqnarray}.
$$

These correspond to the $x$-coordinates of points of small order on the curve and its twist, as you have pointed out. The remaining values you see are the multiples of those $x$-coordinates below $2^{256}$:

$0 \equiv 2^{255}-19 \equiv 2(2^{255}-19)  \pmod{2^{255}-19}$
$1 \equiv 2^{255}-19 + 1 \equiv 2(2^{255}-19) + 1 \pmod{2^{255}-19}$
$2^{255} - 19 - 1 \equiv 2(2^{255}-19) - 1 \pmod{2^{255}-19}$
$x_1 \equiv 2^{255} - 19 + x_1 \pmod{2^{255}-19}$
$x_2 \equiv 2^{255} - 19 + x_2 \pmod{2^{255}-19}$

These extra values are checked because curve25519 was designed to accept any $256$-bit string as public-key, and each value has one or more 256-bit representations modulo $2^{255}-19$.


How can one prove correctness of shared secrets in secret sharing schemes? Assume we are in a centralized secret sharing setting, where one party generates the shares, and distributes them to other parties. How can the distributor who creates the shares prove to the parties that they received the correct share?

Imagine the parties later share their shares or some other information between themselves to check whether the shares indeed combine to the correct value. But if this fails, it means one or more of the shares were wrong. Can one identify which shares were indeed wrong? And if yes, how does one know whether the distributor gave a wrong share to a party, or if this party deviated from the protocol and sampled a random share himself/herself?

For simplicity we can assume that shares are additive, and they are generated as $s_1,\ldots,s_{n-1} \gets \mathbb{Z}_p$, and $s_n = s - \sum^{n-1}_{i=1} s_i$, for a secret value $s$ that we want to share. And we are in n-out-of-n setting.

Also we can imagine that the distributor is the one that samples $s$ and then sends $g^s$ to other parties, so they can just combine their shares in the exponent to check whether it is equal to $g^s$. Which again opens a door for distributor to cheat, what if it sends wrong value, such as $g^{s’}$?

Here is one possible approach:

The dealer generates a group suitable for a Pedersen commitment scheme (namely, an Elliptic Curve with prime order $p$, and two elements $G, H$ where no one knows the discrete log of $H$ with respect to $G$) - we can do this in a multiplicative group; I just find the additive notation a bit easier in this case, as the notation for the math on the commitments matches that of the uncommitted values.
The dealer selects a Shamir Secret Sharing polynomial (the constant term the shared secret, the rest of the coefficients random) over $GF(p)$; he also creates a Pedersen commitment for each coefficient $c_i$ (using a random value $r_i$), and publishes it (and so he publishes the values $c_iG + r_iH$), along with a series of NIZKPs that he knows the values $c_i$ that he committed to
The dealer generates shares for each one; with user $x$, he generates the share $z = c_nx^n + c_{n-1}x^{n-1} + … + c_0x^0$ and also generates a NIZPF that $x^n(c_nG + r_nH) + x^{n-1}(c_{n-1}G + r_{n-1}H) + … + x^0(c_0G + r_0H)$ is a commitment to $z$; he sends $z$ and the NIZKP to the user.

Each user can verify (based on the public NIZKPs) that the dealer has committed to a single group-wide polynomial.  In addition, based on the NIZKP that the dealer gives to each user, they can verify that their share is consistent with that group-wide polynomial.


Single-pass authentication with a block cipher that accepts a counter Suppose we have a tweakable block cipher ($E(K, T, X)$ and $D(K, T, X)$) that is used in a scheme where the tweak, either in whole or in part, is used as a counter to make each block encrypt to a distinct ciphertext. If we XOR all of the blocks together and then encrypt the result, do we have a secure tag?

It is not secure if you use the $E(K, T, X)$ values as the exposed ciphertext; it is secure if you're using this scheme as a MAC (and use an independent scheme to encrypt).

If you send the $C_i = E(K, T_i, X_i)$ as the ciphertext (and send $E(K, 0, \bigoplus C_i)$ as the tag, then what the attacker could do is flip the same bit on two different $C_i$ values.  The resulting $\bigoplus C_i$ will remain the same, and so the tag would validate (and the decrypted plaintext would be incorrect).

On the other hand, if you keep all the $C_i$ values internal, then this system can be viewed as a Carter-Wegman MAC.  All you need to show is that $\bigoplus C_i$ is an almost universal hash function (which is fairly easy to do, assuming you get the message padding right), and the standard CW proofs apply.


Encrypting more than ~64GiB with AES-GCM - Integrity I'm looking for solution to encrypt more than acceptable limit ~64GiB under same key with AES-GCM. I know I'm obligated to exchange nonces for each next ~64GiB chunk, but there is one thing that is bothering me. I need to keep also integrity of order of ~64GiB blocks, to disable block swaps. I was thinking about adding previous auth tag as AAD to next block. Is it enough? I can't find answer for this question anywere.

Thanks for help

The nonce is included in the computation of the tag.

If the nonce is incremented after each message, chunks cannot be reordered or duplicated. If the third message is expected to have been encrypted with nonce 3, the tag verification is not going to pass if a message encrypted with nonce 2 is provided instead.

One thing you need to detect, though, is when the last message has been received. It can be achieved by reserving a bit of the nonce to indicate this, as in the STREAM construction.

If the nonce is effectively a chunk index, the key can only be used once, as you don't want a (key, nonce) pair to repeat, especially with different messages.

So, you either need to use unique keys, or reserve part of the nonce as an IV (or message -not chunk- index), and the rest as a chunk index.

Individual chunks should have a reasonable size, if only because you don't want to download, store and verify 64 GB to finally discard everything due to a tag that doesn't verify. 16 KB and 64 KB are common sizes.

And, especially with AES-GCM, you may also want to frequently do key rotation.

If this is an option, just use TLS that will take care of all these things.

If you don't want to use TLS, but AES-GCM is not mandatory, a construction such as xchacha20-poly1305 is easier to use safely with large messages.

If you don't want to use TLS, and want to use AES-GCM, use the STREAM construction.

If you don't want to use TLS, AES-GCM is not a requirement, and you don't want to write the code, use libsodium's secretstream construction.

For more practical details on this topic, see Encrypting a set of related messages
.


Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$ Please consider we have finite field $\mathbb{F}_p$ for large prime number $p$. We have a fixed field element $\alpha$. By $r_i\leftarrow \mathbb{F}_p$ we mean we pick $r_i$ uniformly random from the field. We assume the values $r_i$ are distinct so $r_i\neq r_j$

Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$?

Intuitively one may say the adversary can compute $gcd(v_1,...v_n)$ to extract value $\alpha$.

Am I right that the adversary cannot learn anything; otherwise, ElGamal encryption would not be secure?

Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$?

Answer: assuming that the $r_i$ values are random (that is, equidistributed and uncorrelated), then the attacker gets absolutely no information about $\alpha$ (other than whether or not it's 0).

We can see this because, for any sets of values $v_i$, there are a unique set of $r_i$ values that is consistent with $\alpha$ being a specific nonzero value, namely, $r_i = \alpha^{-1} v_i$.  So, if someone cannot distinguish the $r_i$ values from random, they cannot determine which nonzero $\alpha$ value is any more likely than any other.

You state that the $r_i$ values are distinct, and so technically that is a correlation.  However, we can show that distinct $v_i$ values translate to distinct $r_i$ values (for any fixed nonzero $\alpha$), and hence any $\alpha$ value will preserve uniqueness.  So, the attacker cannot use this correlation to gain any information.


Does it make sense to have long SSH Key with shorter Passphrase? If we encrypt our data with a longer SSH key which is protected by a shorter passphrase (with a decent entropy), then the limiting factor is entropy of the passphrase. So why do we use a longer key at all? We could simply encrypt the data with the passphrase.

You're not modeling what information the attacker has.  The strength of the system only reduces to that of the passphrase if the attacker has a copy of the passphrase-encrypted private key.  If they don't, then the strength of the system is the strength of the private key.

You're not supposed to let your passphrase-encrypted private key file fall into adversarial hands.  The passphrase is providing a fallback in case that condition is violated.

Note that the passphrase is optional, and that there also exist non-passphrase mechanisms for protecting the private key. OpenSSH supports using smartcards instead of private key files, and there are apps for smartphone-based SSH authentication, where the private key is protected by the device's hardware.


Dimension of Encryption of a linearly dependent set of plaintexts Suppose I have an encryption scheme of the form $ E(P)=C $ where $P$ is the plaintext and belongs in $\{0,1\}^N$, $C$ the ciphertext which belongs to $\{0,1\}^M$ and the encryption is performed under the key $K$ in $\{0,1\}^R$.

If I pick a subspace of messages $M_0$ and I perform encryption on this set, can I conclude anything about the dimension of $E(M_0)$ as a subspace of $\{0,1\}^M$.

If $E$ was a random function from $\{0,1\}^N$ to $\{0,1\}^M$, then encrypting $n = |M_0|$ distinct messages with $E$ would be equivalent to picking $n$ independent random elements from $\{0,1\}^M$.  If $n \ll M$, these random elements are with very high probability linearly independent, and thus span a subspace of dimension $n$; conversely, if $n \gg M$, with high probability they'll span the entire $M$-dimensional space.

In any case, of course, $\dim(E(M_0)) \le \min(n,M)$.  If $n \approx M$, there's a non-negligible probability that the inequality is strict, but it decreases exponentially in either direction.  (In particular, the probability that $\dim(E(M_0)) < n$ equals $1 - \prod_{i=0}^{n-1}( 1-2^{i-M} ) \le \sum_{i=0}^{n-1} 2^{i-M} < 2^{n-M}$.)

Now, determining the dimension of the subspace spanned by $E(M_0)$ is computationally fairly easy (at least unless both $M$ and $n$ are really huge), so any non-negligible difference in it between the actual encryption scheme $E$ and a random function would allow a distinguishing attack on $E$.  Secure encryption schemes are not supposed to be distinguishable from random functions (without knowledge of the key), so if $E$ is secure, there shouldn't be any detectable statistical difference between the dimension of $E(M_0)$ and that predicted for a random function.


UOV signature scheme, how does the affine transformation work? What does the composition of the core map and the affine map yield? I am having trouble understanding part of the UOV scheme, i get how it works except for when it comes to composing the core map F with an affine transformation say T, which i understand to be an invertible square matrix? I understand F to be composed of the o number of oil-vinegar polynomials where o is the number of oil variables. So does this mean that each multivariate equation in the core map F is multiplied by a square matrix representing the affine map T? What exactly would be the product of this multiplication? Is each multivariate oil vinegar equation treated as a 1x1 matrix and multiplied with T?
I know that the map T is used to do a change of basis on the system but the public key is supposed to be a system of multivariate equations so could someone help clarify what the composition of the core map F and the affine map T actually yields? Perhaps with a small example if possible?  For example in the case where o = 2 if i say the core map F is given by

$F = [3x_0^2 - 4x_0x_1 - 4x_1^2 + 8x_0x_2 + 11x_2^2 - 2x_0x_3 - x_1x_3 + 9x_2x_3 + 12x_3^2 + 7x_0x_4 - 11x_1x_4 - 9x_2x_4 - 2x_3x_4 + 3x_0x_5 + 5x_1x_5 + 14x_2x_5 - 11x_3x_5]$

$[-6x_0^2 + 10x_0x_1 + 10x_1^2 + 13x_0x_2 + 4x_1x_2 + 7x_2^2 - 7x_0x_3 - x_1x_3 - 13x_2x_3 + 4x_3^2 + 6x_0x_4 + 15x_1x_4 - 11x_2x_4 - 12x_3x_4 - 12x_0x_5 + 7x_1x_5 - 13x_2x_5 - 9x_3x_5]$

And an affine transformation $T$ given by:

$\begin{bmatrix}
18 & 23 & 14 &  1 & 6 & 21 \\
24 & 3 & 3 & 0 & 2 & 0 \\
17 & 25 & 2 & 16 & 23 & 8 \\
8 & 21 & 16 &  5 &  1 &  9 \\
14 & 28 &  8 & 17& 12& 12 \\
6 & 24& 18& 19&  3&  1& \end{bmatrix}$

what would the public key/the composition of the core map F and the map T be?

The secret polynomials are multivariate polynomials whose oil-oil terms have coefficient zero. You can represent it as a sum of terms, or as a vector-matrix-vector product. Take for example the polynomial of your example, $F_0(x_0, \ldots, x_5) = x^2_0 − 4x_0x_1 − 4x^2_1 + 8x_0x_2 + 11x_2^2 − 2x_0x_3 − x_1x_3 + 9x_2x_3 + 12x^2_3 + 7x_0x_4 − 11x_1x_4 − 9x_2x_4 − 2x_3x_4+3x_0x_5+5x_1x_5 + 14x_2x_5 − 11x_3x_5$. Using the vector notation $\mathbf{x}^\mathsf{T} = (x_0, x_1, \ldots, x_5)$ we can write this polynomial as the following product:
$$ F_0(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix}
1 & -4 & 8 & -2 & 7 & 3 \\
0 & -4 & 0 & -1 & -11 & 5 \\
0 & 0 & 0 & 9 & -9 & 14 \\
0 & 0 & 0 & 12 & -2 & -11 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{matrix} \right) \mathbf{x} \enspace .$$
The coefficients in the matrix are the same as in the sum-of-terms representation. Note that in this matrix representation, the bottom-right block consists of zeros; this reflects the fact that oil-times-oil terms have coefficient zero. Also note that this matrix is not unique: whenever $F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} M_{F_i} \mathbf{x}$ then for any skew-symmetric matrix $A$ (i.e. such that $A^\mathsf{T} = -A$) you can also write $F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T}(M_{F_i}+A)\mathbf{x}$. In particular, this means that (assuming odd characteristic) it is always possible to choose the central matrix to be symmetric by computing $\frac{1}{2}(M_{F_i}+M_{F_i}^\mathsf{T})$.

The secret linear transform $\mathcal{T}$ can also be represented in two ways. You give the matrix representation
$$ T = \left( \begin{matrix}
18 & 23 & 14 & 1 & 6 & 21 \\
24 & 3 & 3 & 0 & 2 & 0 \\
17 & 25 & 2 & 16 & 23 & 8 \\
8 & 21 & 16& 5 & 1 & 9 \\
14 & 28 & 8 & 17 & 12 & 12 \\
6 & 24 & 18 & 19 & 3 & 1
\end{matrix} \right) \enspace ,$$
in which case $\mathcal{T}(\mathbf{x}) = T\mathbf{x}$. You could also have chosen the list of polynomials representation, in which case there are 6 polynomials, $\mathcal{T}_0$ throught $\mathcal{T}_5$. For illustration, the first polynomial is given by $\mathcal{T}_0(x_0, x_1, x_2, x_3, x_4, x_5) = 18 x_0 + 23  x_1 + 14 x_2 + 1 x_3 + 6 x_4 + 21 x_5$.

To compute the composition $F \circ \mathcal{T}$ you must first choose a representation. In the polynomial representation we have $F \circ \mathcal{T} (\mathbf{x}) = F(\mathcal{T}(\mathbf{x})) = F(\mathcal{T}_0(\mathbf{x}), \mathcal{T}_1(\mathbf{x}), \ldots, \mathcal{T}_5(\mathbf{x}))$. So you can compute $F \circ \mathcal{T}$ by starting with a copy of $F$ and then substituting every occurrence of $x_i$ with $\mathcal{T}(\mathbf{x}) = \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5)$. But make sure to keep track of which occurrences of $x_i$ appear as a result of the substitution, because they obviously shouldn't be substituted twice.

In the matrix representation, we have $F_i \circ \mathcal{T} (\mathbf{x}) = \mathcal{T}(\mathbf{x})^\mathsf{T} M_{F_i} \mathcal{T}(\mathbf{x}) = (T\mathbf{x})^\mathsf{T} M_{F_i} (T \mathbf{x}) = \mathbf{x}^\mathsf{T} (T^\mathsf{T} M_{F_i} T) \mathbf{x}$. So a matrix representation $M_{F_i \circ \mathcal{T}}$ of the composition can be computed just by sandwiching $M_{F_i}$ between $T^\mathsf{T}$ and $T$, i.e., $M_{F_i \circ \mathcal{T}} = T^\mathsf{T} M_{F_i} T$.

To complete the example you started, let's assume we're working modulo 31 (because otherwise the numbers get quite large). Then we have
$$ M_{F_0 \circ \mathcal{T}} \cong T^\mathsf{T} M_{F_i} T = \left( \begin{matrix}
6 & 25 & 19 & 19 & 3 & 26 \\
22 & 29 & 3 & 29 & 28 & 2 \\
8 & 15 & 12 & 18 & 6 & 7 \\
28 & 1 & 24 & 17 & 4 & 1 \\
6 & 21 & 18 & 5 & 30 & 23 \\
11 & 23 & 8 & 15 & 5 & 5
\end{matrix}\right) \cong \left( \begin{matrix}
6 & 8 & 29 & 8 & 20 & 3 \\
8 & 29 & 9 & 15 & 9 & 28 \\
29 & 19 & 12 & 21 & 12 & 23 \\
8 & 15 & 21 & 17 & 20 & 8 \\
20 & 9 & 12 & 20 & 30 & 14 \\
3 & 28 & 23 & 8 & 14 & 5
\end{matrix}\right) \cong \left( \begin{matrix}
6 & 16 & 27 & 16 & 9 & 6 \\
0 & 29 & 18 & 30 & 18 & 25 \\
0 & 0 & 12 & 11 & 24 & 15 \\
0 & 0 & 0 & 17 & 9 & 16 \\
0 & 0 & 0 & 0 & 30 & 28 \\
0 & 0 & 0 & 0 & 0 & 5
\end{matrix}\right) \enspace .$$
Here the congruence sign ($\cong$) indicates that the matrices represent the same quadratic form, i.e., up to addition of skew-symmetric matrices. In other words, after sandwiching them between $\mathbf{x}^\mathsf{T}$ and $\mathbf{x}$ they will result in the same polynomial. From the last upper triangular matrix we can read out the representation of the polynomial as a sum of terms, namely
$$ F_0 \circ \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5) = 6x_0^2 + 16x_0x_1 + 27x_0x_2 + 16x_0x_3 + 9x_0x_4 + 6x_0x_5 + 29x_1^2 + 18x_1x_2 + 30x_1x_3 + 18 x_1x_4 + 25x_1x_5 + 12x_2^2 + 11x_2x_3 + 24x_2x_4 + 15x_2x_5 + 17x_3^2 + 9x_3x_4 + 16x_3x_5 + 30x_4^2 + 28x_4x_5 + 5x_5^2 \enspace .$$
This should be the same result as obtained through the substitution method applied to the polynomial representations.

One more thing: it is a good idea to avoid mixing homogeneous quadratic polynomials (i.e., without linear or constant terms) with affine transforms (i.e., with constant terms) -- or vice versa. In other words, whenever your secret polynomials are homogeneous, your secret transforms should be linear; whenever they are inhomogeneous, they should be affine. This guarantees that the public polynomials are (in)homogeneous whenever the secret ones are.


Ignoring the TAG of the AEAD-SIV encryption I am working with personal data that contain Identifying attributes such as a player ID and i need to prepare the data for analysis purposes, therefore i need to pseudoanonymize the data beforehand. However, the data should be pseudo-anonymized in a deterministic way in order to always have the same pseudo-anonym for the same player ID.
While searching through different sources, i ended up working with the encryption AEAD-SIV method mode implemented https://pycryptodome.readthedocs.io/en/latest/src/cipher/modern.html?highlight=siv#siv-mode where i specify a fixed nonce.
AEAD by definition creates a ciphertxt and a tag for each plaintext message and no one can decrypt the ciphertext except when providing the tag.  Therefore, from my side because i dont need to decrypt the ciphertext after encryption , i am only storing the ciphertext and completely ignoring the tag upon creation.
Therefore my questions:
1- Does it decrease the level of security of the encryption if we do not store the tag?
2- Also, In some cases am specifying a fixed padding in order to not have ciphertexts with different lengh. Does this process affect the level of security of the encryption?
3- Is AEAD-SIV still considered a standard for deterministic encryption? (I read about AEAD-GSM-SIV but there doesnt seem to be any available implementation yet).
Thanks in advance

Short answer: AEAD is completely the wrong tool for the job. You need a MAC, or perhaps a hash.
Here are two important facts about cryptography:

Details matter. You can't just take a good, secure construction and modify it and expect it to remain secure.
Cryptography is not limited to encryption.

from my side because i dont need to decrypt the ciphertext after encryption

If you don't decrypt, why would you encrypt? The whole point of encryption is that it can be decrypted if you have the key.
If you want to transform private identifiers into pseudonymous identifiers, a basic tool is a hash function. (More precisely, a cryptographic hash function: hash functions are also used outside cryptography. In a cryptographic context, "hash" means a cryptographic one.) Hash functions have the property that given y = H(x) but not x itself, the only way to recover $x$ is to guess it. This is probably not good enough in your case because anyone could just get a list of player IDs, or guess them, and calculate their hashes.
You can throw a secret key into the mix. With a MAC function M and a secret key k, given y = M(k, x) but not x or k, it's impossible to find x (or even to determine whether there is a valid x at all). Furthermore, given x and y but not k, it's still impossible to determine (or even make a good guess) whether y corresponds to this x. So you can use a MAC with a secret key, and only people with the secret key can associate player IDs with pseudonymous IDs in either direction.
Given the key k and a pseudonymous ID y, it's at the very least possible to guess x and verify whether M(k, x) = y. If you can't figure out x by guessing, it may still be possible to use the knowledge of k and y to get candidate x. Whether this is possible depends on the nature of the MAC. A popular class of MAC functions, HMAC, has the property that even with the key, it's impossible to find x other than by guessing, similar to the property of hash functions. (And for the same underlying reasons: HMAC leverages a hash function to build a MAC function.) HMAC is a good choice of MAC regardless of whether you care about this property.
Given your problem statement, I think HMAC matches your requirements. However, I am unsure whether your technical requirements match your expectations on privacy. I would recommend that you consult with an expert on privacy.

AEAD by definition creates a ciphertxt and a tag

Not necessarily. In general, AEAD encryption creates a ciphertext and decryption takes this ciphertext as input, plus the key, nonce and additional data, and either returns the plaintext or a decryption failure report. It is true for many AEAD mechanisms, including SIV, that the ciphertext can be broken up into a tag which is necessary to determine whether the ciphertext is authentic and a ciphertext-without-tag which is sufficient to recover the plaintext if the ciphertext is authentic. But this decomposition is not an intrinsic requirement of AEAD and is not a useful way to process AEAD functionally.

no one can decrypt the ciphertext except when providing the tag

This is wrong (for AEAD modes that do have a distinctive tag, which includes SIV and most others). Without the tag, it's still possible to decrypt the ciphertext, in the sense that it's possible to find the original plaintext. It's just not possible to determine whether the plaintext is authentic.

Does it decrease the level of security of the encryption if we do not store the tag?

Not as such. If you don't store a part of the ciphertext, it can reduce the security of authentication (you lose part of your ability to verify that the data is genuine), but not the security of encryption (erasing some information doesn't reduce the confidentiality of data).
However, not verifying the tag can reduce the security of the encryption – see next paragraph.

Also, In some cases am specifying a fixed padding in order to not have ciphertexts with different lengh. Does this process affect the level of security of the encryption?

Maybe: padding can allow padding oracle attacks. The gist of a padding oracle attack is that an attacker makes up some fake ciphertexts and asks you to decrypt them. You decrypt, and verify the padding. If the response reveals something about the validity of the padding, this can allow the attacker to decrypt arbitrary ciphertexts, or perhaps only ciphertexts in a certain format. This happens if there's some way to present part of the plaintext as padding, which there usually is since the point of padding is to be in the place where some plaintext would be if it was longer. The details depend on the nature of the padding and the encryption.
AEAD is invulnerable to padding oracle attacks because the attacker can't make up valid ciphertexts. (Also, most common AEAD modes don't have padding – but even if they did, the authentication would protect them.) That, of course, goes for AEAD used as such. If you take an AEAD construction and throw some parts out, all bets are off.

Is AEAD-SIV still considered a standard for deterministic encryption?

Yes, if you needed deterministic authenticated encryption, then SIV would be a good choice.


Is it possible to have 11 rounds with an AES of 128 bits? I want to attack a hardware AES. It is with a 128bit in its key. However, according to the documentation I have 11 rounds in this AES.

I don't understand why I have 11 rounds? What is the role of the 11th round?
Let's suppose that I want t attack the 10th round, must I compute the 10th ciphertext? (I mean that my 11th subkey is different from the 10th round subkey.)

I don't understand why I have 11 rounds? What is the role of the 11th round?

I suspect that they are doing standard AES-128, and thus have 10 rounds.

By '11 rounds', I suspect they mean '11 subkeys'; AES uses one more subkey than it has rounds.

  Let's suppose that I want t attack the 10th round, must I compute the 10th ciphertext?

I rather suspect what's actually needed to perform the attack will depend on the details of the attack.  On the other hand, without the final subkey, you can't compute the intermediate cipherstate (and if you knew the final subkey, that'd give you the entire key anyways).

I suspect that it's easiest, for a DPA-style attack, to attack either the first or the last subkey; those subkey bits satisfy the equation $S = K \oplus I$, where $S$ is one of the subkey bits, and $K$ is a bit you know (it's either a plaintext bit or a ciphertext bit), and $I$ is a bit of the AES internal state; if you can find a correlation with $I$, you can recover $S$; recover enough $S$ bits, and that's the game...


Example use case of signature using RSA I understand how RSA can be used for message encryption:

Alice wants to send a message to Bob.
Bob generates a public key $(n, e)$ and private key $d$; he keeps the private key for himself only, and sends the public key to Alice.
Alice encrypts the message with the public key.
Alice sends the encrypted message to Bob.
Bob can decrypt it with the private key.
Eve who stole the encrypted message (but who has not the private key) cannot decrypt it.

Can we describe a similar situation (in Layman's terms, with two people and a third malicious person) to explain how RSA can be used for message signature?

Note: My problem is not the maths (I studied RSA and understand the maths in it) but more an example of situation showing how signature works.

Alice wants to prepare Bob for a future message.
Alice generates a public key $(n, e)$ and private key $d$; she keeps the private key for herself only, and gives the public key to Bob up front.
When Alice has decided on the message $m$, she scrambles it and compresses it irreversibly into an integer $h$ the same size as $n$ by a public hash function $H$ of the message, giving $h = H(m)$, and computes $s \equiv h^d \pmod n$.
Alice sends Bob the signed message $(m, s)$.
When Bob gets a possibly forged signed message $(\hat m, \hat s)$, he computes $\hat h = H(\hat m)$ using the public hash function $H$, and rejects it unless $\hat h \equiv \hat s^e \pmod n$.

For Alice's original legitimate message, $s^e \equiv (h^d)^e \equiv h^{de} \equiv h \pmod n$, so Bob always accepts a legitimate message from Alice.
Mallory, who intercepted the message $m$ in transit, and wants to replace it by $\hat m$ (but who does not have the private key $d$), does not know the corresponding $\hat s$ that Bob will accept.
Bob can show the message to Charlie, if he also has Alice's public key, and Charlie can verify it too using the same procedure—Alice can't send one message to Bob and claim to Charlie she didn't sign that message.  (This property is called ‘nonrepudiation’ or ‘undeniability’.)


Hash function based on block cipher (and proof of security in the PRP model) Do there exist proofs of security for primitives like hash functions (based on a block cipher) in the PRP model.

I often see proofs in the random oracle model (for hash function based on compression function) and proofs in the ideal cipher model (for hash function based on block cipher).

Are there proofs of such primitive in a real world model?

A PRP is a keyed primitive, so proving properties of a keyed hash on top of it is often possible. Reducing the security of an unkeyed hash to a keyed primitive on the other hand is rarely possible.

For example keyed Skein (a hash) is provably a PRF if Threefish (a block-cipher) is a PRP:

  PRF, MAC, and KDF. We prove that if Threefish is a tweakable PRP (pseudorandom permutation) then Skein is a PRF. It is important to understand that we are referring, in this context,
  to the keyed version of Skein. The PRF property is that the input-output behavior of keyed Skein
  should look like that of a random function to an attacker who is not given the key. This proof
  supports the usage of keyed Skein for key derivation (KDF). It also supports the use of keyed Skein
  as a MAC. This is true because any PRF is a secure MAC


Security of Diffie Hellman in specific cyclic group For some $k$, let's say $p = 1+ \prod_{j=1}^k q( j)$, where $q(1)=2$, $q(2)=3$,
if $p$ is prime, the diffie-hellman key exchange is not secure in cyclic group $Z^*_p$. Why?

If $p$ is a prime of the specified structure then the order of the multiplicative group $\mathbb Z_p^*$ is $p-1=\prod_{j=1}^k q( j)$. As you may notice this is a product only consisting of small factors and thereby called smooth.

We actually know an attack on groups with smooth order, called Pohlig-Hellman-Algorithm and the specified structure yields the optimal performance for that algorithm to compute discrete logarithms.


How to calculate initial RC5 encryption parameters? I learn from a minithesis to understand RC5.
As we can see at the formula, the round 0 must be using A=A+S[0], because the loop is starting at r(round) 1.

I tried addition and OR(bitwise) to get the answer DA679BFB but keep missing, Here is my result of calculating.

A = A + S[0]

  = 4B726970 + BF0A8B1D

  = 10A7CF48D

A = A OR S[0]

  = 4B726970 OR BF0A8B1D

  = FF7AEB7D

The S Data is the result of 3rd phase key expanding on RC5. I really need help because I have been stuck here for 2 days and thank you in advance.

Plaintext : 4B726970 746F2053 74656761 6E6F
key       : 4B726970 746F6772 616669
w(blocksize) = 32, r(round) = 12, b(key lenght) = 16

First: you should use addition, not XOR. Next, if you're doing this calculation with a computer, make sure you're processing the bytes as little-endian, and that you pad your key to the 16 bytes you mentioned:

4B726970 746F6772 61666900 00000000

Now, you have basically answered the question yourself of why you aren't getting the correct value:

  The S Data is the result of 3rd phase key expanding on RC5.

The formula A = A + S[0] is correct, but as you note there are multiple phases of mixing the $L$ and $S$ arrays. During the first phase, $A$ and $B$ look like:

i=1 A= **0xbf0a8b1d** B= **0x5ee7fad**
i=2 A= 0xd88eaf30 B= 0x2a1c93ca
i=3 A= 0xb7dc3e7f B= 0xc47155c4
...

These are the values on the right-hand side of the image you posted. The value 0xbf0a8b1d in particular is the one you've been trying to add. What you should be using are values from the 3rd phase:

i=1 A= **0x8ef5328b** B= **0x600e18b6**
i=2 A= 0x64aa69d0 B= 0x384a0d6
i=3 A= 0x7a471ae8 B= 0xd5a140fa
...

So now, take your plaintext word 0x4b726970 and add it to 0x8ef5328b, and you get the desired value of 0xda679b7b:

i=1 A= **0xda679bfb** B= 0xd9198a23 # before the loop even starts
i=2 A= 0x9637a9a8 B= 0x7e949194
i=3 A= 0x4ec0dda1 B= 0x299ed426
...

I followed Rivest's paper on RC5 and double-checked my values against a Python implementation. We don't do implementation details here, but that should answer why you haven't been able to match up to that example.


What is the relation between AES and PTK in WPA2 wifi I know that modern wpa2 wifis use AES key to encrypt data.

a client who has the password, can obtain psk/pmk use it for handshaking .

so what is the purpose of ptk, and   how AES key is generated?

WPA2 uses either a password or a pre-shared key to create the PMK.

Specifically, the PMK comes from:

If there is a PSK, the PMK is the PSK
A PSK is either a 256-bit key or derived from a passphrase
If a passphrase is used, it generates the PSK using the AP SSID as the salt: PSK = PBKDF2(HMAC−SHA1, Passphrase, SSID, 4096, 256)
If there is no PSK, the PMK is derived using 802.1x EAP exchange, usually RADIUS

Once both the client and AP have the same PMK, they prove to eachother they have matching keys using a 4-way handshake, which is also used to derive the PTK by adding a nonce from each party.

Specifically, the 4-way handshake does the following:

Confirm the client’s knowledge of the PMK
Confirm the AP's knowledge of the PMK
Derive a new and unique PTK
Install encryption and integrity keys
Encrypt transport of the AP generated GTK to the client
Confirm cipher suite selection

The PMK, nonces, and handshake MAC addresses are run through a PRF based on HMAC-SHA1 to derive the 512-bit PTK. During the handshake the AP also transmits the 256-bit GTK, or Group Temporal Key, to the client. The PTK and GTK are split into several components, some of which are used as AES keys for different types of network traffic, and some of which are integrity keys.

KCK = PTK bits 0-127, the key confirmation key
KEK = PTK bits 128-255, the key encryption key
TEK = PTK bits 256-383, the temporal encryption key for unicast traffic
TMK = PTK bits 384-511, the temporal MIC keys for TKIP
GEK = GTK bits 0-127, the group encryption key for multicast traffic
GIK = GTK bits 128-255, the group integrity key for TKIP

When WPA2 is used the cipher is CCMP, which is an AES-CTR based mode with a CBC message authentication, and thus the TKIP integrity keys are not used


What is the new attack on SHA-1 "SHAttered" and how does it work? There's a new recent Attack on SHA-1 named "SHAttered" by Google and some researchers. I understand that it uses some fancy new techniques, but not the details.

My question is: How?

How does the attack work (on a high level)? How does it compare to previous attacks?

Note: The matter of implications is already handled by this other question, so don't focus on it please.

In order to get a collision on a $n$ bit Random Oracle using the birthday paradox, one needs $\sqrt{\pi / 2} \cdot 2^{n/2}$ calls. In other words, in the case of the 160 output bits of SHA-1 the limit is in the order of $2^{160/2} = 2^{80}$.

Previous Attacks

SHA-1 (and the broken SHA-0) have been under the following attacks over the past few years:

Differential collisions in SHA-0 by Chabaud F., Joux A. have collisions in SHA-0 in $2^{61}$ calls.
Near Collision in SHA-0 by Biham E., Chen R. at CRYPTO 2004
Collision of SHA-0 and Round reduced SHA-1 by Biham E., Chen R., Joux A., Carribault P., Lemuet C., Jalby W. at EUROCRYPT 2005
Finding Collisions in the Full SHA-1 by Wang et al. at CRYPTO 2005
Practical Free-Start Collision Attacks on 76-step SHA-1 by Pierre Karpman, Thomas Peyrin and Marc Stevens at CRYPTO 2015
New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis by Stevens M. at EUROCRYPT 2013

The 4th paper presented an attack in $2^{69}$ calls showing the weaknesses of SHA-1. The 6th paper will be the ground work of the SHAttered attack.

The main idea behind these attacks relies on Differential cryptanalysis.
You have two inputs $t_0$ and $t'_0$ with a difference of $\Delta_0$. Once these two inputs have gone through the function $f$ (the compression function in the case of SHA-1) you get a difference $\Delta_1$ and so on (see following picture)...

The goal here is to find a difference in the input $\Delta_0$ such that after some iterations you get $\Delta_2 = 0$, in other words no difference.

the SHAttered Attack

Because of the Merkle–Damgård construction of SHA-1, one can choose to alter the differences between the iterations in order to improve the differences to match his needs. In the case of the SHAttered Attack, they chose an initial prefix ($P$), then later on the next blocks they introduce a difference ($M^{(1)}_1$,$M^{(2)}_1$) and remove it ($M^{(1)}_2$ and $M^{(2)}_2$). At this point they already have their collision. They just need to continue with the same following blocks ($S$), leading to a collision on the whole input.

$\mathrm{SHA-1}(P||M^{(1)}_1\mathbin\Vert M^{(1)}_2\mathbin\Vert S)=\mathrm{SHA-1}(P||M^{(2)}_1\mathbin\Vert M^{(2)}_2\mathbin\Vert S)$

The values of $M^{(1)}_1$, $M^{(2)}_1$, $M^{(1)}_2$ and $M^{(2)}_2$ are as follows:

The difficulty is thus to find the correct $M_i$ that satisfy the chosen prefix criteria $P$ and that cancel themselves nicely afterwards. The probabilities of such to occur are really small, thus the need of massive amount of calls to SHA-1 compression function ($2^{63.1}$).

In the case of the provided PDFs, they also give a nice infographic which explain where the difference is located in the PDFs:


Serpent intermediate rounds differs from example code, but result is still correct, is it a problem? Through great pain and suffering, I've been able to successfully implement Serpent. For example, when using the key 00112233445566778899aabbccddeeff, and encrypting the plaintext 0123456789abcdeffedcba9876543210, the result is 929dd890dcc881c9a7d8b94b0aa0bad5.

However, when I compare my internal rounds to those of the example implementation, there are differences in all rounds except the final one, which is correct. Notice the difference too, my last round is the ciphertext, but it's not the case for the example.

Is that difference a problem, or not ? All other plaintext and keys output the correct ciphertext, so it's correct. Will that difference mean any issue for implementing different modes, is it an attack vector ?

For the key 00112233445566778899aabbccddeeff, and encrypting the plaintext 0123456789abcdeffedcba9876543210 I obtain:

R[00]=763c678fe817625f538ba6e05b920db9
R[01]=3d2fdec36f875b312c3b4dff7bdfd128
R[02]=bd9e4ae53f686b1da714cf4a9d2e6868
R[03]=8acc4503741256b9225d581711eacf4d
R[04]=d765bcb8c133fea981064ec5eb09f56f
R[05]=baa2fd5c5628e8445e79ee7ea5cf9cb5
R[06]=25023893d3789b727be0440a5cfa39e3
R[07]=2d93f0484f3dbc800c4537fd742b62f5
R[08]=6f36c03ab9a62671d418cfb487d45fe7
R[09]=b3d6210bf3bbd2d702a208ef25cfdbe0
R[10]=5c9af1c0d10ce8a3818b22f17f0e097b
R[11]=efb1e65f22e8e68826ce7db29492e5e2
R[12]=97443a983133cbe233b9fef910b96bce
R[13]=5f827660c8f7a489092ca20651ba18a4
R[14]=0a415d75cfe2d976980ac48c41fc5efd
R[15]=f23153c6a50110eead08f8b1cfdcbd47
R[16]=ef002fc254c43e7990da5474d7879461
R[17]=d7b61d1a39aee4c8a14cc4b1d8dc4226
R[18]=7b8cdd49398741c0d0ae6e095812b6a6
R[19]=34d5f60fd24717e0c4dcd1214e502833
R[20]=de5ba6aa229feebc9f34f62001ddc55f
R[21]=9fbd25551344a04b6a6744f9c2739b5a
R[22]=4f25a8e314d8ca550d99451ed02d1e67
R[23]=51880459ded93b04a54327624424c37d
R[24]=da4457c92effe0fe6956a25daa628f22
R[25]=82c6ef91a38269c14ca8b3b8c0f988f1
R[26]=cd2ecf8555c299fc37a7d9df59359b58
R[27]=cf8e350c9738ce9a45b63843eb175c00
R[28]=779285520a7e22fdbb4d7a83984944b2
R[29]=c66612592163cb3c0c83d2a4801ebe86
R[30]=c5be4758e4241f04383888de8aa432d6
R[31]=929dd890dcc881c9a7d8b94b0aa0bad5

And the example implementation is supposed to output this:

R[0]=4fcb58b3308dac762ce01be9b635dccd
R[1]=05f9fe5d51a3bdff9f0deac7aa7632ae
R[2]=b0eddf6f845adb902f50f2e68b947c2c
R[3]=846584a19b16ba521f063d59414653af
R[4]=fd18189f08c41a6dd7ddef61e3d8d317
R[5]=969ea7e193e27193fee9fb281e3baf21
R[6]=47a7396e37755090429dd245955c20f9
R[7]=0591ef4c825c569fc9fe46327b33a303
R[8]=7ac6cb9d51cb2dc0ab41377335fe8395
R[9]=c4dc01edf96c59f5558530597734a6ee
R[10]=6d1d9917a008f5b2cce85029eb731057
R[11]=98e18be8f6c96238dff22fc3793ac8b8
R[12]=806f08ae3877384767baf2f5f76ab152
R[13]=4d09e88bd47536d468e91ca058904324
R[14]=6502e4c55d5131686f0ddb1c3ddd3f49
R[15]=f9e837971189310c3a3f3189ed624dd3
R[16]=bd878d997602253112c7cfc88f764285
R[17]=b96d588ed3c97fc067488e18643ac192
R[18]=2bcfd08ce021ae749e39ab3c5c10a11a
R[19]=678c1b50af0b2e4caa9e1cc64471889b
R[20]=a84aaae3592fd7cdf7e24fe1c1e5d591
R[21]=932ca8fc87b98e3b52c11a192f2b785e
R[22]=1905ae8a6496790bc681d3528d9627bd
R[23]=6d2c474ac614c12611644a770b399529
R[24]=9a78f4d24f564e747c6819b9ce56e65a
R[25]=d34022c4f93138c1bce2d8aef53b200d
R[26]=8d279e2f64b18be3fa07f89fe7477e2a
R[27]=db149edfa067cbb145ab7d484204c862
R[28]=38ab78ea874c76c3836229687c5d44b6
R[29]=98402a842cc119f6761b51f4386cc718
R[30]=dc623c1890faad8028156cdc3b0ba730
R[31]=e42c56b2f61ae808f83bb016d7096127
CT=929dd890dcc881c9a7d8b94b0aa0bad5

To check if it is a bitslice issue, we can look at a round output, this is round 1 from the example:

0000 0101 1111 1001 1111 1110 0101 1101 0101 0001 1010 0011 1011 1101 1111 1111 1001 1111 0000 1101 1110 1010 1100 0111 1010 1010 0111 0110 0011 0010 1010 1110

And yours:

0011 1101 0010 1111 1101 1110 1100 0011 0110 1111 1000 0111 0101 1011 0011 0001 0010 1100 0011 1011 0100 1101 1111 1111 0111 1011 1101 1111 1101 0001 0010 1000

To check for bitslicing, start selecting every 4th bit in one of them (starting at 0), then compare it to the first 32-bit word of the other

As we can see, every 4th bit of the example does indeed match the first 32-bits of your output. I also spot checked the final 16 bits which also match. I suspect that if you keep going with that round, all bits match, as would the rest of the rounds. A rapid way to check if that is probably the case is to convert to binary then use an iterative counter to count the number of 1 bits per round.


Are block ciphers vulnerable to “key reuse” and/or “bit-flipping” attacks? I know that almost all stream ciphers are vulnerable to “key reuse” and “bit-flipping” attacks.

Because AES also uses $XOR$ in its algorithm, is it possible for block ciphers – like AES – to be vulnerable to “key reuse” and/or “bit-flipping” attacks?

XOR may be used internally, but that doesn't mean the resulting ciphertext is automatically vulnerable against bit flipping or key reuse attacks. XOR is used for techniques to create confusion & diffusion, over multiple rounds.

An attacker doesn't usually have any influence on those internal operations unless side channel attacks apply (or when we're talking about white-box cryptography). If the attacker does have access, then changing a bit operation for XOR is likely to affect multiple output bits.

As for AES: to create a IND_CCA secure cipher, AES needs to be used within a block cipher mode of operation. That cipher mode could e.g. be CTR or any other mode that generates a key stream. That streaming mode of operation in turn will be vulnerable with regards reuse (same IV/nonce) and bit flipping attacks.

Other modes of operation such as CBC are also vulnerable against IV reuse, although the resulting attacks are much less powerful. For instance, an attacker could distinguish completely identical starts of the plaintext, as the ciphertext will be identical as well.

The same goes for bit flipping, although for CBC mode a whole block + one bit will change. It depends on the implementation if these larger changes will be picked up. If it does, it may result in a plaintext-oracle (e.g. a padding oracle), which may further compromise confidentiality.

So in the end it is (almost) always required to create a unique IV for any cipher and mode of operation. To avoid bit flipping an authenticated mode of operation or (H)MAC could be used.


Authentication using a one-time pad I am building a small embedded system of two nodes that communicate wirelessly.  The microcontrollers I'm using are very limited: they only have 256 bytes of RAM.  I would like to be able to authenticate messages sent and received between the nodes, but traditional methods such as HMAC aren't possible because of the constraints of the system (lack of RAM).

I do have a large (2 megabit) EEPROM that is largely unused.  I would like to use this space to store a (relatively) large one-time pad that could be used to authenticate the messages, which are only a few bytes long.  I do not care about the secrecy of the messages, only their unforgeability and integrity.  If only, say, 4 bytes of pad are used per message, the pad should far outlast the system's expected usefulness.  Finally, messages are not guaranteed to be received by the other node (for example, due to interference, malicious or not).

Are there any schemes that use a one-time pad for message authentication?  Assume the one-time pad is truly random.  Or is this an entirely hair-brained idea that is inherently insecure?

Actually, it's not a hare-brained idea at all; you certainly can do integrity checking using a one-time pad.  However, I believe that you'll need to use the one-time pad bits a bit faster than you'd expect, to achieve a forgery probability of at most $2^{-32}$, I believe you'll need at least 64 pad bits per packet (assuming informational theoretical security - that is, we don't include any computational problems that are too difficult for the attacker to solve).

One way to do this would be do a polynomial hash over $GF(2^{32})$; that is, you use 32 bits of the pad as a value $H$, and compute the value $V = X_i H^i + X_{i-1} H^{i-1} + ... + X_1 H^1 + R$ (where the message is $(X_i, X_{i-1}, ..., X_1$, and $R$ is 32 other bits from your pad, and where the computation is done within $GF(2^{32})$; the value $V$ is your tag that you send with the packet.  This provably has a forgery probability of a modified packet of at most $i 2^{-32}$ and a blind forgery probability of $2^{-32}$.  You'd need to implement a $GF(2^{32})$ multiply routine; assuming you don't need extreme speed, that's not that difficult.

That being said, might I suggest a totally different approach: how about using Speck in a Davies-Meyer construction with a key?  Speck is a block cipher that can be evaluated with minimal memory, and a Davies-Meyer construction would't require much memory.  You'd start the construction with a secret state; assuming that you don't use the block size of 128, you'd also want to end the hash with hashing some other secret data).  The advantages of this approach: you can reuse the same secret data (keying material) for every packet (and so there's no possibility of running out); you don't need to worry about packet drops (as this construction is stateless), and it should fit within your restrictions.


RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N? For $N=pq$, if the first $x$ least significant bits of both $p$ and $q$ are leaked.

what is the advantage in factoring $N$?
Does this give an advantage beyond simply lowering the number of bits we have to guess for the smaller factor?

This question looked due to the Cold boot attack, by Halderman et. al. Normally researchers look at some random known bit known due to the decaying of the memory.

2009 Heninger et. al Reconstructing RSA Private Keys from Random Key Bits

if $\delta = .57$ fraction of the bits of $p$ and $q$ is randomly is given they can construct them.

The closest article is by Maira et. al.

2010 - Maitra Factoring RSA Modulus Using Prime Reconstruction from Random Known Bits, also a slide of one of the authors.

In Section 2 and 3, they look at LSB case. With theorem 1;

Theorem 1: Let $N = pq$, when $p, q$ are primes of same bit size. Let $S = \{0,\ldots, l_{N /4}\}$. Consider $U \subseteq S$ and $V = S \backslash U$. Assume that p[i]’s for $i \in U$ and $q[j]$’s for $j \in V$ are known. Then one can factor $N$ in $poly(\log N)$-time.

$l_N$ the bit size of $N$, i.e, $l_N = \lceil log_2 N\rceil$.


SHA1 padding on length extension attack I was recently trying to replicate a length extension attack on SHA1. I implemented the registers state and also the new padding implementation (with the whole of the message that I want to extend). And it works, I know the length of the key, so I'm able to get the total length of the message and forge a hash. However, when I try to brute force the length of the key (as it should be unknown), I always end up getting the same hashes for groups of 64 lengths, and not different ones for each. This makes sense for me, as I am padding the (original message + key) and so the length of the padded message should be the same for a certain number of key sizes, right? Does this imply that it is impossible to retrieve the key length? I think there is something wrong in my reasoning... Here is the code that I'm using:

for i in range(0, 200):

        specificLength = len(padSHA1(i * "a" + originalMsg) + "extension")

        forged = sha1ExtensionAttack("extension", registers, specificLength)

        print i, forged, payloadSHA, specificLength

        if forged == payloadSHA:
            print i, len(key)
            assert len(key) == i

            print "[*] Length of key is {}".format(i)
            break

When I run it with a key length of 49 I end up getting a success with a length of 43, which doesn't make much sense. Then, I get the same hash for lengths 43 to 107...

I'll be very grateful if anyone explains to me what's wrong with this approach, thank you!

Yes, the length extension is identical for key sizes that are a multiple of 64 as SHA-1 has an input block size of 512 bits. So you would have to generate the exact same padding for the same message in that case. However, commonly this includes the encoding of the length of the input message of the hash in bits.

The output of a number of blocks of SHA-1 cannot be distinguished from random if the input is sufficiently randomized. This is definitely true if a fully randomized key is used at the start of the hash. So you cannot get any information out of it. This is also true for any MD5, SHA-2 or any other Merkle-Damgård hash without any pre/post-processing to avoid it.

The fact that you can test your attack successfully while the sizes are unknown  in advance must therefore mean that you have some kind of oracle to test against. And this oracle simply returns success if you guessed the total message input size correctly, which is the addition of the key size and message size of the keyed hash.

For most protocols you'd know the key size, or consider it known due to the Kerckhoff principle. This is just a configuration parameter after all, it is not part of the security delivered by the key. However, that doesn't mean that you can calculate it from just the output of the hash function.


MQV protocol and man-in-middle attack Why MQV is said to be an “authenticated Diffie-Hellman” protocol? The process in the picture shows nothing about authentication. Besides, a man-in-middle can impersonate B to negotiate with A, because A does not verify the identity of B.

The process in the picture shows nothing about authentication

You are correct in that explicit signatures are never sent, however the exchange involves so-called implicit signatures. You will note that the derivation of the shared secret relies not only on the ephemeral session keys $(x,X)$ and $(y,Y)$, but also the long-term authentication keys $(a,A)$ and $(b,B)$. The concept then is to create a system where knowledge of both $x$ and $a$ is required for Alice to construct the correct shared secret. If either party does not know both the private keys, then they will disagree on the established secret, and thus the exchange will fail.
The importance of this in AKE is that we construct a scheme which retains many of the desirable traits of ephemeral key exchange whilst still having a long-term key which can be used as the basis for a certificate. If the protocol succeeds (assuming there are no good attacks on MQV), the parties can be assured that they know the correstponding private keys to their long-term public keys $A,B$.

Besides, a man-in-middle can impersonate B to negotiate with A, because A does not verify the identity of B.

You're correct; the scheme in its raw form, without a trusted third party, is vulnerable to someone simply publishing their own long-term keys whilst purporting to be a legitimate party. However, this is not the purpose of authenticated key exchange in the form presented here. The purpose of authenticated key exchange as presented here is to verify private key ownership, which is different to identity. Much like how a digital signature does not actually prove that Alice signed something, only that someone who knows the private key corresponding to the public key you believe to be Alice's signed it.
We can construct a system which verifies identity from a system that verifies private key ownership with the aid of certificates and a T3P in the form of a CA.
This is not to say there are not attacks on MQV which can undermine some aspects of its intended goals
B. Kaliski showed that MQV is vulnerable to a Unknown Key Share attack whereby Eve can trick two participants into performing a key exchange where:

Alice knows she is performing a key exchange with Bob
Bob thinks he is performing a key exchange with Eve

Note that Eve does not actually discover the shared secret, and this can be mitigated with a key confirmation step, where participants prove to each other that they know the shared secret, but the MQV protocol does not force this. HMQV is a version of the protocol which aims to stop the attack whilst not requiring explicit key confirmation.


PKI Validation - Usefulness of the public key with the identity certificate I have some understanding of how PKI works, similar to this:
- https://knowledge.digicert.com/solution/SO16297.html
- https://security.stackexchange.com/questions/59566/ssl-certificate-chain-verification
- https://security.stackexchange.com/questions/56389/ssl-certificate-framework-101-how-does-the-browser-actually-verify-the-validity

What isn't obvious to me is how the public key at the end of the chain, or the identity certificate is used. Previously RSA may have been used for encryption, or as the key exchange for a symmetric cipher key, however ECDHE appears to be the modern primitive for key exchange.

My guess is the certificate is also signed by itself, along with the intermediates and roots in the chain. This would make sense to me since in my mind anyone would be able to use the cert in various ways, however if signed with the private key of the identity it's an extra check. Other wise I would see the identity private key as being pretty useless.

Most explanations are very simple with how a chain is evaluated and I'd like some detail.

So my question - is an identity certificate also signed by itself? Does my logic above stand up?

I may have found an answer here: https://devcentral.f5.com/questions/difference-between-root-cert-intermediate-cert-and-ssl-cert

  One more thing one the public key of your server certificate. There is
  the same mathematical relationship as described above between the
  public key and private key of your server certificate.

  It will be used during the SSL handshake. The client encrypts some key
  material servers public key (retrieved by the client out of the server
  certificate) and sends it to the server. It can be decrypted by the
  server using the private key. If the server does not have the matching
  private key it cannot decode the key material and the handshake
  brakes.

But the above may be referring to using RSA for symmetric key transference, which like I posted earlier is generally done by ECDHE these days.

I imagine you'd just be able to take the certificate and use it to spoof a site if you successfully hijack DNS without any validation of the identity certificates public key. Surely it's validated in some way.