Improving differential cryptanalysis of a vulnerable cipher How to avoid differential cryptanalysis attacks when you are inventing new cipher?
Let's say you have a $16$-round $128$-bit cipher vulnerable on differential cryptanalysis attacks. Now let's say you will add between every round:

bitwise NOT (optional you make it ot not - randomly),
xor with $128$-bit subkey,
moving bits by $0$ to $127$ places.

Now it looks like the attacker have to guess many variables first (we defined it by keys), to make differential cryptanalysis attack. Because he can do it easily only without this obstructing steps between rounds. Is it good idea to use it, if I would like to make cipher resistant on differential cryptanalysis?

Your cipher seems quite vulnerable to side-channels the way you describe it. Also, differential cryptanalysis depends mostly on a secure S-box. The steps you describe are superficial, since they don't effectively destroy patterns.
Assuming you're using an SP-network, which is generally what a 16-round block cipher would be, let's see what the steps are to perform encryption:

For each round, you

Perform the nonlinear operation (S-box) on the plaintext
mix the key with your intermediate ciphertext
permutate the bits of your immediate ciphertext, providing diffusion

Your obstructing steps are:

bitwise NOT (optional you make it ot not - randomly),

A bitwise NOT destroys no patterns and provides no nonlinearity
Deciding randomly whether to perform this operation only adds 1 bit per round, and makes side-channels that much more likely. This step is pretty much useless while adding potential for faulty implementation.

xor with 128-bit subkey,

You should be mixing the round key anyway. I don't see how this is any different from a normal round cipher.

moving bits by 0 to 127 places.

This could add 7 bits of security per round... maybe? but would be near-impossible to implement without allowing side-channel attacks. Data-dependent memory accesses are a really bad idea (I assume the amount you move the data would depend on the key, the plaintext, or some wacky logic based on both; this would immediately allow side-channels).
If, however, you mean to move the bits by some predefined amount, congratulations! You've implemented a P-box... Which you should be using anyway, considering you're making an SP-network.

In short,
If you want to resist differential cryptanalysis, the real solution is to design the nonlinear component (S-box) in a way that isn't vulnerable to differential cryptanalysis. Perhaps you could steal the S-box from AES since it's already well-understood?
Addendum: Make sure to defend against slide attacks! Your key cycle should be decently designed, as well, and side-channel attacks are horribly easy to accidentally allow in your implementation.


How to find the order of a generator on an elliptic curve? I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm:

Choose random point $P$ on the curve.
Find the order of a generator $\ell$.
Calculate the number of points $n=\#E(\mathbb F_p)$.
Calculate the cofactor $h=n/\ell$.
Calculate a generator as $G=[h]P$.

Here I can find $n=\#E(\mathbb F_p)$ using Schoof's algorithm. I need to find $\ell$. How is that possible? How can I find the order of a generator/base point of an elliptic curve defined over a prime field?

Due to the Pohlig-Hellman algorithm, the hardness of discrete logarithms is dominated by the largest prime factor $\ell$ of the group order $n$. In particular, one typically works in a subgroup of order $\ell$ of the curve group, since the additional factors $h$ in a generator's order would not significantly contribute to security.

In that, note that $\ell$ depends on the group order $n$: You cannot just decide for some order $\ell$ and then find a point $G$ of that order on an arbitrary fixed curve, since it general such a point will not exist. (However, there is  the complex multiplication method, which generates a new curve of given order.)
Therefore, steps 2 and 3 of the algorithm given in the question must be swapped: You first compute the curve group order $n$, factor it, and determine $\ell$ from the factorization. (And if $\ell$ is too small, you should start over with a new curve. For example, Curve25519 has cofactor $h=8$.)

Other than that, the algorithm is fine, except that you might want to check whether $G=\infty$ and start over in that case. However, this only happens with probability $1/\ell$, so it should never occur in practice for cryptographically-sized curves. (Moreover, you would compute and factor the group order only once and find a good $P$ afterwards, but this does not impact the expected runtime much as $P$ usually is good at the first try.)

Thus, we have the following algorithm:

Compute the curve order $n=\#E(\mathbb F_p)$.
Factor $n$ to determine its largest prime factor $\ell$. (Note that you do not need to fully factor $n$: If the remainder after removing a few "small" divisors is not prime, the cofactor is going to be too big anyway.)
Compute the cofactor $h=n/\ell$. If $h$ is "too big", start over with a new curve.
Choose a random point $P\in E(\mathbb F_p)$ and let $G=[h]P$.
If $G$ is the point at infinity, go back to choosing a new $P$. Else, $G$ has order $\ell$.


Encrypt-then-MAC when encrypting data in multiple blocks? Given a stream cipher such as ChaCha20 and a MAC such as Poly1305, how do we handle data that comes in chunks in the encrypt-then-MAC scheme ?

For example, the plaintext is 530 bytes long. We read the first 512 bytes into a buffer, process this chunk, but what happens then ?

Do we

1.

write the ciphertext of the incoming chunk
update and write the MAC of this ciphertext

or

2.

while (incoming chunk == 512B)

write the ciphertext of the incoming chunk
update the MAC with this ciphertext

write the ciphertext of the last chunk with length L (<512)
update the mac with this ciphertext
write out the MAC

What about decryption ?

The goal of EtM is to be able to check the MAC before decrypting, so I think 2 is the right way of doing it, except if we just need one MAC tag at the end of the file (like with GCM).

You can do either. Though make sure you tighten up how you do the first scheme.

In the first case you are going to have multiple tags, 1 for each chunk. In the latter, you will have a single tag. If you are downloading files that are approximately 1MB, I think #2 makes sense. If you are downloading files that are 1GB or 1TB, maybe #1 makes the most sense, as you can stop the download if one of the chunks is bad.


Can I use M1 straight away and get rid of IV in Merkle–Damgård? In Merkle–Damgård is there any reason why we use a fixed $IV$ at the beginning? Can we use the first block ($M_1$) right away instead of $IV$ and feed it through the compression function with $M_2$.

TL;DR: A simple reason why we use the IV is to mitigate second preimage attacks.

This is the typical Merkle–Damgård construction: you split your messages in blocs of $k$ bits (input size of the compression function).

    M1         M2 ...     Mn
    |          |          |
    +--|\      +--|\      +--|\
       | \        | \        | \
 IV ---|  |-------|  |-------|  |---  Hash
       +--+       +--+       +--+

your proposal is the following :

    M2         M3 ...     Mn
    |          |          |
    +--|\      +--|\      +--|\
       | \        | \        | \
 M1 ---|  |-------|  |-------|  |---  Hash
       +--+       +--+       +--+

This assumes that the message is longer than $k$ bits! What if the message is shorter ? Well you get the following because you don't have an IV to compress with.

 M1 ---  Hash

Also this idea of using $M_1$ as an $IV$ assumes that the inputs of your compression function have the same size e.g. if you take $f(x,y) \to h$ where:

$\texttt{sizeof}(x) = 128 \texttt{bits}$ and
$\texttt{sizeof}(h) = 160 \texttt{bits}$

This implies that  $\texttt{sizeof}(y) = 160 \texttt{bits}$. Therefore the use of an IV is encouraged unless you want to manage a padding for the first input...

What if we have a fixed last bloc compression ?

Such that:

    M2         M3 ...     Mn ...     LB
    |          |          |          |
    +--|\      +--|\      +--|\      +--|\
       | \        | \        | \        | \
 M1 ---|  |-------|  |-------|  |-------|  |---  Hash
       +--+       +--+       +--+       +--+

And in the case of very short messages:

    LB
    |
    +--|\
       | \
 M1 ---|  |---  Hash
       +--+

In the end don't you agree that this is the same has having a fixed first block, also called an IV ? You still need to save this value. Whether it is at the end or at the beginning, it is needed.

A Second Pre-image attack

Quick reminder:

  Given an input $m_1$ it should be difficult to find another input $m_2$ such that $m_1 \neq m_2$ and $hash(m_1)=hash(m_2)$. Functions that lack this property are vulnerable to second-preimage attacks.

Feeding directly $M_1$ instead of the IV whatever the construction above (with or without a fixed last block) leads to a second-preimage attack:

Let $M_1$ such that $M_1 = a || b || c || d$ where $||$ is the concatenation and $a,b,c,d$ are of the right size. We pose $H(a || b || c || d) = h$.

    b          c          d
    |          |          |
    +--|\      +--|\      +--|\
       | \        | \        | \
  a ---|  |---h'--|  |---h"--|  |---  h
       +--+       +--+       +--+

Notice that we have $h'$ and $h''$ such that $h = H(a||b)$ and $h'' = H(a||b||c)$.

What happen if we compute $H(h'||c||d)$ or $H(h''||d)$ ?

   c         d
   |         |
   +--|\     +--|\
      | \       | \
  h'--|  |------|  |---  h
      +--+      +--+

    d
    |
    +--|\
       | \
 h'' --|  |---  h
       +--+

In both case you will get $h$ which leads to:
$$\begin{align*}
H(a || b || c || d) &= h\\
&= H(h' || c || d)\\
&= H(h''||d)
\end{align*}$$

Thus we have a collision through a second preimage attack (note that the compression function may be perfectly secure!).

How to solve this?

Multiple solutions exists:

Use an IV.
Encode the length of the input in the last block.
add a domain separation encoding at the end of each block.

Solutions has been discussed in the following paper (see section 8:  Implications for sequential hashing).


If $P \neq NP$ why doesn't this prove the existence of OWF? i know that $P = NP \Rightarrow$ non existence of OWF.
but i don't understand why the claim:  $P \neq NP \Rightarrow$ existence of OWF is wrong?

An intuitive answer would be enough.

an answer from  Goldwasser and Bellare's lecture notes.
P ≠ NP is not a sufficient one. P ≠ NP only implies that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility that the encryption scheme is easy to break in almost all cases. In fact, one can easily construct “encryption schemes” for which the breaking problem is NP-complete and yet there exist an efficient breaking algorithm that succeeds on 99% of the cases. Hence, worst-case hardness is a poor measure of security. Security requires hardness on most cases or at least average-case hardness. Hence, a necessary condition for the existence of secure encryption schemes is the existence of languages in NP which are hard on the average. Furthermore, P≠ NP is not known to imply the existence of languages in NP which are hard on the average.


Why is LCG PRNG chosen to be as c++ rand() function? The C++ rand() function is an  Linear Congruential Generator (LCG) PRNG. my questions are:

Why was this algorithm  chosen?
What are the pros and cons?
Is it good for cryptography?

The C++ rand() function (actually C function) is not (intended | designed | standarized) for Cryptographic purposes.

  Why was this algorithm chosen?

As SEJPM noted in the comments, the rand function comes from C and C++ has no upper restriction for the implementation.

  What are the pros and cons?
  Is it good for cryptography?

Long story short answer; don't use it for cryptography. For cryptographic purposes use /dev/urandom

The good; it is fast and small. The bad; it is deterministic, and the seed is small ( as noted by poncho in the comments) that prevents it from producing a cryptographically secure RNG from LCG.


Small Quantum Signatures - Reality check needed I've been thinking a bit lately about how to get quantum resistant signatures fast and (relatively) small.

One idea I've been keen on exploring is finding a crypto PRNG that allows fast-forwarding, e.g. Calculating what the hash will be N states in the future, without the ability of moving backwards.

The grand idea being, with a large fast-fowardable sequence generator, start with random-generated state A (private key), fast forward 2^256 states to get the public key.  To sign, you would give a state in the middle, which when iterated N steps ( where N==H==the hash value of the data you're signing) forward to equal the public key.  You would need to repeat this with a second private/public pair with N=(2^256-H) to prove the H is correct.

The lovely thing about that of course is your public key could be 32 bytes long (the hash of the 2 end states), and the signature == 2*the initial start positions to reach the public end state, say 2*64 bytes == 128 bytes.

A fatal issue, aka major reason for falling down, is that while many PRNG can be "fast-fowarded" in this way, when the cycle length is known you can in effect reverse by moving ahead (cycle_length-1) steps.
Thus for system to be practical, in order to sign a 256 bit value in this way you need to know that the cycle length is >2^256, and that the cycle length is unknown (and not easily knowable)
As a side note, SHA256 may or may not have multiple cycles.  It's also unknown.

I've been looking into a few possibilities involving a vector (X,Y) multiplied into a new X,Y using a singular matrix followed by modulo. (think LCG with singular mixing). Sure enough the vector seems to have multiple/many cycles depending on the start position.

As I always do, I'm putting far too much time into this without asking the appropriate questions - can quantum computing break these methods anyway using either shors, grovers or some combinatorial magic?

Would like to humbly ask then the experts out there - What are the fatal flaws of the basic approach, based on the realities of quantum computing and math?

Many thanks.

I see two problems with this idea.

The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs).  In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the initial state stepped $n$ times (with the group operation defined as $H^a + H^b = H^{a+b}$), Shor's algorithm should be able to find the cycle length of the group, and as you point out, that allows the attacker to reverse the operation.  The only defense I can see it to deliberately select an operation where the above is a semigroup; that is, where the set of elements $H^n$ never come back to the initial state $H^0$, but instead hits a loop later on (and so the first collision $H^x = H^y$ occurs with $x, y > 2^{256}$).  I don't know how you would ensure that.

The second problem I foresee is the mathematical structure that you would need within your PRNG; to be able to compute $H^n$ in $o(n)$ time, you need quite a bit of mathematical structure within your PRNG; I would worry that such structure could be exploited by an attacker.  For example, in your case of multiplying by a noninvertable matrix, I believe that an attacker can just look at the subspace defined by the nonintertable matrix, and effectively step backwards (by looking only for solutions that are within that subspace).  There are methods that appear to be strong against classical computers (e.g. squaring modulo a hard to factor composite), but the ones I can think of run into issues against a Quantum Computer.

Bottom line: I don't believe the idea's quite dead; I do see a number of difficulties in the path.


Does classifying an integer as a discrete log require it be part of a multiplicative group? This question is not a question about the discrete log problem, the generalized discrete log problem, or an additive group.

The confusion is whether any integer can be considered a discrete log or whether a discrete log has as a precondition, that it be part of a multiplicative group. This wikipedia would seem to indicate that the answer is yes.

For example 0 doesn't have a multiplicative inverse and is therefore not part of a multiplicative group.

The discrete logarithm $\log_b a$ is an integer $x$ such that  $b^x = a$. Similarly to the logarithms, we need a base, here $b$.

If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$.

Take a generator $g$ of a multiplicative group $G$ with order $n$, and then  take $g'=g^k$ where $\gcd(k,n) \neq 1$. Now the $g'$ will generate a subgroup $G'\leqslant G$, not the full group. Then any element of the full group $ a \in G$ and $a \not\in G'$ has not discrete logarithm according to base $g'$, even it is not a member of the subgroup.

When we consider the non-zero elements of a field $F\backslash\{0\}$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.


How do you make Fermat's primality test go fast? This small Lisp-function implements Fermat's primality test in a very simple way and it is very slow at $n >= 10^6$ because we reach into bignum territory.

(defun prime-p (n)
  (= 1 (mod (expt 5 (1- n)) n)))

What am I missing? I assume that this is not the form that is actually used in implementations of RSA to find appropriate primes, what is actually used?

I'm not very good at reading Lisp, so please correct me if I'm wrong, but it looks as if you're naïvely calculating $a^{n-1} \bmod n$ by first raising $a$ to the $n-1$ -th power, and then reducing the result modulo $n$.

This is a very inefficient way to implement modular exponentiation since, as you've noticed, the intermediate result $a^{n-1}$ can quickly grow to an enormous size.  It is far more efficient to reduce any intermediate results modulo $n$ while raising $a$ to the $n-1$ -th power, effectively doing the calculation directly in the ring $\mathbb Z / n \mathbb Z$ of residues modulo $n$.

Unfortunately, I don't know enough Lisp to directly suggest an efficient implementation of modular exponentiation for you, but the Wikipedia page I linked above does describe some suitable algorithms, and provides some iterative pseudocode implementations that you may be able to adapt.


Cryptanalysis in the middle ages -- publications Are there any publications, articles or literature discussing cryptanalysis and crypt breaking techniques in the middle-ages?

I have seen various manuals from the middle ages describing various types of encryption, also mentioning that Caesar substitution cipher can be easily broken, but I cannot find any information on algorithms and knowledge they used to do so.

Update:

I've found first description of substitution cipher breaking called unfolding at John Wilkins (1641) Mercury: Or the Secret and Swift Messenger, page 88 and further, chapter XI.: The General rules of unfolding ..., available online: https://archive.org/stream/gu_mercuryorthes00wilk#page/n111

Holden's "The Mathematics of Secrets" has nearly comprehensive explanations with rough algorithms to follow for each of the steps. It is meticulously filled with citation and rife with references to materials for additional study. It is an excellent resource for this inquiry. A good companion for it is Singh's "The Code Book".


RSA generation of private key using public key In RSA private key generation

e*d ≡ 1 mod φ

e is public, also n is public. How to prove mathematically, generation of private key d is not possible using the same equation and public key e

It isn't impossible. Otherwise, we wouldn't have to keep increasing key sizes of our RSA keys, see this for the history.

As stated in a comment, it is believed to be computationally hard. Though, even that has never been proven.


Cipher that interleaves rounds from other ciphers? Is there a cipher that interleaves rounds from other ciphers (with the same block size)? For example, interleaving the rounds of AES/Twofish/Serpent/RC6?

kodlu mentions the interactions of the key schedules; with such a design, I would worry far more about the interaction between the round functions themselves.

A single round of AES, Serpent, Twofish, RC6 has high probability linear and differential characteristics; there's a reason why we have multiple rounds.  Now, the round functions within these ciphers are designed so that they play nicely with themselves; that while (say) a single round of AES has high probability characteristics, these high probability characteristics do no apply to multiple rounds.  That is, while we can find a high probability characteristic for a single round, we cannot join these high probability characteristics across multiple rounds.  This isn't by happenstance, the designers of these ciphers deliberately set things up this way.

This is not necessarily true while you mix-and-match round functions; while we can't find a high-probability characteristic that goes through several AES round functions in succession, there's nothing that says we can't find a characteristic that goes through an AES round function, followed by a Serpent round function, followed by a Twofish round function.  I'm not saying there is such a characteristic; I am saying it would appear foolish without doing a whole lot of analysis first.

If you feel an absolute need to do this sort of thing, it would make a lot more sense to keep the round functions from the same cipher together; do a bunch of AES round functions, followed by a bunch of Serpent round functions, followed by a bunch of Twofish round functions.  There, we can at least leverage some of the security proofs inherent within the separate ciphers.


How passwords are fed to key derivation functions? Suppose I want to encrypt data, send it over the network, and decrypt it on the receiver side.

I know the elegant way to do this is by using a symmetric key to encrypt the data and an asymmetric key to send the symmetric key to the receiver so he can decrypt the data.

But I just read about another way which is to use a password based key derivation function to calculate a key on both sides. This way, no key exchanged. But this requires both sides to use the same password in the calculation of the key, so I suppose I have to send the password to the receiver at some point so he can calculate the same key and use it to decrypt.

If what I understood is correct, then I don't see the goal of using a PBKDF since I have to send something at some point. If not, then what I'm I missing?

You are correct: generally it is required to synchronize or otherwise synchronize information if you want to use a password based key derivation function (PBKDF) for sending messages.

That doesn't mean that using a password on the client side a derived key on the server side doesn't have advantages:

the password isn't stored on the server side, so an attacker may not be able learn the password if the backing database is stolen;
the password nor key needs to be stored client side (and a key is not so easy to remember) so stealing the device on the client side will likely not lead to any breach of the protocol.

That said, a PBKDF is commonly not used for sending messages in an online protocol. Instead a password based key agreement or PAKE could be used to authenticate the client and establish symmetric keys. However, a PAKE also requires a setup phase. In Augmented PAKE the server doesn't learn the password, only a derived value used for verification.

In the end, there is nothing asymmetric about password based encryption; the password is a secret; that secret or a derived value needs to be shared with the authenticating party.

Note that often the client application is often also from the same organization as the server. This means that the client will have to rely on the organization's security at some point - whichever cryptographic protocol is used. It's only possible to mitigate that problem as much as possible.


Help understanding how to decrypt cipher I am trying to create a padding oracle attack to decrypt a cipher that is encrypted with cbc and PKCS#7 padding.
My first step is just to try and decrypt the second block.
I have read a lot about it, and have started to code the first step of the attack, where I edit last byte in the first block and send it to the oracle.
But there is a point of the attack/decryption method I'm a bit confused about regarding the xor of the bytes.
The part I don't understand completely is the math on how manipulating the last byte in the first block result in the last byte in the decrypted byte to turns out to be 0x01, 0x02 etc.
I haven't figured out how the math for that works, for what I have researched it should just be to xor OriginalByte xor TestByte xor 1.
Should that be equal to 0x01?
Here I have a string "TestBlockForStackBBBBBBBBBBBa31", it is 31 bytes. That means that it has to get padded with 1 to make it equal to 32 bytes so it fits inside 16 byte blocks.
The string byte is as following (without encryption):

54657374426C6F636B466F72537461636B4242424242424242424242613331

Then we decrypt the string with the key and IV below using cbc and PKCS#7.
byte[] Key = new byte[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9, 9, 9, 9, 9, 9};
       //we don't need key the key under the attach, only under encryption.
byte[] IV  = new byte[]{2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2 };

We then get this result:

Ciphertext:  ;fŒ˜ÆOgÄ:VûÎ{Ž+6iXK¿îMŠžÌš

Cipher bytes: 3B668C98C64F67C43A56FBCE7B8E150E9D2B1F3669584BBFEE4D8A0E189ECC9A

Under the padding oracle attack I edit the last byte in the first block

(3B668C98C64F67C43A56FBCE7B8E15 0E <--).

I know that when I edit the last byte in the first block to 0D the decryption result will have a 0x01 at the end.
The first block is then going to look like this:

3B668C98C64F67C43A56FBCE7B8E150D

And what I then send to the oracle in this case DecryptStringFromBytes (code can be found in RijndaelManaged.CreateDecryptor Method) is the following
first the edited chiper 3B668C98C64F67C43A56FBCE7B8E150D9D2B1F3669584BBFEE4D8A0E189ECC9A, then the key that is only 0 (Key = new byte[16]), then the same iv as above.
It then returns that the padding is valid. I did go into the function BCryptDecrypt (used inside the decryption call) and set a breakpoint to confirm this, and it is indeed 0x01.
The output bytes from the call BCryptDecrypt is then like this:

 [0]  0x95    byte        [1] 0x28    byte        [2] 0xE5    byte        [3] 0x18    byte
 [4]  0x90    byte        [5] 0x8E    byte        [6] 0x31    byte        [7] 0xFF    byte
 [8]  0xF0    byte        [9] 0x28    byte       [10] 0x86    byte       [11] 0x7B    byte
[12]  0x9D    byte       [13] 0x63    byte       [14] 0x2F    byte       [15] 0x01    byte

The decrypted file result that returns from the decrypter to the user looks like this:

Text :  ?????xi?G?w?T}!y?(???1??(?{?c/ Bytes :
3F3F3F3F3F78693F473F773F547D21793F283F183F3F313F3F283F7B3F632F (Thay
have removed the 0x01 and the bytes is a bit different, maybe something
with how I formatted it or it does something more before returning the
bytes?)

So my questions are:

How does the info I did send turn out to be 0x01 at the end?
What do I need to xor to the result to get the plaintext/byte?

You don't start by manipulating the last byte of the first block. Rather you manipulate the last byte of the last block. You start at the end and work backwards. The side-channel leak in the padding oracle attack is that the server distinguishes between a bad cipher and bad padding. This is the leak that lets you figure out the message.

If you try every possibility for the last byte, the server will tell you if the padding is bad. If you get no "bad padding" error you know the value you tried is likely 1 xor'd with what will decrypt the last byte of the actual message. So then you try changing the last two values to get "2" and "2". You already know to xor 2 with the last value at the end that gave no bad padding error. So it's a matter of figuring out the second to last byte and trying every byte until you get no padding error and so on.

The best way to understand this that I know of is to do the cryptopals challenge (google it). It's also very helpful to look at a diagram of how CBC works because you can visualize what's happening.


Why do we use addition and multiplication in GMW protocol So i'm reading about secure computation and the GMW protocol.

I don't understand why the protocol evaluates the addition and the multiplication ?

Why not just the multiplication ?

I didn't find any information about the OT used in this protocol. Is this a basic one like Rabin's or not ?

Any efficiently computable function can be represented by a circuit containing XOR gates and AND gates - AND gates alone would not suffice (but NAND gates would). The standard practice in secure computation is to use this {XOR, AND} basis to represent functions, since evaluating a XOR is often very cheap (it only involves cheap local operations, and no communication).

In GMW, a 1-out-of-4 OT is used to evaluate the AND gates (as I said above, XOR gates only require local computation - i.e., XORing the corresponding shares). This is the standard OT, i.e., not Rabin OT: the sender has 4 messages $(m_i)_{i\leq 4}$, and the receiver with input $j \in \{1,2,3,4\}$ learns $m_j$ without learning anything else; $j$ remains hidden to the sender.

(note that such an OT can be constructed from the Rabin OT, and conversely, Rabin OT can be constructed from this standard OT - so although their functionality differ, they are essentially "equivalent" in terms of what they allow to do).


What does the "x" operator stands for in cryptography? I am studying commitment scheme and in of the notes from the class this statement comes up.

I'd like to know exactly what the X = M x R mean, since I don't seem to understand how the "x" operator should be interpreted in here

$\mathcal X=\mathcal M\times \mathcal R$ simply means that all elements of $\mathcal X$ have the form $(m,r)$ with $m\in\mathcal M$ and $r\in\mathcal R$. So this is an operator that takes two sets and then joins them in a tuple. This is also called Cartesian product.


Does Signal Application use Eliptic Curve cryptography for encryption as well? I am studying how Signal application works and as I was reading the documentation on how is applied the XEdDSA and VXEdDSA Signature Schemes.

But I kept wondering: if Signal uses elliptic curve for signing a message (as far as I understood), then how does it apply cryptography for encrypting the actual voice and instant messages. Does it use an eliptic curve cryptography scheme with a different key besides the other one?

Signal Double Rachet and X3DH protocols for key initialization and session/temptorary encryption key generation. Whilst the XEdDSA and VXEdDSA are used for signing.

All of the schemes are based on X25519 and X448 curves.


comparison of security for identity based signature and Hashing (SHA-1) the identities I would like to know which method can provide better security: using identity based signature or hashing the identities and message (using SHA-1) for authentication?

Of the two, identity based is more secure. In fact, unless you have left details out of the question, a SHA-1 hash (or any hash for that matter) of the sender's identity and the message content provides no source authentication (or data integrity check).

According to your comment, the way you would use SHA-1 to authenticate this is to concatenate the senders identity and the message, and compute the SHA-1 hash of that value. The problem is, anyone who knows your identifier can do this for any message. To illustrate this, consider the message I, SARA, give all my money to mikeazo.. Surely you wouldn't send this message, but, as proof that you sent it, here is the "authentication" tag: 92a7904e083e41d8667b92b7100d9d970eb0e84c.

You can check that SHA-1(SARA I, SARA, give all my money to mikeazo.) == 92a7904e083e41d8667b92b7100d9d970eb0e84c. So that message must have come from you, so where is my money?


Seeking special-use fingerprinting/hashing algorithm For a project I wonder if there exists some kind of fixed-size checksumming/fingerprinting function in which based on this fingerprint given data block 1, it is easy to generate more data blocks that share the same fingerprint/hash key.

Therefore this is unlike an MD5 sum. (In that I don't know how to easily go back from MD5 sum → new matching file.)

Basically, I am looking to generate the set of data blocks that hash to the same fingerprint of data block 1. Data blocks 2, 3, 4 etc... may be the same size or even smaller than 1 – ideally the less information entropy the better – but the series must be deterministic and finite, and computationally easy to find.

Comment#1 helps me tighten some properties.
In particular, considering the mapping

hash[key][index] -> datablock

Given a 32-byte key for instance, index should be consecutive integers like you would expect in arrays, and a fixed index should map to a fixed datablock (for that key).  Within that set of datablocks, each datablock should calculate to the same hash key, but when enumerated should maintain their relative index position (eg. datablockYYY should always and only be found at 15 index positions higher than datablockBBB).

The tricky part might be that the index range of hashes should not have to be so vast as to need as many bits of entropy as the data blocks themselves generally, but substantially less: limited to a 31bit unsigned integer for simpler testing, let's say.  In fact, when I come to calculating the key1 given my starting datablock1, I hope to find a datablockN whose index in the hash is not too far from datablock1's index.  The data blocks need not all be the same size, nor all possible blocks of a certain size be mappable by a particular key (pigeonhole principle in reverse). An onto function? Not sure about the terminology.

Hoping that a much reduced problem using familiar things will help shed some light, though there are significant differences here.

For cryptographic hash functions we usually want to avoid collisions as much as possible (and even more we want to avoid any way to get from the output back to the preimage).

So what you want certainly is not a cryptographic hash function, but something else.

On the first look, something like a CRC (cyclic redundancy check) could fit your bill. These have the property that they reduce arbitrary-length messages to fixed-length checksums ($n$ bit for a CRC-$n$), and given a $n$-bit checksum and a prefix of a string with only $n$ bits missing, it requires just some linear algebra to compute the exactly one postfix missing. (You can have other parts missing instead, but then the computation is a bit more complicated.)

So assuming your datablocks are $m$ bit, we have the functions
$$\def\Z{\mathbb Z}\def\invC{\operatorname{inv}\!CRC} CRC : \Z_2^m \to \Z_2^n,$$
$$ \invC : \Z_2^{m-n} \times \Z_2^n \to \Z_2^m, $$
where $\invC(x,y)$ has $x$ as the first $m-n$ bits, and $CRC(\invC(x,y)) = y$.

I'm not sure if this fits your bill - you could have $y$ as key and $x$ as index, or the other way around.


Cryptography in virtual currencies Apart from bitcoins and altcoins, are there any other virtual currencies (like game currencies, gift cards or coupons) that include cryptography in their algorithm?

Is suppose you choose to not consider online payment, credit card payment with euros, pounds, yens, etc(which include cryptography in their algorithms)...

In the 90's, there was a company called Digi-cash funded by David Chaum:
https://en.wikipedia.org/wiki/DigiCash
The goal was to provide anonymous transactions to users and was based on his previous academic work about e-cash
 The company doesn't exist any more, but it's the best example of "cryptocurrency" not based on the "blockchain protocol".


byte significance with hash functions I am using the python hmac module to generate an authentication code. Given a key, message, and hash function (I am using md5), the library returns an authentication code as a python bytes object. I am using the first N bytes of the code, i.e. digest[0:N] if digest is the variable storing the code.
How do I unambiguously (i.e. in a library-independent fashion) describe the truncation I am using? Would it be the N most-signficant bytes? Least-significant? If I declare that I am using the HMAC algorithm (RFC 2104) with md5 hash, is it sufficient to say that I take the "first N bytes" of the MAC?

I'd confidently go for "first N bytes". It's quite universally recognized that the output of practical cryptographic hashes are bitstrings or bytestrings; where a bytestring starts is subject to little ambiguity; and how to count starting from that is unambiguous.
That's not to say that an error is impossible. In particular, the MD5 output is 128 bits that internally are 4 words of 32 bits, and MD5 words are to be converted to bytes per little-endian convention. That has caused headaches including to researchers working on MD5, see this anecdote. And later hashes often used with HMAC (e.g. SHA-1, SHA-256 and SHA-512) use big-endian.
Note: even though HMAC-MD5 is still standing strong when the key is secret, is the small speed gain compared to HMAC-SHA-256 or HMAC-SHA-512 worth exposing a design to criticism?


Absorbing r + c bits in first round of a sponge function In the standard sponge construction, r bits are consumed in each absorption step, and they get concatenated with c capacity bits. In the first round, the capacity bits are 0, so the r input bits just get zero-extended. Can we instead consume r + c bits in the first round, while maintaining the security properties of a random sponge?

Intuitively, it seems like the capacity bits serve no purpose in the first step, since there's no state from a previous round that needs to be propagated. My intuition could be wrong though.

If it's valid, this optimization would be particularly helpful in SNARK programming. If we're compressing two field elements to one, for example, this would let us use a state width of two field elements instead of three.

Here's how to create a second preimage with your modification.

We'll assume that the original message is at least $2r+c$ bits long, and consists of an initial message segment $M_0$ ($2r+c$ bits) and the rest of the message $M_1$.

After processing block $M_0$, the sponge state will be some setting, with the public $r$ bits at some value $R_0$ and the capacity $c$ bits at some value $C_0$.

Concatenate the values $R_0$ and $C_0$ to be an initial block, and then prepend that to $M_1$, giving $R_0 || C_0 || M_1$.

When hashing that, the sponge construction will take the $R_0$ and $C_0$ bits and set the initial Sponge state to be precisely what it was after the initial processing of $M_0$.  Then, it'll process the rest of the message $M_1$; because the state is the same, it'll perform the same operations, and generate the same hash.

And, because the lengths of the two messages are different, the messages are different, and thus we have generated a second preimage.

The OP since asked about the security if the length of the input is fixed.  Well, if the length of the output $n$ is at most $r$ (i.e. one squeeze cycle), then it is easy to generate preimages.  The method is straight-forward; you start with the final state (with the known $n$ bits in the $r$ region), and arbitrarily select values for the other $r+c-n$ state bits.  Then, you run the hash backwards (using the inverse permutation, and arbitrary settings for intermediate message blocks) until you get to the initial state, and then you select a message where the first $r+c$ bits are that initial state, and the rest of the message blocks are those arbitrary message blocks you selected.

If we have $n > r$, this still can be used to reduce the amount of work to find a preimage by a factor of $2^r$

The bottom line: the entire security of SHA-3 comes from the capacity bits; letting the adversary arbitrarily select them breaks things bad...


Show G is insecure against adaptive adversaries Hey crypto SE, i'm having a bit of trouble with this question. Can anyone help me to understand how to go about solving this problem? Any help is appreciated :)

Show G is insecure against adaptive adversaries by designing an adaptive adversary?

Is it possible that a comparable advantage could be achieved by a non-adaptive adversary.

(a) Adaptive case: To show that the adversary can get a very large advantage, send an arbitrary query $x$ to the oracle. The left part of the response is the input of the second query. If the oracle is a PRF, the left part of the second response equals the right part of the first response. If the oracle is a random oracle the two parts are not equal with a very high probability $p \rightarrow 1$ for $n \rightarrow \infty$.

Let $$L: \{0,1\}^{2n} \rightarrow \{0,1\}^n, ~L(x_1, \ldots, x_n, x_{n+1}, \ldots, x_{2n}) = (x_1, \ldots, x_n)$$ and $$R: \{0,1\}^{2n} \rightarrow \{0,1\}^n, L(x_1, \ldots, x_n, x_{n+1}, \ldots, x_{2n}) = (x_{n+1}, \ldots, x_{2n})$$ be the projection to the left and right $n$ Bits, respectively.

Query $$G_k(x) = F_K(x) \parallel F_K(F_K(x))$$
Query $$G_k(L(G_k(x))) = F_K(L(G_k(x))) \parallel F_K(F_K(L(G_k(x)))) =
 F_K(F_K(x)) \parallel F_K(F_K(F_K(x)))$$

And hence $$R(G_k(x)) = L(G_k(L(G_k(x))))$$

(b) Non-adaptive case: Since $F$ is a PRF both $F_K(x)$ and $F_K(F_K(x))$, and hence $G_k(x)$ cannot be distinguished from random output. Since the inputs in a sequence of queries are chosen beforehand, their responses appear completely unrelated and do not provide any information about the nature of the oracle.


What is the best technique I can use to encrypt inner nodes in B+tree? I'am working on searchable encryption.

First I create an index for a set of files. The index is B+ tree. The leaf of this tree is a bloom filter which represents the words in each file. Each bloom filter represents one file. Inner nodes represent XOR of these leaf nodes.

Last but not least: to encrypt this tree, I'ld like to encrypt each leaf node separately, but I'm confused which techniqe should be used to encrypt the inner nodes – while keeping it easy to do searches in this tree. What is the best technique I can use to encrypt inner nodes in B+tree?

We don't know your scheme, so we cannot say which technique is better for you, but in most earlier schemes that use binary vector (or any integer vector) for store information, Secure Inner Product is most used tools for encrypting! And it's useful for searching in some condition and depend on search construction.

P.S. Why you using bloom filter that has false positive issue?
I'm working on SE too.


Is NTRU still hard if $G$ is set to 1? I'm looking at the description of NTRUEncrypt given on page 21 of http://archive.dimacs.rutgers.edu/Workshops/Post-Quantum/Slides/Silverman.pdf and using its notation. So in NTRU there are always two private parameters $F$ and $G$. However, decryption only requires knowledge of $F$. I'm confused about what the purpose of $G$ is because it doesn't come into the decryption and I don't see why removing $G$ hurts the security of NTRU - more specifically, is NTRU still hard if $G$ is always set to 1 (i.e., $(1,0,0,...,0)\in \{-1,0,1\}^N$)?

If $G$ is set to $1$, then the adversary can easily decrypt the ciphertext because in this case $h = pf^{-1} \mod q,  p$ is coprime with $q$, then inverting  $p \mod q$ is possible and  after that he calculates $f \mod q$ from $h$, then he calculates $f^{-1} \mod p$ from $f$


Why is this voting system not secure? Why not have each person simply treated as a counterparty to an off-the-record chat?

People show up in groups and show an ID which is cross-referenced against a central database to prevent Sybil attacks.
They have their apps generate a set of random numbers by each committing to one or more values and then revealing their values, combining them to form some set of random numbers.
Based on this, they each receive a provably random series of off-the-record MAC keys to use for upcoming elections onto their device, without the issuer knowing anything about the device, e.g. scan QR codes.
Then in each election, they vote once using Off-The-Record Messaging and have all the votes stored in a Merkle tree?

This scheme has the following properties:

Verifiability - seeing one’s own Merkle branch is all that’s needed to verify the vote was counted correctly. Seeing the whole Merkle tree one can show that a certain % of issued tokens were used and used only once.
Unlinkability - just like in OTR chat, once you sent the message, the zero-knowledge proof has been conveyed but now no one can prove how you voted.

Is there a flaw I missed? Why can’t we do voting like this?

Unfortunately, most of the reasons that e-voting is not popular have  nothing to do with the integrity of the underlying mathematics.  This makes the question slight moot on a cryptography forum, but the following un-cryptographic answer still entirely relevant.  Unless you solve the following (non exhaustive) problems:-

It's a  requirement of law enforcement (and thus oddly necessary for the protection of democracy) that you have to be able to check how people voted. Just proving that someone voted once is insufficient. Zero knowledge by definition can't be evidence in a proceeding.
Ella points out the conundrum that if point 1 is satisfied and voter behaviours can be verified, it can encourage more vote fraud by people selling their votes which can then be machine verified as bought by the orchestrator. Could this lead to an alt-Trustpilot system emerging of "quality" voters ranked by cost and reliability?
You also have to be able to prove who hasn't voted so that they can be prosecuted in certain jurisdictions /Australia. This is probably easier to solve than point 1, but clearly the issue of tokens does not guarantee a cast ballot. But such proof gets complicated again if run in parallel with traditional paper schemes.
Your requirement for ID is a H U G E problem.  25% of African-American voting-age citizens lack a US issued photo ID. My mum and dad don't have any either. Ginswich points out that several of these points share the common theme of  voter identification /authentication. This speaks to the broader issue of whether we want a society where everyone must carry "papers".
Can I spoil my vote?  I reserve the right to draw a squirrel on my voting slip or have an option for non of the above.  This must be the easiest to solve with the addition of a dummy candidate.
The bad guys will just hack the phones. So the Merkle tree remains intact collating the votes, it's just that you can set the app to vote for Hillary all the time whilst swearing to you that it registered a vote for the other one. Or play a tune instead on the central collation point.
What are these apps you mention?  I'm blind so I can't easily use a phone and therefore automatically technologically disenfranchised.  Although progress on accessibility is being made, how would the blind and /or deaf interact with a QR code?
And if I don't have a phone (my granny doesn't) can I borrow someone else's to vote with legally? Can multiple vote tokens be issued to the same device if sharing?
My daughter has three phones.
What is the relationship between the contents of the Merkle tree and any cast/spoiled paper ballots, or do you plan to go 100% paperless? That would be quite a societal change.

Before the deluge of up votes, please consider that some cryptography is fine academically on a black board, but it often has to operate in the real political and social world.  A broader view has to be taken of cryptography and it's role in   society.

Update:

Regarding voter anonymity in parts #1 and #3, and comments. The following is the back of the current UK Parliamentary Election ballot paper. You may spot the unique bar and QR codes. The bar code is over 70mm long so it's not really a secret.   It's not a problem as long as the voting remains paper based.


Given an input x, can a distinguisher D output 1/2? Consider a PPT distinguisher $D$. Now if I give it an input (a bit string) $x$, it outputs 1 if $x$ ends with $1$ and $0$ otherwise. We know such a distinguisher exists and is often given as an example many times.
Now consider another distinguisher strategy, where on input $x$, it checks if $x$ is $0^n$ or $1^n$. If yes, it outputs $0$. Otherwise it tosses a coin. If the result is heads, it outputs $1$, else it outputs $0$.
My question is - Is such a distinguisher valid according to the assumptions we make in cryptography?
I think it should be valid as our distinguisher being PPT, has access to a random number generator (hence the coin tosses). Can someone please confirm.

Such a distinguisher is certainly valid. In fact, in many proofs of security, we use this strategy. In particular, assume that there is some event that can be detected by $D$ with some non-negligible probability $\epsilon=\epsilon(n)$ when $D$ is given distribution $X$, but not when given distribution $Y$. You can use this to build a distinguisher but the problem is that the distinguisher needs to distinguish with probability non-negligibly greater than $1/2$ over all possible samples. In order to bridge this gap, we typically have $D$ output 1 if the detected value is received and output a random bit otherwise. This means that $D$ outputs 1 on distribution $X$ with probability $\epsilon \cdot 1 + (1-\epsilon)\cdot\frac12 = \frac12 + \frac\epsilon2$. If this detected event never happens on distribution $Y$, then $D$ will output 1 with probability $\frac12$ on random, and so it distinguishes with non-negligible probability $\frac\epsilon2$. Note that sometimes the detected event does happen on distribution $Y$ as well. But if it is with negligible probability then it's still OK. Letting $\mu=\mu(n)$ be a negligible function, we would have that $D$ outputs 1 on distribution $Y$ with probability $\frac12 + \frac\mu2$ (using the same computation as above) and the distinguishing probability is $\frac\epsilon2 - \frac\mu2$. Since $\epsilon$ is non-negligible and $\mu$ is negligible, this is still a non-negligible probability.


In which cases AES doesn't need IV? I was trying to decrypt a text encrypted with AES and ECB mode.
I did try several keys and IV. I solved it by ignoring IV. (The IV was given, but it was maybe a distraction)
My question is in which cases IV is needed and in which is not?

A quick list from Wikipedia;

ECB : doesn't use IV and don't use ECB which is insecure, see the penguin from Wikipedia.
CBC : uses IV
PCB : uses IV
CFB : uses IV
CTR : uses IV
OFB : uses IV
GCM : uses IV
CCM : uses IV
....

In short, all secure modes need an IV. To achieve semantical security the Probabilistic encryption is required.


Proper forward secrecy Currently I have a protocol using a simple RSA to AES handshake. I have been reading more and more and would like to implement proper forward secrecy, but at the same time I'd like to improve the performance on mobile devices.

My question is, where would I start reading / learning about how to implement proper ECDHE ( as this seems to be the preferred choice ) and how to properly implement it?

The documentation on OpenSSL seems to be rather unfinished and annoying to work with.

I'd recommend you to read those two documents:

RFC 6090: Fundamental Elliptic Curve Cryptography Algorithms - describes all the fundamental operations in ECC algorithms (including ECDH), and includes references to further readings with more details.
The security impact of a new cryptographic library - explains design and implementation decisions behind NaCl, an OpenSSL alternative from Daniel J. Bernstein.


Zero-knowledge proof of a product I have non-negative integers $x,y,z$.  I'm going to give you commitments $C(x),C(y),C(z)$ to them.  Then, I would like to prove in zero knowledge that $xy=z$.  I can choose the commitment scheme to make the zero-knowledge proof easy, if that helps.  What protocol should I use?  Is there a highly efficient protocol for this?

Details: Assume I know that all three of $x,y,z$ fit in $k$-bit integers, i.e., $x,y,z \in [0,2^k-1]$, and $k$ is publicly known.  Given commitments $c_x,c_y,c_z$, I want a zero-knowledge proof of knowledge that I know $k$-bit non-negative integers $x,y,z$ such that $xy=z$ (over the integers) and $c_x,c_y,c_z$ can be opened to $x,y,z$.  It is not sufficient to prove that $xy=z \pmod q$; I want a proof that the equation holds over the integers.  I don't care whether the commitment scheme is information-theoretically hiding or computationally hiding; either is fine.

Preferably, the commitment scheme should also allow me to do range proofs (to prove in zero knowledge that $x,y,z$ are in a particular range).

Use the exponential variant of ElGamal, where the plaintext is encoded in the exponent. Elliptic curve ElGamal is fine. In fact, any public key cryptosystem which allows raising ciphertexts to a power such that this operation corresponds homomorphically to multiplication for the plaintext.

Your commitments are $c_x = \mathsf{E}(x)$; $c_y = \mathsf{E}(y)$; and $c_z = \mathsf{E}(z)$. Additionally, you must commit to an encryption of one: $c_1 = \mathsf{E}(1)$, and prove that it is an encryption of one using a Schnorr proof.

Next, use the Chaum-Pedersen proof of equivalent discrete logarithms to prove the following relation: dlog$_{c_1}c_y = $ dlog$_{c_x}c_z$.

Schnorr proof:

Public knowledge: $a, b$

Private knowledge for $\mathcal{P}$: $s$

Claim: $a = b^s$

$\begin{matrix}
\mathcal{P} & & \mathcal{V} \\
u \xleftarrow{\$} \mathbb{Z}_q & & \\
v \leftarrow b^u & & \\
 & \xrightarrow{\quad v \quad} & \\
 & & e \xleftarrow{\$} \mathbb{Z}_q \\
 & \xleftarrow{\quad e \quad} & \\
r \leftarrow se + u \mod q & & \\
 & \xleftarrow{\quad r \quad} & \\
 & & b^r \stackrel{?}{=} a^ev
\end{matrix}$

The Chaum-Pedersen proof is very similar:

Public knowledge: $a_1, a_2, b_1, b_2$

Private knowledge for $\mathcal{P}$: $s$

Claim: $s = $ dlog$_{b_1}a_1 = $ dlog$_{b_2}a_2$

$\begin{matrix}
\mathcal{P} & & \mathcal{V} \\
u \xleftarrow{\$} \mathbb{Z}_q & & \\
v_1 \leftarrow b_1^u & & \\
v_2 \leftarrow b_2^u & & \\
 & \xrightarrow{\quad v_1,v_2 \quad} & \\
 & & e \xleftarrow{\$} \mathbb{Z}_q \\
 & \xleftarrow{\quad e \quad} & \\
r \leftarrow se + u \mod q & & \\
 & \xleftarrow{\quad r \quad} & \\
 & & b_1^r \stackrel{?}{=} a_1^ev_1 \\
 & & b_2^r \stackrel{?}{=} a_2^ev_2 \\
\end{matrix}$

At this point, I thought my answer was complete, but the questioner correctly notes: "This is an excellent start, but it proves that $xy \equiv z \pmod q$, rather than that $xy=z$. I think if you choose $q$ to be $>2k$ bits long, and combine it with a range proof of the size of $x,y,z$, though, this might work."

It is nice that you specify that $x, y$ and $z$ are in $[0,2^k]$, because that makes the range proof a little easier. In order to prove this range of $x$ (same for $y$ and $z$), do the following:

Commit to $k$ bits of $x$, i.e.: send $\mathsf{E}(x_i)$ to the verifier, where $x_i$ is the $i$th bit of x.
Prove the commitments are encryptions of either 1 or 0.
The verifier can aggregate the bits homomorphically: $\mathsf{E}(x) = \prod_i \mathsf{E}(x_i)^{2^i}$. Use this as the commitment of $x$.

It remains to be shown how to prove that an encryption is an encryption either of 1 or else of 0. This can be done using the CDS proof linking technique (link).

First, note that in the ElGamal cryptosystem, it is easy to prove that an encryption $\mathsf{E}(a)$ encrypts a plaintext $a$. The encryption is given by $\mathsf{E}(a) = (g^y, g^{a+xy})$. Divide $g^a$ out of the second value and then produce a (Chaum-Pedersen) proof that dlog$_g g^y = $ dlog$_{g^x}g^{xy}$.

Second, note that it is also easy to falsely "prove" that an encryption $\mathsf{E}(a)$ encrypts a different plaintext $b$, provided that you control the challenge $e$ sent by the challenger. The claim to be proved is dlog$_g g^y = $ dlog$_{g^x}g^{-b+a+xy}$. Generate the proof transcript as follows (let $a_1$ correspond to $g^y$, $b_1$ to $g$, $a_2$ to $g^{xy}$ and $b_2$ to $g^x$): $e, r \xleftarrow{\$} \mathbb{Z}_q$; $v_1 \leftarrow b_1^ra_1^{-e}$; $v_2 \leftarrow b_2^ra_2^{-e}$.

The central idea of the CDS technique is to generate two proof transcripts, one of which is made interactively with the verifier and the other of which was generated beforehand. This is done in such a way that the verifier cannot tell which one of the two proofs was interactively made and which one was generated earlier. In particular,

The prover generates a proof transcript $T_f$ of the false claim: $T_f = (c_f,e_f,t_f)$, and a first message of the true claim: $c_t$.
The prover sends the two first messages to the verifier: $\mathcal{P} \xrightarrow{\quad c_f, c_t \quad} \mathcal{V}$.
The verifier chooses a random challenge $e \xleftarrow{\$} \mathbb{Z}_q$ and sends it to the prover: $\mathcal{P} \xleftarrow{\quad e \quad} \mathcal{V}$.
The prover interpolates on the line defined by the two points $(0,e), (1,e_f)$ and evaluates it in $2$ to obtain $e_t$.
The prover completes the transcript $T_t$ of the proof of the true claim using $e_t$.
The prover sends both transcripts to the verifier: $\mathcal{P} \xrightarrow{\quad T_f, T_t \quad} \mathcal{V}$.
The verifier verifies the proof transcripts and verifies that $(0,e), (1,e_f), (2,e_t)$ are on the same straight line.

The reason this technique works is because the prover can prove only one of the claims. Having committed to the false proof, he has no degrees of freedom left to choose his challenge for the true proof. Thus, the verifier knows that at least one of the transcripts was produced interactively. Obviously, the order of $T_t$ and $T_f$ must be random because otherwise the verifier can easily tell which one is true and which one is false.


DES generating the same ciphertext for different plaintexts and identical key Is it possible to get the same output for DES while the inputs are different while using the same key? The key should not have to be a weak key.

If yes could you give me a hint how to show how to do this? Is there a specific S-BOX to work with? If this cannot be done, then why is it considered impossible?

No, that is impossible. The reason is simple: How would you decrypt this? If you input the ciphertext and the key into the decryption function, than you have to get exactly one output, not two. How would you decide which output is the correct one?

The DES encryption and decryption functions are bijective under one given key. This means that for every possible input there is exactly one output. Not more, not less. Every output has only one matching input, not more, not less. You can reverse any transformation made, forward and backward, at least if you have the key. This behavior is assured by the inner Feistel network of DES.

All this has to be the case for every possible key, even weak or semi-weak ones.

This is the case for every "standard" block cipher: DES, AES, Blowfish, Twofish, MARS, Serpent, RC5, RC6, ... They all meet this requirement. Different operating modes can change this, through. Different plaintexts can lead to the same ciphertext with different IVs, for example for CBC. I don't think that the question focuses at this, but I want to include it after reading Maarten Bodewes - owlstead's answer.


Are private and public key sizes of Elliptic curve related? I'm new to elliptic curve cryptography.

I just want to know in the case where I take a random number (private key) and find its associated public key, does the size of the public key depends upon the size of the random number chosen?. If so then how is it related? If not then what determines the size of the public key?

The size of the public key depends on the elliptic curve used. Any private key will produce a point on the curve, which is the same size – approximately 256 bits for 256-bit curves, for example.

Random numbers from a small range could be insecure, however. The secure way to generate the private key is to take it from the range $[1, l-1]$, where $l$ is the order of the base point. So in the end the size of the private key and the public key should be related, though not necessarily equal (if the cofactor is larger than 1).


Why doesn't this factoring to order-finding reduction work? Scott Aaronson likes to motivate the factoring-to-period-finding algorithm used inside Shor's algorithm as follows.

Now, I want you to step back and think about what this means. It means that, if we can find the period of the sequence
$$x \bmod N,\quad x^2 \bmod N, \quad x^3 \bmod N, \quad x^4 \bmod N, \quad \dots $$
then we can learn something about the prime factors of $N$! In particular, we can learn a divisor of $(p-1)(q-1)$. Now, I’ll admit that’s not as good as learning $p$ and $q$ themselves, but grant me that it’s something. Indeed, it’s more than something: it turns out that if we could learn several random divisors of $(p-1)(q-1)$ (for example, by trying different random values of $x$), then with high probability we could put those divisors together to learn $(p-1)(q-1)$ itself. And once we knew $(p-1)(q-1)$, we could then use some more little tricks to recover $p$ and $q$, the prime factors we wanted.

See also Section 19.2 (pp 156) of his Lecture notes where he expounds upon on the same idea. However, in both expositions he ends with a dismissal of the idea:

Unfortunately, this doesn’t quite  work  with  Shor’s  algorithm,  because  the  period  of $f \colon r \mapsto x^r \bmod N$ might  not  equal $\phi(N)$, the most we can say is that the period divides $\phi(N)$.

But why doesn't it work?
As Aaronson himself noted, by repeating the algorithm with different values of $x$ wouldn't there be a chance of finding all the factors of $\phi(N)$ (or at least sufficiently many to figure out the remaining factors somehow)?

Aaronson's notes discuss finding $p$ and $q$ if we know $\phi(N)$ by solving the quadratic equation $X^2-(N-\phi(N)+1)X+N=0$ whose roots are $p$ and $q$. This only works if $N$ is the product of two distinct primes (which is the case in most applications of interest) and if we know $\phi(N)$ exactly.
What doesn't often get mentioned about RSA and multiplicative orders is that although the multiplicative order divides $\phi(N)$, it is never equal to it. In fact it always divides the smaller quantity $\lambda(N)$, the Carmichael function of $N$ and sometimes is equal to it. In the case of two distinct prime factors $p$ and $q$, $\lambda(N)=\mathrm{LCM}(p-1,q-1)$. Shor's algorithm has a pretty good chance of delivering $\lambda(N)$ and the LCM of multiple runs should give the exact value. One then knows (in the two prime case) that $\phi(N)=\mathrm{GCD}(p-1,q-1)\lambda(N)$ and might hope to exhaust over possible values of the GCD in order to use the quadratic equation.
People could start to build $p$ and $q$ to make this GCD large (which is not a good use of time) specifically to block the quadratic equation recovery. Instead we prefer to teach the ``random square root of unity'' recovery of the factors which only needs $\lambda(N)$, which works for moduli with more than 2 prime factors and is not effectively blocked by trying to choose $p$ and $q$ in strange ways.
ETA: On further reflection, rather than exhaust over possible values of $\mathrm{GCD}(p-1,q-1)$ on could take the GCD of $N-1$ and $\lambda(N)$ and mess around. This would probably lead to $\phi(N)$ in short order in the two prime case, but the details begin to get more involved than the square root of unity description.


Discrete Gaussian Sampling role in Lattice-Based Crypto? I'm reading up on how post-quantum cryptography works, and stumbled upon the notion of discrete Gaussian sampling. However, I can't understand where it fits in the greater picture - currently it feels to me like a solution to a problem nobody put out.

Where exactly in a SVP problem (or any other commonly used lattice problem) would Discrete Gaussian Sampling provide a benefit?

I'm still new to PQ so pardon the highly likely banality of the question

A Gaussian distribution satisfies the following desirable properties:

It can be implemented coordinate-wise: If $x_1, x_2, \ldots , x_n$ are each sampled from a one-variable Gaussian distribution, then $(x_1,x_2,\ldots,x_n)$ is sampled from a multivariable Gaussian distribution.
It approximates a uniform error distribution modulo a lattice exponentially well, regardless of what the lattice is.

The first property makes implementation easy, and the second property makes security proofs easy, since many security proofs in lattice-based crypto involve switching around the lattice lots of times until you get what you want.

To show what I mean by the second property, let's consider a one-dimensional lattice $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\} \subset \mathbb{R}^1$. Take a normal distribution with standard deviation $1/2$. In other words, just your average normal distribution:

Suppose that I sample real numbers from this distribution and take the fractional part of the resulting real numbers. (Taking fractional parts correpsonds to taking error vectors with respect to the lattice $\mathbb{Z}$.) The resulting distribution amounts to taking the original normal distribution, chopping it up into unit intervals $\ldots, [-2,-1], [-1,0], [0,1], [1,2], \ldots$, and adding them up. When we do that, we get something quite magical:

Notice how close this distribution is to uniform! The "radius" or standard deviation of this distribution is only $1/2$, which is not much larger than the size of the unit interval; in fact it's smaller. Even with such a small radius, we get a ridiculously good approximation to the uniform distribution. You can prove (and you should prove, as an exercise) that the quality of the approximation is independent of the choice of where the original normal distribution is centered.

Suppose we take a slightly larger normal distribution, say with standard deviation $2/3$:

If we graph the fractional part of this distribution, we get:

That's really really good! You can't even tell that it deviates from uniform. In mathematical terms, we say that the distribution is exponentially close to uniform. Even a small increase in the width of the distribution (from $1/2$ to $2/3$) improves the quality of the approximation dramatically.

You might say, what's the big deal? We can easily get a uniform distribution on any interval. But that's not the point. In lattice-based cryptography, you often don't know what the lattice is. (It's part of someone's secret key.) Suppose as an exercise that we didn't know what this lattice is, and we tried to sample error vectors by taking them uniformly from an interval $[0,n]$ for some $n$. We can't just take the perfect choice of $n=1$. That's cheating, since we're assuming we don't know what the lattice is. In this case, any choice of a small number $n$ will cause the distribution to be horribly wrong; for example, if we chose $n=2/3$ in this scenario, then all of our error vectors would lie in $[0,2/3]$, which is far from uniform in $[0,1]$. Even a slightly larger $n$ is no good; for example if $n=3/2$ then random real numbers sampled uniformly from $[0,3/2]$ will be much more likely to have fractional part (i.e. error vector) lying in $[0,1/2]$ than in $[1/2,1]$. Of course, a very large $n$ (say $n \approx 10^9$) would do the job, but that's exactly the problem: since our distribution on $[0,n]$ doesn't converge to the uniform distribution on $[0,1]$ exponentially fast (unless we cheat by taking $n \in \mathbb{Z}$, which is not allowed), we end up needing to take very large values of $n$, which is not only hard to implement, but a nightmare in security proofs where theoretical analysis is required.

What you need is a way to approximate uniform error vectors exponentially well, without relying on prior knowledge of what the lattice is. Gaussian distributions do that job.


Efficient algorithm for finding Sophie Germain primes What's the industry standard for an efficient finding large Sophie Germain primes?

As a part of request handling in my application, I need to generate Paillier key.

My current approach is to generate a pseudorandom probably prime number q backed up by Miller-Rabin test, then setting p = 2q + 1 and checking if p is also prime with Miller-Rabin and Baillie-PSW. This is repeated until p is prime.

loop {
  q <- randomPrime(nbits - 1) // generates probably prime number,
                              // performs Miller-Rabin tests on the result
  p = 2q + 1
  return if isPrime(p)  //applying the Miller-Rabin & Baillie-PSW tests
}

For nbits = 1024 one loop step takes about 100ms on my laptop. Not that bad, but in order to find desired p and q I need to execute several loop steps. The best result so far was 156 retries  (~16s), the worst one was 1616 retries (~160s).

It's a way above required latency so I wonder what's considered the correct approach nowadays.

I don't know of any industry standards, however it's obvious that your code is fairly suboptimal.

The initial randomPrime() will effectively pick a candidate number $q$, and then spend a lot of time ensuring that number is prime.  Now, half the time it'll pick a $q \equiv 1 \pmod 3$; if so, p will be a multiple of 3, and so you've just wasted all that time testing if $q$ is prime.

Now, what all random prime routines I've seen do is first ensure that their candidate number doesn't have any small factors (so we don't need to run our expensive primality tests on those values); this can be done either by computing $q \bmod s$ for small primes $s$, or by creating a sieve (a bitmap where each bit $i$ corresponds a value $a + bi$; the bit gets marked if $a + bi$ has a small factor).

Both methods can be extended to check either $q$ or $p = 2q+1$ has a small factor:

For the explicit $q \bmod s$ computation, we skip it if that is either 0 or $(s-1)/2$
For the sieve case, we mark bits where $a + bi \bmod s$ is either 0 or $(s-1)/2$

Doing this will significantly reduce the number of iterations you'll need to perform.

Now, if your randomPrime() logic is in a library you can't touch, this advice doesn't help you.  However, if you can do it, this will be of help.


Is the product of two primes only factorisable by those two primes? The question is as per the subject line. Does the fundamental theorem of arithmetic imply (prove?) that if I multiply two primes, then those two primes are the only factors of the product? I.e. 17 x 23 = 391 and the only factors of 391 are 17 and 23. I have searched, but can't find an answer to this precise question.

Yes, that is true (unless you count the trivial factors of 391, namely 1 and 391).  The fundamental theorem of arithmetic states that any postive integer is a product of a unique multiset of primes, and that no other multiset will multiply together to form that integer.

And so, since $391$'s multiset of primes is $(17, 23)$ (because both $17$ and $23$ are prime, and $17 \times 23 = 391$), that implies that no other prime can possibly divide $391$.  If there were such a prime $p$, then we'd have an alternative multiset that consisted of $p$ and a multiset that was the factorization of $391/p$; that would be a different multiset (because, by assumption, $p$ is neither $17$ nor $23$) with the same product, and we know that can't happen.


Elliptic curve ElGamal with homomorphic mapping I am interested in ElGamal due to the fact that you can achieve some degree of homomorphic properties. I became interested in applying ElGamal to elliptic curves, and found this other question with an answer that shows 2 different ways to apply ElGamal to elliptic curves, but from what I can tell neither approach has the additive homomorphic property.

So are there any other ways to apply ECEG that give us the additive homomorphic property?

The only thing I was able to come up with is using a message-point mapping function that encodes the message with scalar point multiplication, ie the cipher text $(kP, mkY)$

It seems to work because with $(\sum k_iP, \sum m_i k_i Y)$ we can solve $\sum m_i = \frac{\sum m_i k_i Y}{x \sum k_i P}$, but this is solving the ECDLP so is very difficult. Are there any other options?

EDIT: I'm looking for the additive homomorphic property over integers, not points.

There is a way to use ECEG that gives us an additive homomorphic property, however the addition in this case is Elliptic Curve point addition, not addition over the integers.

One way to use ECEG to encrypt a point $M$ is to have the encrypted value be the pair of points $(kP, M + kY)$

That way, if you have the encryption of the points $M, M'$ as $(kP, M + kY)$ and $(k'P, M' + k'Y)$, you can add each element in the pair to form $( kP + k'P, M + kY + M' + k'Y) = ((k + k')P, M + M' + (k + k')Y)$, which is a valid encryption of the point $M + M'$


Sieving the sequence $x^2-n$ to recognize b-smooth numbers I am currently programming the quadratic sieve and have several literature books / papers and will take an example out of [1] for my question:

[1] An Introduction to Mathemtaical Cryptography by J. Hoffstein, J. Pipher and H. Silverman.

[2] Prime Numbers by R. Crandall and C. Pomerance.

[3] Smooth numbers and the quadratic sieve by C. Pomerance.

To factorize a number $n$ with the quadratic sieve, we are looking for a product of numbers $x^2-n$ giving a perfect square. The numbers $x^2-n$ has to be B-smooth. We also only look prime numbers where the jacobi symbol is $(\frac{n}{p}) = 1$, so we can solve the equation $a^2 \equiv n\ \textrm{mod}\ p$ for every $p$ with $2 \leq p \leq B$. If $p = 2$ there is only one solution and for $p \gt 2$ there are either no solutions or two soluions. But in our case are always 2 solutions, because $n$ is a quadratic residue for our prime numbers.

I will now come to the point where my problem starts. In [1] and [3] is the sieve step explained to recognize B-smooth numbers in our sequence $x^2 - n$. We are looking for the numbers $x$ where $p\ |\ (x^2- n)$.

The values of $x$ can be found "easily" by the roots of $a^2 \equiv n\ \textrm{mod}\ p$ namely the number $x$ which are congruent to $a_1 \textrm{ mod } p$ or $a_2 \textrm{ mod } p$ ($a_1, a_2$ are the roots of $a^2$).

So, we start with the first number in our sequence $x^2-n$ where $x \equiv a_1 \textrm{ mod } p$ and then every $p$-th entry is divisible by $p$. We start again at some start point of $x^2 -n$ and look for a number $x$ for which $x \equiv a_2 \textrm{ mod } p$ hold.

Now I have tried to this with some example from the book but it will stop getting the correct entry of $x$:

In [1] is the example for the number $N = 9788111$. Also, the first 20 numbers which are 50-smooth are listed with the factorization of $x^2 - n$.

The first $x$ is $x = \Big\lceil\sqrt{N}\Big\rceil = 3129$.

It starts now with:

$3129^2 \equiv 2530 \textrm{ mod } 9788111$

$3130^2 \equiv 8789 \textrm{ mod } 9788111$

$3131^2 \equiv 15050 \textrm{ mod } 9788111$

...

$4394^2 \equiv 9519125 \textrm{ mod } 9788111$

Until this number everything works. My program gives the correct factorization. And if we test it with the prime number $p = 7$ and the roots $a_1 = 2$ and $a_2 = 5$, we see that $3131 \equiv 2 \textrm{ mod } 7$. So, we can divide $15050$ with $7$.

But the next number in the list, which is 50-smooth doesn't hold the procedure:

$4425^2 \equiv 4403 \textrm{ mod } 9788111$ and $4403 = 7 * 17 * 37$

We see, that $4403$ is divisible by $7$. That means that $4425$ has to be congruent to $2 \textrm{ mod } 7$ or $5 \textrm{ mod } 7$. But it's not. That means, that at some point I can't just count $x$ with $p$ to get the next number in the sequence which is divisible by $p$. I think its because that the result of $x^2 - n$ is bigger than $n$ self at some specifically $x$ like $4425$:

$4425^2 - n = 19580625 - 9788111 = 9792514 > 9788111$

So, my question is what is the reason that at some $x$ it doesn't work anymore? What can I do to restart the procedure with counting $x$ with $p$ to recognize the valid spot to divide with $p$.

The statement "To factorize a number $n$ with the quadratic sieve, we are looking for a product of numbers $x^2−n$ giving a perfect square" is incorrect is only a subset of a possible more general definition: looking for a product of numbers $x^2-k\cdot n$ giving a perfect square (by restricting the numbers to be suitably smooth, factoring them, and using some equivalent of Gaussian elimination to form the product so that the multiplicity of every prime in its factorization is even). Introducing $k$ allows more freedom in the search (but is seldom used in practice).

The definition of QS used in reference [1] is identical to that in Wikipedia. It is looking for smooths of the form $x^2\bmod n$. That falls under the more general definition of QS that I give, since $x^2\bmod n$ is $x^2-k\cdot n$ with $k=\Big\lfloor{x^2\over n}\Big\rfloor$.

The issue encountered in the question is that the sieving algorithm used finds $x$ such that $x^2-n$ is smooth; but when $x$ exceeds $\sqrt{2n}$, that sieving algorithm no longer is sieving $x^2\bmod n$.

Options to fix this

Sieve only $x^2-n$, including when that exceeds $n$; and use $x^2-n$ rather than $x^2\bmod n$ everywhere else. Problem is, the density of suitable $x$ decreases as $x$ grows. Also, that's not an option for large $n$, since sieving even a fraction of $(\sqrt2-1)\sqrt n$ values is way too long.
Sieve only $x^2-n$, but use a larger factor base. That increases the number of relations to be found, but increases the number of smooths retained even more, so that the required number of relations will be reached sooner.
Sieve $x^2-k\cdot n$ for several values of $k$. For example: until there is enough smooth collected, and for $k$ from $1$ onward, sieve $x^2-k\cdot n$ for smooths, varying $x$ from $\Big\lceil\sqrt{k\cdot n}\Big\rceil$ to $\Big\lfloor\sqrt{k\cdot n+m}\Big\rfloor$ for some bound $m$. That matches reference [1] when the bound $m$ is set to $n$. That could be viewed as an overly naive Multiple Polynomial Quadratic Sieve.
Sieve integers of the form $(a\cdot x+b)^2-n$, with $(a,b)$ chosen appropriately, in particular such that $(a\cdot x+b)^2-n$ is divisible by $a$ (allowing $a$ as a factor, if it does not belong to the factor base). This is what actually used variants of the Multiple Polynomial Quadratic Sieve do. The multiple polynomials allows to remain in the region where the un-factored part of what's sieved is small, so that the rate of finding smooth does not become vanishingly small. One advantage compared to the previous solution is that the factor base used for sieving is the same for all the polynomials used, see this question.

There are several other, independent optimizations of QS; including:

Allow what's sieved to be negative, and include $p_0=-1$ in the factor base.
Actually factor $m\cdot N$ for some small $m$ chosen to optimize the yield of the factor base.


Clarification on the origin of `01` in this oracle padding attack? I have found what I believe to be a straightforward explanation of the oracle padding attack here: http://robertheaton.com/2013/07/29/padding-oracle-attack/

I am however getting confused by something which experts here should I believe find so easy.

When you open the link and browse to the subsection titled "Manipulating the Cipher text", there is a statement which says ...

  If the server says that we have produced a plaintext with valid padding, then we can be pretty sure that P2'[16] must be 01.

I am unable to understand why a value of 01 will imply that the padding is OK. I know that as per PKCS#5, the only way we can get 01 as the last byte is when there was only 1 byte of padding. But according to the example on this page, I don't see anything that suggests that the data had 1 byte of padding. So, I fail to understand why a result of 01 is considered successful.

Is anyone able to look at the document and advise where the 01 comes from?

Actually, we don't care about the amount of padding the original message had; we care whether the modified plaintext (that is, the result of the decryption of the modified ciphertext) has good padding or not.

The padding will be valid if the last block had one of these patterns:

  XX XX XX XX XX XX XX 01

  XX XX XX XX XX XX 02 02

  XX XX XX XX XX 03 03 03

  XX XX XX XX 04 04 04 04

  XX XX XX 05 05 05 05 05

  etc

(where XX is any byte value).  If we modify the ciphertext, and then the decryptor decrypts and packet and finds a valid padding, then we know that the value in that last block is one of those patterns.

Now, why do we initially consider one the first one, and essentially ignores the others?  Well, for a random change (that is, if the attacker is in the initial stages of that attack, and may have no information about the decryption), then the last block will have the last byte 01 with probability 1/256; the rest of the alternatives will, in aggregate, happen with probability less than 1/65280, hence with quite high probability, the ciphertext being accepted with indicate that the last byte of the plaintext was 01.


Are there key-derivation functions that are safe to use in parallel on the same secret? I'm considering using a key-derivation scheme for generating multiple keys from the same user secret. It is important that given all but one of these derived keys, it is not feasible to calculate the last one. Tunable difficulty would be a big plus.

Is there such a function, or set of functions, that are safe to use in parallel on the same secret?

This is not a duplicate of this question because I do not have any way to store a client-side salt between different devices. Using a constant would work, since that can be stored in the source code, e.g. sha256(user_secret + "first_static_salt"), but I have no idea if such a scheme would be secure. I also don't have the same parameters and same key derivation function requirements of that question. Using three different functions would work fine for me.

EDIT:
I only have the user password for entropy. Any user-specific salt used would have to be stored on a server, which means that it would be known for all parties involved (unless you encrypt it with the user password...).

The goal here is to hide sensitive data from the servers; they only need metadata to function properly, so there's no reason to send sensitive data through them. The current setup would use two different keys, one for authenticating with the servers, and one for encrypting/decrypting the actual data. Most servers would just push around uuid's, and these uuid's would be used to access a separate system where the actual sensitive encrypted data is stored. The client would then interact with these two separate systems.

You need to split this up into two separate problems:

you may have a low entropy password (as you indicate you want to have "tunable difficulty");
you need the keys of a specific user not to reveal any information about the password or the other keys.

Lets solve this in two steps:

First you need a salt and a work factor or iteration count. You can do this by choosing a secure password hash or Password Based Key Derivation Function (PBKDF). Passable options include PBKDF2, bcrypt, scrypt and Argon2 (ordered from standardized/available to secure).

You've indicated that you worry that the server knows the salt. This is however not a problem as a salt may be a publicly known value. The salt is mainly used to assure that:

you cannot search all the password hash results of the separate users using a single salt until you find a match;
you cannot find indications of duplicate passwords by looking at the password hash results.

OK, so now you should have a secret that depends on the password and the publicly available salt. It is possible to simply create create a large secret and split that up into multiple keys. The output of the PBKDF should be indistinguishable from random so as long as you don't mistakenly have an overlap between keys the keys should be independent of each other.

It is however much nicer to use a Key Based Key Derivation Function (KBKDF) such as HKDF for this step. You would then use the result of the PBKDF as key for the KBKDF. In that case you can use a label for each key, e.g. Authentication_key and Data_encryption_key. Those keys would both depend on the master key, but they would otherwise be independent of each other.


Is it possible to see whether different EC encrypted messages are (likely to be) encrypted on the same public key? There are two non-equal (different at least in one bit) messages $M_1$ and $M_2$ both encrypted with elliptic curves on public key $K_{pu}$: $E_1=\mathsf{Enc}(K_{pu}, M_1)$ and $E_2=\mathsf{Enc}(K_{pu}, M_2)$.

An attacker possesses $E_1$ and $E_2$ but does not know whether they are encrypted with the same key.

Is it somehow possible for at attacker to establish that $E_1$ and $E_2$ are encrypted with the same key, or to make such judgement with reasonable probability?

I suppose that you mean "encrypted with the Elliptic Curve ElGamal scheme"; an elliptic curve is a particular type of group, you do not "encrypt a message with elliptic curves", but with an encryption scheme that works over an elliptic curve.

That being said, the ElGamal encryption scheme is randomized, so the fact that $M_1$ and $M_2$ are not equal does not matter at all: encryptions of $M_1$ and $M_2$ will look random to anyone that does not hold the secret key anyway, even if they are the same.

Finally, to answer your question, no, one cannot tell whether the same public key was used to encrypt both message, as each encryption is provably indistinguishable from a pair of uniformly random group elements, whatever the public key (unless, obviously, the attacker knows one of the corresponding secret keys).

EDIT: let's extend a bit on that, as your comment seems to ask for more details. Let $g$ be a generator of some group $\mathbb{G}$. Let $h_1,h_2$ be two public keys ($h_i = g^{s_i}$ for secret keys $s_i$, $i \in \{1,2\}$). Let $(M_1,M_2)$ be any two messages (id est arbitrary group elements, possibly identical). We consider two random encryptions of $M_1$ and $M_2$, with keys $h_1$ and $h_2$:

$E_1 = (g^{r_1}, h_1^{r_1}M_1)$ with a random exponent $r_1$
$E_2 = (g^{r_2}, h_2^{r_2}M_2)$ with a random exponent $r_2$

Consider an attacker that attempts to check whether the same public key was used for both encryptions. As it can only help him, let us assume that this attacker knows $M_1$ and $M_2$. Therefore, the adversary gets $(g^{r_1}, h_1^{r_1})$ and $(g^{r_2}, h_2^{r_2})$ for uniformly random exponents $r_1,r_2$, and tries to check whether $h_1 = h_2$. Suppose that he can do that with some non-negligible probability. Then I can use this adversary to break the decisional Diffie-Hellman assumption. Indeed, suppose I receive a tuple $(u, v, u', v') \in \mathbb{G}^4$, and I have to tell wether this is a random tuple, or a Diffie-Hellman tuple (id est a tuple of the form $(u,v,u^r,v^r)$ for some $r$).

I can simply proceed as follows: I send the pair $(u,v)$ to the adversary, as well as the pair $(u',v')$, and ask him whether "the same public key is used in both pair". Indeed, observe that $u = g^x$ for some $x$, and $v = h_1^x$ for some $h_1$, so $(u,v)$ can be seen as a pair $(g^x, h_1^x)$ for some random coin $x$ and public key $h_1$. Similarly, $(u',v') = (g^{x'}, h_2^{x'})$ for some exponent $x'$, and some public-key $h_2$. Now, if $(u,v,u',v')$ is a Diffie-Hellman tuple (hence $(u',v') = (u^r, v^r)$ for some $r$), then we necessarily have $h_1 = h_2$ above (and $x' = rx$), while if it is a random pair, then we have $h_1 \neq h_2$ with overwhelming probability.

So, if the adversary tells me that the same public key was used in both pair, it means $(u,v,u',v')$ is a DH tuple, and if not, it means it's a random tuple, so I can break the DDH assumption with the same probability that the adversary finds out whether the same key was used in both pairs.

Put otherwise, this means that assuming the DDH assumption (which is equivalent to the IND-CPA security of ElGamal), it is infeasible to tell whether the same public key was used for two encryptions.


Can you help me understand Bernstein’s Notes on Diagonal constant of Salsa20? Explaining the choice of the Salsa20 constant Bernstein explains:

[...] shifting the entire Salsa20 hash-function input array along the diagonal has exactly the same effect on the output.
The Salsa20 expansion function eliminates this shift structure by limiting the attacker’s control over the hash-function input. In particular, the input diagonal is always 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574, which is different from all its nontrivial shifts. In other words, two distinct arrays with this diagonal are always in distinct orbits under the shift group.

What is the meaning of the terms nontrivial shifts and distinct orbits under the shift group?

The Salsa20 core is defined on a $4\times4$ matrix $x$ of 32-bit words by $\operatorname{Salsa20}(x) = \pi(x) + x$, where $\pi$ is a permutation.

Consider a matrix:

\begin{equation}
  x =
  \begin{pmatrix}
    A_0 & B_0 & C_0 & D_0 \\
    A_1 & B_1 & C_1 & D_1 \\
    A_2 & B_2 & C_2 & D_2 \\
    A_3 & B_3 & C_3 & D_3
  \end{pmatrix}.
\end{equation}

If we transform it into the matrix

\begin{equation}
  S(x) =
  \begin{pmatrix}
    D_3 & D_2 & D_1 & D_0 \\
    C_3 & A_0 & B_0 & C_0 \\
    B_3 & A_1 & B_1 & C_1 \\
    A_3 & A_2 & B_2 & C_2
  \end{pmatrix},
\end{equation}

that is move every cell downward and to the right along the diagonal, then it turns out that $\pi(S(x)) = S(\pi(x))$, for the particular $\pi$ used in Salsa20; consequently, since $S(x + y) = S(x) + S(y)$, the Salsa20 core has the property that $$\operatorname{Salsa20}(S(x)) = \pi(S(x)) + S(x) = S(\pi(x) + x) = S(\operatorname{Salsa20}(x)).$$  This transformation $S$ is called a shift, and it is invertible, so the space of all transformations $S \circ \cdots \circ S$ forms a group called the shift group; there are, of course, only four distinct shifts, since shifting four times is the same as not shifting at all.  The orbit of an element $x$ under the shift group is the set $\{x, S(x), S(S(x)), S(S(S(x)))\}$.

Similarly, consider a 32-bit integer $A \in \mathbb Z/2^{32}\mathbb Z$ of the form $$A = a_0 + 2 a_1 + 4 a_2 + 8 a_3 + \cdots + 2^{31} a_{31}.$$  Define the 32-bit integer $$R(A) = a_{31} + 2 a_0 + 4 a_1 + 8 a_2 + \cdots + 2^{31} a_{30},$$ and for a $4\times4$ matrix $x$ of 32-bit integers define $R(x)$ elementwise; that is,

\begin{equation}
  R(x) =
  \begin{pmatrix}
    R(A_0) & R(B_0) & R(C_0) & R(D_0) \\
    R(A_1) & R(B_1) & R(C_1) & R(D_1) \\
    R(A_2) & R(B_2) & R(C_2) & R(D_2) \\
    R(A_3) & R(B_3) & R(C_3) & R(D_3)
  \end{pmatrix}.
\end{equation}

It turns out that, again, $$\operatorname{Salsa20}(R(x)) = R(\operatorname{Salsa20}(x)).$$  The transformation $R$ is called a rotation, and it too is invertible, so the space of all transformations $R \circ \cdots \circ R$ forms a group called the rotation group; there are, of course, 32 distinct rotations.  Again, the orbit of an element $x$ under the rotation group is the set $\{x, R(x), R(R(x)), \dots\}$.

We can also consider shifts and rotations, like $S(R(R(x))$.  As it happens, this is the same as $R(S(R(x))$ and $R(R(S(x))$, because $S$ only affects the matrix structure while leaving the elements intact, while $R$ only affects the elements and leaves the matrix structure intact—it doesn't matter which order you shift or rotate, so you can always uniquely write a composition of shifts and rotations as $R^\nu \circ S^\mu$ for some $\nu, \mu$, forming the shift/rotation group; as before, the orbit of an element $x$ under this group is the set $\{R^\nu(S^\mu(x))\}_{\nu,\mu}$.

These symmetries spell trouble if we use the Salsa20 core directly with arbitrary matrices—cryptography is normally about destroying structure so an adversary can't recover it, but shifts and rotations pass through the Salsa20 core unscathed.  Fortunately, we don't use the Salsa20 core that way.  When we use it with a key $k$ to generate the $n^{\mathit{th}}$ block $\operatorname{Salsa20}_k(n)$ of pad material for encryption, we encode the 8-word (32-byte) key $k$, the 4-word (16-byte) nonce/counter $n$, and a constant $\sigma$ (4-word/16-byte) into the matrix $x$:

\begin{equation}
  \operatorname{Salsa20}_k(n) = \operatorname{Salsa20}(x), \quad\text{where}\quad
  x =
  \begin{pmatrix}
    \sigma_0 & k_0 & k_1 & k_2 \\
    k_3 & \sigma_1 & n_0 & n_1 \\
    n_2 & n_3 & \sigma_2 & k_4 \\
    k_5 & k_6 & k_7 & \sigma_3
  \end{pmatrix}.
\end{equation}

This form has the property that there is no rotation or shift $R^\nu(S^\mu(x))$ that has the same form $$\begin{pmatrix} \sigma_0 & \cdots \\ \vdots & \sigma_1 \\ & & \sigma_2 \\ & & & \sigma_3 \end{pmatrix},$$ except when $\nu = \mu = 0$, i.e. the trivial shift and rotation that leaves the matrix unchanged.  That is, under the shift/rotation group, the orbit of $x$ in $\operatorname{Salsa20}_k(n)$ is entirely distinct from the orbit of $x'$ in $\operatorname{Salsa20}_{k'}(n')$ when $(k, n) \ne (k', n')$—there is no amount of shifting and rotating you can do to get from $x$ to $x'$.  So no amount of control over the inputs to Salsa20 encryption—not control of the nonce, not control of the message, and not even control of the key!—enables an attacker to exploit the shift and rotational symmetry of the Salsa20 core.

This depends, of course, on the particular string $\sigma$.  Had we chosen, say, $\sigma_0 = \sigma_1 = \sigma_2 = \sigma_3$, then the Salsa20 stream cipher might be vulnerable to attacks exploiting shifts, because $S(\operatorname{diag}(\sigma)) = \sigma$.  Had we chosen, say, $\sigma_0 = 1 + 2^{16}$, $\sigma_1 = 2 + 2^{17}$, $\sigma_2 = 4 + 2^{18}$, and $\sigma_3 = 8 + 2^{19}$, then the Salsa20 stream cipher might be vulnerable to attacks exploiting rotations, because $R^{16}(\sigma_i) = \sigma_i$.


Does EAX require padding to be secure? I have been seeing code using "AES/EAX/NoPadding" but I'm also aware that padding schemes are supported for AES-EAX. I would like to know if choosing NoPadding as a padding scheme has security implications for EAX mode of operation. Thanks!

The EAX mode of operation is defined for 128 bit block ciphers. It consists of a combination of CTR mode for confidentiality and OMAC for authentication and nonce derivation. CTR mode does not require padding, but OMAC does, since it is based on CBC-MAC, when the length of the plain text is not a multiple of 128 bits.

Hence, such specifications might mean one of two things.

It means that standard OMAC padding is implied and doesn't have to be specified twice.
It means that the plain text will always be an integer multiple of 128 bits, meaning that the OMAC padding algorithm would never have to be invoked.

Hence, if the API doesn't require you to explicitly specify the OMAC padding specified in the EAX paper, NoPadding will comply with the security claims in the EAX paper.

That said, in some cases there are additional security requirements for hiding the length of the plain text, by padding each message to a fixed length, but that falls outside of the scope of EAX, as well as most (all) other AEAD modes as well.


What is the technical name for a public key container in DER format? I have a public key in the following (format-neutral; the type is specified by the DER bytes) format:

$ cat pubkey.der | openssl asn1parse -inform der -i
    0:d=0  hl=4 l= 290 cons: SEQUENCE
    4:d=1  hl=2 l=  13 cons:  SEQUENCE
    6:d=2  hl=2 l=   9 prim:   OBJECT            :rsaEncryption
   17:d=2  hl=2 l=   0 prim:   NULL
   19:d=1  hl=4 l= 271 prim:  BIT STRING

$ cat pubkey.der | openssl rsa -inform der -pubin -text
Public-Key: (2048 bit)
Modulus:
    00:ac:f3:c2:c6:60:c2:9b:1e:db:fb:b6:32:67:45:
    09:25:be:b0:d9:66:21:a0:80:ac:52:be:d4:59:1c:
    7f:85:c0:45:ed:4e:85:69:55:80:a9:1e:36:94:93:
    19:ce:30:8b:89:5d:1a:8e:9a:d6:7a:88:6a:1a:68:
    6d:72:57:5e:11:a2:ec:9e:44:b7:64:06:6a:1c:d0:
    81:b2:18:cb:a1:82:7f:ef:ad:ef:1a:61:52:46:54:
    d0:50:1f:73:14:ad:2c:8e:4c:d8:90:74:9a:f5:37:
    e7:54:91:3b:79:0a:2e:af:7e:f3:de:98:1c:3c:fd:
    d6:67:73:63:7b:10:7d:b7:77:04:ab:42:17:33:4d:
    28:79:ed:4c:a1:96:71:94:32:bf:2d:49:d6:bd:b2:
    c5:26:42:ad:3e:f4:bb:8e:e8:70:1d:7f:cc:3b:a6:
    04:6c:be:6f:1a:a2:40:c4:a5:ee:d5:83:87:44:a5:
    90:22:c5:96:14:69:3c:ae:65:76:9c:45:41:4b:5f:
    04:03:27:b6:74:a5:3b:c4:27:d4:83:7c:0a:18:b4:
    5d:36:95:6f:9b:08:f4:14:37:8d:33:be:bd:e0:46:
    11:89:9e:f9:5b:49:f7:9e:c6:2f:86:5e:96:83:5e:
    47:9c:c0:3a:60:91:ea:41:98:7f:3e:85:a5:ab:73:
    b0:59
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEArPPCxmDCmx7b+7YyZ0UJ
Jb6w2WYhoICsUr7UWRx/hcBF7U6FaVWAqR42lJMZzjCLiV0ajprWeohqGmhtclde
EaLsnkS3ZAZqHNCBshjLoYJ/763vGmFSRlTQUB9zFK0sjkzYkHSa9TfnVJE7eQou
r37z3pgcPP3WZ3NjexB9t3cEq0IXM00oee1MoZZxlDK/LUnWvbLFJkKtPvS7juhw
HX/MO6YEbL5vGqJAxKXu1YOHRKWQIsWWFGk8rmV2nEVBS18EAye2dKU7xCfUg3wK
GLRdNpVvmwj0FDeNM7694EYRiZ75W0n3nsYvhl6Wg15HnMA6YJHqQZh/PoWlq3Ow
WQIDAQAB
-----END PUBLIC KEY-----

What is the technical name for this format? I keep wanting to call it PKCS#8, but I think that would be incorrect, since PKCS#8 is a private key format. What do we name the PKCS#8 equivalent DER format for public keys?

As can be seen by RFC 5280 (X.509), this structure is the SubjectPublicKeyInfo. This field is formatted as follows:

SubjectPublicKeyInfo  ::=  SEQUENCE  {
     algorithm            AlgorithmIdentifier,
     subjectPublicKey     BIT STRING  }

The AlgorithmIdentifier is defined as follows:

AlgorithmIdentifier  ::=  SEQUENCE  {
     algorithm               OBJECT IDENTIFIER,
     parameters              ANY DEFINED BY algorithm OPTIONAL  }

The above two types define the format of the outer container in the ASN.1 in question (with the NULL value corresponding to the parameters field). The BIT STRING is an inner object defined by Appendix A.1.1 of PKCS #1 v2.1 as follows:

RSAPublicKey ::= SEQUENCE {
    modulus           INTEGER,  -- n
    publicExponent    INTEGER   -- e
}