Entropy when iterating cryptographic hash functions Consider a cryptographic hash function that maps $n$-bit strings to $n$-bit strings:

$$
\DeclareMathOperator{\H}{H}
\DeclareMathOperator{\SHA}{SHA-256}
\H(x) : \left\{0,1\right\}^{n} \mapsto \left\{0,1\right\}^{n}.
$$

Let $\H^i$ denote the result of iterating $\H$ $i$ times, i.e., $\H^1 = \H$, $\H^2 = \H \circ \H$, etc.

Suppose we choose $x \in \{0,1\}^n$ uniformly at random.  What is the estimated amount of entropy in $\H^i(x)$?  I'm most interested in the case $n=128$.

More specifically, I'm particularly interested in the following special case.  Define a hash function $\H$ by truncating the output of $\SHA$ to $128$ bits, i.e.,

$$
\H(x) = \SHA\left(x\right)\mid_{128}
$$

With this definition of $\H$, what is the entropy of $\H^i(x)$ now, when $x$ is chosen uniformly at random from $\{0,1\}^{128}$?  Does $\H$ maintain 128 bits of preimage resistance from $\SHA$, or is it significantly weakened? Are any other security properties of the underlying hash function weakened?

My estimate of the entropy after $i$ iterations is roughly $128- \lg i$ bits (as $i$ grows large).  I don't have a proof of this, but I'll lay out my rough back-of-the-envelope calculations below.

Here is the general problem:

  Problem 1. Let $F:\{0,1\}^n \to \{0,1\}^n$ be a random, i.e., chosen uniformly at random from the set of all functions with that signature.  Let $F^i$ denote the result of iterating $F$ $i$ times.  Let $X$ be uniformly distributed on $\{0,1\}^n$.  Let $F$ be known to the adversary, and $X$ be secret.  What is the entropy of $F^i(X)$?

I don't know how to solve that problem.  But here is a related problem that I do know how to solve.

  Problem 2. Let $F$ be as above.  Let $f_i$ denote the fraction of $n$-bit values that can appear at the output of $F^i$.  In other words, $f_i = |S_i|/2^n$, where we define $S_i$ to be the the set $S_i = \{F^i(x) : x\in \{0,1\}^n\}$ of all values that can appear as the output of $F$ iterated $i$ times.  What is the value of $f_i$, as a function of $i$?

Note that the answer to the problem 2 gives us a heuristic rough estimate at the answer to problem 1.  In particular, if we assume that $F^i(X)$ is approximately uniformly distributed on the set of all possible values (i.e., on $S_i$), then the entropy of $F^i(X)$ will be approximately $n - \lg f_i$.

And I can give you a reasonable solution to problem 2.  In particular, using a crude heuristic, $f_i$ approximately satisfies the following recurrence relation:

$$f_{i+1} \approx 1 - e^{-f_i},$$

where $f_0 = 1$.  The first few values of $f_i$ are $f_1=0.632$, $f_2=0.469$, $f_3=0.374$, $f_4=0.312$, $f_5=0.268$, $f_6=0.235$, $f_7=0.210$.  This recurrence relation does break down when $i$ gets extremely large, certainly by the time $i$ reaches $2^{n/2}$ or so, but this might not be a major concern for the values of $i$ you care about in practice.

Asymptotically, when $i$ gets large enough (but not so large that it gets close to $2^{n/2}$), I think that a crude approximation to $f_i$ is

$$f_i \sim 2/i.$$

Thus, for large (but not too large) $i$, this gives us a crude estimate for the entropy of $F^i(X)$ as

$$n-\lg f_i \approx n+1-\lg(i).$$

Plugging in $n=128$ in your particular problem, we get $129-\lg(i)$ as an estimate of the entropy after $i$ iterations.  This is within $\pm 1$ bit of my estimate at the top of the answer.

Incidentally, I have in my notes that a better approximation is $f_i \sim 2/(i+\log(i))$, but I don't know where I got this from, so it might be faulty.  If that approximation is accurate, then a better estimate of the entropy of $F^i(X)$ is $n+1-\lg(i+\log(i))$.

Again, as a reminder, all of these estimates are only intended to be used when $i$ gets large (but not crazy large).  When $i$ is small, you can calculate $f_i$ directly using the recurrence relation above.  And all of these estimates are just estimates, that rely upon several approximations, which may be pretty crude.

My thanks to @fgrieu for helpful comments on this answer.


One-time-pad encryption As we know, intercepted ciphertext created by a one-time pad only reveals the length of the message. That is the only information the attacker can get since this ciphertext is unbreakable without the key.

I understand that for a file 1GB in size we need a key that is 1GB long. My question is: why is the one-time pad not more widely used in encryption for communications that use a small bandwidth?

One time pads are used in many low bandwidth situations.  However, they suffer from a fundamental problem of key distribution.  It's hard to transmit 1GB of key information.

One time pads are most effective in situations where the trust communication channels are highly asymmetric.  If you can hand deliver your OTP to an individual, positively confirm their identity, and then hand the pad over, then OTP can be quite effective.  In times of war, where you can be physically provided your key material before you travel into the hostile area, this pattern can be very powerful.  In more symmetric situations, transferring the key material securely can be just as difficult as transmitting the material itself!  These symmetric situations are more common on the internet.


How to break an arbitrary XOR and Rotation based encryption? I heard encryption based purely on XOR and Rotation is inherently weak. The paper Rotational Cryptanalysis of ARX says:

  It is also easy to prove that omitting addition or rotation is devastating, and such systems (XR and AX) can always be broken.

But I am not able to find any information on how to actually do it. Can anyone give a hint?

(Update:)

@CodesInChaos pointed out: "You can describe each output bit as the XOR of a fixed set of input/key bits. This results in a few hundred linear equations modulo $2$, which can be solved efficiently." For simple XR cipher, I understand how it works. But there are issues for me for more complex ones. Illustrated as follows:

Suppose a toy XOR/Rotation based cipher (cipher 1) which encrypts a 4 bit plaintext $P$ to a 4 bit ciphertext $C$ with a 4 bit key $K$. The encryption process is as follows (with example $p = 1001$, $k= 1000$, and $c = 1110$, all additions are modulo $2$ additions):

$E_1$. Right rotate $P$ by 2 bits, producing $M$ ($1001 \rightarrow 0110$),
$E_2$. XOR $M$ with $K$, producing $C$ ($0110 + 1000 = 1110$)

The corresponding decryption process:

$D_1$. XOR $C$ with $K$, producing $M$ ($1110 + 1000 = 0110$)
$D_2$. Left rotate $M$ by 2 bits, producing $P$ ($0110 \rightarrow 1001$)

Following @CodesInChaos 's advice, I can convert the decryption to the following linear equation system :

c1 + k1 = p3       1 + k1 = 1       k3 = 1
c0 + k0 = p2  ==>  0 + k0 = 0  ==>  k2 = 0          (A)
c3 + k3 = p1       1 + k3 = 0       k1 = 0
c2 + k2 = p0       1 + k2 = 1       k0 = 0

So far so good. But what if the rotation bits in the above step $E_2$ is not a constant 2, but changes with the input plaintext? For example, let's modify the above cipher a little bit to this (cipher 2):

$E_1$. Right rotate $P$ by $n$ bits, producing $M$. In which $n$ = the upper 2 bits of $P$ ($1001 \rightarrow 0110$),
$E_2$. XOR $M$ with $K$, producing $C$ ($0110 + 1000 = 1110$)

I cannot convert this cipher to a simple linear equation system. Because there is no longer a fixed function for each output bit as of key & input bits.

So my questions is: Is cipher 2 still qualified as a "pure XR" system? Is there still a generic way to break it?

XOR operations, fixed bit movements (as in taking the 2 topmost bits or
concatenating bits etc.) and data dependent rotations form a
functional complete set of operations. This means that you can realize
any function between fixed length binary strings, including all possible
blockciphers, using them.

To show that these operations form a functional complete set one can show that
all operations of another functional complete set can be realized. For example
the set {NOT, AND}:

Realizing a NOT operation is easy, since this is only a XOR operation with
a 1 constant.
Realizing an AND operation requires the data dependent rotations. Given the
inputs $a$ and $b$ construct the value $v = RotLeft_{a}(0b)$. The leftmost
bit of $v$ is now the result of the AND operation of $a$ and $b$. This can
be verified by looking at the possible input values: If $a$ is zero the
rotation is does nothing and the leftmost bit stays zero. If $a$ is one the
rotation will move the value of $b$ to the leftmost bit and the result is
one exactly if $b$ is also one.

This would turn any algorithm that could break any cipher based on these
operations efficiently into an algorithm that breaks any arbitrary cipher
efficiently, unlikely to exist and certainly not known.

Nevertheless I would not assume that most or even many of the ciphers
constructed from these primitives are secure. For example: if there are only
few data dependent rotations and it is feasible to enumerate all possible
rotation count combinations, the system can be broken by just trying to solve
the resulting linear system for each combination.


SHA-512 faster than SHA-256? I'm getting this strange result that SHA-512 is around 50% faster than SHA-256. I'm using .net's SHA512Managed and SHA256Managed classes. The code is similar to the one posted here but I'm referring to tests taking caching into account (from the second time reading the file onwards it seems that it's cached completely). I've tested it several times with the same results.
My question is: is this logical or must there be something wrong with my test?

This isn't necessarily unexpected. 32-bit platforms vs 64-bit platforms can make a significant difference, as well as the amount of data you're hashing.

$ uname -m
x86_64

$ openssl speed sha256 sha512
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
sha256           29685.74k    79537.52k   148376.58k   186700.77k   196588.36k
sha512           23606.96k    96415.90k   173050.74k   253669.59k   291315.50

As you can see, on my 64-bit machine, SHA-512 beats SHA-256 for hashing anything more than 16 bytes of data at a time. And generally, the more data being hashed at once, the bigger the performance improvement.

Edit: As @MaartenBodewes points out in the comments, there's also SHA-512/256 which does the same computation as normal SHA-512 (with a different initial value) but truncates the output to 256 bits. This is a better option (due to the different IV) than simply truncating the output of SHA-512 to 256 bits by yourself in the case where you need the higher throughput but are limited to 256 bit outputs. Alternatively, if you really need higher throughput, BLAKE2b is an excellent cryptographic hash that is extremely fast and natively supports arbitrarily sized outputs (between 1 and 64 bytes).


Elliptic Curve Cryptography messages vs keys encryption I have read a few tutorials about ECC implementaiton in C. What I am confused is this: Can I encrypt messages with ECC and without the use of any other algorithm, like AES, RSA or should I use them also?

What I mean is this: Can ECC alone can be used for text message encryption, or is it only for key generation?

Hybrid cryptosystems, as @kelala has mentioned, are used in practice in favour of public-key encryption systems. It's not a particularity of Elliptic Curve vs Integer-Group based cryptosystems: it's rather that bit-twiddling (symmetric-key) cyphers are much faster than algebraic (public-key) ones.

So, what we do is to create a symmetric key and use a public-key scheme to encrypt it in the KEM/DEM paradigm (and also 2) and then use a symmetric scheme to actually encrypt.

Also, keep in mind that even if you do encryption wholly in an Elliptic Curve, you probably need a hash function at some point that maps the text message (a sequence of bytes) to a field element or a curve point itself.
You can look up the work of Icart, Fouque, Tibouchi, Coron, Maurer and others, for examples of how to do this (depending on the curve family you're targetting)


Basic CPA walkthrough My professor put this on the slides but gave us very little context. It is meant to be an overview of how it works at a high level.

I have a programming background and I get the general idea of attacks like Chosen Plaintext Attack. Be warned I am terrible at maths!

Request: I hope someone can walk through what this is doing step by step in English. Please refer to the lecture slide.

Other questions:

What does the '.' dot symbol mean in the ChosenPlaintext(.) part?
What is a and b storing?
If a=b goto ... is this checking length or if both are the same text?

What I think is happening:
It checks if chosen plaintext a is equal to b and if true then quit the program. Else it sets m to the chosen plaintext a. It uses ChosenPlaintext(m) to encrypt it and assign returned ciphertext to c. For some reason, it does XOR next but I am lost...

This slide came before, hopefully it provides better context:

What does the '.' dot symbol mean in the ChosenPlaintext($\cdot$) part?

It means that you, the adversary, may call this function with any value replaced for $\cdot$. This is useful if you want to give the adversary access to a partially applied function, e.g. $E(K,\cdot)$ the pre-keyed encryption function so that the adversary gets to see encrytions without learning the key.

  I hope someone can walk through what this is doing step by step in English.

You should really ask the person having presented / created this or their support staff for confirmation, but I think the idea of the slide is to give you some intution of common operations that an adversary might do and not lay out any specific concrete adversary.

If a=b goto ..., an adversary may commonly check / compare the content of two self-computed variables, e.g. when attacking a stream cipher which suffers from IV-reuse $a$ may be the keystream from one chosen plaintext-ciphertext pair and $b$ the keystream from the challenge ciphertext XORed with $m_0$. The goto is just there to show that adversaries can skip execution steps / break out of loops if some condition holds.
Else m=a, a default action to be taken when a previous if did not hold, e.g. to preserve loop-invariants.
c=ChosenPlaintext(m), the adversary may ask for encryptions of arbitrary data before and after submitting the challenge messages. This could e.g. be useful when the encryption function is stateful if you want to force a specific state for the challenge query.
d=c XOR b, the adversary may want to make computations on query results and / or other variables.
If 1=1 then m0=a, m1=b the adversary may select their challenge messages conditionally based on previous computations.
c=ChallengeCiphertext(m0,m1) the adversary can submit (once) a pair of messages to get the challenge ciphertext.
d=ChosenPlaintext(m0) submitting challenge messages to the encryption oracle is a totally fine thing for the adversary to do and may actually break deterministic schemes.
Return 1 and halt, the adversary can just return a fixed value, or some variable content or some expression and decide to stop execution.


Why does DES implement so much Cross Wiring? I've been going through DES, and I find that most of the blocks simply Reshuffle the input, which may be termed as "Cross Wiring". This include IP, IP-1, PC-1, PC-2 and even Expansion (although this seems to be more useful than the rest).

Why does DES do it? Is it for a reason, or just for fun maybe?

Inside each round, DES has a permutation that is used for diffusion and is crucial for security. However, you rightly point out that the initial and final permutations on the block of input/output and on the key have no effect whatsoever on security. Formally, it's not difficult to show that if you have an attack on DES without these initial and final permutations, then the attack also works when you do have.

So why does DES do this? Well, we can only guess. However, the assumption in the cryptographic community is that permutations are really really fast in hardware and really really slow in software. (In fact, a good percentage of the encryption time in software goes on these permutations. In hardware, it's just a matter of moving wires so it's almost zero cost.) This therefore slows down brute force search in software, relative to what can be done in hardware.

Why was this done? My guess is that this gives an advantage to certain very large organizations who have the resources to build special-purpose hardware. One such organization was instrumental in making DES secure (helping in the design of the S-boxes). However, they also pushed to make the key 56 bits long instead of 64 bits long. I guess that by making the software implementation slow, they felt that this could enough security (since most of the world would only have software) while enabling them to do brute force searches.

One could of course go for a less exciting theory which is that this was an additional level of security to slow down brute force searches in the future. But, I don't really buy it since if this was the concern at the time, then a bigger key would have been the right solution.


The number of cipher texts possible for each plaintext This is from Dan Boneh's book
Theorem 2.1. Let X = (E, D) be a Shannon cipher defined over (K, M, C). The following are
equivalent:
(i) X is perfectly secure.
(ii) For every $c \in C$, there exists $N_c$ (possibly depending on c) such that for all $m \in M$, we have
$|\{k \in K : E(k, m) = c\}| = N_c$
(iii) If the random variable k is uniformly distributed over K, then each of the random variables E(k, m), for $m \in M$, has the same distribution.
Proof:
For every $c \in C$, there exists a number $P_c$ (depending on c) such that for all $m \in M$, we have Pr[E(k, m) = c] = $P_c$. Here, k is a random variable uniformly distributed over K. Note that $P_c = N_c/|K|, where N_c$ is as in the original statement of (ii)
(Partially copied, not the full thing)

Point (ii) is not clear to me. What exactly is $N_c$? If is the number of ciphertexts possible for each plaintext, then it's always equal to 0 or 1 for perfect secrecy, right. Or can it be something else?

What exactly is $N_c$?

It is a number that may depend on a given ciphertext and states how many keys exist for every message that produce this ciphertext. The statement here is that every ciphertext can be produced from every message with an equal number of keys, i.e. if you draw keys uniformly at random all messages had the same probability of being the source.
For perfectly secret schemes with $|K|=|M|$ this will always be either 1 or 0. It could be 0 e.g. if the ciphertext is longer than anything in the message space for a OTP.


Advantages/Disadvantages of Bcrypt vs. hash/salt I have an application that I use sha3-512 to hash my password with a randomly generated 64 characters salt for each password. Is it bad to use this method to store passwords? I know many people reference using bcrypt for password storage. What are the advantages/disadvantages of using bcrypt vs. a hash/salt combo?

Is it bad to use this method to store passwords?

Yes. It is bad.
Why?

It's bad because you're rolling your own crypto, which is generally considered a bad choice.
It's bad because SHA-3 is slow in software (e.g. on servers and consumer PCs) and fast in hardware (e.g. FPGAs, ASICs) and hence attackers can relatively fast try out many passwords.

So the disadvantages:

SHA-3/2 is fast and therefore an attacker can try many passwords very fast even though you're using a salt.
SHA-3 isn't widely deployed yet and availability of bcrypt/scrypt may be better.
SHA-3 is designed to be a good hash-function, not a good password-hashing-scheme (PHS), whereas bcrypt is designed to be a PHS and was analyzed in this direction as well.
Bcrypt is slower and requires some memory (4 kiB IIRC), so one spends 100ms to check a valid password whereas an attacker needs days / years to crack it because he's slowed down and can't use GPUs efficiently.

So all in all, always prefer bcrypt over standard (iterated) hash-functions.

You may also want to take a look at scrypt and the password-hashing competition (PHC). PHC is in the final phase and until winners are selected and deployed scrypt may be a better option - if you don't want to authenticate users on your server.


Extracting $ x $ given $ g^x, g^{x + y}, y $ Given a cyclic group $ G $ of prime order $ q $ with generator $ g $ in which computing the discrete logarithm is hard.

Is it (still) hard to find the discrete logarithm $ dlog_g(g^x) = x $ if the
values $ g, g^x, g^{x + y} $, $ y $ are known?

Ok, I gave the answer in my comment; however so that you can accept an answer (and so close this question out), I'll repeat my answer here.

Yes, it is still hard to find the discrete log, given $g, g^x, g^{x+y}, y$.  The reasoning is simple; if that were an easy problem, that is, if we had an oracle that, given $g, g^x, g^{x+y}, y$, recover $x$, we could then solve the discrete log problem.  Here's how we would do that: given $g, g^x$, we would select a random $y$, and compute $g^y \cdot g^x = g^{x+y}$.  Then, as we had $g, g^x, g^{x+y}, y$, we could hand those values to the oracle, which would give us $x$, solving the original DLog problem.

You also have an obvious reduction in the other direction; hence your problem is precisely equivalent to the standard DLog problem.


Krack WPA2 decrypt only some small pieces of packets I have gone through the paper (PDF) available at krackattacks.com.

However, from what I understood you force a key reinstallation causing you a nonce reuse over 2 blob of data. As it is a keystream, you might be able to decrypt the data.

Limitations are:

You MUST know clear text of one of both data
It is one shot as the counter gets incremented, you need to perform another key reinstallation to be able to decrypt further data

This doesn't sound very practical in my point of view, am I missing something?

It's depressingly practical. And you can reset the key multiple times, getting the same key stream every time. So if the third or forth time you get guessable plain text content in different parts of the key stream you can combine this until you have everything.
Your computer does all kinds of communications, it polls stuff, it makes DNS lookups it uses standard headers and standard protocols all of this produce lots of guessable data. On a not busy network we can also use packet sizes to help us find our guessable data.
In reality finding known plain-text is not difficult.


Determine whether a given function is a pseudorandom generator/function I am trying to solve the following three tasks (for exam practice, not as a homework):

Define $ : \{0,1\}^* \rightarrow \{0,1\}^*$ by $G(x_1,...,x_n) = _1 \oplus _2,_1,⋅⋅⋅,x_n.$ Prove that this $G$ is not a pseudorandom generator.
Let $G$ be a pseudorandom generator, and define $G'(x_1, ..., x_n) = G(x_1, ..., x_n)|(x_1 \vee x_2)$. Is $G'$ a pseudorandom generator?
Define $ : \{0,1\}^* × \{0,1\}^* \rightarrow \{0,1\}^*$ as follows: $_{_1,...,_} (_1,..., _) = \bigoplus_i _ _$, where $_, _ \in \{0,1\}^*$ (Note that, different from the usual convention, $F$ takes an n-bit key and an n-bit input, but has only a single-bit output). Prove that this  is not a pseudorandom function.

My guesses are:

Not a pseudorandom generator since a distinguisher can always distinguish G(s) from a truly random string because the first bit of G(s) is always equal to the XOR of the second and third bit.
Not a pseudorandom generator because a distinguisher could simply check whether the last bit of the string equals $x_1 \vee x_2$ and could thus distinguish G(s) from a truly random string.
I cannot determine how to solve this.

Are my guesses correct? Can someone provide an idea for 3?

I have fully solved the questions now.

Not a pseudorandom generator since the first bit of $G(s)$ is always equal to the XOR of the second and third bit, i.e. a distinguisher can easily tell $G(s)$ apart from a truly random string $r$.
Not a pseudorandom generator. We can for example construct a distinguisher $D$ that, on input of a string $w$, outputs 1 if and only if the final bit is 0. If $w$ is uniformly distributed then the final bit is 0 with probability $\frac{1}{2}$ but if $w = G(s)$ for a uniformly distributed seed s  the final bit will be 0 with probability $\frac{1}{4}$.
Not a pseudorandom function. A distinguisher D could tell $F_k$ apart from a truly random function $f$ in the following way: Given access to an oracle $W$, D queries $W(0...0)$. If $W = F_k$ then the result will always be 0, but if $W$ is a random function then it should be 0 only with probability $\frac{1}{2}$.


Deniable Encryption from simple primitives Is there a deniable encryption scheme $M = E(p_1,k_1,p_2,k_2,...,p_n,k_n), p_j = D(M,k_j)$ of $n$ plaintexts $p_1,p_2,...,p_n$ and $n$ keys $k_1,k_2,...,k_n$, such that we can fix $D$ to be a known algorithm such as AES (without preprossessing $M$) and such that $|M| \ll \sum_{i=1}^n {|p_i|}$ (since this leaks information about how many false plaintexts there are to a party suspicious their adversary may be using deniable encryption)?

Let me expound a little bit on the motivation for these constraints. Let's say that a soldier of country A were captured and country B wanted said soldier to aid them in deciphering the data on his military issued laptop. Country B is not going to allow the soldier to operate the decryption himself. They are going to take an image of his hard drive and ask which algorithm and key he used. The soldier had better reply with a standard algorithm (not known to be deniable). In addition we would expect every bit of the ciphertext is required to decrypt the plaintext, or else country B may begin to suspect deniable encryption.

This last constraint (pertaining to the ciphertext size) seems information theoretically impossible. So let me ask my question in a less rigorous way:
Most deniable encryption systems seem to me to be heuristic engineering solutions. Out of purely academic interest: What scholarly work has been done on deniable encryption that meets the motivation for my formulation?

Deniable encryption is a topic that has been worked on for a while, but recently (in the last year or two), I have seen many more papers.

I haven't kept up with the area but can make a few comments:

The schemes are typically built with public key primitives instead of symmetric key ones (the distinguishing feature not being the symmetry of the keys, rather the use of a clean mathematical structure instead of non-linear block cipher design)
Most schemes encrypt the message bit-by-bit. This means you only have to embed two possible plaintexts (0 and 1) and it is easy to open a message to any possible message.

Scheme based on Elgamal

There is only one scheme that I know that comes close to fitting your scenario. It is from this paper (sorry, couldn't find a non-gated version) and is based on Elgamal.

Properties

The scheme only allows opening to two possible messages however this should be sufficient for your motivating example.
Instead of recovering the different messages using, simply, different keys, it uses two different decryption algorithms. Using the standard Elgamal decryption will give you one message (the fake one) and using a special decryption algorithm will give you the real message. Schemes like these are sometimes called multi-distributional instead of fully-deniable. (Aside: To me, this is reminiscent of steganography: hiding a secret message in innocuous looking data).
This is a plan ahead scheme meaning you have to know what fake message you want to open the ciphertext up to ahead of time
The scheme is receiver-deniable, meaning the receiver of the message (the person performing decrypt) can deny the true plaintext value. For reasons we will see, the sender cannot.
Despite being based on Elgamal, the scheme is actually symmetric key; the consequences we will see.

Construction

Recall normal Elgamal, where Alice sends a message to Bob. Bob has a secret key $x$ and a public key $y=g^x$ (for some generator $g$). To encrypt message $m$, Alice chooses a random value $r$ and computes $\langle c_1, c_2 \rangle = \langle g^r, my^r \rangle$. To decrypt, Bob uses secret key $x$ to compute $c_{1}^{-x}c_2$.

Let's generalize slightly: replace in the ciphertext $g^r$ with some arbitrary value $a$ and $y^r$ with some value b. Then the ciphertext is $\langle a, mb\rangle$. There are lots of a values of $a$ and $b$ that will decrypt to $m$, not just $g^r$ and $y^r$. In fact, any $a$ and $b$ such that $b=a^x$ will work. In this scheme, Bob gives Alice his secret key $x$ (see fine-print below).

Once Alice has $x$, it is simple. She can, for example (my example, not from the paper), set $a=\mathrm{AES}_k(m)$, using an additional shared secret key $k$ (only used for decrypting the true value), and then compute $b=a^x$. For fake message $\hat{m}$, Alice sends $\langle a, \hat{m}b\rangle$. If Bob wants the real message, he decrypts $c_1$ with AES. If he wants to deny, he claims it is an Elgamal ciphertext and decrypts as normal, with $x$, and gets $\hat{m}$.

In the paper, they set $a=g^km$ and $b=y^km^x$. Here, instead of $k$ being a shared secret, there is a shared secret $s$ and $k=\mathcal{H}(s||\hat{m})$. I don't fully appreciate why the construction needs to be this complicated (comments welcome). To decrypt, Bob, uses $x$ and standard Elgamal decryption to recover $\hat{m}$. With $\hat{m}$ and $s$, he computes $k$ and then computes $g^{-k}c_1$ to recover $m$.

Fine-print

Because Alice is given Bob's secret key, this means it is no longer a public key encryption scheme. This has consequences: If Charlie also wants to send messages (standard or deniable) to Bob, Bob either has to use a different key pair (which is odd for what is ostensibly a true public key) or Alice can read all the messages.
If Bob is coerced, he can deny that anything more than standard Elgamal is going on. However, if Alice is coerced, they will ask her what message $m$ and randomness $r$ she used to create the ciphertext. Because she didn't create a standard Elgamal ciphertext, she cannot answer for $r$ or compute a suitable one without solving a discrete log.
Finally, it may be odd for something like disk encryption or file encryption to use Elgamal on the data itself. Usually you'd use it to encrypt an AES key, and then use AES to encrypt the actual data.


How can I implement the "Multiplication Modulo" and "Addition Modulo" operations in IDEA? I am currently working on IDEA (International Data Encryption Algorithm), and I don't know how to perform Multiplication Modulo and Addition Modulo.
This is how IDEA operates:

IDEA operates on 64-bit blocks using a 128-bit key, and consists of
a series of eight identical transformations (a round, see the illustration)
and an output transformation (the half-round). The processes for encryption
and decryption are similar. IDEA derives much of its security by interleaving
operations from different groups — modular addition and multiplication, and
bitwise eXclusive OR (XOR) — which are algebraically "incompatible" in
some sense.

Bitwise eXclusive OR (denoted with a circled plus ⊕).

Addition modulo $2^{16}$ (denoted with a boxed plus ⊞).

Multiplication modulo $2^{16}+1$, where the all-zero word (0x0000) is
interpreted as $2^{16}$ (denoted by a circled dot ⊙).

Addition modulo $2^{16}$ just means, add the two numbers as you normally would, and subtract $2^{16}$ from the result until the sum is less than $2^{16}$. So suppose you wanted to add, say, 51995 and 29291 modulo $2^{16}$:

51995 + 29291 = 81286

Subtract 2^16 = 65536, you get 81286 - 65536 = 15750

This is less than 65536, so 51995 + 29291 = 15750 modulo 2^16.

Multiplication modulo $2^{16} + 1$ is exactly the same, except you multiply the two numbers instead of adding and you subtract $2^{16} + 1 = 65537$ repeatedly instead of $2^{16}$. And note the extra condition required by IDEA to prevent entropy destruction, that if one of the operands is zero, it is replaced by $2^{16}$ (this is not part of the definition of modular multiplication, but it is required to ensure reversibility - can you see why?).

This is a bit long-winded, fortunately there is a modulo operation available in most programming languages, usually called "mod" or "%", which you can use. Finite data types also have an implicit $2^n$ modulo operation where $n$ is the data type's bit width, through overflow (for instance, if you have a 1-byte variable set to 255, and increment it by one, it'll become zero), unless they are explicitly designed to saturate. There are also bitwise shortcuts you can use for IDEA to make it much faster since multiplication is slow, but I guess you don't really need those.

For a more detailed explanation, please see this link.


pwd-hash like algorithm which can be computed on paper "Common password problem" is well known problem, when user uses one password for many resources (web sites, logins to computers, etc...) For example, if one web site loses it' database, which contains user passwords and emails, somebody when might try to use this password on other sites and come to success...
To solve this issue pwdhash exists. This is good solution, only problem is, that user needs special software to compute the password for each web site, for example. So user needs some reliable software for this. User should be sure, that this software doesn't remembers and transfers to somewhere in network entered main password. User should be sure, that this software can't be imperceptibly replaced with malicious version of program that is indistinguishable from the original. For example, it's hard to trust to "pwdhash" application from Google Play market (because it is issued by unknown person and might be silently updated in future). Also it's hard to trust to original "pwdhash" web site, because it might be replaced in some moment of time. Moreover, web site might be just inaccessible.
To solve "common password problem" I want to use some sort of one way hash, which can be computed by hands, on sheet of paper, or even can be counted in mind. I understood, that this might be not strong cryptographic hash, but from other side, I can completely trust this method.
Suppose I have service name, for example "booking" (.com). I want mix it with some permanent password, lets suppose this will by my name "kirill", and I will get password which I can use for login to "booking.com" website.
At first, I will translate name of service and permanent password to numeric form. To do this, I will use telephone keypad layout. So translation will be following:

"booking" = 2665464
"kirill" = 547455

Then I compute: $R = N * 1000000 \bmod S$, where $N$ is name of service encoded in numberic form, $S$ is my permanent password in numeric form. And $R$ is resulting password, which is valid only for some particular service.
I will get:

R = N % P * S = 2665464 * 1000000 % 547455 = 64052235

Now I translate $R$ back to alphanumeric form, again by using telephone keypad. First time i selecting first letter for each corresponding digit (zeros and ones i can't tranlate, so i leave it as is). So I will get:

314715 = "M1gp1j"

Also I will make the first letter capital (many services require to mix capital and lowecase letters). And in case, if resulting string doesn't contains any digits, I will leave last digit as is (again, some services require to include digits in passwords).
So, I get password, which is unique for each service and looks like randomly selected characters. And it's hard to reverse it, to get my permanent password (547455 or "kirill"). Of course, for practical purposes length of my permanent password should be longer, more than 8-10 characters.
This is good or bad method?  And why?  And how this method can be improved?
Links:

What you're after is fundamentally impossible. Password hashing algorithms are inherently slow. They're designed to be slow even on a computer. Otherwise they would not serve their purpose, which is to make brute force search infeasible. A fast password hash is a broken password hash. You cannot possibly get anywhere near the requisite level of slowness with manual calculation.

For anyone with a computer, given a site-specific password that is calculated from a master password by hand, it will be trivial to go try billions of potential master passwords until they find a matching one.

And having potential multiple matches won't save you, because there can't be many of them, otherwise the number of possible site-specific passwords would be ridiculously low.


An example of CCM - AES Mode I need to test if my AES-CCM implementation works correctly, but I don't find any example to test that.

Could you please help me and provide test vectors / other value-inserted examples?

In case there are none, I'd like to ask for the ciphertext of the following test vector for verification purposes:

AES-128
Plaintext = 00112233445566778899AABBCCDDEEFF
Key = 000102030405060708090A0B0C0D0E0F


Lightweight block ciphers that support decryption with minimal overhead? Lightweight block ciphers are mostly expressed for encryption routine and efforts are made to keep it as light as possible mostly in terms of gates count and power usage although some try to keep latency and critical path in consideration. The designers assume that such lightweight block ciphers will be used in a mode of operation which does not need the decryption routine like Counter mode. However, a few innovative designs also support the decryption routine with minimal overhead in terms of gate count like PRINCE and Piccolo block cipher.

Piccolo needs just 60 extra gates to support decryption on top of encryption circuitry.

Why is there a need for a lightweight block cipher to support decryption routine?
What all other lightweight block ciphers support decryption with minimal overhead in terms of gate count?

I know feistel structures do support decryption by using round keys in reverse order, but we are talking here about lightweight block ciphers. These are implemented in resource constrained devices and really small implementations of these lightweight block ciphers often cant afford to store expanded keys so even feistel structures do need extra gates to manage these issues for supporting decyption.

I do know modes other than Counter like CBC needs implementation of decryption methods, but what practical scenarios force this to happen. Cant the implementers just use counter mode.

Why is there a need for lightweight block cipher to support decryption routine?

You might want to use a mode that is not based on CTR mode, which will require the availability of the decryption procedure.

  What all other lightweight block ciphers support decryption with minimal overhead?

Any designs that are Feistel networks and/or use components that are involutions will offer minimal overhead for the decryption procedure.

The following designs mention using components that are involutions, according to wikipedia:

Anubis
KHAZAD
Cellular Message Encryption Algorithm
MULTI2
NOEKEON

This list is probably not exhaustive.


FHE over the integers - Is that paper's scheme known to be insecure against quantum adversaries? I was reading the paper Fully Homomorphic Encryption over the Integers, and started

wondering if there is a known quantum attack on their main scheme, because

There is an efficient quantum attack on their "even slightly simpler scheme", as follows:
completely factor $x_{\hspace{.025 in}0}$,

for each [product of a very small number of $\hspace{.03 in}x_{\hspace{.025 in}0}\hspace{-0.04 in}$'s prime factors] with the right number of bits,

see if using that as a private key correctly decrypts a moderate

number of "test ciphertexts" generated for that purpose

if one does, then use it to decrypt the challenge ciphertext and output that decryption result

otherwise output failure

That attack works because $p$, as a random odd integer of a given bit length, has a noticeable

probability of being prime, so in particular of having a very small number of prime factors.

and

The section that describes their "even slightly simpler scheme" also says they

"do not know of ant attack that works for this 'easier case' but not for the general case.".

(The "ant" typo is in the paper that I linked to.)

On the other hand, the version on Springer does not include that section.

  Is there a known efficient quantum attack on the main scheme of those two papers?

(I say "those two papers" because I'm not aware of any difference between their schemes,

and if there is one then I don't know which of them I mean.)

According to the answer by Hilder Vitor Lima Pereira in the this question, the main scheme is believed to be quantum secure.


Attacks of the MAC construction $\mathcal{H}(m\mathbin\|k)$ for common hashes $\mathcal{H}$? Consider a common practically-collision-resistant hash function $\mathcal{H}$ (e.g. SHA-1, SHA-256, SHA-512, RIPEMD-160), perhaps based on the Merkle–Damgård construction as are the first three. We define a Message Authentication Code $\mathcal{C}$
$$(k,m) \mapsto \mathcal{C}(k,m)=\mathcal{H}(m\mathbin\|k)$$
where $\mathbin\|$ denotes concatenation, $k$ is a secret key (constant, or at least of fixed size), and $m$ is a message (possibly of variable length). Assume that an adversary can (iteratively) submit queries with $m_j$ and obtain $C(k,m_j)$, and wants to obtain $k$ or otherwise compute $C(k,m)$ for some $m\ne m_j$.

That MAC $\mathcal{C}$ is not trivially bad. In particular, if $\mathcal{H}$ was indistinguishable from a random function in the Random Oracle Model, $\mathcal{C}$ would be secure. And even though $\mathcal{H}$ may have the length-extension property, it does not turn into a devastating attack on $\mathcal{C}$.

The less impractical generic attack that I see is that if a collision was known for $\mathcal{H}$ with the colliding messages of moderate identical length, it could be deduced countless collisions for $\mathcal{C}$. Hence security is demonstrably not better than collision-resistance of $\mathcal{H}$ (for identical-length messages). We could assume that $k$ is half the size of the result of $\mathcal{H}$, and hope that the security is about 269 or is it 257 or even 252, 280, 2128, 2256 hash rounds for SHA-1, RIPEMD-160, SHA-256, SHA-512.

What are the known attacks against $\mathcal{C}$ (better than the above), and their cost, for each of these common hashes?

Is there hope for an argument that an attack against $\mathcal{C}$ would turn into an attack of similar cost against $\mathcal{H}$, or hint of the contrary?

Update: this answer to a similar question is of interest, but I fail to find that it really answers the present question.

Update 2: I am aware that the construction considered is weaker than HMAC, and in particular is vulnerable to collision on $\mathcal H$; I stated that, and that it is thus pointless to have the key wider hopeless to target security against some attacks better than half the hash's size. I'm asking exactly what cryptanalytic attack better than finding a collision on $\mathcal H$ there are. There is room for such an attack only by exploiting a weakness in the structure or/and the round function of a concrete $\mathcal H$.

Using $H(m\mathbin\Vert k)$ with hash function $H$, message $m$ and key $k$, is one possible way to build a MAC algorithm. It is not necessarily a good one; it depends on the used hash function. Even when it is a good one, that does not preclude the possibility of other, "better" algorithms (e.g. for performance).

As an illustration of potential security issues, let's define hash function $H$ as being SHA-256 applied on the bit-reversed input; that is, we take the input to the hash function as a sequence of bits, reverse the order of bits (first bit becomes last, second bit becomes next-to-last, and so on). It's a bit of a contrived example, but it should show my point. That function $H$ is (obviously) as resistant to collisions, preimages and second-preimages as SHA-256, so, from that point of view, it is a secure cryptographic hash function. However, using $H(m\mathbin\|k)$ with that hash function would be weak, because $H(m\mathbin\|k) = \textrm{SHA-256}(\textrm{rev}(k)\mathbin\|\textrm{rev}(m))$, for which so-called length extension attacks apply.

So whether $H(m\mathbin\|k)$ is a secure MAC depends on subtle properties of the hash function $H$ which are not covered by the classic assertions of resistance to collisions and preimages. HMAC was defined with two nested function hash function calls precisely so that its security could be proven in the case of hash functions of the Merkle-Damgård type (like SHA-256); a simpler construction like $H(m\mathbin\|k)$ was not amenable to such proofs. So this is the reason why HMAC exists: because we can convince ourselves that it is secure, more readily than with your proposal.

As for performance, you have to consider that hash functions are not necessarily the best in town for processing bulk data. On a modern PC, dedicated MAC algorithms like Poly1305 or GHASH (the MAC part of GCM) are easily 5 times faster (or more) than SHA-256 or SHA-512.


Excluding specific factors for Pohlig-Hellman I want to use Pohlig-Hellman and BSGS to solve the discrete log of an Elliptic Curve which has a composite order generator.

The tricky part is, one of the composite factor groups is large (99bits), so I want to exclude it from the Pohlig-Hellman/BSGS.

Is it possible in SageMath to apply the discrete_log() function to an elliptic curve, and exclude one of the generators factors?

Is there a trick with Chinese remainder theorem?

Suppose we have a point $P$ of order $q$ on an elliptic curve where the prime decomposition of $q$ is $q =  p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$. We also have a point $Q=kP$ and we want to find $k$.

Pohlig-Hellman algorithm

The idea of Pohlig-Hellman's algorithm is to to compute a discrete logarithm in the subgroups of prime order.

Easy case

We suppose $\alpha_i=1$ for $1\leq i \leq n$, so $q=p_1\cdots p_n$ and all primes are distinct.

Let
\begin{align}
q_i & = \frac{q}{\displaystyle\prod_{1 \leq j \leq n, j\neq i} p_j} \\
P_i & =  q_i P, \\
Q_i & =  q_i Q.
\end{align}

The point $P_i$ has order $p_i$ and we have $Q_i = k_i P_i$ where $k_i = k \bmod p_i$. The discrete logarithm can be computed with discrete_log on Sage or another software, and the value $k_i$ is recovered.

Do this only for primes that are in your interest, such as those that are small enough. If the value $k$ is inferior to the product of those primes, it will be found using the Chinese Remainder Theorem (with CRT([list of k_i], [list of p_i]).

Hard case

Now we suppose $\alpha_i$ is larger than $1$ for some of them. Again, we compute
$$
\begin{align}
q_i & = \frac{q}{\displaystyle\prod_{1 \leq j \leq n, j\neq i} p_j^{\alpha_j}} \\
P_i & =  q_i P, \\
Q_i & =  q_i Q.
\end{align}
$$
The point $P_i$ has order $p_i^{\alpha_i}$ and we have $Q_i = k_i P_i$ where $k_i = k \bmod p_i^{\alpha_i}$. Then, we write the decomposition of $k_i$ in base $p_i$:
$$
k_i = k_{i,0} + k_{i,1}p_i + k_{i,2}p_i^2 + \cdots + k_{i,\alpha_i-1}p_i^{\alpha_i-1},
$$
where $0 \leq k_{i,j} < p_i$ for $0 \leq j < \alpha_i$. To obtain $k_i$, we will get all $k_{i,j}$ one by one. First, for $k_{i,0}$, we construct the two following points:
\begin{align}
P_{i,0} & = p_i^{\alpha_i-1} P_i, \\
Q_{i,0} & = p_i^{\alpha_i-1} P_i.
\end{align}
The point $P_{i,0}$ is a point of order $p_i$ and we have the relation $Q_{i,0} = k_{i,0} P_{i,0}$. The discrete logarithm can be computed with discrete_log.

The next value $k_{i,1}$ can be found in a similar way. We compute
$$
Q_{i,1} = p_i^{\alpha_i-2} (Q_i-k_{i,0}P_i)
$$
and we have $Q_{i,1} = k_{i,1}P_{i,0}$, and discrete_log gives the value $k_{i,1}$. Then
$$
Q_{i,2} = p_i^{\alpha_i-3} (Q_i-(k_{i,0}+k_{i,1}p_i)P_i)),
$$
and we have $Q_{i,2} = k_{i,2}P_{i,0}$, and we get $k_{i,2}$, and so on, until $k_i$ is complete.

Again, do this only for primes $p_i$ that are in your interest.


Use a SHA256 as a key for AES256 Is it safe to use the SHA256 of a hard-to-bruteforce string as the key to encrypt data with AES256?

Yes, it is safe. The answer of @kelalaka (the first part, before update) it not correct.

The OP is saying that the password is a strong string which is hard to bruteforce. That's why the answer of @kelalaka the attacker, firstly, will try to brute-force is not relevant to the question. Everything @kelalaka is saying about password stretching is correct, but it is not relevant to this particular question.

I am curious why would you want to use SHA256 instead of password, if your password is complex and is hard to bruteforce. But this is another story.

I would suppose that some readers who didn't read the question attentively will vote  my answer down. Some people don't think much and just apply patterns that they have in their minds, like Password? --> hashing is bad --> use stretching instead But guys, read the question once again.


How can PUF hardware be proportional to the number of challenge/response bits? Wikipedia article claims that physical unclonable functions are superior to ROM because they require less hardware:

  Unlike a ROM containing a table of responses to all possible challenges, which would require hardware exponential in the number of challenge bits, a PUF can be constructed in hardware proportional to the number of challenge and response bits.

Then, examples of PUFs are given, such as reading a device-specific signature present in DRAM upon startup, which indeed requires exponential hardware. Other kinds of PUFs are based on different physical principles (optical, mechanical, magnetic) which encode the device-specific differences, but I fail to see how using a different physical principle could lead to linear (rather than exponential) hardware requirements.

Could someone provide an example of such hardware or explain how such low hardware requirements are possible in PUFs?

To implement challenge-response in ROM only (no computations), you basically need a lookup table, a mapping from challenges to responses. So for a $k$ bit challenge, you would need $2^k$ entries in your lookup table.

How would this work on a PUF?

Consider the following PUF example (taken from Improved Ring Oscillator PUF: An FPGA-friendly Secure
Primitive, Journal of Cryptology, 2011):

The portion on the right shows the ring oscillator (RO), whose value is going to be entirely dependent on the fabrication process and therefore is "unclonable". You put a bunch of these ROs together, feeding into two MUXs, with the challenge determining which RO value to select. Finally, the outputs of the two MUXs are used to increment two counters, which are (after some short period of time) used to determine a single bit by doing a comparison. Your $k$ bit challenge may be divided up into smaller challenges to get a larger response from the PUF than a single bit. This would be a deterministic process so that given the same $k$ bit challenge, you would get the same response (in practice there is some probability of bits being flipped in the response, so typically some error correcting is done).

To get a secure $k$ bit response, you will need some number of ROs, but you won't need an exponential number of ROs. If you have $N$ ROs, there are $N(N-1)/2$ distinct pairs of ROs. Each pairing can be used to generate a single bit using the setup shown above. However, as noted in Physical Unclonable Functions for Device Authentication
and Secret Key Generation, the entropy of the circuit will not be as high as that. In that paper, the authors derive the maximum entropy of the circuit as $\log_2(N!)$. So for a desired $k$, you could compute $N$. As an alternative method, the authors note that for simplicity, you could design the system such that each oscillator is used only once for any challenge value. If you did this, you would need $2k$ oscillators to generate a $k$ bit response. I would note that due to error correcting, you may need additional bits, but this should only increase the number of oscillators by a constant factor.

Now, how would this be used in a challenge/response protocol. Well, first there must be a trusted setup. The challenger, in a clean environment, sends a bunch of challenges to the PUF and records the responses. So, the challenger may have to store a lot of challenge/response pairs depending on the application. The point is, the hardware does not have to store all that information.

Then, when the system is fielded, the challenger sends a challenge to the device. The device runs it through the PUF and returns the response. Someone without access to the PUF could not compute the correct response. Further, someone trying to clone the PUF would not succeed because of the manufacturing variations in the ROs. Those manufacturing variations, even when very subtle, would be enough that the responses would not be the same.


Need for 3 rounds in Luby Rackoff theorem I get that using Feistel network we can create a secure PRP from a secure PRF (in 3 rounds according to theorem).

My question is why not just 2 rounds of Feistel network  is sufficient. Is it that the output is random enough compared to a truly random string before 3 rounds?

The simple answer is that fewer than 3 rounds can be easily distinguished from a random permutation. The 2-round Luby-Rackoff cipher on $2n$ bits, using random functions $f_i$ mapping $n$ bits to $n$ bits, consists of
$$
F(L, R) = (A, B),
$$
where $A = L \oplus f_1(R)$ and $B = R \oplus f_2(L \oplus f_1(R))$.

Now consider an attacker that wants to distinguish $F$ from a random permutation. First they send some arbitrary $(L_1, R_1)$ to the oracle, and get back $(A_1, B_1)$.

Next they send $(L_2, R_1)$, which results in $(A_2, B_2)$. Verifying that $A_1 \oplus A_2$ = $L_1 \oplus f_1(R_1) \oplus L_2 \oplus f_1(R_1)$ = $L_1 \oplus L_2$, the attacker is now pretty sure this is the Luby-Rackoff cipher.

What happens at 3 rounds is that no such distinguisher (querying only in the forward direction, of course!) is now possible. The proof relies on showing that collisions on the internal variables $A_i, B_i$ are necessary to mount any distinguisher, and then shows that those collisions are rare, in that you need approximately $2^{n/2}$ oracle queries to obtain one.


Is using derived keys for HKDF + AES-GCM safe I have an existing system which takes a cryptographically secure BLOB from user and pass it to lower API which calls HKDF-Expand to get 2 keys: one is effectively discarded in this scenario and second is actually used.

Previously this second key was used to authenticate-encrypt using AES256-GCM data from user (again get from user and passed to lower API). However this turned out to be problematic and some metadata needs to be added to the format in some cases. However it is hard to do while maintaining backward compatibility.

I'm consider 'versioning' the API by generating the key twice - once with key from user and once with key from user XORed with 1 - as it will allow to avoiding changing of API or similar tricks. My intuition is that I should get a two unrelated keys due to avalanche properties.

However I'm not a cryptographer so I'm not sure if there isn't something fishy about such schemes.

// info is publicly known; operation discards first 256-bits for key that
// is not used
(_, key1) <- HKDF-Expand(key, info)
(_, key2) <- HKDF-Expand(key ⊕ 1, info)

def decrypt(data) {
    decryptedData <- AES256-GCM-Decrypt(key2, data)
    if decryptedData is not null {
        return parseFormatWithMetadata(decryptedData)
    }
    # Try to use old format
    decryptedData <- AES256-GCM-Decrypt(key1, data)
    if decryptedData is not null {
        return (decryptedData, default metadata for v1)
    }
    return null;
}

def encrypt(data, metadata) {
    if metadata != default metadata for v1 {
        return AES256-GCM-Encrypt(key2, metadata || data)
    } else {
        return AES256-GCM-Encrypt(key1, data)
    }
}

By itself, this is fine. Running a KDF with two different inputs generates uncorrelated sequences: knowing the output of HKDF(K1, L) doesn't give any information about the output of HKDF(K2, L) unless K1 = K2.

However, as a system design, this is fragile. What if one day someone decides that they need a new version of this format, and they decide to flip the last bit of key?

Given the constraint that you can only change the key input to HKDF, if key has a fixed size, I would append a suffix to key to indicate the format version. Version 0 uses an empty suffix, version 1 will use the 4-byte suffix {0x00, 0x00, 0x00, 0x01}, etc.

If there is an additional constraint that key has to remain the same size, I would run it through a KDF first. To avoid running into potential trouble with related keys, key should still only be used for a single purpose, which is as the key input to HKDF. Use a label that cannot possibly be equal to any valid value for info.

key' <- HKDF-Expand(key, "not a possible prefix of info; version 1")
(_, key1) <- HKDF-Expand(key, info)
(_, key2) <- HKDF-Expand(key', info)


Can you help me understand pairing $e:G \times G \to G_T$ and ( Decision) BDH assumption? From DrLecter's comment, I know that DDH problem can be efficiently solved with this $$e(g^a,g^b)\stackrel{?}{=} e(g,g^z).$$

I have some trouble to understand this map $e:G \times G \to G_T$. Am I right to understand this to be the "multiplication" of two elements in $Z_p^*$ where $p$  is prime. For example, can  $e(U=g^u,V=g^v)$ be "seen" as the form $UV$ in $Z_p^*$ ?

Another problem is about the BDH assumption, which says that given $g^a,g^b,g^c$ compute $e(g,g)^{abc}$. There are also the Decision-BDH which says that given $g^a,g^b,g^c$ and $e(g,g)^z$, determine whether $$e(g,g)^z \stackrel{?}{=} e(g,g)^{abc}.$$

As to this two assumptions, where the obstacle lies?

At last, as  $e(g^a,g^b)$ can be efficiently solved, what's the algorithm it involved? And could someone do me a favor to give me the source code of the algorithm? If that I will deeply appreciate it.

An attack against the signature scheme over some group where DDH is easy, can be turned into a solver for the CDH problem over the same group, as is shown in Section 2.3 in the Asiacrypt paper you refer to.

So what you are really asking is: In what groups where DDH is easy is CDH still hard?

I would not use elliptic curves over extension fields of low characteristic. Using ordinary elliptic curves over prime fields with a relatively small embedding degree seems ok.


How to securely compute AES where the key is splitted across different servers? How can we use secure multiparty computation in evaluating one AES circuit, where the key would not be stored at one computer instead it would be divided into pieces and given to multiple servers. Is there any good reference to follow ?

If you only use secret sharing, then upon reconstruction the key could be stolen. Therefore, secure multiparty computation can be used. There are many different methods, depending on your setting. If you are interested in two-party computation with semi-honest adversaries then simple Yao works (e.g., http://eprint.iacr.org/2015/751.pdf); if you are interested in two-party computation with malicious adversaries and a single execution then http://eprint.iacr.org/2016/762.pdf is a good option; if you are interested in two-party computation with malicious adversaries and many executions then http://eprint.iacr.org/2015/987.pdf or http://eprint.iacr.org/2016/632.pdf; if you are interested in 3 party secure computation for malicious adversaries and with at most one party corrupted then http://eprint.iacr.org/2015/931.pdf is easy to implement but you can get much faster with http://eprint.iacr.org/2016/944.pdf; if you are interested in 3 party secure computation for semi-honest adversaries and with at most one corrupted then http://eprint.iacr.org/2016/768.pdf is by far the fastest; if you are interested in multiparty (more than 3 parties) and semi-honest then http://eprint.iacr.org/2011/257.pdf or http://eprint.iacr.org/2016/1066.pdf; if you are interested in multiparty (more than 3 parties) and malicious then http://eprint.iacr.org/2016/505.pdf. All of these are the state-of-the-art for their settings (but there are many other options) and the state-of-the-art is likely to change very quickly.


TLS: How is the shared secret (via Diffie-Hellman) used in the symmetric crypto function? So let's say we use a cipher suite with DH key exchange and AES symmetric encryption. Alice and Bob both end up with the same shared secret key $k$.

How is this value k used in e.g. AES? Will it be hashed before use, or is there a PBKDF involved? And what do we do about small $k$ (e.g. $10, …$)

The shared secret that Diffie-Hellman produces is known as the premaster secret. This is then passed through the cipher suite's PRF to get the master secret, which is then passed through the PRF again to get the various keys and IVs. The master secret is always exactly 48 bytes long; the keys can be as long as needed.

Now, the PRF. TLS tends to use a PRF based on HMAC, using a hash specified by the cipher suite. The PRF takes three inputs: a secret, a label (which is generally "the thing this is calculating", and a seed (which, for key derivation, is derived from random values in client and server handshake messages). It outputs as much data as is needed. While this is a key derivation function, it is not a password-based key derivation; it is a key-based key derivation function. A PBKDF must be slow, as that's the only hope to stop someone from brute-forcing a password. But TLS's cipher suites produce high-quality premaster secrets: it is infeasible to guess them. So, all you need to do is to make it infeasible to figure out one key given a different key, and a PRF is sufficient for this.

For small values of $k$: First, keep in mind that these are constant-width data types. The output of 1024-bit Diffie-Hellman is always 1024 bits, regardless of the numeric value. If you mean "what about brute-forcing," this is what "high-quality premaster secrets" is about. While it's possible DH might result in an output of 10, it's monumentally unlikely. Any attacker who's starting his brute-forcing at zero and going up is an idiot, who will almost certainly never break any connection. If the attacker guesses what your key is, he can break the connection, but the point is that he can't feasibly guess it.


Is using EAX mode with a 64-bit block cipher a bad idea? EAX mode produces an authentication tag no longer than the length of the underlying cipher's blocksize.  So in the case of using Blowfish (a 64-bit block cipher) in EAX mode, the resulting tag would be 8 bytes.

Is an 8-byte tag sufficiently long (I doubt it)?  Could such a short tag subject the ciphertext to any sort of cryptanalysis to which a longer tag could resist?

I understand, of course, that there are plenty of reasons to prefer a 128-bit block cipher...  I'm merely curious.

Using EAX with a 64-bit block cipher is problematic, because the short block size causes some weaknesses due to internal collisions.  I do not recommend it.  Use a 128-bit block cipher.
Indeed, the world has moved away from 3DES and towards AES exactly because of these fundamental problems with a 64-bit block size: the internal collision effect means that, with a 64-bit block cipher, once you encrypt more than about $2^{32}$ blocks of data, it is very likely that there will be at least partial leakage of secret information.  This problem is not specific to EAX: it is endemic to essentially every block-cipher-based mode of operation around.
We can be more precise and quantify the nature of the problem by looking at the security theorem for EAX.

Confidentiality. The security theorem (Corollary 6 in the EAX paper) says that, assuming our block cipher is perfect, an adversary who wants to violate confidentiality can do so with advantage at most $9.5 \sigma^2/2^n$.  Here $\sigma$ counts the number of $n$-bit blocks that are encrypted, and $n$ is the block size.  If you want to use EAX with a 64-bit block cipher, then  you have $n=64$, so this expression for the adversary's advantage evaluates to $9.5 \sigma^2/2^{64}$.  For good security, you want to keep this number significantly lower than 1.  Unfortunately, if you encrypt one billion blocks (8 GB of data, i.e., $\sigma = 2^{30}$), then this expression evaluates to $0.59$, so the adversary's advantage might be that big.
In rough intuitive terms, if you encrypt 8GB of data under a single key using EAX with a 64-bit block cipher, there's at least a 50% chance that the attacker learns some partial information about the secret messages.  That's not good.  Instead of 50%, we would much prefer this number to be much smaller: like one in a million or something.  So,  the security level obtained is not really acceptable.

Integrity. The same security theorem also gives us a bound on the chances that the attacker is able to create a forged packet, assuming the attacker gets a single attempt.  This probability is at most $11 \sigma^2/2^n + 1/2^\tau$, where $\sigma,n$ are as before and where $\tau$ is the length of the authentication tag.  Assuming you use a 64-bit authentication tag (which I recommend), the security level is $(11 \sigma^2 + 1)/2^{64}$.  For $\sigma=2^{30}$ (8GB of data), this probability is about $0.69$.
In other words, if you encrypt up to 8GB of data using EAX with 64-bit block cipher (using the same key for all data), then an attacker who makes a single attempt at forgery might have as large as a $0.69$ chance of success, with just a single attempt.  If the attacker makes multiple attempts (which of course the attacker can do), then the attacker's success probability might increase even more.  This is totally unacceptable.  We probably want the attacker's success probability, after making (say) a billion attempts, to be small (say, one in a million or something).  A 64-bit block cipher falls far short.

TL;DR: Use a 128-bit block cipher.  A 64-bit block cipher is cutting things too fine.


What does non-collusion assumption mean in server-aided protocol based on secret sharing? Suppose $m$ clients split their own input into $n$ shares using additive secret sharing scheme (mod something).
Then, each of the clients sends each share to each of $n$ external servers.
After receiving the shares from the clients, the servers run MPC protocols where no client will be involved in the protocol.
(Later, some or all clients receive the output share from the servers and reconstruct the result.)

General assumption is on non-collusion assumption, meaning that the protocol is safe (at least no client input is leaked) as long as $t (\leq m)$ servers do not collude.

I have a question regarding the assumption.

Does the "collusion" mean any possibility that $t$ shares in the servers are somehow assembled?

If so, do the followings have all the same meaning in the assumption?

server operators are all malicious and share their information about clients' shares (and assemble them)
some clients are malicious and get access to more than $t$ servers to see clients shares (and assemble them)
some malicious guys (who are neither any of the clients nor any of the server operators) hack the servers and assemble the shares on them.

Does the "collusion" mean any possibility that t shares in the servers are somehow assembled?

It refers to the possibility that t or more server admins/owners collude to pool their shares to break protocol.

Regarding the follow-up questions: non-collusion is in this context in regards to server operators being malicious. Malicious clients are considered a non issue in the context since clients should not have access to each others shares. Hacking of servers or data leaks is considered out-of-scope since it has nothing to do with the scheme in question.


How do I validate the AES cipher? I have used AES CTR mode of operation. Each time a file is uploaded an encrypted file is obtained and the corresponding cipher is got – this is a mini project I have done.

I wanted to know so as to what methods I could use to

validate the cipher to just prove that it is a valid cipher got by the actual encryption technique and not just the one generated by some random number generation method
it would be better if I can get a tool that subjects cipher to attacks (brute force, letter frequency analysis) to just prove that the cipher is secure (for validation purpose).

I am aware of the NIST validation, but since this is a mini project, I wanted some simpler solution. Does anyone please have suggestions?

The entire premise of modern ciphers is that they're indistinguishable from random by a computationally-bound adversary. If you believe the assertion that a modern cipher is secure, then it follows that you believe you cannot reliably distinguish it from randomness.

If you share a secret key with your clients, what you can do is verify a MAC over the ciphertext to ensure that it was generated by a client who has the same secret key as you (which is a good idea regardless, and the basis behind AEAD modes like GCM).

Your second point doesn't make much sense in the context of modern ciphers. About the only thing you can do is subject ciphertexts to randomness tests, but those results aren't of much use without extremely large amounts of input (on the order of gigabytes).

It's unclear though what exactly you're hoping to gain with such tools.


How hard is it to recover $p$ if I can get $h(p) \oplus h(p^*) \oplus r$ and $h(r)$? Assume that $h:\{0,1\}^* \rightarrow \{0,1\}^\lambda$ is a cryptologic hash function, $r$ is taken randomly from $\{0,1\}^\lambda$, $p$ is a low-entropy password and $p^*$ is a guess. Now we get $h(p) \oplus h(p^*) \oplus r$ and $h(r)$ but don't know $h(p)$ or $h(p^*)$.

Then there are two problems is a problem:

Can we get $\Delta{}h = h(p) \oplus h(p^*)$ by a brute-force cracking? (Yes.)
Can we get $h(p)$ (and $p$, due to the low-entropy property)?

There may be a slight different problem to consider easily, what if we get $\mathsf{pad}(p) \oplus \mathsf{pad}(p^*) \oplus r$ and $h(r)$, where $\mathsf{pad} (x)$ simply pads x with zeros?

Let $x = h(p)\oplus h(p^*)\oplus r$. If $h(x) = h(r)$, then either $p = p^*$ or you've found a collision for $h$ (which happens with low probability). Since $p$ is generated from some low-entropy distribution, I assume it's feasible to brute-force over all possible values of $p$, allowing you to recover $p$ by checking whether $h(x) = h(r)$ for each guess $p^*$.


Why does Hasse's theorem sometimes seem to be invalid? In order to generate secure elliptic curves, this answer recommends to

  Calculate the cardinal $|E(\mathbb{F}_p)|$
  Check this cardinal is in the hasse interval

(with $p$ prime) and to restart the process with a different $p$ if step 5 (or others) fails. This suggests that cardinality is not always bounded in the way Hasse's theorem indicates.

I understand that different generator points can lead to "different cardinalities" in $\mathbb{F}_p$ (given prime $p$ and fixed parameters $a$ and $b$ in $y^2=x^3+ax+b$), but I see various examples where cardinality is well below the lower bound of Hasse's interval no matter what generator I choose.

Is it that I just need to brute-force generators in $\mathbb{F}_p$ until I find one that leads to an acceptable cardinality? or what am I missing?

The order of a point on $E(\mathbb F_p)$ merely divides the cardinality $\#E(\mathbb F_p)$ (or $|E(\mathbb F_p)|$) of the group.  If $\#E(\mathbb F_p)$ has composite order, it may have small prime factors and therefore there may be low-order points that don't generate all of $E(\mathbb F_p)$.  For example, on any Montgomery curve $y^2 = x^3 + A x^2 + x$, the point $(0, 0)$ always has order 2, even if the curve has large order like Curve25519, where $p = 2^{255} - 19$ and $A = 486662$, whose order is $8\ell$ for $\ell$ near $2^{252}$.  But the standard base point $(9, \cdots)$ on Curve25519 has order $\ell$, and $(8, \cdots)$ has order $8\ell$.


Why do one-time pads not provide message authentication? It is often said that one-time pads do not provide message authentication. But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication? The probability of you getting a non-gibberish message is, I would have to spam you a noticeable quantity of messages to get one that decodes to something resembling what you expect to get.

Update: I was mostly considering attacks where ciphertext is not known, but the recipient is known. In that case, to try and guess what to send them is impossible, and the message seems like it is inherently authenticated. An attacker intercepting the ciphertext could, like the answers say, alter a bit here or there, maybe it could be good to have a message authentication hash as well.

But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication?

The informal criterion of "not complete gibberish" that you are applying here has two problems:

Malleability: It is trivial to modify OTP-encrypted ciphertexts so that they will decrypt to something that's unlikely to be "complete gibberish";
Computers are dumb: It assumes that the decrypted message is read by a human being possessed of common sense instead of acted upon by a dumb computer;

Malleability

This is the property many ciphers have that an attacker that doesn't know the key can nevertheless modify a ciphertext in such a way as to cause a predictable change in the plaintext it will decrypt to.  One-time pads and stream ciphers (the computationally secure variant thereof) are subject to one particularly trivial form of this:

If you flip any bit of a ciphertext, that causes the corresponding bit of the plaintext to flip.

This means that if I flip a bit in a ciphertext, the resulting fake plaintext will be minimally different from the real one. I hope you agree this means it's unlikely to be "gibberish."

In comments you've expressed skepticism that an attacker could exploit that to fool a recipient, because they'd have to know or guess a fair amount about the plaintext that corresponds to a the ciphertext.  But that's a condition that is often met in real life—for example we routinely encrypt network protocols and file formats that are publicly specified and such that an attacker can effectively guess the protocolar "skeleton" of encrypted messages.  And we don't want them to be able to exploit this to modify that skeleton.

Computers are dumb

The other problem is that the scenario you're implicitly contemplating—a human being, possessed of common sense, reading a single decrypted message—is not the norm by any means.  Most decrypted messages are acted upon by computers, slavishly literal and poorly programmed machines that will happily repeat the same humanly-absurd mistake billions of time per second with unintended consequences that nobody predicted.  We can't rely on some common-sense human notion of "gibberish" to reject forgeries—we need a fool-proof mechanical way of rejecting forgeries, one that not even a computer can goof up.

Example: EFail attack

One recent real-life example that combines these two motifs is the EFail attack on encrypted email.  It exploits:

Malleability: The attacker is able to modify an HTML emails' ciphertext to craft a forgery that decrypts to an HTML image tag with the original plaintext inside its URL;
Computers are dumb: Many email clients will obliviously decrypt that forged message and automatically make the HTTP request for the forged image tag before showing the plaintext to the user.

EFail is an attack against CBC-mode encryption, not stream ciphers or one-time pads, but cryptographers' general attitude to malleability is that it should not be allowed in practical systems, period.


For the scrypt HMAC storage format, why run the input of the hash and the hash itself into the HMAC Generally if the body is hashed, why provide the body and the hash as input into the HMAC.  Instead wouldn't the same security be achieved by hashing the body and providing only the hash as input into the HMAC?

I looked at the documentation here. I also looked at the answer here which provides detailed description of which byte is used for which algorithm.

These two documentations state that when computing the HMAC bytes 0 to 63 are used as input. Also, when computing the SHA-256 HASH bytes 0 to 47 are used as input.

Since any change in bytes 0 to 47 would change bytes 48 to 63.  Why bother providing bytes 0 to 47 as input into the HMAC.  Would the security be the same if the HMAC used bytes 48 to 63 as input?

Since any change in bytes 0 to 47 would change bytes 48 to 63. Why bother providing bytes 0 to 47 as input into the HMAC. Would the security be the same if the HMAC used bytes 48 to 63 as input?

No, because that would be taking the HMAC of a 16-byte, i.e. 128-bit hash, rather than the 48-byte actual value. The HMAC has 256-bit security, while taking the HMAC of the hash would only have 128-bit preimage resistance and 64-bit collision resistance.

Now, whether that could lead to a practical attack, I am not so sure. A collision attack on the hash could be within reach, but I cannot immediately see any benefit to an attacker from it. Still, if you are going to take a 256-bit HMAC, there is no need to reduce the security with an initial hash.


Differential Cryptanalysis for Hash functions How is differential cryptanalysis used to attack hash functions? I've been struggling through a couple academic papers and thesis's on the subject but they all sound like greek to me. Does anyone know who to explain this in simple enough (layish) terms?

I get how differential cryptanalysis methods work (a few of them) against Block ciphers but I'd really like to know how they can be used to target hash functions.

In the case of block ciphers, differential cryptanalysis aim to measure the changes between inputs and outputs with a probability. The goal is to predict what the result will be before the last round and try to extract the key.

For hash functions, your aim is to find a second-pre-image.

I will take Keccak as an example. It is a sponge construction interweaved with 24 iterations of a round function $\text{Keccak-$f$}$.

How does it work (very simple version)?

Analyse the round function and retrieve its differential probabilities or interesting properties (here $\text{Keccak-$f$}$ has some invariants). Consider $(a_0 \implies a_1)$ where [$a_0$/$a_1$] is the difference [before/after] the application of the round function.
Try to find a trail such as $(a_0 \implies a_1 \implies \ldots \implies a_n)$ which keeps an interesting probability and where $a_n = 0$.

In the case of SHA3-256, you will be looking for the 256 first bit of the difference state to be $0$ as they correspond to the output.

Once you get this characteristic (good luck with that!), you can try to find a collision by computing random inputs with difference $a_0$ and try to find two with the same hash. There you got a collision.

More information about the differential cryptanalysis of Keccak can be found here.


Can we encrypt part of the XChaCha/XSalsa nonce? The xChaCha cipher detailed here extends the nonce 192bits and works as follows (from the link):

Pass the key and the first 16 bytes of the 24-byte nonce to HChaCha20 to obtain the subkey.
Use the subkey and remaining 8 byte nonce with ChaCha20 as normal (prefixed by 4 NUL bytes, since [RFC8439] specifies a 12-byte nonce).

My question is could we encrypt the 2nd part of the nonce by running an additional initial round (HChaCha20) with the 16 bytes of the nonce and the key?
We could use one of the two parts of the nonce as a counter by incrementing them, given they occupy the usual counter slots.  I suppose the same question applies to XSalsa20.
I presume this would compromise something somewhere.  It seems like a very simple and cheap way to make a brute force more difficult.  The additional round(s) would take about 10ms.
EDIT - hopefully the below makes the idea (somewhat) clearer.  My impoverished code is in javascript.
Note:
HChaCha20 is initialized the same way as the ChaCha cipher, except that HChaCha20 uses a 128-bit nonce and has no counter.  Instead, the block counter is replaced by the first 32 bits of the nonce.
//Encrypt
 subkey = hchacha20(key, nonce[0:15]);
 nonce[0]+=1; //or any part which occupies the usual counter block, nonce[0-4]?
 subkey2 = hchacha20(key, nonce[0:15]);
 nonce[0]-=1; //or..etc
 subnonce = subkey2 ^ nonce[16:23];
 chacha20_nonce = "\x00\x00\x00\x00" + nonce[16:23];
 //Run ChaCha20
 output = ciphertext + nonce[0:15] + subnonce);

//Decrypt
 subkey = hchacha20(key, nonce[0:15]);
  nonce[0]+=1; //or any part which occupies the usual counter block, nonce[0-4]?
 subkey2 = hchacha20(key, nonce[0:15]);
 subnonce = subkey2 ^ nonce[16:23];
 chacha20_nonce = "\x00\x00\x00\x00" + subnonce;
 //Run ChaCha20
 output = plaintext;

First the XChaCha20-Poly1305 basics

Why one may need XChaCha20
ChaCha20 is 20 round from the ChaCha family. The Bernstein version of ChaChax has a 64-bit nonce and 64 bit counter. Bernstein argued that this should be enough in the XSalsa paper

There is a standard argument that a 64-bit nonce is long enough. Nonce security does not mean unpredictability; it means uniqueness. Applications can generate a nonce as a monotonic timestamp or simply a counter 1,2,3,...

For long-lived keys, the 64-bit nonce of ChaCa20 is too short to use securely since with the birthday attack around the 2^32 messages one will have 50% of hitting the same random nonce that will at least result in the loss of the confidentiality.
XChaCha20 is based on the IETF version that uses 96-bit nonces.

The security of ChaCha20-Poly1305 with random nonces
The ietf' docs say that after around $2^{96}$ messages one should expect a collision with the birthday attack. 50% is very advantageous for the attacker and a more conservative one is generating at most $2^{80}$ nonce so that the collision probability is $\frac{1}{2^{32}}$. And, still, this $2^{80}$ message under one key should be enough for all. Therefore, the XChaCha20 is safe to use with random nonces. The security reduced to the security of the ChaCha20-Poly1305

How the ChaCha20-Poly1305 works

The 128-bit key and the first 128-bit (16-byte) of the uniform random nonce is processed with the HChaCha20
The HChaCha20 returns two 128 bits.
The remaining 64-bit ( 8-byte) of the nonce is appended with 4 null bytes.
xchacha20_encrypt(key, nonce, plaintext, blk_ctr = 0):
     subkey = hchacha20(key, nonce[0:15])
     chacha20_nonce = "\x00\x00\x00\x00" + nonce[16:23]

     return chacha20_encrypt(subkey, chacha20_nonce, plaintext, blk_ctr)

Back to Questions

My question is could we encrypt the 2nd part of the nonce by running an additional initial round (HChaCha20) with the 16 bytes of the nonce and the key?

I'm reading this like this
```
xchacha20_encrypt(key, nonce, plaintext, blk_ctr = 0):
     subkey = hchacha20(key, nonce[0:15])
     subNonce = hchacha20(key + nonce[0:15], nonce[16:23])
     chacha20_nonce = "\x00\x00\x00\x00" + subNonce
     return chacha20_encrypt(subkey, chacha20_nonce, plaintext, blk_ctr)
```

To decrypt the other side must follow the same steps since they are not reversible! Therefore you need to send the nonce[16:23] as it is.
Therefore is no need for this since we expect that the nonce is generated uniform randomly. If you want to really do it, you can, you will get no advantage on the brute-force side. The attacker will still need to search over 128-bit. As a result, this adds nothing at all to the security.

I presume this would compromise something somewhere. It seems like a very simple and cheap way to make a brute force more difficult. The additional round(s) would take about 10ms.

It doesn't compromise anything at all but also doesn't provide any at all in the security of the XChaCha20-Poly1305. The brute-force attack, as mentioned above, will still need for a 128-bit key search.


Randomized public-key encryption as binding commitment / "collision-resistance"? I am looking to use randomized public-key encryption in a context where it should also serve as a sort of "binding commitment". That is, I want to encrypt a value $x$ with some randomness $rnd$ under a public key $pk$, denoted $enc(x, rnd, pk)$ for short, such that it is infeasible to find a different plaintext $x'$ and randomness $rnd'$ such that $enc(x, rnd, pk) = enc(x', rnd', pk)$ (the ciphertexts are the same).

I want this because a party A should be able to convince a party B that a given ciphertext $c$ is an encryption of a plaintext (known to the parties) $x$. For this, A would send the ciphertext $c$ and the randomness $rnd$ to B, and B would re-compute $enc(x, rnd, pk)$. When this equals $c$, then B should be convinced that $c$ is an encryption of $x$.

Is this a property that randomized public-key encryption schemes usually have, or can be derived from another property?

Yes, this is a property that most randomized public-key encryption schemes have. In fact, every standard public-key encryption scheme you could think of satisfies this property (e.g. RSA-OAEP, ElGamal, Goldwasser-Micali, Paillier...).

However, the binding property is not implied by the semantic security of an encryption scheme. In fact, under very strong cryptographic assumptions (the existence of a primitive called indistinguishability obfuscation), there exists public-key encryption schemes which are deniable, in the sense that for any ciphertext $c$ and any plaintext $m$ (possibly different from the one encrypted in $c$), a party can always find a randomness $r$ such that $c = \mathsf{Enc}(m;r)$ (see this paper). Such encryption schemes are interesting objects (intuitively, they would allow to guarantee security even if the government break into your house, point a gun on your head, and asks you to reveal the random coins that you used to encrypt a message - with a deniable encryption scheme, you will always be able to lie and to claim that you encrypted an innocent message). By definition, such encryption scheme are semantically secure but not binding.


What is a Pedersen commitment? I couldn't find any answer providing a high-level overview on what Pedersen commitments are or what they are used for.

what Pedersen commitments are

In a commitment scheme such as Pedersen

the committer (or sender) decides (or is given) a secret message $m$ taken in some public message space with at least two elements;
decides a random secret $r$;
produces from that $m$ and $r$ a commitment $c=\mathcal C(m,r)$ by applying some public method (the commitment algorithm $\mathcal C$) defined by the scheme;
makes $c$ public;
later reveals $m$ and $r$.
The verifier (or receiver) is given $c$, $m$, $r$ and can check if indeed $\mathcal C(m,r)=c$. That will always hold if 1/2/3/4/5 are carried out as stated.

Informally, that must not hold in any other case met, including if the committer changes $m$ between steps 1 and 5 or chooses $r$ maliciously. Further, $c$ must give no clue about $m$ before step 5.

More formally: an adversary succeeds if s/he can exhibit any of the following

$m$, $m'$, $r$ and $r'$ with $m\ne m'$ and $\mathcal C(m,r)=\mathcal C(m',r')$
$m$ and $m'$ with $m\ne m'$ and such that, for a random secret choice of $r$ and given a randomly chosen value among $c=\mathcal C(m,r)$ and $c'=\mathcal C(m',r)$, the adversary can decide with probability sizably better than 50% it the given value is $c$ or $c'$.

Pedersen commitment uses a public group $(G,\cdot)$ of large order $q$ in which the discrete logarithm is hard, and two random public generators $g$ and $h$. Random secret $r$ is chosen in $\Bbb Z_q$, the message $m$ is from any subset of that. The commitment is $\mathcal C(m,r)=g^m\cdot h^r$.

The reference description is section 3 of Torben Pryds Pedersen's Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, in proceedings of Crypto 1991.

  what they are used for

Commitments are the cryptographic equivalent of secretly writing $m$ in a sealed, tamper-evident, individually numbered (or/and countersigned) envelope kept by who wrote the message. The envelope's content can't be changed (binding property), and the message can't leak (hiding property). Among improvements brought by cryptography, we do not need to check that the envelope was actually sealed, and things can be done remotely; numbers are aplenty and recyclable. On the other hand, we need computers, and the method will convince only those that trust both math and the computer they use.

An example application is fairly deciding who serves first in a tennis match between Bob and Carol, in a way convincing both of them and Valery (acting as referee). It is agreed that if Bob can guess Carol's choice, Bob serves first; otherwise, Carol does.

Using such envelope, that could be done as:

Carol secretly decides $m$ in $\{0, 1\}$, writes it on a paper, puts it the envelope, seals it, shows that to Bob and Valery, but keeps the envelope.
Bob announces a guess $m_b$ in $\{0, 1\}$; he and Valery do not know the outcome yet, but Carol does.
Carol states her choice of $m$ and gives the envelope to Valery.
Valery checks if $m\ne m_b$ and (needed only in the affirmative) opens the envelope to check if it does contain a paper with $m$ written on it; in which case Carol serves first. Otherwise, Bob does.

Using a commitment, Carol acting as committer and Valery acting as verifier:

Carol secretly decides $m$ in $\{0, 1\}$ and performs 2/3/4, announcing $c$.
Bob announces a guess $m_b$ in $\{0, 1\}$; he and Valery do not know the outcome yet, but Carol does.
Carol states her choice of $m$ and $r$.
Valery checks if $m\ne m_b$ and (needed only in the affirmative) $\mathcal C(m,r)=c$; in which case Carol serves first. Otherwise, Bob does.

Bob can't cheat, because $c$ (which he knows when choosing $m_b$) gives him no clue about $m$.

Carol can't cheat by choosing $r$ so that $\mathcal C(0,r)=\mathcal C(1,r)$ and giving the resulting value as $c$, which would allow her to announce $m$ per $m_b$. Having failed that, she can't reverse her choice of $m$, because the check $\mathcal C(m,r)=c$ will then catch that.

As pointed by Poncho, $H(m,r)$ where $H$ is a (preimage-resistant) hash is a commitment of $m$. Compared to this, Pedersen commitments:

Allow things such as proving additive equalities (modulo the group order) among committed values, without revealing them; and more.
Maintain their hiding property even w.r.t. computationally unbounded adversaries.


Is it safe to use a counter as IV for AES256-GCM What if I will use 96-bit integer counter starting from 0 as IV for AES256-GCM cipher. Is it safe? Is there any other ways to ensure uniqueness of IV for GCM cipher?

See page 20 of the NIST recommendations (28 in the pdf, 20 on the page) - basically this is the deterministic construction (assuming you're doing less than $2^{64}$ messages), so yes this should be fine - assuming (!) that you don't reuse IV (even across restarts / crashes).

Alternatively, you can use the RBG construction, and use a secure random source to generate the IV.


Quadratic Equations to Describe SBox I am using a 8 bit Sbox having 16 entries with a lookup table of 4x4 in cryptographic algorithm. Sbox is constructed on subgroup of galois field 2^8. I want to calculate number of quadratic equations used to describe this Sbox over GF(2) so I can calculate resistance of algorithm against algebraic attacks.Since AES Sbox can be described by 23 quadratic equations and my Sbox is also 8 bit but its size is small having 16 entries only. So kindly if anyone can tell by how many quadratic equations my Sbox can be represented over GF(2)?

You cannot, without fully specifying the Sbox table. The equations are determined by something like a grobner basis algorithm or some other means which require input of the Sbox specification.
See https://eprint.iacr.org/2017/007.pdf


How can I decrypt this kind of variation of block cipher? I have a block cipher $E$ that is a permutation of $\{0,1\}^\ell$ for key $K\in\{0,1\}^\ell$.

$c = E_{K_1}(m \oplus K_1 \oplus K_2)$ for unknown keys $K_1, K_2$ is given. I need to figure out the strategy to find the message $m$ and its complexity.

However, before choosing which attack to find the message, I have no idea how to break this block cipher. I'm new to block cipher and it's hard to break a new kind of cipher I haven't seen. I need some help.

If we have some (m, c), and permutation is usually known, then I guess we can figure out $K_1 \oplus K_2$. Is this right? And then, how can we find $K_1$ and $K_2$ respectively? Or $K_1 \oplus K_2$ is sufficient to find the original message?

The question likely really is:

It is known $c$ with $c = E_{K_1}(m \oplus K_1 \oplus K_2)$, and a few distinct plaintext/ciphertext pairs $(m_i,c_i)$, that is with $c_i = E_{K_1}(m_i \oplus K_1 \oplus K_2)$. However, $c$ is not one of the $c_i$ (which would make finding $m$ trivial).

Define a strategy to find $m$, despite the terms $\oplus K_1 \oplus K_2$ in how the cipher operates. That should work whatever the internals of $E$ (which is assumed known per Kerckhoffs's principle, but not given). If necessary, assume that a lot of computing power is available, enough for about $2^\ell$ encryptions or decryptions using $E$ and whatever key, which would be enough to brute-force a normal use of $E$ as $m\mapsto E_K(m)$.

Hint 1: How would you confirm (with excellent confidence) or infirm (overwhelmingly often) an hypothetic guess of $K_1$, despite not knowing $K_2$?

Hint 2: Put yourself in the skin of an attacker. You have a black box implementing $E$, where you can enter key and data each as $\ell$ bits, press one of two buttons marked "encrypt" or "decrypt", and that applies $E$ or $E^{-1}$ as asked, data gets changed, and you see the new value thanks to $\ell$ LEDs wired on the data bits. In particular, if you press the other button, the data gets back to the previous value. That black box is an encryption/decryption oracle for $E$ (though one not knowing the key, as some oracles do; rather, it operates with any given key).

Assume that some fairy gave a tip that $K_1$ is that $\ell$-bit value. How do you put that box and what you know (stated in this answer) to use in order to confirm or infirm the tip, then (if confirmed) find $m$ ?

Next, replace the fairy (these are harder to implement with silicon chips than oracles are) by a lot of uses of the black box.

Further hints (hover mouse to see)

   3. You'll need at least two plaintext/ciphertext pairs to check the fairy's tip, and three to carry the attack.

   4. You'll need a mere two uses of the box to check that fairy's claim, and very little extra computations that one can carry with pencil and paper to note intermediary results. Addition seems complicated in comparison.

   5. You can achieve that with a single button of the black box, but not any button.

   6. If the fairy gave the right $K_1$, also putting the values of $m_0$ and $c_0$ to use, a single precise use of the black box plus a little extra allows to find $K_2$. The rest is easy.


AES S-Box: Possible options for constant to calculate S-Box values To calculate the values of S-Box in AES, I came across a lot of resources where constant {63} was chosen. It is said that {63} satisfies the condition of S-Box that it should not have any fixed points or opposite fixed points. What are other choices for constants?

eg: will {1},{2},{3},{4} be valid choices for constants? what are other options for constant available?

Out of the 256 possible 8 bit additive constants for the AES S-box, 34 satisfy the requirement of there being no fixed points or opposite fixed points:

0x05, 0x07, 0x08, 0x15, 0x1D, 0x20, 0x30, 0x37, 0x38, 0x3B, 0x3D, 0x49,
0x52, 0x56, 0x5D, 0x63, 0x76, 0x89, 0x9C, 0xA2, 0xA9, 0xAD, 0xB6, 0xC2,
0xC4, 0xC7, 0xC8, 0xCF, 0xDF, 0xE2, 0xEA, 0xF7, 0xF8, 0xFA

To address the obvious follow-up question, no, I do not know why specifically the constant 0x63 was chosen from among these 34 options.

The only immediately apparent property of 0x63 that I could guess might have influenced the choice is that it has exactly four of its eight bits set; but that's still not enough to narrow down the choice completely, since 0x1D, 0x56, 0x9C, 0xA9 and 0xE2 also share this property.

Ps. To obtain the list above, the easiest way is to start with the normal AES S-box (which can be found in many sources, including Wikipedia) as a table of 256 bytes.  You can then bitwise XOR each byte in the table with the standard additive constant 0x63 to cancel it out and obtain the S-box as it would look with a zero constant.  Then you can just test all the 256 possible constants between 0 and 255 to see if XORing them with each of the table entries will yield any entries matching their index in the table or its bitwise negation.