OpenSSL cipher suite support / key requirement for ecdhe_ecdsa_with_aes128_cbc_sha256 I hope this is the right place for that kind of question.
So actually I am trying to test the TLS implementation of some industrial device. I have to write my own TLS implementation for this, for which I am using the OpenSSL library and I also do testing via console commands, the version is 1.1.1f.
The device I test only supports the cipher suite tls_ecdhe_ecdsa_with_aes128_cbc_sha256 (0xc023).
As a preparation I want to test an OpenSSL client vs. an OpenSSL server and I am using the follwoing commands to set up both (the certificate has been generated before with OpenSSL as well):
openssl.exe s_server -accept 2 -cipher ECDHE-ECDSA-AES128-SHA256 -key cs_key.pem -cert cs_cert.pem -msg -state -debug -tlsextdebug -bugs

and
openssl.exe s_client -connect localhost:2 -tls1_2 -cipher ECDHE-ECDSA-AES128-SHA256 -msg -state -debug -tlsextdebug -bugs

The server aborts the TLS handshake with an alert message and the console output
11096:error:1417A0C1:SSL routines:tls_post_process_client_hello:no shared cipher:ssl\statem\statem_srvr.c:2284:
shutting down SSL

This also happens when I use my real device as client.
My questions are:

Why does the server say there was no shared cipher when I explicitely set up the server to support only that one cipher suite? I suppose it is supported by the OpenSSL implementation as otherwise the s_server call would fail.
How can I make this work?

Addendum:
If I support all the ECDHE-ECDSA ciphers in the client hello by using
openssl.exe s_client -connect localhost:2 -tls1_2 -cipher ECDHE+ECDSA -msg -state -debug -tlsextdebug

the handshake fails in the same way.
Solution:
In the meantime i stumbled over this and found out this issue is a matter of proper key generation. By applying the proposed solution in the linked thread I was able to get my example working.

Why does the server say there was no shared cipher when I explicitely set up the server to support only that one cipher suite?

The chosen cipher suite requires that an ECC certificate gets used. Likely you have a RSA certificate instead since most instructions on how to create a certificate cover only this. If you have a RSA certificate you cannot use an ECDSA cipher and thus the server has essentially no cipher to choose from - which results in no shared cipher.

How can I make this work?

Create an ECC certificate for the server. See for example Create a self-signed ECC certificate for instructions.


Time complexity of looking up in a rainbow table It is mentioned in the famous paper Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf) by Philippe Oechslin that:

  The total number of calculations we have to make is thus
  $\frac{t(t−1)}{2}$. This is half as much as with the classical
  method. Indeed, we need $t^2$ calculations to search the corresponding
  $t$ tables of size $m × t$.

However, my result doesn't agree with his. Here is my idea:

If we count a single application of a reduction function as 0.5 calculation, we'll have to do $0.5 + 1.5 + ... + t-0.5$ calculations in the worst case when looking up in a rainbow chart, that is, $\frac{t^2}{2}$ calculations, greater than the author's $\frac{t(t-1)}{2}$. In contrast, the original method seems to call for $t(t-\frac{1}{2})$ calculations, fewer than the author's $t^2$.

Also, the author's $\frac{t(t-1)}{2}$ and $t^2$ gives $0$ and $1$ respectively when $t=1$, which seems strange.

So who is wrong?

If we count a single application of a reduction function as 0.5 calculation [...]

That does not seem to be an assumption made in the paper? I would expect the reduction function to take much less time than a hash/cipher, so discounting them completely is a good enough approximation. That gives the value in the paper.

If you count it as 0.5, then it would take $0.5 + 2 + 3.5 +\dots + (t-1+0.5t)$ rather than what you have, since at each step you add 1.5 work for both another hash/cipher and another reduction.

  In contrast, the original method seems to call for $t(t-\frac{1}{2})$ calculations, fewer than the author's $t^2$.

This part I am not sure about. I would think it should be $t(t-1)$, which matches the later text saying that a rainbow table approach takes half the time of the original.


Decryption or attacking DES encrypted file I have a file that has been encrypted using DES and am looking to decrypt and find a secret message encoded. All I have is the file which is full of binary data. There is no key or anything else which makes me wonder how can I be able to do it by Brute Force.

I spent some time reading and understanding DES and I know how it works but would appreciate some advice.

Brute force is feasible as codesinchaos points out. That said there is more to it than that.

First you'll need some way to tell whether or not decryption was successful. For example, you may look for english language text upon decryption. Automating this will be essential as you don't want to manually look at every decryption to decide whether or not you were successful.

Second, you'll have to try different modes. If it was encrypted with ECB, you should be able to recognize that by looking at the ciphertext (see if there are lots of repeated blocks of ciphertext; a block in des is 8 bytes). Otherwise, you'll have to try all the common modes. Still, should be able to be accomplished via brute force.


Is there a standard way to extend the output of a hash? Say I have a hash function, a state-of-the-art hash function that we would all approve of that produces a fixed number of bits (n) as output. (I'll call it HASH.)

Is there are a standard way to produce a different number of bits from this building block? (I'd prefer it if HASH is treated as a black-box component that can't be modified internally.)

If I wanted less than n, I could just use as many bits from the output I want, ignoring the rest. (I think SHA-224 does this internally.) But what if I want more than n?

Or to put it another way, can I call (say) SHA256 sixteen times and produce something that's just as good (other than for speed) as a hypothetical SHA4096 would be?

If you assume the hash function as block box with no known preimage attack, then you can do the following to get a "more secure" hash:

You have a message $m$ and a hash function $h(\cdot)$, and you want to extend the hash length by factor $k$.
Assuming the hash function as block box, you don't change anything if you add a fixed prefix or suffix to the input string.
However, if the prefix or suffix is different, you will get a random different output.
Therefore if you have e.g. $h_0=h(m|0)$ and $h_1=(m|1)$, it should be even harder to find a common preimage $m$ than for a single hash function. But I have no idea how much harder it actually gets. But if you assume a random oracle for the hash function, and find a preimage for $h(m)$  after testing $x$ values in average, the common preimage should be found after testing $x^2$ values.

This leaves us with this formula (the suffix number inside the hash functions should be fixed size bitstrings):
$h'(m):=h(m|1)\,|\,h(m|2)\,|\,...\,|\,h(m|k)$

Finding a preimage or a collision then is not reduced to finding a match for a single input to the hash function but to several.


If p mod 4 = 3, does choosing a=1 in the parameters of EdDSA really achieve best performance? I am implementing Ed448 in my crypto library. I found that if $a=-1$, I can use the formulas describing in this webpage, which saves some multiplications.

However, in the page 6 of RFC 8032, it says

  A non-zero square element $a$ of $GF(p)$.  The usual recommendation
  for best performance is $a = -1$ if $p \bmod 4 = 1$, and $a = 1$ if
  $p \bmod 4 = 3$.

Why does choosing $a=1$ if $p \bmod 4 = 3$ achieve the best performance?

There are probably better ways to do this, but at least this is quite elementary.

Let $p$ be an odd prime, and $\mathbb{F}_p^*=\langle\alpha\rangle$ be the cyclic subgroup of order $p-1$. Let $x\in\mathbb{F}_p^*$ such that $x^2=-1$. Take $t\in\{0,\ldots,p-2\}$ such that $x=\alpha^t$. Then $\alpha^{4t}=x^4=1$, so $4t\equiv 0\bmod p-1$. As $0\leq 4t\leq 4p-8$, there are 4 options:

$4t=0$. Then $t=0$, so $x=1$, a contradiction.
$4t=p-1$. Then $p=4t+1$, so $p\equiv 1\bmod 4$.
$4t=2p-2$. Then $t = (p-1)/2$, so $x^2 = 1$, a contradiction.
$4t = 3p-3$. Then $3p\equiv 3\bmod 4$, so $p\equiv 1\bmod 4$.

In other words, $-1$ is not a square if $p\equiv 3\bmod 4$. This is an explicit assumption in your quote.


Inverting RSA using an oracle Say you are given an efficient deterministic algorithm 'I' that can invert the RSA
function on 1% of the points in $Z^*_{N}$. That is to say that if y $ \in $ $Z^*_{N}$ is a "good" point for 'I', then
$(I(N, e, y))^e$ = y. (You don't know what these "good" points for 'I' are, however.) Show that you can use 'I' to build an algorithm 'A' that inverts the RSA function on any input, and that is fast on average. That is, if x $ \xleftarrow{$} Z^*_{N}$ and y $\xleftarrow{$} x^e$ mod N, then A(N, e, y) returns x. Give a description of your 'A', and explain why it is always correct and fast on average.
As a hint, consider using randomization and exploiting the multiplicative property of the RSA function.

My idea was to come up with an algorithm which picks $y_1$ and $y_2$, which when multiplied together get y and then proceed to invert both those points.

$y_1 \xleftarrow{$} Z^*_{N}-\lbrace{1,y\rbrace} $
$y_2 \xleftarrow{$} y.y^{-1} mod N $
$x_1 \leftarrow I(n, e, y_1) $
$x_2 \leftarrow I(n, e, y_2) $
$x \leftarrow x_1.x_2 $ mod N
Ret y, x

Now, x has to be the inverse of y because
$ x^e \equiv (x_1.x_2)^e \equiv x_1^e.x_2^e \equiv y_1.y_2 \equiv y $
But, the problem is the probability that I can successfully invert $y_1$ or $y_2$ is less than 1% with algorithm I(?). So, this algorithm probably fails in 99 out of 100 cases. Even if I repeat it until I get "good" set of points, it is going to be horribly slow. How do I solve this problem and make the new algorithm fast? And, how do I prove its fast?

This is homework, and so I won't give you the answer outright; I will give hints:

Hint 1: how could you efficiently generate a random pair $x_1, y_1$ with $x_1^e = y_1$, without resorting to the Oracle?

Hint 2: how could you use the above observation to accelerate your algorithm?


Can public key cryptography survive quantum computers? Quantum computation is based on the superposition principle of quantum physics. Bits in a normal computer are either 0 or 1. Quantum physics allows bits to be in a superposition of 0 and 1, in the same way, Schrödinger’s cat can be in a superposition of “alive” and “dead.” [http://nautil.us]

My question is: Can public key cryptography survive quantum computers?

Current commonly used public key cryptography systems are based on the hardness assumption of factorization and/or discrete lograrithm.

Both these problems are solved efficiently using Shor's algorithm using a quantum computer.

Should someone build a quantum computer capable of running the algorithm with thousands of qbits and the ability to apply enough operations on them without decoherence, then it would break RSA and diffie-hellman including elliptic curvre variants.

This breaks all commonly used public key cryptography but does not break all known public key cryptography. There are other asymmetirc algorithms, for example those based on lattice problems which are currently believed to be secure even in the face of quantum computers.


Warding an ECIES setup against MitM: ECDSA? Is it necessary/appropriate to digitally sign an ETM file in an ECIES context? The encryption mode is CTR(using Inferno). The current output is:

[shared public key] [ciphertext] [MAC].

The encrypted files travel through email between users, if it matters.

The users need to make sure the messages they receive come from the expected person, and none of them is willing to trust a CA. Would it make sense to sign the files with ECDSA?

Here is the application's current code(C#) used for encryption, decryption and authentication, using Inferno(without ECDSA):

    internal static void Encrypt(CngKey k, string file, object data)
    {
        var ephemeralBundle = k.GetSharedEphemeralDhmSecret();
        var ephemeralPublic = ephemeralBundle.EphemeralDhmPublicKeyBlob;
        var symmetricKey = ephemeralBundle.SharedSecret;

        using (var fs = new FileStream(file, FileMode.Create, FileAccess.Write))
        {
            fs.Write(ephemeralPublic, 0, ephemeralPublic.Length);
            using (var etm = new EtM_EncryptTransform(symmetricKey))
            using (var cs = new CryptoStream(fs, etm, CryptoStreamMode.Write))
                new BinaryFormatter().Serialize(cs, data);
        }
    }

    internal static object Decrypt(string file, CngKey k)
    {
        object decrypted = null;
        var ephemeralPublic = new byte[104];

        using (var fs = new FileStream(file, FileMode.Open, FileAccess.Read))
        {
            fs.Read(ephemeralPublic, 0, 104);
            var ephemeralSymmetric = k.GetSharedDhmSecret(ephemeralPublic.ToPublicKeyFromBlob());
            if (Authenticate(file, ephemeralSymmetric, 104))
            {
                using (var etm = new EtM_DecryptTransform(ephemeralSymmetric))
                using (var cs = new CryptoStream(fs, etm, CryptoStreamMode.Read))
                    decrypted = new BinaryFormatter().Deserialize(cs);
            }
        }
        return decrypted;
    }

    private static bool Authenticate(string file, byte[] key, int offset)
    {
        using (var fs = new FileStream(file, FileMode.Open, FileAccess.Read))
        using (var etm = new EtM_DecryptTransform(key, authenticateOnly: true))
        {
            fs.Position = offset;
            using (var cs = new CryptoStream(fs, etm, CryptoStreamMode.Read)) cs.CopyTo(Stream.Null);
            if (!etm.IsComplete) throw new Exception("Authentication failed.");
        }
        return true;
    }

Yes, if you want to protect the message you could use sign-then-encrypt or sign-then-encrypt-then sign to provide authenticity and integrity. Without it an attacker may change the bits of the ciphertext, or simply create an encrypted message.

ECDSA would be the logical choice if you're already using ECIES. It may still be a good idea to use separate keys for signing and encrypting though (if just because you need the keys on different occasions).

You need to trust the public key of the other person before signing or encryption makes any sense though. It's OK not to trust a CA, but in that case you need a different way of performing key management within your PKI.

You could use separate channels to confirm key fingerprints, you could use a web-of-trust, share keys by sneakernet (memory sticks) whatever. But if eavesdropping is possible then 9 times out of 10 so are MitM, so you should make sure that an attacker cannot substitute the public key with their own public key.


How does Hash with random cryptography work? I am new in this world of cryptography and while reading some articles I got stuck into something that I did not understand correctly: the use of hash based on random cryptography.

On my knowledge, when I am using any program which needs authentication the program uses a Hash to save the password into the database and then when the user try to access the program, it get the password that the user insert into some textbox, use the same cryptography as used to save to hash the password and compare the insert result with the result saved in database.

How is this possible to do so if the cryptography is random?

Like I said in the comment I think You mean hashing password with random salt.
The salt is a random string. It's good for it to be more then 128 characters.

Usually adversarys use rainbow tables for cracking hashes. Rainbow table is pretty much a list of all possible strings and their hases. Every day powerfull computers add more strings to those tables. At the moment every password that's 8 and less characters can be cracked in matter of seconds.

Let's say Alice wants to log in into website of "Bob Bank". Her browser takes her six letter password from textbox, hashes it and sends it to the server. Evil Edvard intercepts those hases and in seconds finds the password. Doesn't sound so good.

With salt situation looks better. Bank has assigned a 128 character long string when Alice was making an account. Banks server sends this string to the browser. Evil Edvard can see it. Alices browser adds this string to the password and then hashes it. But now the hash is not of 6 character password, but of 134. Edvards rainbow tables are useless. He has to make new ones. This process can take months.

If another user will also use identical password he's salt still will be different, and hash acquired by Edvard will be different. He has to compute rainbow tables


What is the best way of deterministically choosing N of M, given 32 bytes of sha256? I have a list of M=10,000..100,000 items and 32 bytes of sha256 H.
I want to choose N=10..100 items (without order).
Is there an efficient way to do this?
Or should I use something like (sha256hmac(n, H) & 0xFFFFFFFFFFFFFFFF) % N and skip duplicates.  (Where n is 0..N-1.)

Is there an efficient way to do this?

32 bytes of "good randomness" provided by hashing some secret value gives much less entropy than required to directly compute a sample of 100 items from a list of 100000. If this is required for any cryptographic purpose, you must use a good CSPRNG to convert your starting entropy into as much randomness as you need.
If by efficient you mean "a one-liner", then probably not

Or should I use something like (sha256hmac(n, H) & 0xFFFFFFFFFFFFFFFF) % N and skip duplicates. (Where n is 0..N-1.)

DO NOT attempt to roll your own CSPRNG to generate what you need
What you are describing (repeated application of an HMAC to a changing value) is approximately an HMAC_DRBG described by NIST. If you want to use something along those lines to generate your bitstream, use that instead as it is far more secure than what you have described.
Furthermore, once you have a strong source of random bytes (e.g. the NIST DRBG), it is NOT enough to simply generate some bits, say $k$ such that $2^k$ is greater than $N = 100000$, take this mod $N$ and be done with it. When doing this, as $N$ will never perfectly divide $2^k$, you are inroducing bias into the random numbers generated; the smaller $2^k$ is in comparison to $N$, the greater the bias. Where $k$ is 64, as in the example you proposed, the bias is approximately $2^{-48}$. This may not seem like a lot, but if we consider the negligible function as $2^{-b}$, where $b$ is the "bits of security" of some cryptographic function, as we often do, then your RNG has only 48 "bits of security". Conseridering we are aiming for closer to 256, I would go as far as to suggest using a full 32 byte word of data from the CSPRNG to generate each of your indices.
This is quite a computationally intensive process, however, and it may be a better idea to, instead of taking a modulus in this manner, just generate the minimal number of bytes required to get a single index between 0 and $N$ and discard those bytes if they are at or above the highest multiple of $N$ smaller than the possible number represented by your bytes. For example, in 3 bytes with a max. possible value of 16777216: if the value is below 16700000, then take that mod $N$ and use the result, otherwise discard it and generate 3 fresh bytes from the CSPRNG stream. This could take theoretically infinite time to complete, but less on average than the previous method.


How to determine the multiplicative inverse modulo 64 (or other power of two)? I am trying to determine the multiplicative inverse of $47$ modulo $64$. So I have looked for an algorithm or scheme in order to perform this.

I found this wiki explaining how to find a multiplicative inverse. I tried to perform all the calculations, but the result was incorrect. I got $5$ as a multiplicative inverse, but this cannot be true: $47\times5\not\equiv1\pmod{64}$. Who can help me?

A boring method is to carefully apply the (partially) extended Euclidean algorithm.

But in the question, the modulus is a power of two (specifically $2^6$), and we can use that
$$a\,x\equiv1\pmod{2^k}\implies a\,x\,(2-a\,x)\equiv1\pmod{2^{2k}}$$
from which it follows this fact:

  if the modular inverse of $a$ modulo $2^k$ is (the lower $k$ bits of) $x$, then
  the modular inverse of $a$ modulo $2^{2k}$ is (the lower $2k$ bits of) $x\,(2-a\,x)$
  (where negative integers are in 2's-complement convention, dominant in modern CPUs).

This not-so-much-known fact allows computation of multiplicative inverse modulo $2^k$. We start from an inverse $x$ of $a$ over few bits (that can be $x=a$, perhaps $\bmod 7$, which is the inverse for any odd $a$ over three bits), and iterate $x\gets x\,(2-a\,x)$, possibly truncated to the number of known-correct result bits. That number of bits doubles at each iteration, thus about $\log_2(k)$ steps are enough, and it is only used product, subtraction, and bit truncation on values no wider than $k$ bits. That is blindingly fast compared to the Euclidean algorithm's $O(k)$ steps; and eases getting data-independent execution time, which comes handy in some cryptographic computations (e.g. the preliminary computation of $m'$ in Montgomery multiplication, algorithm 14.36 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography).

I learned the technique from Colin Plumb's Computing multiplicative inverses (post on sci.crypt with Message-ID: <1994Apr6.093116.27805@mnemosyne.cs.du.edu>, 1994). His statement applies to inverse modulo a prime power, and points the relation to the Newton's iteration for finding $x = 1/a$ in $\Bbb R$.

A modern exposition, with benchmarks, is in Jean-Guillaume Dumas: On Newton-Raphson iteration for multiplicative inverses modulo prime powers.

A bibliography, and other techniques faster than the Euclidean algorithm, are in Çetin Kaya Koç: A New Algorithm for Inversion mod $p^k$.

Here, to perform the desired computation quickly, we use $k=3$, $a=47$, and compute $a\bmod2^k=47\bmod8=7$, which multiplicative inverse modulo $8$ is also $x=7$. Now we compute
$$\begin{align}
(x\,(2-a\,x))\bmod2^{2k}&=(7\,(2-47\times7))\bmod 64\\
&=15\end{align}$$

Hence the desired modular inverse of $47$ modulo $64$ is $15$.


obscuring timing attacks in vulnerable libraries Let's say you're using a library that you know is vulnerable to timing attacks. Short of switching libraries all together it seems to me that putting a sleep in the code for a random number of microseconds (or seconds or whatever) would be sufficient to obscure the time it took?

Like why do RSA blinding when you can just sleep for a random number of seconds before or after the RSA decrypting code is ran?

Let's talk with an example, RSA modular exponentiation where the timing of square $T_s \approx x$ and square and multiply is $T_{sm} \approx 2x$. Assume that we have $n$ operation that can be square or square and multiply.

Here we assume that the attacker knows everything about the random sleep;

Let the random values named $y_i; \; 1 \leq i \leq n$. If the $y_i < x$, then the timing attack will work. So, first rule;  $ \text{upper bound of  } y_i > x$.
Let $ 0 \leq y_i \leq 2x$. Clearly, any timing value greater then $3x$ is a square and multiply. If the attacker, capture the timings for the same key more than once, due to the randomization, it will reveal more square and multiply.
Let $ 0 \leq y_i \leq  (t \gg x)$. Here the randomization much bigger than $x$. It does not much differ from the previous, same idea. Only the attacker will need to capture more timings.

The result, direct randomization doesn't help.

If needed, one can talk about the required timing captures with probability.

What about an interesting one; that is adding a random wait according to average timings.

Let $ x \leq R_s < 2x $ be random delay for square and $ 0 \leq R_{sm} < x $ be random delay for square and multiply. So the randomized timings are $ 2x \leq R_s + T_s \leq 3x$ and  $2x \leq R_{sm} + T_{sm} \leq 3x$

This method prevents the attacker from distinguishing the timings.

Update: Actually, The last method may fail,too, since the random delay won't use any cpu at all ( There is an issue about C++ delay it is not supporting microseconds, POSIX does.).


Creating a PKCS#12 file where public key doesn't match the private key For testing purpose, I want to create a PKCS#12 file in which the private key doesn't match the certificate. Is there any tool which will help me do this?

If I use openssl pkcs12 -export command line to create the p12 file using a cert and a private key which are mismatched, then openssl gives me an error

No certificate matches private key

Is there an alternate tool/way to do this?

You could try portecle. Import your keystore.p12 store, using the correct password of course or it will (silently) fail. Delete the certificate entry, and import a new "trusted" certificate entry.

Now it could be that some PKCS#12 defined attributes are different (e.g. friendlyName, which is visible as alias in portecle. Normally the key and certificate are linked through the modulus value however, so this should not make a difference for anybody trying to use the private key and certificate. It's probably best to copy the alias of the certificate just to be sure.

Portecle is written to use the Java KeyStore class, which supports PKCS#12 out of the box. The Java keytool utility uses the same class, but it seems to automatically delete certificates and keys together so it is not much use here.


Perfect secrecy over Stirling numbers For all $c_0\leftarrow m_0 \oplus k$ there exists a $k'$ such that $c_1  \leftarrow m_1 \oplus k'$, where $m_0 \neq m_1$ and $c_0 = c_1$.

Assuming a truly random $k$, the first assignment is a one-time pad. If we were to repeat the process over all $m \in M$, we would create a Stirling set of the first kind.

To use better notation, each key $k_n$ can be given by $G(k_{n-1},m_{n-1})$ where $k_0$ is a perfectly random bitstream.

The scheme would be a bit impractical, but let's not focus on that initially. Since all $c \in C$ are exactly the same, and assuming that no two $m$s are the same, is it safe to claim that the above scheme is perfectly secure?

Subquestion: Is $k'$ still perfectly random?

To clarify: This construction is completely useless. I thought it would be fun to come up with a OTP variation which allows key reuse, not necessarily one that would be of any practical value.

What, exactly, are your trying to accomplish with this construction?

Yes, you're correct in that, given a sequence of messages $m_0, m_1, m_2, \dotsc$ and a fixed ciphertext $c$ (assumed to be all of the same length), we can easily calculate a sequence of keys $k_i = c \oplus m_i$ such that $k_i \oplus m_i = c$.

However, I don't see any way to get a useful cryptosystem out of this.  If you don't transmit the keys $k_i$ to the recipient, there's no way for them to recover the messages $m_i$ just from $c$; indeed, that would be clearly absurd, since $c$ may be chosen to be completely random and independent of all $m_i$.  Conversely, if you do transmit the keys $k_i$, then the system is easily broken by an adversary who intercepts the "keys" — it's basically just a many-time pad.

Also note that you can't transmit the keys in advance, since, once $c$ is fixed, each key $k_i$ will depend on the corresponding message $m_i$.  So, unlike a traditional one-time pad, your scheme isn't even good for the "have secure channel now, need to communicate securely later" scenario.


Quality test for an hardware source of randomness Say that I developed an hardware source of randomness, which I would like to use to seed a cryptographically secure random number generator.

How would I go about testing it? Are there standardized tests that one can use to check wether or not his source of entropy is reliable enough to seed cryptographic random number generation?

For example, the guys at onerng.info claim to generate the entropy any user needs to protect his privacy and blablabla. How do they substantiate their claim? How can random number generators be verified?

NIST has a statistical test suite for testing (pseudo) random number generators.  There are a number of other suites as well, such as Diehard, Dieharder, and TestU01.

But all these tests can do is disprove the claim that your generator is random; they cannot prove it.  So you really need, in addition, an independent argument for why your generator's output really is random.  A true random number generators generally comprises of:

A entropy source that outputs digitized samples of a random process (but whose output may be neither uniform nor independent).
A nondeterministic random bit generator (NRBG) that uses the entropy source's output to produce uniform and independent random bits.

So correspondingly, you need:

An argument that your entropy source is random and that justifies a lower bound on its entropy rate (how random it is, per unit of time);
An argument that your NRBG, given the noise source's output, produces full entropy outputs (uniform and independent random bits).

And there's no "bright line" test to be had here.  You don't prove that your outputs "really are random"—you prove that the processes you're using to produce your outputs are sound, that your implementation of them reliable, that your hardware resists monitoring and interference, etc.  You also provide health check mechanisms and fallbacks to detect and guard against failures.

You may be interested in the NIST SP 800-90 series, which details standards for random number generators:

SP 800-90Ar1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators (1st revision)
SP 800-90B: Recommendation for the Entropy Sources Used for Random Bit Generation (2nd draft)
SP 800-90C: Recommendation for Random Bit Generator (RBG) Constructions (2n draft)

In particular 90B deals with the entropy sources, and parts of 90C deal with nondeterministic random bit generators (NRBGs)—algorithms designed to take the output of a noise source and produce truly random outputs.


Is it possible to combine two operations rotation and xor? I can see many xor and rotation operations in cryptography. I just want to make some algorithms fast. So, I'm looking for a way to combine between xor rotation operations. I don't know if it is possible or not.

R3(A) xor R4(B) = A * B (R3,R4 means left rotate shift by 3 bits and 4 bits)

I'm looking for *. Is there any idea? If you have please, let me know. And if it is impossible, please show me why. Thanks.

The question asks for simple variations of the $*$ operations defined by formulas similar to $A*B=(A\lll3)\oplus(B\lll4)$ or $A*B=(A\lll3)\oplus(B\ggg4)$, where uppercase letters are words of $n=32$ bits, lowercase letters are integers, $\lll$ designates left rotation, $\ggg$ designates right rotation, $\oplus$ designates eXclusive-OR.

There are a number of properties we can use:
$$\begin{align*}
\forall X, \forall Y,           &&X\oplus Y          &=Y\oplus X\\
\forall X, \forall Y, \forall Z,&&(X\oplus Y)\oplus Z&=X\oplus(Y\oplus Z)\\
\forall X, \forall Y, \forall u,&&(X\oplus Y)\lll u  &= (X\lll u)\oplus(Y\lll u)\\
\forall X, \forall u, \forall v,&&(X\lll u)\lll v    &= X\lll((u+v)\bmod n)\\
\forall X, \forall u,           &&X\ggg u            &= X\lll((-u)\bmod n)
\end{align*}$$
where $a\bmod n$ is defined to be the $r$ such that $0\le r<n$ and $n$ divides $a-r$.

It follows that
$$\begin{align*}
(A\lll3)\oplus(B\lll4)&=(A\oplus (B\lll1))\lll3\\
                      &=((B\lll1)\oplus A)\lll3\\
                      &=((A\ggg1)\oplus B)\lll4
\end{align*}$$
which can be considered a simplification (in particular, absent a smart compiler, some of these alternate forms will likely be faster on 8-bit CPUs, and 32-bit CPUs lacking a barrel shifter)

Similarly we can write
$$\begin{align*}
(A\lll3)\oplus(B\ggg4)&=((B\ggg7)\oplus A)\lll3\\
                      &=(A\oplus (B\ggg7))\lll3\\
                      &=((A\lll7)\oplus B)\ggg4\\
                      &=(((A\lll8)\ggg1)\oplus B)\ggg4
\end{align*}$$
with the last form geared for 8-bit CPUs, where rotation by multiples of 8 is relatively efficient.

There's no way to simplify $((A\ggg3)\boxplus(B\lll4))\lll4$, or $((A\oplus B)\boxplus(C\oplus D))\oplus E$, where $\boxplus$ is addition modulo $2^n$. Problem is, we have no simple exact properties of $\boxplus$ with respect to $\lll$, $\ggg$, and $\oplus$.


Padding schemes reversal and space efficiency My crypto course proposes the following padding schemes:

$\operatorname{pad}(m) = m \mathbin\| 0^i$
$\operatorname{pad}(m) = m \mathbin\| 10^i$
$\operatorname{pad}(m) = m \mathbin\| 0^i \mathbin\| E(\left|m\right|)_l$
$\operatorname{pad}(m) = E(\left|m\right|)_l \mathbin\| m \mathbin\| 0^i$

where $E(\left|m\right|)_l$ is the $l$-bit encoding of the length of $m$ and $l$ is the size of the block in the scheme. The question is:

How can one reverse each padding?
Which padding is more space efficient?

I'm at risk of overthinking these questions. Thus, I ask for your experience. To me, the first the more space efficient but not always applicable. It can only be reverted under certain assumptions. But these assumptions hold for 3 and 4 also, if I'm not mistaken. For 2, I don't see very well the advantage. It may help sometimes but others (say 1 has to be written in the next block) it may force to introduce another block. So, overcomplicating matters one could do an average analysis of cases.

What are, in your opinion, the correct answers to these questions?

The more space efficient but cannot always be reverted, for instance if one inputs $m = 1$.
The second space efficient but can always be reverted, this appears in Wikipedia entry as bit padding.
and 4. They consume the same space (which is greater than 1. and 2.) but also, they're always reversable.


Safely sorting secret data Suppose you have a secret list of n distinct integers. How would you sort this list in a way that is not vulnerable to timing attacks? I tried looking up "constant time sorting" and other related queries but that expectedly lead nowhere.

Yes, you can; you can use Batcher's Merge Exchange algorithm, paired with a constant time/access compare-and-swap routine (which reads two elements from locations A and B, and writes the larger element into location A and the smaller element into location B).
This takes $O(n (\log n)^2)$ time, which makes it not quite as fast as other sort algorithms; however if you want constant time/memory accesses, that's about the best we have.
The code on Wikipedia assumes that $n$ is a power of two; it is not hard to extend it to arbitrary $n$...


Inconsistency with PKCS#11 v2.40 CKM_AES_KEY_WRAP_PAD There appears to be some inconsistencies between the PKCS#11 v2.40 Current  Mechanism Specification and the specification for AES Key Wrap Pad as defined in SP800-38F.

First, according to PKCS#11:

  The mechanisms will accept an optional mechanism parameter as the Initialization vector which, if
  present, must be a fixed size array of 8 bytes, and, if NULL, will use the default initial value defined in
  Section 2.2.3.1 of [AES KEYWRAP].

  The type of this parameter is CK_BYTE_PTR and the pointer points to the array of 8 bytes to be used as
  the initial value. The length shall be either 0 and the pointer NULL, or 8, and the pointer non-NULL.

However, according to SP800-38F, the ICV2 value for AES-Key Wrap PAD must be four bytes in order to correctly pad the input to the cipher routine (section 6.3 algorithm 5).

Secondly, PKCS#11 specifies that CKM_AES_KEY_WRAP_PAD is used for Encryption/Decryption only, not for Wrapping/Unwrapping operations (Table 65, in section 2.14 in the PKCS#11 current mechanism specification).  This seems inconsistent with the goals of the AES KEY Wrap Pad algorithm.

So my questions are:

Is this a known inconsistency and has Cryptoki released any updates to how the CKM_AES_KEY_WRAP_PAD algorithm can be used?  I cannot find anything on Google but maybe I missed something.
In my PKCS#11 implementation, can my solution be to inform the user (through documentation) that the IV for CKM_AES_KEY_WRAP_PAD will be truncated to 4-bytes?
I know this appears to be out of spec, but can I in my PKCS#11 implementation allow the user to use CKM_AES_KEY_WRAP_PAD for Wrapping/Unwrapping as well as Encryption/Decryption.

The PKCS#11 technical committee is currently working on standard version 3.0. You can find the latest working draft here: https://www.oasis-open.org/committees/download.php/64968/pkcs11-curr-v3.0-wd09.docx

In fact, reworked section "AES Key Wrap" (now 2.16) solves your problems:

It allows all mechanisms to be used with Encrypt&Decrypt and Wrap&Unwrap.
It clarifies that CKM_AES_KEY_WRAP and CKM_AES_KEY_WRAP_PAD actually refer to NIST SP800-38F section 6.2 ("KW"), which in fact require an 8 byte IV.
It introduces new CKM_AES_KEY_WRAP_KWP, which is algorithm KWP of NIST SP800-38F section 6.3 you are looking for.

Header files for the working draft can be found here: https://github.com/oasis-tcs/pkcs11/tree/master/working/3-00-wd-01


Strength of key derived from a hash function considering the birthday attack When a hash function is used to derive a key from a shared secret (either by simply hashing the shared secret or using a more robust construct like HKDF) what's the strength of the derived material?
If, for example, the shared secret is 256-bit, is the security of the derived result also 256-bit or is it $2^{n/2}$ (that is 128-bit in this case) since as per the birthday problem, it "only" takes $2^{n/2}$ guesses to generate a collision. Thus in this case a collision would mean getting the same output and so the same material of the KDF.

You—the adversary—have a way to test whether a candidate key $k_i$ might be the true secret key $k^*$.  Since $k^*$ is uniformly distributed among all 256-bit keys, each candidate $k_i$ has probability $\Pr[k_i = k^*] = 1/2^{256}$ of being correct.  No matter what order you try things in, the expected number of guesses is $$\sum_{i=1}^{2^{256}} i \cdot \Pr[k_i = k^*] = \sum_{i=1}^{2^{256}} i \cdot \frac{1}{2^{256}} = \frac{2^{256} (2^{256} - 1)/2}{2^{256}} = 2^{255} - {\textstyle\frac12}.$$  (You may, of course, encounter false positives, which you will have to deal with; they do not affect this expected number of guesses before finding the true key, only the probability of falsely thinking you have found the true key when you haven't.)

Why don't collisions and the birthday paradox appear in this analysis?
Collisions are relevant when you're looking for any $k_i \ne k_j$ such that $H(k_i) = H(k_j)$, but you don't care what either $k_i$ or $k_j$ are.  As you try $k_1, k_2, \dots$, searching for a collision, each new key could potentially collide with every previous key, so the probability of a collision among some pair of $n$ keys grows quadratically—specifically, for $n \ll 2^{128}$, it is $$1 - \biggl(1 - \frac{1}{2^{256}}\biggr) \biggl(1 - \frac{2}{2^{256}}\biggr) \cdots \biggl(1 - \frac{n}{2^{256}}\biggr) \approx \frac{n^2}{2^{256}}.$$  (proof; more on birthday paradox)

Note: There may be a batch advantage in the multi-user setting.  If the way you can test a candidate key $k_i$ is by testing whether $H(k_i) = h$ where you know $h = H(k^*)$, and you actually have many target keys $k^*_j$ and hashes $h_j = H(k^*_j)$, you can save cost in a batch attack like computing Oeschlin's rainbow tables in parallel, for a total expected cost of about $2^{256}\!/t$ trials to find the first of $t$ targets, and in the total expected time of as little as about $2^{256}\!/t^3$ sequential evaluations of $H$ if you parallelize it at least about $t^2$ ways.

However, if each user had used a different function, that is if you have $h_j = H_{s_j}(k^*_j)$ with a unique salt $s_i$ per user, then the multi-target advantage vanishes, and you're back to the expected cost of about $2^{256}$.


How does the GCM encryption limit affect TLS connections? According to the Wikipedia article on Galois/Counter Mode, GCM is limited to encrypting $2^{39} − 256$ bits of plain text (64 GiB) for any given key and initialization vector. In light of this limit, what considerations should be made for a TLS 1.2 connection with an AES GCM cipher suite?

Should the session/connection be renegotiated or manually closed when the limit is reached? Or does the TLS protocol specify that the connection will be automatically closed or generate a new IV when the limit is reached? Or is it implementation dependent?
Does the limit apply separately to each peer (server and client) or does the limit apply to the total of all data encrypted on both sides of the connection?
Will resumed sessions use a new key/IV combination thus resetting the count against the limit?
Do AES key size or other cipher suite options affect the encryption limit or answers to the above questions (as long as it's AES GCM)?

Note: Using TLS 1.2 with AES-256 GCM encryption and ECDHE-ECDSA key exchange/agreement via SslStream for .NET 4.6.2.

Actually, that limit does not affect TLS.

TLS encrypts each record separately, using a fresh IV for each.  A record is limited to 16kbytes in length, and hence you'll never hit the 64Gbyte limit in TLS.  In other words, you'll use a fresh IV after every 16kbytes (and possibly earlier).


Understanding Fourier Coefficient In Bogdanov's and others, PRESENT: An Ultra-Lightweight Block Cipher, they mention that the S-box in PRESENT fulfill four primary conditions. They denote the Fourier coefficient as $$S_b^W (a) = \sum_{x\in \mathbb{F}_2^4} (-1) ^{\langle b, S(x)\rangle+\langle a,x \rangle}.$$

I am trying to understand what conditions (3) and (4) are trying to say. They are:

(3) For all non-zero $a\in \mathbb{F}_2^4$ and all non-zero $b\in \mathbb{F}_2^4$ it holds that $|S_b^W|\leq 8$.

(4) For all $a \in \mathbb{F}_2^4$ and all non-zero $b \in \mathbb{F}_2^4$ such that $wt(a) = wt(b) = 1$ it holds that $S_b^W (a) = \pm 4$

How does one raise a power to Bogdanov's notation (or compute such sum)?

You have a typo, $x$ is also in $\mathbb{F}_2^4,$ since the Present Sbox is $4\times 4$ bits.

The quantities $S(x),a,b,x$ all lie in $\mathbb{F}_2^4,$ and the inner products such as $\langle b,S(x)\rangle$ etc lie in $\mathbb{F}_2.$ We now treat the inner product values as in $\mathbb{N},$ so we can calculate
$(-1)^{\langle b,S(x)\rangle+\langle a,x\rangle}.$

Basically if the two inner products in the exponent match we have a $+1$ in the overall sum, otherwise a $-1$. Thus the sum computes the imbalance function defined as $$2^4-2d_H(\langle b,S(x)\rangle,\langle a,x\rangle)$$
between the two quantities in the exponent as $x$ ranges over $\mathbb{F}_2^4.$

Here $d_H$ is the hamming distance along the truth tables.


Rationale of "r" AES key use in OTR version 3 AKE protocol? I just tried to review & understand AKE (Authenticated Key Exchange) protocol as defined in OTR secure messaging protocol version 3 here  , and aiming to achieve Perfect Forward Secrecy

I am a little bit confused with the described handling of the "r" aes key in the presented DHE (Ephemeral Diffie-Hellman) protocol:

DHE is used in asymmetric way : g^x is sent encrypted with r aes key by Bob while g^y is sent in clear form by Alice
then r (step 7) is further sent in clear form by Bob so that g^x is recovered by Alice

What may be the rationale for such r aes  key use which seems very strange to me ?

is g^x to be temporarily hidden to Alice until Bob check that g^y has legal value ?
I surely missed the real reason

The usage of the r key forces both parties to "fix" the public DH keys.

So Alice doesn't know Bob's public DH key before she's generating her own one.

And Bob can not make the choice of the public key dependant on Alice's choice and vice versa.

This forces both parties to be honest and to generate both public keys at random as there is no opportunity to force a specific derived key that may have some weak properties.


Why invent new hash functions for zero-knowledge proofs? Recently, new hash functions were invented. Their primary purpose is serving the needs of zero-knowledge proof systems. I'm talking about Poseidon-256, Starkad-256, etc. See the paper.

What is the main advantage of those hash functions against existing ones like Blake3 or SHA3? How are those functions different?

Let us see an example of how cryptographic hash functions are used in Zero-Knowledge Proof Systems. Following code written in Zokrates DSL Toolbox is an example of computing a Hash using Zero-Knowledge Proof systems. The programming instructions are compiled first. Then we will proceed to the setup of the arithmetic circuit through the setup. Then we export the verifier and will compute the proof.

import "hashes/sha256/512bitPacked" as sha256packed

def main(private field a, private field b, private field c, private field d) -> (field[2]):
    h = sha256packed([a, b, c, d])
    return h

Let us also analyse another code example to construct a Pedersen Hash in the construction of a Zero-Knowledge Proof using Zokrates Toolbox.

import "hashes/pedersen/6bit" as pedersen

def main() -> (field):

    field[6] e = [1, 1, 0, 0, 0, 0]
    field[2] d = pedersen(e)

    5483803361072598088157572477433311028290255512997784196805059543720485966024 == d[0]
    8712718144085345152615259409576985937188455136179509057889474614313734076278 == d[1]

    return 1

As we can see in these two examples, proving the knowledge of a preimage under a cryptographic hash function expressed as a circuit over a large prime field becomes one of the most computationally expensive parts in the arithmetic circuit construction in a zero-knowledge proof system. Hence all the pursuits for inventing SNARK and STARK friendly cryptographic hash functions are greeted with much of enthusiasms!

The paper mentioned in this question claims a reduction in the number of constraints per message bit than Pedersen Hash which would potentially improve the performance in the construction of polynomial commitments for ZKSNARK. Likewise, the proposed binary hash function STARKAD could be beneficial in the construction of ZKSTARK based systems in the near future.

  Our hash-function Poseidon uses up to 8x fewer constraints per message bit than Pedersen Hash, whereas our binary hash-function Starkad wins by a substantial margin over the other recent designs


Secret sharing scheme with possibility to change the secret Here's a scenario I want to handle with a secret sharing scheme:

Alice wants to share the secret $S$ with Bob, Charlie and Dave. Alice generates private shares
based on $S$ for Bob, Charlie and Dave, and communicates them to their intended recipients via a secure
channel.
Alice generates a parameter $P$ based on $S$ and publishes it.
Each of Bob, Charlie and Dave can reconstruct the secret using $P$ and their personal share. Eve can't reconstruct it, even if she knows $P$.
Alice needs to change the secret. Alice recomputes only a new $P$. All private shares of the participants stay the same.
Each of Bob, Charlie and Dave can reconstruct the new secret using the new public parameter $P$.
Alice wants to add a new participant Fred and remove participant Bob from the group. Alice recomputes a new $P$ and a new private share for Fred.
Each of Charlie, Dave and Fred can reconstruct the secret using their shares and the new $P$. Bob can't reconstruct the secret using the new $P$.

Is there some secret sharing scheme that can handle such a scenario? I found myself some secret sharing schemes like Shamir's secret sharing or secret sharing using the Chinese remainder theorem, but those do no satisfy all my requirements.

An obvious solution that handles steps 1–5 (changing the secret) would be for Alice to generate a random encryption key $K$ (of, say, 128 bits), encrypt $S$ with $K$ to generate $P$, and then share $K$ with the other participants using a conventional secret sharing scheme such as Shamir's.

Indeed, if all the shareholders (other than Alice) are always needed to reconstruct the secret, you don't even need to use Shamir's scheme: trivial XOR secret sharing (where Alice gives all but one of the shareholders a random bitstring, and gives the last one the XOR of all the other shares plus the secret) will do the job just as well.

Indeed, with XOR secret sharing, steps 6 and 7 (adding and removing participants) can also be achieved: Alice simply sends random bitstrings to the new participants, computes a new key $K$ by XORing together the shares of all the active participants, and encrypts the secret $S$ with the new $K$ to obtain the new $P$.

In fact, if the key $K$ is (at least) as long as the secret $S$, you don't even really need a separate encryption step: as long as $K$ is random, you can simply XOR $K$ with $S$ to obtain $P$, making this an instance of one-time pad encryption.

This also works with Shamir's scheme, as long the reconstruction threshold equals the number of shareholders; Alice can just send random shares to all the shareholders, reconstruct a (random) key $K$ by applying Shamir's reconstruction algorithm to the shares of the active participants, and use that key to encrypt the secret.

However, note that all these protocols suffer from some fundamentally unavoidable flaws:

if the shareholders can remember old $P$ values, they will be able to reconstruct old secrets even after Alice has changed them, and
if removed shareholders can remember their old shares (and the old $P$), they can still reconstruct the secret (assuming the other old shareholders cooperate) as it was before they were removed.  However, if the secret $S$ is changed whenever participants are removed, the remove participants won't be able to contribute anything useful to reconstructing the new secret.

Edit: Based on the comment below, it seems I misunderstood the question: you want each of Bob, Charlie and Dave alone to be able to reconstruct the secret using $P$.

A simple way to achieve this would be for Alice to distribute different random keys $K_i$ to each of the other participants $i$, encrypt her own key $K$ with each of $K_i$, and combine the ciphertexts into $P$.

Of course, the down side to this method is that the length of $P$ would be proportional to the number of participants, which could be a problem if that number is large.  However, I'm not sure if it's possible to do any better, and I suspect it may not be.


If A and B are co-primes, does Ax mod B (where x, any positive int) gives {0,1,2,....,B-1}? If $A$ and $B$ are co-primes (i.e. $\gcd(A,B)=1$), does $A\cdot x \bmod B$ (where $x\in \mathbb N$) give as result an element of $\{0,1,2,....,B-1\}$ ?

Claim: If $A$ and $B$ are coprime, the map
$$\begin{align*}
\{0,\dots,B-1\}\ &\to\ \{0,\dots,B-1\}
,\\
x \ &\mapsto\  A\cdot x\bmod B
\end{align*}$$
is a well-defined bijection.

It is clear directly from the definition of $\bmod$ that $A\cdot x\bmod B$ is indeed between $0$ and $B-1$.
Surjectivity follows, e.g., from Bézout's lemma.
Any surjection between finite sets of the same cardinality is automatically bijective.

In particular, this implies that the map
$$\begin{align*}
\mathbb Z\ &\to\ \{0,\dots,B-1\}
,\\
x \ &\mapsto\  A\cdot x\bmod B
\end{align*}$$
is also surjective.


Initialize a PRNG with a password Let's assume that we have a secure PRNG. Is it "safe" to initialize it with password, or seed based on a password like SHA256(password)?

If yes, is it "safe" to generate an RSA or DSA key from it?

The idea behind this is to initialize a PRNG with a password, then use it to generate RSA or DSA keys. So, the scheme will always generate the same prime numbers when generating private keys, meaning that you would not need to store your private key anywhere but would instead regenerate it each time it was needed. Only the password would need to be stored (or remembered).

UPDATE: Obviously this scheme would inherit the general risks of bad password choices, but how about a password requiring a reasonable range of characters. Alternatively, one could use 2 passwords, where the system uses the 2nd password as the salt of an PBKDF2 calculation.

No, it's not safe to seed a PRNG with the hash of a password, then generate a key from that PRNG. That is especially bad with DSA and shared parameters $(p,q,g)$, and only slightly less unsafe for RSA, or DSA with per-key parameters $(p,q,g)$. Two essentials things are missing: some slow step, and salt.
If the proposed procedure was applied, all there is to do to test (with high confidence) if a given password is the right password boils down to Check(password):

Hash the input password.
Seed the PRNG with that hash.
Generate a key using that PRNG, as per the normal key generation procedure.
Return true if the public part of the key generated in step 3 matches the known public key; else return false (for symmetric cryptography, use the key generated in step 3 to decipher a portion of ciphertext, test if the result matches known-plaintext; or, lacking sizable known plaintext, the test that byte distribution in the candidate plaintext is uneven according to a chi-squared test, deciphering more plaintext in case of doubt).

None of these steps is compute-intensive; that's the first problem. An adversary can enumerate likely passwords until it steps on the right one. A password cracker's basic function is to test passwords, approximately from most likely to least likely, using the above Check(password) procedure, until it returns true; at which point it is trivial to recover any non-public part of the key, and any plaintext.
If we assume that the actual password has been chosen randomly, or that the password cracker is good at ordering the passwords tested from most likely to least likely, then the expected cost of finding a password with $N$ bits of entropy is $C\cdot2^{N-1}$, where $C$ is the average cost of the Check(password) procedure above. Costs can be expressed in monetary or energy units; or in core·time, in which case the expected duration of the attack is its cost divided by the average number of cores.
In the particular case of DSA with shared parameters $(p,q,g)$, step 3 boils down to generating $x$ with $0<x<q$ (the private part of the key) by a straight invocation of the PRNG, then computing $y=g^x\bmod p$ (the characteristic part of the public key). That modular exponentiation, if performed naively, is the bottleneck of Check(password). It is not unrealistic to test $10^4$ passwords per core per second even with this straightforward algorithm; and there's an easy time-memory trade-off to speed that exponentiation by I guess a factor of 10 or more, by pre-computing $g^u\bmod p$ for $u$ of the form $u=v·2^{j·w}$ and $0≤v<2^w$, which allows reducing the number of modular multiplications by a factor of ${3\over2}·w$ compared to straight modular exponentiation. I'll thus assume a cost of $10^{-5}$ core·second (perhaps that requires dedicated CPU instructions for the hash and block cipher used by the PRNG, but that's increasingly common).
XKCD's estimate for the entropy in a 4-word password is $N=44$ bits; let's use that, even though it seems more than common practice. We get an expected $2^{44-1}·10^{-5}/3600/24≈10^3$ core. days to find the password. Using rented CPU time at $\\\$0.2$ per core·day (based on EC2 spot price), the expected monetary cost is $\\\$200$ plus adapting an existing password cracker. For Sequoia and its 1572864 cores, that's $2^{44-1}·10^{-5}/1572864/60≈1$ minute.
With RSA, or DSA with per-key parameters, testing a password is perhaps two decimal orders of magnitude more costly (because step 3 is much more complex), and that will make the scheme correspondingly less insecure; but that's an artifact, and still very insecure.
Also, only step 4 in that Check(password) procedure depends on the key; that's the second problem. This fact allows the attacker to amortize all other costs against the keys of several users. All there is to do is replace step 4 by If the public part of the key generated in step 3 matches any of the known public keys, return an identifier of that key; else return not_found; that change introduces negligible extra cost (for each password tested: little more than a single indexed memory accesses into little more memory than needed to store the public keys). That trivial change reduces the expected cost of attack proportionally to the number of users, which is a disaster for security. As a related issue, a rainbow table can be computed once for only a few times the cost or delay that would be necessary for finding the password for one particular key; after that initial effort, most keys are breakable with no sizable cost or delay.
Add that the password with the worse entropy is often what matters to the attacker (e.g. when restricting or accounting for use of a resource shared among several users) and that a sizable fraction of users choose poor passwords, and you'll find that a practical attack is feasible at low cost with a high probability of success using only commodity hardware.

The right technique if it is wanted to generate a key from a password is to replace the hashing (and optionally the PRNG) by stretching of the password (and if at all possible a per-user salt) into pseudo-random bits, using an appropriately parameterized Password-Based Key Derivation Function. A typical PBKDF is a public, deterministic, computable function accepting as input a password (assumed secret), salt (possibly public), and some parameter(s) controlling the cost of its evaluation (and typically, the size of the output). That PBKDF shall behave like a Pseudo-Random Function of (at least) its password and salt inputs.
The PBKDF transforms the password and salt (or something derived from them) iteratively, a high and parameterizable number of times. The transformation is such that it is unlikely that a shortcut requiring fewer iterations is feasible. The number of iterations should be chosen as high as tolerable for legitimate use. That dramatically raises the attacker's cost, since it must evaluate the PBKDF in step 1 of Check(password). Most importantly, optimization of later steps (like PRNG, key generation including modular exponentiation, primality test..) no longer helps the attacker significantly.
The minimum common PBKDF is PBKDF2, based on iterated hashing; a very serious drawback is that it is very susceptible to hardware-assisted acceleration, using ASICs or GPUs. A better one is Bcrypt also known as Eksblowfish, which by using 4kiB RAM makes such acceleration less economical. The state of the art is scrypt: it offers larger and parameterizable RAM usage (in turn raising cost of attack significantly and in a relatively precisely predictable manner); has a structural safeguard against massive hardware acceleration by virtue of using Salsa20/8; can use multiple cores (if available) to reduce the time penalty perceived by a legitimate user, and comes with convincing security argument.
The salt can be a (say) 128-bit random (that's the best when it is possible); or just a unique identifier (like the email of user concatenated with a value common to all users of a given server). It is enough that the salt is different for each public key to ensure that a password cracker must evaluate the PBKDF for each password·key combination tested, rather than for each password tested; and salt comes almost for free in most practical applications. Further, if the salt is unpredictable, the adversary can't start an attack before getting the salt.
Using a salted PBKDF, the expected cost to test a password becomes a parameter that can be adjusted, as a compromise between security and cost of legitimate use. Parameterize script to require 0.5 seconds on a 4-cores machine with a gigabyte of RAM per core (a fair desktop PC; that may translate to 3 seconds on a lost-cost dual-core portable PC); use the email address associated with the key and an arbitrary fixed string as salt; and you can have fair confidence that today's supercomputer would take weeks per XKCD-class password guessed (ignoring the hard-to-estimate difference between one of Sequoia's 1572864 cores and one in that desktop PC, the expected duration of the attack is $2^{44-1}·0.5·4/1572864/3600/24>129$ days, thus odds that an attack succeeds in less than 2 weeks are less than one in 36). Adjust the parameters every odd year (when you force users to change password and key), and you have decent long term security.
Caveat: it is highly recommendable to have in addition the key-dependent on something secret beyond the password, made part of the salt. That's a practical necessity when users are allowed to choose their password and have no incentive to choose a good one.

In addition: it is customary to allow users to change passwords while keeping the same public key. One simple technique is:

Generate a true-random seed S, e.g. 256-bit, that will remain unchanged as long as the user keeps the same asymmetric key.
Stretch password and salt into a symmetric key K, e.g. 256-bit, using an appropriately parameterized PBKDF.
Store the exclusive-OR of S and K; that will be used to recompute S from the password, and will be adjusted to change the password without changing S.
Seed PRNG with S.
Generate asymmetric key (public and private) using PRNG.

An often-used, slighting more complex technique towards the same goal is to symmetrically encipher the asymmetric key using K; that avoids re-generation of the asymmetric key each time the password is entered, and most importantly allows interoperability of various generation algorithms and PRNGs.

It is further asked:

If there was a strict requirement to derive a key from a few bits as possible (if you need salt at some point, it counts against those bits), would seeding a PRNG from N bits be acceptable, or is there a better method in terms of security level per bit to input?

If salt is counted as input the same way as a secret password (despite salt being usually assumed public and coming for free, e.g. the name or email of the key holder), then one is best with no salt.
Again, and in summary, if the input entropy is low, it is bad to feed that precious little to a PRNG (be it directly or through a standard hash) then use the PRNG to establish a key (be it asymmetric, or for a fast symmetric algorithm). Somewhere in the chain between the input and anything the attacker can observe (public key or ciphertext), there must be an inherently costly process, that is a PBKDF. Its salt input should be different for each user, if at all possible without reducing the entropy in what's secret. If a user must remember the whole secret input, not using a PBKDF amount to gross negligence; same for not salting that PBKDF if any characteristic of the user is available.


Simple designs for provable security in cryptographic primitives We can say that a cryptographic primitive has $n$ bits security against a type of attack if it cannot break it in less than $2^n$ time (time-area product in some cases). The cryptographic primitive could be said to be $n$ bits secure if the fastest possible attack (theoretical and future attacks of the same type included) takes at least $2^n$ time.

To make such security proofs, we need to analyze our crypto primitive. If we have more complex design, we may have more security (and performance, whatever else is desired) out of the box, but we won't be able to prove it.

Examples:

Salsa20/15 according to Wikipedia is 128-bit secure against differential cryptanalysis, and uses only add, rotate, xor with nonlinearity from add
SHA3 has 24 rounds and for $n$ output bits is $\frac{n}{2}$-bit secure against collisions with some reasonable assumptions, and uses only rotate, xor, not, and with nonlinearity from and

So we could use a simpler design, and thus make it easier enough to cryptanalyze that we can make a security proof. With that, we can know exactly how many rounds are needed and use only that many. In contrast:

AES-128 was 128-bit secure against all attacks with 6 rounds at the time of creation, 4 rounds were added as a security margin, for total of 10 rounds, uses s-box, xor, shift, add  with nonlinearity mostly from s-box
SHA-256 has 64 rounds (no reason?) and is 128-bit secure against collisions for 47 rounds, uses add, rotate, xor, and (for Choose/Majority) with nonlinearity from add, and

We expect that with their more elaborate design, they are more efficient, needing less rounds for the same security and offering better performance. Their complexity makes designing an attack against them much harder.

What is better practice now, to design something simply so it can be proved secure, or design something more complex and rely on it not being broken in its lifetime?

There is always the possibility that a new attack can come up in the future and break something that was proven secure against every type of attack known at the time. But nothing can defend against that really.

Also, the comparison here is of the designs - it wouldn't be fair to put a 256-bit stream cipher up against a 128-bit block cipher, and a sponge hash against a Merkle-Damgard hash. It also happens to be that Salsa20 and SHA3 are newer than AES and SHA2.

to design something simply so it can be proved secure

We currently cannot prove the security of anything (well, other than informational secure things such as OTP), without making some assumptions.  The best we can do is:

This is secure, assuming that this abstract problem is hard (but that says nothing about whether the abstract problem is actually hard).  Public key cryptosystems tend to be in this category.
This is secure against these classes of attacks (but that says nothing about other types of attacks).  AES is in this category, as we have a proof of security against linear and differential cryptanalysis.

  and hope that it's not broken in its lifetime?

We don't know how that can be avoided, either in simple or in complex systems.


Can ChaCha20 provide integrity? I have read that in general stream ciphers do not provide data integrity. Can ChaCha20 be implemented in such a way (perhaps like counter mode with message authentication in AES) to provide this?

ChaCha20 has Ind-CPA security and beyond this ( Ind-CCAx.. [1]), you need integrity and authentication. And note that Authenticated Encryption > Ind-CCA.
ChaCha20 is already teamed with Poly1305 authenticator to provide confidentiality, integrity and authentication. It exists in TLS standards and one of the five cipher suites in TLS 1.3 as ChaCha20_Poly1305.
If you are going to use ChaCha20 it is better to use XChaCha20-Poly1305 since it has larger nonce sizes (192-bit) so that randomly generated nonces are safe against the collisions, you need $2^{96}$ random nonces to hit another one with 50% probability and that is almost impossible.


Choosing the size of an S-box The most common S-boxes that I've seen are 4-bit and 8-bit (I've seen a 3-bit S-box in PRINTcipher, but I'm pretty sure they only did so due to significant hardware constraints). I understand that anything larger would be difficult to hold in a lookup table, and that 4-bit S-boxes are small enough to exhaustively search for ideal properties (for an 8-bit S-box, that would require checking 256! S-boxes), but what exactly are the tradeoffs made when choosing between the two, or choosing other sizes? I can intuitively understand why small S-boxes are not ideal, but I don't understand much more about the choice of the size.

what exactly are the tradeoffs made when choosing between the two, or
  choosing other sizes?

The triangle of performance , area and security. Smaller sboxes requires less resouces for implementation but it comes with lesser cryptographic properties (compared to larger size) therefore higher number of rounds to achieve minimum security requirement for the cipher (higher number of rounds , lesser speed performance).

One method used to merge the benefits of smaller and larger boxes sizes by constructing larger s-boxes from smaller s-boxes such as one of Clefia cipher sboxes, skinny etc. This type of construction allows implementation of 4-bit (for example) goes into "mini-cipher" structure to generate 8-bits boxes . The resulted 8-bit sbox has higher cryptographic properties but not as good as AES s-box.

Most of block ciphers come in 64 or 128 bit size  which is divisible by 4 or 8  and friendly to software implementation( minimum cpu register size is 8-bit).

However , I have seen other sizes mostly in authenticated encryption , for example , FIDES is the first cipher that uses 5-bit (almost bent) and 6-bit (APN) s-boxes due to their optimal differential and linear probability.moreover , with bitslice implementation of butterfly APN s-box  is advantage  ref

Ascon uses 5-bit sbox but they claim because of mathematical and threshold-implementation properties.


What is the typical block size in RSA? If the input text is divided into a fixed block size for encryption and decryption, what could be the typical block size for RSA algorithm for different size of input like 8 MB, 16 MB, 126 MB and 256 MB?

Well this depends on your key size.

But, in general:

A 1024-bit RSA key using OAEP padding can encrypt up to (1024/8) – 42 = 128 – 42 = 86 bytes.
A 2048-bit key can encrypt up to (2048/8) – 42 = 256 – 42 = 214 bytes.

And so on.
It is highly recommended you use at least a 2048-bit key.
If you need to encrypt more data just break it down into blocks of these sizes and send them independently (with different keys).

This however can be rather cumbersome (your server will need to have a few sets of keys) and it is best to simply send a 256-bit key (or any other size) for an authenticated encryption scheme and then use that scheme to transfer the rest of your data.


Pairing-based cryptography VS ZK-proofs: what's more efficient for threshold systems? In some papers (e.g. 1, 2) the authors approve that pairings are more efficient than classic zk-proofs (e.g. proof of discrete logarithm knowledge) for the described applications (threshold encryption, PVSS).

Let's see the differences between these approaches:

Proof:

Pairings: there are no additional steps.
ZK-proofs (non-interactive dlog knowledge): one (sometimes more) multiplication (we consider elliptic curve cryptography) in the group, hash-function,  a couple of additional arithmetic operations.

Verification:

Pairings: pairing, obviously.
ZK-proofs: two (sometimes more) multiplication, one addition, hash-function.

But pairing is more expensive than point multiplication. If we consider a threshold system, verification is more important (because you should make a proof once and verify all other participants). In this case pairing-based cryptography is less efficient than zk-proofs. Am I wrong?

If you care only about verification, and your protocols are such that the pairing-based approach requires one pairing, while the alternative (so-called "zk-proof") approach requires, say, 2~4 multiplications, one addition, and one hash, then yes, you are right: the pairing-based solution is less efficient. For a rough comparison, see page 14 of my paper: if you pick some of the most common best choices for a pairing-friendly elliptic curve and a pairing-free elliptic curve, then the cost of a pairing will be roughly 8 times the cost of a multiplication (or exponentiation, since we were using multiplicative notations in this paper) in the pairing-free curve. There are two reasons behind that: not only do pairings require more computation than multiplication, it is also the case that the best-known pairing-free curves allow for more efficient operations than the best-known pairing-friendly curves.


Encryption program conseil I'm writing a little program to encrypt and decrypt a file. I'm using AES encryption in CTR mode that takes a key generated by a KDF (script). I have read some articles about cryptography but I have some doubts. To encrypt the file I divide it in chunks and I encrypt them with AES generating a random nonce for every chunk. For key derivation I generate a random salt for every file. Do I need a different salt for every chunk or for every file it's enough? Do I need a padding with CTR mode? Should I follow other guidelines for a correct encryption? Thank you!!

I'm using AES encryption in CTR mode that takes a key generated by a KDF (script).

You should use authenticated encryption unless you have a strong reason not to.  For example, AES-GCM, or AES-CTR with HMAC-SHA256 in encrypt-then-MAC composition like the scrypt(1) utility uses.  If you're not sure, use authenticated encryption.

If you are sure you have a strong reason not to use authenticated encryption, you should have a design document articulating (a) what you're trying to accomplish with what resources, (b) what powers the adversary has to subvert those resources, and (c) what security properties you want to provide to the legitimate users in spite of that—and a clear justification that the adversary's powers enumerated in (b) exclude the ability to modify ciphertext.

Actually, you should write that design document anyway!  But the use of unauthenticated encryption will definitely raise a lot of eyebrows if you don't have a clear justification for it.

  For key derivation I generate a random salt for every file. Do I need a different salt for every chunk or for every file it's enough?

As long as you generate each key independently for each file (which you do already, if you derive it from a password using a random salt generated independently for each file) and never reuse it outside the file, you can safely reuse the key for all the chunks in the file as long as you use a distinct nonce for each chunk.

  To encrypt the file I divide it in chunks and I encrypt them with AES generating a random nonce for every chunk.

Random nonces with AES-CTR (or AES-GCM) are generally unsafe because for plausibly large volumes of data the collision probabilities are uncomfortably high, and nonce reuse is catastrophic.

In this case it may be that you won't ever have a file with more than a few million chunks, which is safe for 64-bit nonces, but I don't know that and I wouldn't rely on it.  Even if you choose 96-bit nonces, which you can safely use if your chunks are never more than a gigabyte, a few billion chunks may be a plausibly large volume of data.

If you used NaCl crypto_secretbox_xsalsa20poly1305, random nonces have negligible collision probability because they're 192 bits long, longer than AES can support directly or efficiently.

Even with authenticated encryption, an adversary may be able to cut and paste chunks to put them out of order or delete them or duplicate them.

You can kill two birds with one stone by using sequential nonces: use the chunk's sequence number in the file as a nonce.  Even with 64-bit nonces, you won't ever get a collision sequentially (you'll hit birthday bounds on the 128-bit block cipher first, and it will take centuries unless you parallelize the computation), and if you demand that the nonce match the chunk's sequence number in the file then even an adversary who can modify the file can't put the chunks out of order.

  Do I need a padding with CTR mode?

CTR mode does not require padding.  CTR mode is just a way to use a block cipher with a key and a per-message nonce to generate a one-time pad in any bit length you want.

All that said: Consider using an existing construction for many-chunk files?


PHE/FHE add and compare attack I am aware of this attack that applies to PHE (partially homomorphic encryption) given the attacker has access to a trusted oracle that can Convert (i.e decrypt and re-encrypt) between AHE (additive, e.g. Paillier) and DET (deterministic) schemes.

Pseudocode:

1. Get ciphertexts E(0) in DET and E(1) in AHE
2. i = 0
3. Convert E(x) to DET encryption
4. Compare E(x) to E(0)
5. If equal, print i and exit
6. Convert E(x) to AHE encryption
7. Add E(x) and E(1) using homomorphic property
8. i = i + 1
9. Goto 3

My question is how is this attack avoided in FHE (fully homomorphic encryption) which allows arbitrary computations (e.g adding and comparing) on ciphertexts.

My question is how is this attack avoided in FHE (fully homomorphic encryption) which allows arbitrary computations (e.g adding and comparing) on ciphertexts.

We don't give attackers access to such Oracles.  Such an Oracle would allow an attacker to decrypt (as you've noted), and so cannot be computed without help of the private key (or so we hope, otherwise the encryption method is broken).  So, unless the attacker gets some help from someone with the private key, he cannot perform this attack (and, if the attacker does get insider help, that insider could just decrypt the text, and hand the decrypted text to the attacker).

Note that this is not specific to homomorphic encryption; for any public key encryption method, an Oracle that will determinize a ciphertext will allow the attacker to test values (by the attacker determinizing the challenge ciphertext, make a guess as to the plaintext, encrypting it, determinizing that encryption, and seeing if it matches the challenge ciphertext).


Public key exponent coprime with totient proof I read this question a while back (In RSA, why is it important to choose e so that it is coprime to φ(n)?). I was wondering whether there is a proof that shows that a public key exponent e that is coprime with the totient of the modulus N will result in a unique answer when the cipher text is decrypted. Please help.

First, if $e$ is the public key exponent, then the private key exponent $d$ is the (unique) multiplicative inverse modulo $\phi(n)$, or alternatively $ed \equiv 1 \pmod{\phi(n)}$. The reason we want $d$ to have this property is because by Euler's theorem, which says $a^{\phi(n)} \equiv 1 \pmod{n}$ for essentially all values of $a$, so $(a^e)^d\equiv a^{ed} \equiv a \pmod{n}$ ensures we can always decrypt $a^e$ to $a$.

Now, how do we know $d$ is the unique multiplicative inverse of $e$? Because if there were another value of $d'$ such that $ed' \equiv 1 \pmod{\phi(n)}$, then $0 \equiv 1-1 \equiv (ed-ed') \equiv (d-d')e \equiv (d-d') \pmod{\phi(n)}$, where the last congruence holds because $\gcd(e,\phi(n))=1$. Thus, $d$ is unique.

Finally, if $\gcd(e,\phi(n)) \ne 1$, then $e$ does not have a multiplicative inverse mod $\phi(n)$. This is because, assuming $e^{-1}$ exists, then there exists some integer $k$ such that $k\phi(n) + ee^{-1} = 1$, which implies $\gcd(e,\phi(n)) = 1$.

In practice, $e$ not having a multiplicative inverse means that the sequence $a^e, a^{2e}, a^{3e}, \ldots$ may never attain the value $a$ modulo $n$.

As fgrieu points out, there are other values of $d$ that can serve as private key exponent (besides the multiplicative inverse of $e$) but we can always choose $d$ to be $e^{-1}$ and we are guaranteed that this choice will work with high probability.


Is it safe to use many nonces for XChaCha20? I have a very simple question. Since XChaCha20 nonces are 192-bit, there's technically no limitation to the max number of message encrypted, since the chances of two random nonces being the same are very very tiny. Is it okay to use the same key, but difference nonces to encrypt large files in chunks? Basically, I read the large file 1KB at a time, encrypt with the same key but random nonce. If the file is 1GB, then I would have used 1000000 nonces. If I encrypted in chunks of 1MB, then I would've used 1000 nonces. Is doing this secure? (Assume everything is authenticated and I use CSPRNGs for nonces)

Yes. Indeed, a "nonce" is a number used once. If you ever reuse a (nonce, key) pair, security breaks catastrophically. For a large chunked file, you can simply use the chunk number as the nonce, as long as you re-key after each file and can keep track of the count.
Libsodium's secretstream API does this internally. If possible, use that, as it's far safer than building your own construction.


How secure would this code be against cryptanalysis? Simple version:

Create software that takes a database of the dictionary, alphabet, and phrases. Randomly generate a database of random strings of letters/numbers/symbols of varying length. Randomly assign different strings to different words/letters/phrases.

Frequency analysis should already be hard because you're operating at a higher level than letters. But to make it more difficult, randomly assign multiple strings to the same word.

Throw in a good assortment of null strings for good measure. Certain strings would indicate that X number of strings following it are to be discarded, or various strings could indicate to disregard everything in between, thus adding gibberish to the mix.

Sophisticated version:

Create multiple versions where the same strings are assigned to different words/letters/phrases across each version. Have strings that signal that the following strings are to be interpreted with a certain version. A single version could be used for a whole message, or it could be changed throughout the message.

For example, in one version, f&1nl8(a#v4 could mean car.
In another version it could mean mountain.

Suppose v19g31dfs meant use version 13.
Then f&1nl8(a#v4 v19g31dfs [...] f&1nl8(a#v4 would appear to repeat the same word.

Assume that the software is secure, and the only means of attack is direct cryptanalysis on intercepted messages.

Question:

How secure would this code be against cryptanalysis?

What you have is a type of substitution cipher, at the level of words rather than letters. Using multiple ciphertexts to correspond with the same plaintext atoms is called homophonic substitution. Homophonic substitution does make frequency analysis on atoms more difficult, but by no means impossible. You merely need more ciphertext to analyze.

Frequency analysis can also be performed on digrams (i.e. pairs of words) or longer sequences. For example, a word that usually precedes a noun has a high probability of being a or the.

Compared with an alphabetic substitution cipher, yours requires a huge key: the key needs to describe all possible substitutions, so it must contain one or more entry per word. Rather than apply complex rules based on such a large key, you'd do better to generate a random key of the same length and use it as a one-time pad. That one-time pad would be good for a plaintext that's as long as your dictionary, whereas frequency attacks would begin in practice long before your dictionary was exhausted.

Adding instructions such as “skip” or “rotate key” in the stream doesn't fundamentally improve things, It does make frequency analysis a lot more difficult if you use them correctly, but not impossible the way modern cryptography does (every byte has exactly the same chance of having any given value, to someone who doesn't know the key). You need to describe the rules in the key, making it even larger.


How to construct a good PRF from a block cipher? We want to explicitly construct a good (as tentatively defined below) Pseudo-Random Function $F$ with $b$-bit input and output, from (preferably just) one Pseudo-Random Permutation $E$ of $b$-bit, as instantiated in practice by TDEA for $b=64$ or AES-256 for $b=128$, and one fixed random secret key.

I tentatively define a good PRF to be one indistinguishable (with small constant advantage) from a random function, assuming $2^{b(1-\epsilon)}$ queries to an oracle implementing our construction of $F$ from $E$, and delegating invocations of $E$ (edit: and in addition of $E^{-1}$ if that helps) to a random oracle for that. Fix this definition as necessary (Update: I'm told by the answers that for $\epsilon<1/2$, this is roughly what's called a PRF with beyond the birthday bound security).

Are there simple constructions of $F$ from $E$ with a security argument?

$F(x)=E(x)$ is squarely unfit: it can be distinguished from a random function by detecting collisions after $2^{b/2}$ distinct queries, which happens with sizable probability for a random function but not for a random permutation. That can even be done with constant memory, using Floyd's cycle finding. A distinguisher can also be built against $F(x)=E(x)\oplus x$.

Right now I fail to find a distinguisher for $F(x)=E(E(x)\oplus x)$, but that's not even a weak security argument. Update: If the security of that is unprovable, I'm still interested by a distinguishing attack, in order to get a feeling of how insecure in practice that could be.

What you're looking for is often called a construction of a PRF with "beyond the birthday bound security," and you can probably find some constructions by searching on variants of that term.

For concreteness, this paper by Iwata (alternate link) almost gives a solution to your problem: The only deficiencies are that the resulting $F$ has inputs one bit narrower than $E$, and it does not achieve your definition of security for every $\varepsilon > 0$.  Specializing that construction down to your setting, and using your notation, it defines $F(x)$ for $x\in\{0,1\}^{b-1}$ as $$F(x) = E(x\|0)\oplus E(x\|1),$$
where $\|$ denotes concatenation.  Its proof applies for a number queries well beyond $2^{b/2}$, which is obviously non-trivially better than the direct $F(x) = E(x)$ construction.


Modified version of a CPA-secure encryption scheme The following encryption scheme: choose a random string $r \leftarrow \{0,1\}^n$ and compute the ciphertext $c= \thinspace <c_0, c_1>= \thinspace <r, F_k(r) \oplus m>$, assuming $F$ a PRF; is CPA-secure, as we have a randomized/non-deterministic encryption process. Why, if applying a modified encryption process, i.e. computing the ciphertext $c'= \thinspace <c_0, c_1'>= \thinspace <r, F_r(k) \oplus m>$, this  is no more CPA-secure? I mean, this modified encryption process is also non-deterministic. Could it be because on each encryption invocation the input to the PRF $F$ is the fixed value $k$? I'm not sure if this makes sense.

Ask a CPA-query with a known $m$ and get back $c_0,c_1'$. Compute $c_1'' = c_1' \oplus m$. Then, compute $F^{-1}_r(c_1'')$ and this will be $k$. Now you know the key.

Of course, this attack assumes that you can invert $F$, but nothing in the definition says you cannot (and in practice you often can).


When using Curve25519, why does the private key always have a fixed bit at 2^254? When using Curve25519, the private key always seems to have a fixed bit set at position $2^{254}$.

Why is that? Is there any good reason to use a fixed positioned most-significant-bit in the private key?

Curve25519 was designed to take advantage of the Montgomery ladder, which combined with Montgomery curves forgoes the $Y$ coordinates, is side-channel resistant, and enables public keys to be any 255-bit string. The ladder looks something like this (pseudocode):

Q[0] = P;
Q[1] = 2*P;
for(int i = log2(exponent) - 2; i >= 0; --i)
{
  Q[ bit(exponent, i)] = 2*Q[ bit(exponent, i)];
  Q[!bit(exponent, i)] = Q[0] + Q[1];
}
return Q[0];

You might notice the format of the loop: the counter is initialized with the index of the most significant bit of the exponent (i.e., the private key), and goes down to 0.

In practice, the first step of the ladder will be to find the most significant bit of the exponent. This is not hard, of course, but doing so may leak, through timing, information about the most significant bits of the exponent: exponents with bit 254 set to 0 will run faster than with that bit set to 1. This can lead to real problems.

Curve25519 completely avoids this problem by always setting the most significant bit to 1. This way, the loop always has the same amount of iterations, and no timing information can accidentally be leaked by the variable iteration count.


Cross correlation of two Boolean functions I have been studying Cryptographic Boolean Functions and got stuck with the calculation of cross correlation of two boolean functions. I know the formula is $$c_{f,g}(y) = \sum_{x \in V_{n}} f(x)\cdot g(x\oplus y).$$ What I don't understand is if $f = g$ and $y$ is $0$ shouldn't the correlation be $2^n$? When I calculate, if $f$ and $h$ has the value $0$, $f(x)\cdot g(x)$ will yield $0$, but shouldn't I have $1$ in order to reach $2^n$ in the end? I am sorry if this question sounds silly but I have really spent so much time trying to figure out. Any help would be greatly appreciated.

In theoretical computer science literature, boolean functions are defined as
$$
f\colon \operatorname{GF}(2)^n \to \{\pm 1\},
$$
and the usual link with functions defined as
$$
\tilde{f}\colon \operatorname{GF}(2)^n \to \{0,1\}
$$
is via $$f(x)=(-1)^{\tilde{f}(x)}.$$

Edit Here's a standard reference from the Boolean function literature.


Is there a cryptographic scheme that allows joint encryption using a shared secret? I'm looking for a type of algorithm that could be used to encrypt text with a shared secret $S$. What I would like to have is the secret to be broken up in three pieces, where any combination of two pieces can be used to reconstruct shared key $S$ in order to decrypt the text.

Is there any mathematical or cryptographic scheme of approaching this? Physically breaking up shared secret $S$ is one approach but what about others?

The common procedure for what's asked is to draw a random key $S$, use it to encipher the plaintext using a symmetric cipher such as AES-CTR, then split the key into so-called key shares per a threshold scheme, so that $k=2$ shares out of $n=3$ are required to reconstruct the key. A generic $(k,n)$ threshold scheme is Shamir Secret Sharing.

Here is a very simple $(2,3)$ threshold scheme: each bit $x$ of the key is splits into three shares values $a$, $b$, $c$. Share value $a$ is chosen uniformly at random among $\{0,1,2\}$, then the other two are determined as $b=(a+x)\bmod3$, $c=(b+x)\bmod3$ (where $\bmod3$ designates subtracting $3$ from the result if it is $3$ or more). For decoding, if any two share values among $a$, $b$, $c$ are equal, then the corresponding key bit $x$ was $0$; otherwise it was $1$. Demonstrably, a single share gives no clue about the key. See this question for schemes still workable by hand and giving a slightly more compact encoding.

As pointed in comment, this has the drawback that who/whatever draws, uses and/or splits $S$ could be dishonest, keep $S$, and decipher the plaintext.


Caculating Correlation for CPA attack on AES I am having some trouble understanding how to calculate the correlation coefficient for CPA attack on AES.

In the article Study of Deep Learning Techniques for Side-Channel Analysis and Introduction to ASCAD Database, they actually keep 700 measurements for the computation of 1 SBox (page 11), in step 7 of the algorithm (page 12).

But when we want to calculate the hamming distance between the input and output of that computation for a guessed subkey, we will get a single value representing the distance. So how will we calculate the coefficient between the measurements and the hamming distance? Since we have 700 measurements for the same instruction, but only one hamming distance.

Premise: I'm not familiar with the paper.

You probably compute 700 correlation values, one for each time sample.

For CPA you need several ($N$) traces, with different/random input but fixed key. Here each trace is made by 700 samples, each sample correspond to a different time instant.

Regarding the hypothesis, we have the HD computation which will depend on the plaintext and the key. The attacker knows the plaintext but not the key so she guesses all key values.

You put the traces in a matrix where the $N$ rows are the different acquisitions (each with a different plaintext) and the columns are the 700 time instants.
You create a second matrix with $N$ rows and 256 columns, where each entry is HD relative to the plaintext of the row and the key of the column.

Then you correlate each column of the first matrix with each column of the second matrix.
You will obtain as result 256 traces with 700 time instant, each showing the correlation of key guess $i$-th ($0<i<256$) at the $j$-th ($0<j<700$) time instant.

You don't expect all the time samples to leak in the same way, so you might have high correlation, with the correct key, only on one or few samples.


Extracting Randomness from a Poisson Distribution I'm working on a quantum random number generator based on the shot noise of CMOS camera sensor. Shot noise in an image is caused by the variance of the number of photons hitting the sensor per unit of time. The distribution follows the Poisson distribution. To collect shot noise, I have to illuminate the sensor with a diffused light source.

A lot of papers discussing how to extract randomness from shot noise usually use equal frequency binning method. The following image is an illustration of randomness extraction using two bins. If the current sample is greater than average, output 1, if the current sample is less than average, output 0.

The problem with this method is it's not easy to determine the cut points, or in this case, the average. I tried to use moving average but the voltage of the light source sometimes drops for a few seconds caused by the other electronics in my room and it makes the output generated by my RNG sometimes biased for a few seconds. I tested the generated data using NIST Statistical Test Suite and it only passed 5/15 tests.

Although it passed 14/15 tests when I applied von Neumann debiasing method, the fact that the quality of the raw data is really bad still bugs me. So I experimented with a different extraction method. Here's how it works using one pixel

Let Brightness(t) be a function that returns the brightness of the pixel at time t

if Brightness(0) < Brightness(1) then
    output 1
if Brightness(0) > Brightness(1) then
    output 0
else
    don't output anything

Basically, take two non-overlapping samples, if the second sample is brighter than the first one, output 1, if the second sample is darker than the first sample, output 0.

The data generated using this method passed 15/15 NIST tests. But since I've never seen any paper discussing a method like this, I need confirmation if this method really as good as it looks, and maybe some explanation why it's good. Thank you.

The question's method is not secure absent a model of the source. In particular, applied to a source evolving in time as this sawtoothassumed of period several times the sampling time between Brightness(0) and Brightness(1), the output will be terribly biased towards 0, because the function is decreasing most of the time (this effect will decrease with added Gaussian noise, spacing the samplings).

Another issue is that multiple pixels can output correlated bits.

Both effects might well occur in practice, for a variety of reasons: switching regulator of the power supply of the gizmo, or of the LED source of the ambient lighting. In a cryptographic context, adversaries often have some level of access to a RNG, and might induce that effect on purpose (e.g. varying the power supply, or a light source). And by a corollary of Murphy's law often verified in this very context, such things will happen without explicit adversaries (e.g. as the effect of aging of power supply capacitors) and at the worst time.

  The data generated using this method passed 15/15 NIST tests

If a source fails any statistical test¹, this conclusively proves that the source is bad from a cryptographic perspective. But if the source passes all tests, it can still be horribly bad from a cryptographic perspective; the best that can be reasonably be said is that the source, as tested, was free from the particular defects that the tests are designed to detect.

My though experiment with the sawtooth shows that the source could fail under different, realistic conditions. And it is trivial to design a bit source that passes all tests, yet is terribly weak cryptographically.

¹ significantly more often that predicted by the test's $p$-value, with the test correctly designed, implemented and applied.


What is an extremely basic asymmetric cipher that I can present at the pub? I'm trying to explain the basics of Bitcoin to my parents.

One of the core components of bitcoin, is signing transactions to make sure your identity can't be impersonated, and thus the need to explain a simplified asymmetric cipher.

What's an extremely simple asymmetric cipher I can use as an example?

How can this simplified cipher be used for signing?

I'm trying to explain the basics of Bitcoin to my parents.

If this is your objective, I would argue that it is not necessary to go in-depth into asymmetric encryption/signing. The basic mechanics of Bitcoin, or blockchain systems in general, are easily, (and probably best) explained on a very abstract level, i.e. it is a decentralised solution to asset transfers and consensus building, and so forth.

As for the signatures, you could say that they serve as transaction authorisation so that only the owner of tokens is able to spend, but everyone can verify the signature.

  What's an extremely simple asymmetric cipher I can use as an example?

If for some reason, your audience is really interested in learning how it works on a more technical level, I would avoid RSA and the effort of doing the transfer from encryption to digital signatures later. In this case, you might simply want to stick to DSA (the classical, non-elliptic curve version), and use small numbers to talk them through step by step.

Not knowing your parents/friends at the pub, I would have my doubts though that they care about the hardness of discrete logarithm problems or finite group operations, and from my experience with similar settings, I advise you to start with the general concepts, and then go into the exact algorithms if required.