Why are PRNG in programming languages not cryptographically secure by default? In most programming languages, there is a module or function in the stdlib for creating random output like random.random() in Python.

Because those functions use a normal PRNG that is not cryptographically secure, over all the years those generators have been used for crypto nonetheless because of the name "random".

Why do not programming languages use only cryptographically secure PRNGs in the stdlib? It's able to produce random output even if not needed for crypto and it's secure if you use crypto.

Is there an advantage of normal PRNGs compared to CSPRNGs? I'd be happy if you could explain it in a way that someone like me without any crypto background can understand, thanks a lot! :)

First, insecure PRNGs are typically faster than CSPRNGs. CSPRNGs based on /dev/urandom (if you're familiar with Linux), for example, have to call the crypto kernel module driver every time. For reference:

the BearSSL implementation of ChaCha20, which can be used as a CSPRNG, on an Intel Xeon CPU at 3.10 GHz, reaches 270.72 MB/s;

an implementation of a Mersenne Twister, which is a typical PRNG, on an Intel Xeon 5160 at 3 GHz, reaches 113.4*32/8=453.6 MB/s;

there are even faster algorithms/implementations. For example, the rand() function in the GNU Scientific Library, according to the same paper, reaches 227.8*32/8=911.2 MB/s. Xorwow, which belongs to the Xorshift PRNG family, reaches 1388.4 MB/s.

Second, writing cryptographic software, including CSPRNGs, is much more complex than writing general-purpose software.

There are also historical reasons. At least until the 1990s, developers, including some developers working on standardizing new programming languages, were afraid to deal with cryptographic algorithms, because the export restrictions on cryptography were severe and not entirely understood by them. Quoting one such developer:

  I would not have even considered putting crypto strength randomness into anything that shipped with the browser without getting a huge amount of legal advice from the MSLegal team. I didn't want to touch crypto with a ten foot pole in a world where shipping code was considered exporting munitions to enemies of the state. This sounds crazy from today's perspective, but that was the world that was.

What about more recent programming languages, such as Python?

Some people argue that baking CSPRNGs into programming languages by default would lead to a false sense of security, especially as new flaws arise and when dealing with older software. Say that now, in 2018, random is cryptographically secure. Do developers remember to check, when dealing with older versions, that the old random was actually insecure?

An interesting quote on this matter:

  Anyone writing crypto code without reading the docs and understanding what they are doing are surely making more mistakes than just using the wrong PRNG. There may be a good argument for adding arc4random support to the stdlib, but making it the default (with the disadvantages discussed, breaking backwards compatibility, surprising non-crypto users, etc.) won't fix the broken crypto code. It will just give people a false sense of security and encourage them to ignore the docs and write broken crypto code.

See this for more insight on how the Python community was reasoning about implementing a CSPRNG by default.

TL;DR. They are faster and easier to implement. In the past, people were afraid of crypto, because of heavy restrictions. Now, people are afraid of giving a false sense of security.


Does using Noise asynchronously weaken its security properties? Can Noise be used asynchronously without weakening its security properties?
Specifically, there are two users, A and B, who communicate asynchronously by leaving messages for each other on an untrusted server, but they may never be online at the same time. They know each other's public static keys in advance, so the KK pattern seems appropriate:
KK:
  -> s
  <- s
  ...
  -> e, es, ss
  <- e, ee, se

It seems to me that this pattern could be used asynchronously without weakening it.
A and B both initially upload a bunch of ephemeral public keys to the server, and top up the supply when they connect at later times.
Now A wants to send a message to B:

Download one of B's ephemeral keys from the server, and run the first handshake step.
Run the second handshake step, generating an encrypted public ephemeral key (so handshake is done).
Run Noise again with the plain-text as a payload, generating an encrypted transport message.
Upload a concatenation of B's plain-text ephemeral key, A's encrypted ephemeral key, and the encrypted message.

When B comes online and downloads the message, they:

Discard the message if the plain-text ephemeral key is not on their list of unused keys.
Run the two steps of the handshake.
Decrypt the encrypted message.

(So in this scenario, B is the initiator and A is the responder.)
I hope this is not off-topic. I thought it was OK because I'm asking more about how to use an existing protocol rather than asking for cryptanalysis of my own design.
Edit 27 August
I found a gotcha in the above scheme today. In section 7.5 of the spec it says:

...patterns starting with K or I have the caveat that the responder is only guaranteed "weak" forward secrecy for the transport messages it sends until it receives a transport message from the initiator. After receiving a transport message from the initiator, the responder becomes assured of "strong" forward secrecy.

So my scheme will only have weak forward secrecy, which is a shame, because the whole point of using Noise was to get forward secrecy. I think X3DH (as used by Signal), gets around this by signing the prekeys (the initial shared ephemeral keys).

Online $\neq$ Synchronous
Yes, Noise can be used in a somewhat asynchronous setting.
Noise is initially meant to be an "online" protocol to establish secure channels, however "online" here does not really imply it requires a "fully synchronous network", but more like a "reliable channel" in which packets will come in the right order but not necessarily at a given time.
The appropriate handshake
In your case you said that:

They know each other's public static keys in advance

Which means indeed that the KK pattern is the most appropriate one.
Now, it seems you'd like to have A perform what is called a "0-RTT" encryption (that is encrypting a message/payload for B without having done an interactive handshake first) and this is actually covered by Noise:

Patterns where the initiator has pre-knowledge of the responder's static public key (i.e. patterns ending in K) allow zero-RTT encryption, meaning the initiator can encrypt the first handshake payload.

So, what you want to achieve is actually already possible using 0-RTT and the KK handshake and it's actually in the spec and you don't need to run the different steps differently from what the spec says.
First notice that the lines above the ... are representing the "pre-knowledge" of the parties.  They have acquired the static keys through some mean (for example by relying on a server) and then the actual protocol start:

-> e, es, ss means that A is sending to B its ephemeral key e and is performing a DH es using its ephemeral key and B's static key, and then it is performing another DH
ss using its own static key and B's static key (of which it had pre-knowledge).
After having performed these 2 DH, A can already compute the shared chaining key ck
which is just a hash of the 2 DH outputs
A can then the payload of its handshake using ck. Notice that in all Noise handshake messages, you have an implicit payload which can be zero-length or not. (And which is encrypted under certain conditions.)
Upon reception B will learn the ephemeral key of A and has pre-knowledge of its static key, so B is able to compute the same 2 DH as A using the e it received and its own static key and then using both static keys, so B gets the same value for ck and will be able to decrypt the encrypted payload.
B generate an ephemeral key, computes the DH ee between the 2 ephemeral keys and compute finally the DH se between A's static key and B's new ephemeral key and now the ck state is updated once more to its "final" state, which A will also be able to compute upon reception of <- e, ee, se. The payload to this message can directly be encrypted as well using ck.
Notice that at this point the final shared key ck has been computed as being the hash of first es hashed with ss hashed with ee hashed with se.
Subsequent messages can just be encrypted using the resulting key ck and incrementing the nonce (and ad hash) as per the spec.

We need to be careful as the spec is telling us the following:

After performing a DH between a remote public key (either static or ephemeral) and the local static key, the local party must not call ENCRYPT() unless it has also performed a DH between its local ephemeral key and the remote public key. In particular, this means that (using canonical notation):

After an "ss" token, the initiator must not send a handshake payload or transport payload unless there has also been an "es" token.

But since we had first an es token and then a ss one, we can call ENCRYPT() on our payload. :)
So IMO you do not need to do anything differently from what the spec already allows and does. This is already possible without any change by simply exploiting the optional handshake payloads.
The alternative
Now, while I'm at it, if you really have strong asynchronous requirements, you might want to take a look at what Signal's X3DH is doing with its one-time prekeys since being asynchronous is the goal of X3DH and it's based on a server setup like yours:

X3DH is designed for asynchronous settings where one user (“Bob”) is offline
but has published some information to a server. Another user (“Alice”) wants to
use that information to send encrypted data to Bob, and also establish a shared
secret key for future communication.


Rubik's Cube as Encryption Consider this scenario:

Alice gets a Rubik's Cube and peels off the colors from each piece. She then writes a small message on one of the faces of the cube and fills the remaining pieces with random letters. Then, she scrambles the pieces in a way that was pre-determined between Alice and Bob. And finally, she ships the cube to Bob.

Can this be considered as encryption, and, if so, how secure can this encryption scheme be?

Can this be considered as Encryption

If the sequence of necessary moves is treated as the key, yes.

  how secure can this encryption scheme be?

First some details about the cube:

6 faces, each with 9 pieces visible each. Because the faces share some pieces, and the immovable cube center is not visible, there are only 26 pieces in total: 6 centers (of faces), 8 corners (each with 3 colored sides), and 12 edges (each with 2 colored sides).
The center piece of each face is, like the cube center itself, not movable. If it is "moved", in reality everything else moves.
The 8 corner pieces always are corner pieces, independent of any moves. Same goes for the. 12 edge pieces.
There are 8! possible position combinations of the 8 corner pieces (naturally). In their position, 7 of the 8 can have 3 possible "rotations", just the last one depends on the others. With this, there are corner $8! \cdot 3^7$ possible corner positions
Similarly, 12! combinations of edge pieces are restricted to $\frac{12!}{2}$ by the corner pieces (for details to everything, see Wikipedia).

Now, we have 9 pieces that contain "good" data: 1 face center, 4 edges (each has two more sides with nonsense data), and 4 corners (each 1 more side with nonsense data). The other 17 pieces contain only nonsense data.

If an attacker wants to (bruteforce-)find the center piece with the good data on it, there are 6 possibilities (6 face centers, just turning the whole cube around to find the right one).

Then there are 4 corner pieces where position and orientation matters, and 4 others that don't matter to find the one good-data face. Meaning, $\frac{8!}{4!} \cdot 3^4$ possibilities to try here.

Finally, 4 edge pieces where position and orientation matters, and 8 others that don't matter to find the one good-data face. Meaning, $\frac{12!}{2} \div \frac{8!}{2} \cdot 2^4$

Multiplying...

$6 \cdot \frac{8!}{4!} \cdot 3^4 \cdot \frac{12!}{2} \div \frac{8!}{2} \cdot 2^4 = 155196518400$ or about $2^{37}$

Your key has 37 bit. With todays computer, that's nothing =>
completely insecure

Aside from that ...

A "padding" of 45 byte for 9 byte payload is impractical
A cube that contains the same symbol multiple times is less secure
The scheme isn't protected against things like known-plaintext attacks etc.etc.
Properties like the avalanche effect etc., etc. are completely missing
Depending on the choice of padding data, just making statistics what symbols exist might be enough to figure the plaintext out
... and many more


Embedding POW in an EC public key I have an application where it would be advantageous for an attacker to have to spend a long time generating public keys.

To do this, I require that the hash of the public key be less than a certain number.   That way a typical user will take 1 second to generate a public key, and an attacker who is trying to DOS public resources will also have to spend more resources to do so than it costs for us to detect.

There are two mechanisms proposed:

Take a public key, hash it many times with an incrementing salt, and require the result to be less than a certain number.
Generate a public key, hash it once, and if the result is not less than a certain number, add one to the private key and add the generator to the public key.

The first mechanism helps mitigate DOS and spam attacks.   The second mechanism helps mitigate some MITM attacks as well.

I like the features of the second, except for some drawbacks:

This reduces the number of valid public keys that exist, and could reduce search space for an attacker attempting in the process of brute forcing public keys.  Since we're using a secure hash, it seems the DLP remains equally hard with or without this hash.
This relies on the point addition algorithm being highly efficient, and assumes an attacker may not have some new and better way to perform this operation.   But this is as opposed to assuming efficient hashing, an equal assumption?
It's possible that an unprivileged attacker observing the initial POW generation could determine some information about the key.   Not a huge deal since these keys are not frequently generated, but perhaps not.

Are there other things I should be thinking about?   Is there a standard out there in the wild I haven't found?

I like the features of the second, except for some drawbacks:

I don't believe the drawbacks are as bad as you think.

  1.This reduces the number of valid public keys that exist, and could reduce search space for an attacker attempting in the process of brute forcing public keys.

It doesn't help the attacker; if the attacker sees the public key, the knowledge that the hash is small doesn't help him (as he sees the exact value).  And the additional hashing requirement doesn't help Pollard Rho or Big-Step-Little-Step (two algorithms for computing discrete logs)

  2.This relies on the point addition algorithm being highly efficient, and assumes an attacker may not have some new and better way to perform this operation.

I believe that's a fairly safe assumption; it's hard to see how someone could generate $(x, xG)$ pairs in a manner that is significantly more efficient than your algorithm.  In any case, the most significant threat is an attacker with a bot or DSP farm; that would allow him to generate a number of public keys considerably faster than an honest user.

  3.It's possible that an unprivileged attacker observing the initial POW generation could determine some information about the key.

With your algorithm, the attacker has no knowledge of where you started the search.  If he learns that you took a while, he can deduce that a $(x - \delta)G$ doesn't meet the hashing criteria for a number of $\delta$s, however, as he can see the value $xG$, he could verify that directly if he wanted to, and so it doesn't actually leak any information about the private key.

So, it looks safe; my only concern is that it might not provide as much DoS protection as you hoped (of course, I don't know how much protection you're looking for, and what assumptions you are willing to make about attacker capabilities...)


What is meaning of the term "language"? I don't have much formal background, and I could not find a suitable explanation for this after searching on Google/Wikipedia.

What is the meaning of the term "language" as used in cryptographic protocols?

Sample sentence from a recent paper:

  Every language in BQP admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical(and quantum) polynomial-time verifiers.

The concept of language has been systematized. For example here you can become familiar with this in an accessible way.

In the article you are reading the language has such meaning:

Wikipedia BQP:

  A language L is in BQP if and only  if and only if and only if there exists a polynomial-time uniform family of quantum circuits   $\{Q_n:n \in \mathbb{N}\}$, such that

  For all $n \in \mathbb{N}$, ''Qn'' takes ''n'' qubits as input and outputs 1 bit
  For all ''x'' in ''L'', $\mathrm{Pr}(Q_{|x|}(x)=1)\geq \tfrac{2}{3}$
  For all ''x'' not in ''L'', $\mathrm{Pr}(Q_{|x|}(x)=0)\geq  \tfrac{2}{3}$

  Alternatively, one can define BQP in terms of quantum Turing machines. A language L is in BQP if and only if there exists a polynomial quantum Turing machine that accepts L with an error probability of at most 1/3 for all instances.


Is there any weak message for an ECDSA signature? Suppose ECDSA is used without hashing the message, but directly using a short message (say 10-bytes long) as the value z (using the definitions at http://en.wikipedia.org/wiki/Elliptic_Curve_DSA) because we need extremely fast signing with ECDSA in a specific embedded platform. We also pre-compute kG and k^-1 values.

Are there any weak z values such that the signature can be forged ?

[Partial answer] In  Generic Groups, Collision Resistance, and ECDSA by D. Brown (see http://cacr.uwaterloo.ca/techreports/2002/corr2002-06.ps or http://eprint.iacr.org/2002/026) on page 17, you have a lot of information about the kind of hash functions that can be used with ECDSA. In your case, taking the identity function as hash and looking at the results you find that two of the proposed weaknesses are particularly relevant to your case:

$z=0$ is a weak value (see Zero-Finder-Resistant Hash)
If the probability that a random number modulo the curve order belongs to your acceptable range of $z$ values is not too low, there also is an attack (see One-Way Hash Function). With 10 bytes long values as suggested, the probability is sufficiently low and you can probably ignore this attack.


How does hash function in Elgamal signature scheme prevent existential forgery attack? I have heard that hashing the message M prevents an existential forgery attack. I was wondering how.

Existential forgery attacks allow the attacker to choose (or calculate) a signature, and then the message is derived from this signature (and the public key) using the existential forgery attack algorithm.

The signature is valid for the derived message, but the problem is that the attacker cannot control the message. It could be anything.

Hashing the message before verification requires the attacker, Oscar, to additionally find some data that hashes to his derived message, which is practically impossible.


Questions about updating the secret key of RSA? I want to update the secret key of RSA.

I understand there exists a common modular attack on RSA. Precisely, if adversary knows $(e_1, m^{e_1})$ and $(e_2, m^{e_2})$, where $e_1$ and $e_2$ are the RSA exponents under the same module $N$. Then it can compute $\lambda_1, \lambda_2$ such that $\lambda_1e_1 + \lambda_2e_2 = {\sf gcd}(e_1, e_2)$, where ${\sf gcd}(\cdot)$ is the greatest common divisor. Thus the plain message can be recovered by computing $(m^{e_1})^{\lambda_1/{\sf gcd}(e_1, e_2)}\cdot (m^{e_2})^{\lambda_2/{\sf gcd}(e_1, e_2)}=m$ (if I am wrong, please correct me).

In my implementation, I want to use the RSA like a private-key encryption. Instead of publishing the public RSA exponent $e$, I keep it secret. Then, the secret key is $(e, d)$ where $ed = 1 \mod \phi(N)$ (I do not consider to update the prime $p$ and $q$). Initially, I compute the RSA ciphertext $m^{e_1}$ and store the secret key $(e_1, d_1)$. At some time, I update the secret key to $(e_2, d_2)$ and give $d_1e_2$ for re-encrypting the ciphertext from $m^{e_1}$ to $m^{e_2}$.

My question is, 1) In my implementation of using RSA like a private-key encryption, the key-update is still vulnerable to common modular attack (or is it secure)? In other words, if the adversary knows $m^{e_1}, m^{e_2}$ and $d_1e_2$, is it able to guess $m$? 2) If 1) is secure, the key-update is resistant against leaking old secret keys? In other words, if the adversary knows $m^{e_2}, d_1e_2$ and $(e_1, d_1)$, is it able to guess $m$?

Waiting for your answers. Thanks a lot.

if the adversary knows $m^{e_1}$, $m^{e_2}$ and $d_1e_2$, is it able to guess m?

Obviously not; if he could, then they could break RSA.

Here's the RSA problem, given $m^e$, $e$ (and the modulus $N$), recover $m$.

Suppose that we can solve your problem, that is, we had a black box that, given $m^{e_1}$, $m^{e_2}$ and $d_1e_2$, could recover $m$.

Then, given the RSA problem parameters $m^e$ and $e$, we would pick a value $\lambda$ which is relatively prime to $\phi(N)$ (and this can be done simply by picking $\lambda$ prime), and compute $(m^e)^\lambda$.  If we assume $e_1 = e$ and $e_2 = e \cdot \lambda \pmod{\phi(N)}$, we then have $e_2 \cdot d_1 = \lambda \pmod{\phi(N)}$ (as $d_1 = e_1^{-1}$)

We then have $m^{e_1} = m^e$, $m^{e_2} = (m^e)^\lambda$ and $d_1e_2 = \lambda$, we then give these parameters to the black box, and recover $m$, solving the RSA problem.

On the other hand, this argument assumes that (at least) $e_2$ is large (because the above procedure effectively selects a random $e_2$).  If you selected $e_1$, $e_2$ small (say, 16 bits or so), then what the attacker could do is go through the possible $e_1, e_2$ combinations, and recover a billion possible $m$ values, one of which is correct.

  Is the key-update is resistant against leaking old secret keys? If the adversary knows $m^{e_2}, d_1e_2$ and $(e_1,d_1)$, is it able to guess $m$?

No, the key-update is not resistant; the adversary can recover $m$. The values $e_1$, $d_1$ are sufficient to allow him to factor $N$ efficiently, with the knowledge of $d_1e_2$ and $d_1$ and $\phi(N)$, he can recover $e_2$, and with that and $m^{e_2}$ (and again, the factorization of $N$), he can recover $m$.


How to calculate M when the attacker know e and w Alice has a pair of RSA keys, the public key is $(n,e)$, the clear
text message $M$ and the ciphertext $C=M^e \pmod n$.

We suppose that Bob wants to encrypt two successive messages and send them to Alice, the messages are of the form, $M$, and $M+w$, the corresponding ciphers are $C$ and $C’$.

We suppose that an attacker intercepted $C$ and $C’$ and that he
knows $w$.

Find out how can the attacker calculate the message $M$, in the case of $e=2$.

You have $\{(n,e=2), M, w, C, \text{ and }, C'\}$ where;
\begin{align}
C &= M^2 \pmod n \\
C'&= (M+w)^2 \pmod n = M^2+2Mw+w^2 \pmod n
\end{align}

Now calculate $C'-C = M^2+2Mw+w^2 - M^2 \pmod n = 2Mw+w^2 \pmod n$
Substruct $w^2 \pmod n$ get $2Mw \pmod n$
Divide by 2 and get $Mw \pmod n$.
Find the inverse of $w$ to mod $n$ and multiply it to get the $M$.

in total $$M = (C' - C - w^2) (2w)^{-1} \pmod n$$
Note : when $e=2$ it is not RSA. The below quote form this answer;

  In fact, the Rabin Cryptosystem does exactly that.


Multi Key Encryption but read only part of data Is there a way to encrypt data/document with multiple keys, but every key is only allowed to read/decrypt only a certain part of the document and not the whole document? The document cannot be sub divided into multiple smaller documents for various users.

every key is only allowed to read/decrypt only a certain part of the document

How about encrypting those parts with separate keys?


Rainbow table for DES with all-zero plaintext? Consider the function $F$ from $\{0,1\}^{56}$ to $\{0,1\}^{64}$, mapping the operative bits of a DES key to the ciphertext for all-zero plaintext. How could we organize a rainbow table to invert that function with high probability, low computational cost, and a reasonably-sized table that can be constructed at reasonable cost (beyond the cost of $2^{56}$ DES computations, of course)?

Is there such a table accessible online, in essence breaking DES knowing ciphertext for all-zero plaintext? It may have (had) practical cryptanalytic applications against (obsolete) protocols using single-DES and spitting ciphertext for all-zero plaintext, perhaps under some stimulus.

Credit: this question was inspired by a recent comment by Antikithira.

As a test vector:
$$F(\mathtt{00000000010001010001001100111000100101010111001101110111})=\mathtt{1101010111010100010011111111011100100000011010000011110100001101}$$
or equivalently
$$F(\mathtt{00451338957377}_{16})=\mathtt{D5D44FF720683D0D}_{16}$$
with this example corresponding to the DES key $\mathtt{0123456789ABCDEF}_{16}$.

Generalization: how do we organize a rainbow table of some easily computable, random-like function $F: \{0,1\}^m\to\{0,1\}^n$?

Addition: I'm unfamiliar with rainbow tables in general, so ideally I would like a self-contained answer that covers the basics as applied to this problem:

What parameter(s) do we use to control $\text{table size}\over\text{search effort}$, and odds of search failure if applicable?
How is the table organized?
How do we compute the table, for what expected cost?
How do we search?

Given a function $F: A \rightarrow B$ and functions $R_1, R_2, \dots, R_k:B \rightarrow A$, we can create a chain of length $k$ from a starting point $a_0$ to an end point $a_k$ using $a_i = R_i(F(a_{i-1}))$.

A rainbow table for $(F, R_1, \dots, R_k, k)$ is a collection of chains with end points $(a_0, a_k)$ organized so that searching for chains ending at $a_k$ is cheap.

We use a rainbow table to (try to) invert $F$ as follows. Given $b$, we compute $u_{11}, u_{12}, \dots, u_{1k}, u_{22}, u_{23}, \dots, u_{kk}$ using the equations $$u_{ii} = R_i(b) \qquad\text{and}\qquad u_{ij} = R_j(F(u_{i,j-1})).$$ After computing each $u_{ij}$, we check to see if there is a chain $(a_0, u_i)$ in the rainbow table. If there is, we compute $a_1, a_2, \dots, a_k$ as above and check if $F(a_j) = b$ for some $j$. If so, we have found a preimage of $b$ and we are done. Otherwise, we continue until we have checked all $u_{ij}$.

The idea is that the $R_i$ are very cheap to compute (compared to $F$), so generating a rainbow table for $(F,R_1, \dots, R_k, k)$ with $L$ entries requires storing $2L$ elements of $A$ and costs essentially $kL$ evaluations of $F$ plus the cost of organizing the table ($O(L \log L)$ or something similar?).

Each lookup costs at most roughly $k^2$ evaluations of $F$ plus the cost of $k^2$ table lookups (each $O(\log L)$ comparisons of elements of $A$ or something similar?).

The total cost for $n$ attempted inversions should be dominated by $kL + k^2n$ evaluations of $F$.

The tricky part (the part where I don't immediately know the answer) is determining fraction of elements of $A$ for which $F$ can be inverted. This is determined by the total number of distinct elements present in the chains in the rainbow table.

It would seem that if the $s$ first chains cover a fraction $\epsilon$ of $A$, then the $s+1$th chain will contain an expected $(1-\epsilon) (1-\epsilon/k)/(\epsilon/k)$ "new" elements of $A$ (or $k$ if $\epsilon/k$ is small). (The second term in the product is the expected number of iterations in the chain before it collides with a previous chain at the same index. The first term is the expected number of repetitions.)

This should mean that a rainbow table can cover a significant fraction of $A$.

When $kL$ is not too big compared to $|A|$, I would guess that the probability of inversion is close to $kL/|A|$.

If you are ok with a probability $\epsilon$ of inverting $F$ significantly smaller than $1$:

A rainbow table with parameters $k$ and $L = \epsilon |A|/k$ inverts $n \epsilon$ elements using $\epsilon |A| + k^2n$ evaluations of $F$ and storage of $2\epsilon |A|/k$ elements of $A$.
A straight-forward table for a fraction $\epsilon$ of the elements of $A$ inverts $n\epsilon$ elements using $\epsilon |A|$ evaluations of $F$ and storage of $\epsilon |A|$ elements of $A$ and $B$.
A sequence of brute force searches for a fraction $\epsilon$ of the elements of $A$ inverts $n\epsilon$ elements using $\epsilon |A|$ evaluations of $F$ and negligible storage.

Suppose you have $n=2^{10}$ target keys and have $2^{40}$ octets of fast memory available for the table. A pair of DES keys requires 14 bytes, which gives us $L \approx 2^{36}$. Choosing $\epsilon = 2^{-10}$, we find that $k=2^{-10} \cdot 2^{56} / 2^{36} = 2^{10}$, which means a total work factor of $2^{46} + 2^{30}$ DES evaluations. (If you use slow memory, memory access time will probably be much higher than DES evaluation time.)


Understanding the Inner State of a RNG Based on the BSI evaluation criteria for quality of deterministic random number generators:

K4 – It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.

What is exactly the inner state in simple words? Is it the the very first seed? Also I would appreciate if you explain what is meant by the above rule?
Many Thanks.

I'll use ChaCha20 as an example. It's a stream cipher, but is used as the core of the system random number generator on Linux.
I'll also refer you to this excellent article about how ChaCha20 works as a stream cipher.
ChaCha20 can be used as a fast key erasure CSPRNG. When a caller requests $N$ bits of random data (a single number in the sequence), it's used to generate $N+256$ bits, and the last 256 bits are used as a new key for future requests. (Some systems like Linux additionally XOR in some bits from various system noise sources when they make this new key.)
ChaCha20 works by scrambling a 512-bit block repeatedly, using 20 rounds (broken into 80 quarter rounds) for each $N-256$ bits of output.
The inner state is the 512-bit block that gets scrambled. It consists of a constant value, a counter, a nonce (a second counter in this case), and a key (which is where the initial seed goes).
ChaCha20 is a strong cipher. It's computationally infeasible (read: effectively impossible) to discover anything about the key given only the output.
So if an attacker gets a copy of the inner state used in the generation of a requested number, they know the key used for that particular request, which is the last 256 bits of the previous request's output. But it's impossible to generate the key used for the previous request from any amount of its output, let alone the last 256 bits only, so they can't discover the number returned by the previous request from this alone. Therefore, they can't discover the previous number returned, and from there can't determine any other previous numbers in the sequence.
CSPRNGs other than ChaCha20 may have different sized inner states, but there's generally some fixed-size block that gets scrambled repeatedly in some manner. Part of it will be the seed, part will be other data needed in the computation of the output.


Can I encrypt a message by swapping bits in the text? I have tried out an encryption method, in which I swap bits in the text.
The text length is N bit, then I generate several random number pairs in the range 0..N-1, as [n,k] pairs. After that, I swap the n-th and k-th bits in the message, if they are different, of course. After several swaps the message becomes unreadable.
The message can be decrypted by applying the swaps in the reverse order.
Can this be a good encryption method or is it equivalent to the usual XOR cipher, or even weaker?
For example, I can generate the random number pairs with a pseudo-random number generator, with a starting seed. And the seed can be obtained from a passphrase, for example, an integer hash of the passphrase. Then I can use the passphrase to encrypt the message this way, and the same passphrase for decrypting, as the random number pairs will be the same again, due to the same seed applied at the start.

First problem is you're not specifying at all how many swaps you need to do for a given message length, other than saying it's "several." For an $n$-bit messsage there are $n!$ ways of rearranging its bits, gives a lower bound of $\mathrm{log}_2(n!) = \sum_{i=1}^{n}\mathrm{log}_2(i)$ bits for on how much pseudorandomness you'll need. Rather than analyze a precise number of rounds your random swaps method needs to achieve a good result, however, it's just simpler to substitute in a Fisher-Yates shuffle that'll fairly permute an $n$-item sequence in $n$ steps.

But whatever you do, even if we assume true random bit permutations, the technical answer is that this is straightforwardly insecure because an adversary can easily and reliably distinguish encryptions from random strings by looking whether the number of ones vs. zeroes is the same as their chosen plaintexts. A special case of this is that any message that's only zeroes or only ones encrypts to itself.

Even if we assume the attacker doesn't get to choose plaintexts, they can use this property to test whether a given ciphertext could be the encryption of some plaintext they guess at.  Take for example the binary ASCII codes for these strings:

HAHA ===> 01001000 01000001 01001000 01000001 ===>  8 ones
YEAH ===> 01011001 01000101 01000001 01001000 ===> 11 ones
NOPE ===> 01001110 01001111 01010000 01000101 ===> 14 ones

If I see a ciphertext with 11 ones I can tell that it's definitely neither HAHA nor NOPE, but could still be YEAH.


How to get a speedup linear in the number of iterations on unsalted iterated password hashing? In their 2015 paper "More Rounds, Less Security?" Guo, Jean, Mouha and Nikolić claim in section 5.4 that one can recover a password $P$ given hashes of $D$ different passwords generated from $H^k(P)$ with about $T_1=\frac{2^n}{D\cdot k}$ hash evaluations.

Now I understand that using standard preimage search you are expected to find at least one preimage in $2^n/D$ evaluations of the full iterated hash, so $T_2=\frac{k\cdot 2^n}{D}$ hash evaluations.

The reasoning given for $T_1$ is:

  Now observe that the time complexity can be reduced by a factor of $k$.
  This is because evaluating one password guess requires $k$ evaluations
  of the hash function used inside [the password hash], but every
  additional guess has an additional cost of only one hash function
  evaluation. This effectively speeds up exhaustive search by a factor
  of $k$: given $D$ password hashes, recovering any of them has a time
  complexity of $2^n/(D \cdot k)$.

My question is now (based on my current understanding of the above quote):
Given $H^{i}(P)$ for $i\in\{1,\ldots,k\}$ using only one evaluation of $H$ how does one compute $H^k(P')$ for any $P'\neq P$?

Or asked differently but (hopefully) equivalently:
How exactly does this pre-image search speedup trick work where additional checks after the initial evaluation only cost one hash evaluation?

The only way I see to justify the claim is that the authors are thinking as follows thus it is not for any $P'\neq P,$ but specific $P'$ in that trail:

Compute $H^i(P),$ for $i=1,2,\ldots,k.$ This gives you the hash for $P,$ call it $H_0.$

Now define the sequence $P'_i=H^i(P),$ for $i\geq 1,2,3,\ldots.$

Evaluate $H^i(H_0)$ to obtain $H(P'_i),$ for $i\geq 1,2,3,\ldots,$ at extra cost of one evaluation each. Of course these $P_i'$ are almost certainly distinct until the trail length is comparable to square root of the hash output space.


Ethereum RLPx protocol for inter-node communication - flaws in the encryption Ethereum uses RLPx/devp2p for inter-node communication. The protocol is encrypted using Elliptic Curve Integrated Encryption Scheme (see ref)

Under Known-Issues I found this paragraph:

  The RLPx handshake is considered 'broken crypto' because aes-secret and mac-secret are reused for both reading and writing. The two sides of a RLPx connection generate two CTR streams from the same key, nonce and IV. If an attacker knows one plaintext, they can decrypt unknown plaintexts of the reused keystream.

Q: Can someone please Explain what this means and how this can be exploited by a third party who is able to observe the encrypted communication between two nodes.

Related to: https://ethereum.stackexchange.com/questions/59549/geth-inter-node-communication-devp2p-rlpx-encryption

Firstly, CTR mode. This is a stream mode that allows a block cipher (AES here) to work as a stream cipher.

Given $(k,IV)$ where $k$ is a random encryption key and $IV$ is an  initialization vector, CTR mode works in this way:

For the $i$th message $m_i$ (less than the block size):

To encrypt: compute $c_i=E_{k}(IV||i)\oplus m_i$;

To decrypt: compute $m_i=E_{k}(IV||i)\oplus c_i$;

Now the two streams use the same key and IV, so if the plaintext of $m_i$ in one stream is known by an attacker (e.g. this is a fixed field like a header or something), the attacker can recover the plaintext $m_i'$ in the other stream.

Stream 1: $c_i=E_{k}(IV||i)\oplus m_i$;

I know $m_i$, so I can recover the key stream for this block:

$E_{k}(IV||i)\oplus m_i\oplus m_i=E_{k}(IV||i)$

Then given the ciphertext $c_i' =E_{k}(IV||i)\oplus m_i'$ in the other stream, I can recover $m_i'$ because the keystream used in encryption is the same:

$E_{k}(IV||i)\oplus m_i'\oplus E_{k}(IV||i)=m_i'$


What is an example of a secure sigma proof? I want to implement Threshold Elgamal as described in section 6.3.1 and in the decryption phase each party must broadcast a sigma proof to show that it actually has a valid secret share of the secret key.

I read about Schnorr protocol as a solution for sigma proof but it is said to be insecure, in chapter 5 of the same lecture notes.

What secure sigma proof could I use ?

It would be great if the sigma proof is non-interactive.

Sigma protocols as-is are secure only for honest verifiers. However, they can be easily compiled into full-blown zero knowledge protocols. If you don't want interaction, then the Fiat-Shamir transform suffices, with security in the random oracle model. With interaction, you can do the transform at little cost using commitments based on DDH. For more information on this, you can see this video. If you have Springer Online access, then you can also see this chapter. If you don't have access, then send me an email and I'll send you the chapter.


How could I make a MAC two time secure? Let us assume that a MAC is calculated as $t = a m + b$ with $a,b,m \in \mathbb{Z}_p$, $p$ prime. $a$ and $b$ denote the private generation keys, $m$ refers to the message.

This MAC is then one time secure, but not two time secure. One time secure means that an attacker who learns of one message-mac pair has only a small chance to find a separate message with a valid mac. Two time insecure means that as he learns two pairs, he is then easily able to solve the resulting system of linear equations for the secret $a$ and $b$.

How could the MAC generation scheme be changed to make it two time secure?

I understand that the $am$ and $b$ components are independently and evenly distributed in $[0..p-1]$, as $p$ is prime. Given that, I thought I could add a third component, derived from a newly added part $c$ of the private key, which again is independent and evenly distributed. But I could not figure out how.

First off, obviously, simply using something like $t = a m + b + c$ or $t = a m + b + c m$ does not work, as the new component can be combined with either $a$ or $b$, thus not providing any effective benefit.

Something like $t = a m + b + c m^2$ does not seem to work, as $m^2$ is not evenly distributed in $\mathbb{Z}_p$. (Am I missing something?)

Another idea might be to add a counter to the generation: $t = a m + b + c i$ where $i$ is a message counter. This appears to be two time secure for $p > 2$, but only given that the attacker cannot simply use $p$-apart messages, which obviously share the same $c i$ component. This requirement seem too high to me, so I'm not a fan of this idea.

Something like $t = a m + b + c m^2$ does not seem to work, as $m^2$ is not evenly distributed in $\mathbb{Z}_p$. (Am I missing something?)

You are missing something.  Given two solutions $(m_0, t_0), (m_1, t_1)$ to the equation $t = cm^2 + am + b$ (for unknown $a, b, c$), any third solution $(m_2, t_2)$ will hold with probability $1/p$ (assuming $m_2 \ne m_0, m_1$); if $p$ is large, this exactly satisfies the criteria you're looking for.  You can see that by fixing $m_2$ and considering the possible $t_2$ values between $0$ and $p-1$; for each such $t_2$ value, there is a unique set of $a, b, c$ values that make all three equations work, and as $a, b, c$ were generated randomly (so any no set has any higher probability than any other), this means that all possible $t_2$ values are equiprobable.

This is precisely the insight that makes Shamir Secret Sharing work.

It doesn't matter that $m^2$ isn't equally distributed.  If it really bothers you, you can perform the operations in $GF(2^n)$ rather than $GF(p)$. In $GF(2^n)$, $m^2$ is evenly distributed (but, as above, it's not actually a concern).


How HMAC is calculated for TLS AES_128_CBC_SHA The RFC 5246 defines generic block cipher as follow:

struct {
          opaque IV[SecurityParameters.record_iv_length];

      block-ciphered struct {
          opaque content[TLSCompressed.length];
          opaque MAC[SecurityParameters.mac_length];
          uint8 padding[GenericBlockCipher.padding_length];
          uint8 padding_length;
      };
  } GenericBlockCipher;

The MAC is generated as described in Section 6.2.3.1.

Does HMAC cover IV, padding and padding_length fields ?

Does HMAC cover IV, padding and padding_length fields ?

As stated in 6.2.3.1, for stream and block ciphers,

The MAC is generated as:

  MAC(MAC_write_key, seq_num +
                        TLSCompressed.type +
                        TLSCompressed.version +
                        TLSCompressed.length +
                        TLSCompressed.fragment);

That is, the MAC is done on the plaintext (that's what TLSCompressed.fragment is, if you don't do compression).  The TLS header is prepended, but no other modification is done.  Hence, it does not include the IV, padding or padding_length.


Multi party anonymous key distribution Consider a protocol, wherein Alice wants to send a message $M$ to many friends $F_1, F_2, \dots F_n$, from whom she has (some form of) public keys ($e_{F_i}$, with private key $d_{F_i}$). She does not want her friend Bob ($B=F_1$) to know that she sent the same message to her friend Charlie ($C=F_2$), and vice versa.

Alice wants to send out one single message, as opposed to distinct messages to every recipient. (Think for example a single email message, or publication on a website, as opposed to distinct emails)

One such scheme would be to encrypt the message with a symmetric key $K$, and attach a dictionary of ($F_i$: $e_{F_i}\{K\}$). In this scheme however, Charlie will notice the presence of a key for Bob (and vice versa).
Even when hiding the index $F_i$ in the dictionary, Charlie might be able to find out that Bob is in the list of recipients.

Is such a scheme possible? Is such a scheme possible, without revealing even the number of recipients?

OpenPGP supports an approximation to what you seek, albeit with at best weak privacy guarantees: To transmit the message $m$, Alice picks a session key $k$ and sends $$E_{f_1}(k) \mathbin\| E_{f_2}(k) \mathbin\| \cdots E_{f_n}(k) \mathbin\| \operatorname{AES-CFB'}_k(m),$$ more or less.  Here $\operatorname{AES-CFB'}$ is OpenPGP's bespoke variant of CFB mode.  See RFC 4880, §5.1 for details of how public keys are identified or not.

Decrypting such a message to many recipients is slower, of course, because it requires trying to decrypt every session key encapsulation $E_{f_i}(k)$ with every private key known to the user.  Variants of this scheme with long-term DH-style shared secrets could enable recipients to cache the long-term shared secret under which a per-message session key is encrypted to make this more efficient for many messages.

The privacy guarantees are weak because not every public-key encryption or KEM scheme provides the property called key privacy or key anonymity.
For example, it is feasible for an adversary to distinguish a collection of RSAES-PKCS1-v1_5 ciphertexts (or RSAES-OAEP, but OpenPGP uses PKCS#1 v1.5) under a target public key from a collection of ciphertexts under any other public key, by solving the German tank problem.

You could use a nonstandard RSA-KEM encryption procedure as follows: Pick $1 < x < n$ uniformly at random, compute $y = x^3 \bmod n$, reject and start over if $y \geq 2^{\ell - 1}$ where $2^{\ell - 1} < n < 2^\ell$, and otherwise yield $y$ as the encapsulation of $k = H(x)$.  The encapsulation $y$ is uniform random in $\{2,3,4,\ldots,2^{\ell - 1} - 1\}$, so it reveals nothing about which $\ell$-bit modulus is used.*  This variant is slower than standard RSA-KEM, but the expected number of trials to pick $x$ is under 2, and decryption remains the same as standard RSA-KEM.  Bellare et al. suggest a corresponding variant of RSAES-OAEP which they dub RAEP.  The security is essentially the same as RSAES-OAEP.  Probably the same could be done in OpenPGP with RSAES-PKCS1-v1_5 by trying a different session key, but you are limited to a single recipient in that case.

Other cryptosystems may naturally provide key privacy, such as ECIES and variants where the appendix is a uniform random element of a standard group.  But it's not a standard criterion for public-key encryption/KEM schemes, so it takes further scrutiny than standard security advertisements to be confident that any particular cryptosystem you use provides or can be adapted provide key privacy.

* Note that there are many ways to generate RSA keys.  In an attempt to generate a 2048-bit modulus $n$, some methods pick 1024-bit primes $p$ and $q$ uniformly at random, and with nonnegligible probability will yield for $n = p\cdot q$ a 2047-bit modulus instead of a 2048-bit one.  In this case, by rejecting $y \geq 2^{\lfloor\lg n\rfloor}$ you would partition the anonymity set of recipients into two: the 2047-bit moduli and the 2048-bit moduli.  If this concerns you, you could (say) reject $y \geq 2^{2046}$ for any 2047- or 2048-bit moduli.  This will increase the rejection rate, but at worst it will double.


Can NORX be used as a general purpose hash function? In general terms, NORX works combining a cryptographic hash function and an stream cipher. At the end of an encryption operation you end with a ciphered message plus its authenticated hash. If you call AEADEnc() whith a zero length secret and postfix message, you basically get a hash function for each $(key, nonce)$ pair.

My question is, given a fixed and public $(key, nonce)$ pair, can NORX AEADEnc() work as a secure cryptographic hash function?

What security goals are you hoping for?

If NORX is a secure nonce-based AEAD as advertised (which it may or may not be—CAESAR dropped it and it's not widely deployed, so there's little incentive to study it), then what it will guarantee, as a nonce-based MAC, is antiforgery.  Specifically, no cost-limited adversary who can query an oracle ‘NORX-MAC’ for a single message under a single nonce can forge an authenticator for another message under that nonce.

But, for this security goal, there are much faster choices like Poly1305-AES.  If you want a stronger security goal, like a nonceless MAC or a PRF such as HMAC-SHA256 or keyed BLAKE2s or KMAC256 are conjectured to be, NORX may or may not provide that: it's not advertised as a security goal of NORX.  If you're looking for collision resistance, it's unlikely that you'll find it in NORX as is.


How to break a 32 bit block cipher without key? From what I know Skip32 is the only 32 bit block cipher and I heard its not secure. What do I do or which tool do I use to break a 32-bit block cipher?
I did search for this but all I find is attacks for DES(64 bit) and AES(128 bit) but none for Skip32.

The block size does not directly determine the security of a block cipher. Even with a 32 bit block cipher the number of possible permutations is 2^32!, a stupendously big number.

Small block sizes are however cumbersome to use in secure modes of operation as the input is limited. For instance, it would be easy to have repeating counters in counter mode encryption.

So attacks generally rely on low key sizes or - of course - the construction of the algorithm itself. Now for Skipjack there don't seem to be any known attacks. The key size is not very large, but brute forcing it seems still (just) out of reach.

Skip32 seems to use the same key size. It seems to use largely the same structures and 24 out of the original 32 rounds. Skipjack has only been attacked successfully for 16 rounds. So it is very possible that it is secure. The problem is that this cipher doesn't seem to have any paper or design document assigned to it. Basically there is just code and comments. This is a likely reason that no crypto-analysis can be found.

So basically: there is no generic attack against 32 bit block ciphers. Skip32 could well be secure, but as it hasn't been analyzed, nobody knows for sure. AES and DES on the other hand are well used and analyzed (and survived pretty well under those circumstances).

If you want to attack it, it might be best to check if the the way it is used is secure or not, because the 32 bit block size will certainly influence that.

If you just want to encrypt 32 bit values you should also have a look at Format Preserving Encryption (FPE). Those modes of operation can use standardized ciphers while achieving the same goal (although possibly at the cost of efficiency).


Is using a broken SHA-1 for password hashing secure? Recently the hashing collision issue of SHA-1 was discovered. Identical hash values for 2 separate PDF files were generated. Does that make SHA-1 any unsafe for using it only for password hashing?. The probability of two different password to match is still negligible, right?

SHA-1 in itself was never safe for password hashing. The hash algorithm itself doesn't have a work factor parameter nor does it have a salt as input. These are requirements for run-of-the-mill passwords that do not have as much security as a good symmetric key.

For this reason password hash algorithms have been invented, also known as password based key derivation functions (PBKDF). The difference between a password hash and a PBKDF is mainly how the result is used: directly as a password hash to compare with a stored password hash or as symmetric key for input in a symmetric cipher or MAC algorithm.

Well known password hash algorithms are PBKDF2, bcrypt, scrypt and of course the already mentioned Argon2. The latter two also contain options for configuring memory hardness, to overcome hardware based attacks.

The above functions can often be configured using a hash function. For instance PBKDF2 requires a secure hash as configuration parameter, and it (kinda) defaults to SHA-1.

As long as SHA-1 doesn't have direct collisions it could still be secure for this purpose. Even if there were collisions, it is unlikely that this would compromise the security of a password database.

Due to the high number of iterations it is even less likely that a password hash is reversed, i.e. that the one-way property of the total hash doesn't hold. This property is of course the most important one for the password hash.

For this reason it's probably OK to keep SHA-1 as configuration parameter for some specific password hash algorithms that require it.

However attacks just get better, never worse. So if possible, even in the above scenario, you should move away from SHA-1 to SHA-2/SHA-3. Or choose a password hash function that doesn't rely on a secure hash at all.


Operation on elliptic curves Let $Y = xG$ be a point on an elliptic curve, $G$ the generator point and $x$ a scalar. Without knowing $x$, is it possible to calculate $x^nG$, being $n$ a natural number?

It is believed to be hard. In fact, even given $G, xG, x^2G,\dots,x^{n-1}G,x^{n+1}G,\dots,x^{2n}G$, you still can't compute $x^nG$; this is called the Generalized Diffie-Hellman Exponent assumption (see Fig. 1 here).


Usefulness of OAEP with ECC Does OAEP make sense for use in an ECC ElGamal cryptosystem? The way I see it, OAEP makes questionable sense even for RSA because even though it's a "all or nothing" transformation, many RSA ciphertexts already have to be split up into multiple blocks so that no one block exceeds the size of the modulus.

Yes, it can make some sense, and I've seen it in practical use. But beware that you can only encrypt very small plaintext and that's only after you make adjustments to the MGF-1 scheme to use a smaller hash (the leftmost bits of an existing hash, for instance).

For a generic cryptosystem you could use a large (512 bit) curve and use hybrid cryptography to get around the small payload size. But for a generic cryptosystem you are much better off using ECIES to accomplish the same thing.

I would only use El Gamal / OAEP if the ElGamal encryption has specific properties that you want to use.


How should I prove this protocol? I'm recently reading Berry Schoenmakers's Lecture Notes Cryptographic Protocols (page. 53) and confused about this following question:

  Let $g$, $h$ denote generators of a group of large prime order $n$
  such that $log_gh$ is unknown to anyone. Design Σ-protocols (and prove
  correctness) for the following relations:

  {($A, B; x, y, z$) : $A = g^xh^y,B = g^{1/x}h^z, x \neq 0$};

My prove intuition is using Okamoto's protocol for $A = g^xh^y$ and $B = g^{1/x}h^z$, then how to prove the relation between $x$ in $A$ and $1/x$ in $B$?
Or is there any other way to prove it?

The two previous answers certainly solve the problem. Soundness of Geoffroy's protocol is fine indeed, but there is the appearance of the witness $x$ in the computation of the announcement $(A',B')$ as $B'=g^{r_x/x} h^r$. This can be avoided, however, and at the same time one can find the protocol maybe in a bit more natural way as follows.

Starting with $A=g^x h^y$ and $B=g^{1/x} h^z$, we see that $B$ is a Pedersen commitment
to the (multiplicative) inverse $1/x$ of the committed value $x$ in the Pedersen commitment $A$. So, $x$ appears both in $A$ and $B$ and these two occurrences need to be connected somehow. EQ-composition is a very effective way to accomplish this, but we cannot directly apply it to exponents of the form $x$ and $1/x$. A simple way out is to move $x$ around a bit in the equation for $B$ by raising both sides to the power of $x$, such that we get:
$$ A=g^x h^y,\qquad g=B^x h^{-zx}.$$
We can now apply EQ-composition to the factors $g^x$ and $B^x$, but one may wonder about the new factor $h^{-zx}$ which also depends on $x$. Fortunately, such a factor causes no problems because we can think of $h^{z'}=h^{-zx}$ as a factor that is independent of $x$; it's like replacing $z$ with $z'=-zx$, which is fine because this is a one-to-one transformation for nonzero $x$.

For the $\Sigma$-protocol we get:

Prover sends announcement $(a,b)=(g^u h^v, B^u h^w)$ with $u,v,w\in_R\mathbb{Z}_n$.
Verifier sends challenge $c\in_R\mathbb{Z}_n$.
Prover sends response $(r,s,t)=(u+c\,x, v+c\,y, w-c\,z\,x) \bmod n$. Verifier accepts if $g^r h^s = a A^c$ and $B^r h^t = b g^c$.

It is instructive to see why special soundness holds. So, let's consider two accepting conversations $(a,b;c;r,s,t)$ and $(a,b;c';r',s',t')$ with $c\neq c'$. Then we find:
$$\begin{array}{cl}
 &  g^r h^s = a A^c,\ g^{r'} h^{s'} = a A^{c'},\quad B^r h^t = b g^c,\ B^{r'} h^{t'} = b g^{c'}\\
 \Rightarrow& g^{r-r'} h^{s-s'} = A^{c-c'} ,\quad B^{r-r'} h^{t-t'} = g^{c-c'} \\
 \Leftrightarrow& A = g^{\frac{r-r'}{c-c'}} h^{\frac{s-s'}{c-c'}},\quad B = g^{\frac{c-c'}{r-r'}} h^{-\frac{t-t'}{r-r'}}.
\end{array}$$
Here, we are using that $r\neq r'$ holds as well: otherwise we see that $B^{r-r'} h^{t-t'} = g^{c-c'}$ is equivalent to $h^{t-t'} = g^{c-c'}$, and we would have $\log_g h = (t-t')/(c-c')$, contradicting the assumption that $\log_g h$ is unknown.
Hence, a witness is obtained as $x=(r-r')/(c-c')$, $y=(s-s')/(c-c')$, and $z=-(t-t')/(r-r')$.
Clearly, $x\neq0$ and $B=g^{1/x} h^z$ holds, as well as $A=g^x h^y$.

The same line of reasoning can be applied to show special soundness for Geoffroy's protocol.


NTRU crypto from unseen.is; myth busting help I am always on the look out for privacy enhancing technologies. I stumbled upon the service from unseen.is. I had a look at their site (specifically here) and even though I lack knowledge there are a few early warning signs:

  a former security contractor told us "if it's publicly available, it's cracked"

I think this is untrue?

  extremely strong but not widely available encryption

I thought extremely strong = widely used/available?

  We've use only super strong NTRU encryption for public key exchange that is believed to be resistant to even quantum computing attacks

Quantum computing doesn't even exist in any (realistically) applicable way, so I think this a bold statement?

I contacted the service asking about their encryption algorithm, how they exchange keys, if they have cryptographers on their team and got this response:

  For the chat we use NTRU for the key and xAES for the message, 4096 bit key.  For email we are using PGP at the moment 2048 bit or 4096 bit.  The email will get upgraded to the same encryption as the chat at some point.  Probably this summer.

I also found out that NTRU is in fact a known standard and has a wikipedia article although I am suspicious of the concept.

Simply put my question is this: would this service and their claims fall under "have no clue" or is it my lack of knowledge and could this be a very decent, functional service?

Update: the website's FAQ (or this recent archive) states about xAES (an AES replacement with 4096-bit key) something that seems falsifiable:

  we add an advanced symmetrical encryption which is very easy to use with keys 16x longer than those found in AEA256, an industry standard. According to our engineers, this will take 23840 times longer to crack than aes256, which is commonly known as "military grade" encryption.

I'll comment only the statement referring to an AES-256 replacement with 4096-bit key:

  According to our engineers, this will take 23840 times longer to crack than aes256

Bob writing that is not able to correctly transcribe even the numbers that engineer Alice allegedly spelled: most likely, $23840$ is intended to be $2^{3840}$, which is the ratio $2^{4096}/2^{256}$ of the number of 4096-bit keys to that of 256-bit keys. For reasons that I'll detail, that ratio of number of keys is irrelevant. Bob is incompetent at crypto, or totally gullible, or dishonest (I mean or as inclusive, not xor). And if anyone left Alice with the impression that $2^{3840}$ was a meaningful number, Alice is incompetent or dishonest, and that does not spell well for the system or code Alice designed or wrote.

Thus at least one holds: The FAQ's author is dishonest; it is dangerous to trust the engineer cited by the FAQ as advisor.

AES-256 is a symmetric cipher with a huge key of 256-bit. Remember the tale of the man who asked the sultan as reward for his good services 1 grain or rice on a first square of a checkerboard, 2 on the second, 4 on the third.. and got impaled for having asked $2^{64}-1$ grains of rice, which is orders of magnitude more than the worldwide yearly rice production nowadays? Well, 256-bit instead of 64-bit is like this man asking a checkerboard with 256 squares instead of 64. 64-bit of key was considered quite safe against key enumeration in 1970, and the reasonable optimists about the power of Moore's law agree that 1 year does not quite give 1 bit when it comes to brute force, and that whatever exponential trend there has been has already started to slow. Meaning 128-bit is still safe from key enumeration for the next two decades, and 256-bit is safe from key enumeration for whatever matters to man (the later is even with quantum computers running full gear). Increasing key size to 4096-bit serves no purpose towards the threat of key enumeration, and it is pointless to consider the ratio $2^{4096}/2^{256}$ of keys for whatever security consideration or practical purpose.

Increasing the key size of a block cipher could conceivably serve some other purpose (like making side-channel attacks harder, although the opposite could also occur). But if that was the intend, the extra protection obtained (if any) would not be anywhere near $2^{3840}$, or quantifiable to 4-digit precision (if we trust $23840$).

Fact is, past a certain key size, the time (as in the quoted statement) or effort it takes to recover a key does not depend so much on the key size (at least, not as $2^\text{size}$), but on how the key is generated in the first place, and how well it is protected from later leakage. Over that limit (much less than 128-bit nowadays), a bad RNG, careless storage, a buffer overflow, another side-channel (timing, power consumed..), a fault-injection attack, younamit, are more likely threats to a key's confidentiality than key enumeration is.


AES-CBC based hashing This question is purely hypothetical.

The idea is to generate variable sized hashes (multiple AES block sizes) like so:

encrypt plain text
encrypt plain text + cipher text from 1.
XOR cipher text blocks over hash blocks.

Step 1 and 2 can be programmatically done as one step.

Step 2 causes at least the second half of the cipher text to be different for each different plain text even if only the last block of plain text is different (changes in the plain text have no effect on cipher text blocks from before the change).

The key and IV are the same for each message.

Apart from being slow, is this a valid way to generate secure hashes?

If I understood the description correctly, with a 4-block (512-bit) hash output $H_0\ldots H_3$, message $M_0\ldots M_3$ of the same size, a fixed public value of the AES key, and all-zero IVs and initializations (because comments allow that), the steps are

$C_0\gets E(M_0)$
$C_1\gets E(M_1\oplus C_0)$
$C_2\gets E(M_2\oplus C_1)$
$C_3\gets E(M_3\oplus C_2)$
$C'_0\gets E(C_0\oplus C_3)$
$C'_1\gets E(C_1\oplus C'_0)$
$C'_2\gets E(C_2\oplus C'_1)$
$C'_3\gets E(C_3\oplus C'_2)$
$H_0\gets C_0\oplus C'_0$
$H_1\gets C_1\oplus C'_1$
$H_2\gets C_2\oplus C'_2$
$H_3\gets C_3\oplus C'_3$

I have noted AES block encryption and decryption with the key $X\mapsto Y=E(X)$, and $Y\mapsto X=D(Y)$.

I'll show that knowing $H_0$, $M_0$, $M_1$, $M_3$, we can find $M_2$, which counts as a break of a model of the hash as a Random Oracle, and is tantamount to a first-preimage attack.

$C_0\gets E(M_0)$, per 1.
$C_1\gets E(M_1\oplus C_0)$, per 2.
$C'_0\gets C_0\oplus H_0$, by inverting 9.
$C_3\gets D(C'_0)\oplus C_0$, by inverting 5.
$C_2\gets D(C_3)\oplus M_3$, by inverting 4.
$M_2\gets D(C_2)\oplus C_1$, by inverting 3.

$H_1\ldots H_3$ can be recomputed trivially since we have $M_0\ldots M_3$.

That hash truncated to its first 256-bits is insecure against collision. That's contrary to a good 512-bit hash like SHA-512, which we can truncate to 256-bit and still get collision-resistance with work for the best known attack about $2^{128}$ compression functions. Sketch of that partial collision: we start from an arbitrary message, change $M_2$, then $M_3$ so that $C_3$ is restored to what it was. These message changes leave $C_0$, $C_1$, $C'_0$, $C'_1$ unchanged, therefore $H_0$ and $H_1$ unchanged.

That attack can be extended to work with the padding and hash size described in comment, to obtain a collision in the first 3712 bits of a 4096-bit hash. Sketch: message and hash are 32-block, we alter $M_{29}$, and $M_{30}$ to return $C_{30}$ to what it was. That leave $H_0\ldots H_{28}$ unchanged.

What's the point of making a wide hash, if most of it is insecure against collision?

Another issue with the construction is that it requires memory size about as the message size in order to keep the result of the first pass. Something requiring about as much memory as the hash size is desirable in many applications.

Making the message a few times the hash size gives more freedom, and I'll walk back from speculating what it might allow.


Factorizing a handiwork number $n$ in two prime factors I have generated two primes $r_0$ and $s_0$ with same bit size $\le 64$, then make another two primes as follows: choose constant $k$ and define $$r_i = r_0 + \alpha_i, \quad 1 \le i \le k, \quad 0 \le \alpha_i \le 1000$$ and
$$s_i = s_0 + \beta_i, \quad  1 \le i \le k, \quad 0 \le \beta_i \le 1000$$
I have chosen $\alpha_i$ and $\beta_i$ such that both p and q are prime,
$p = 2\times r_0\times r_1\times\cdots\times r_k + 1$ and $q = 2\times s_0\times s_1\times\cdots\times s_k + 1$. Can we factor $n = p \times q$ with knowing above facts?

The number you constructed is somewhat vulnerable to Pollard's p-1 method. If $r_0$ and $s_0$ are 64 bit long primes, then these are the largest factors in $p-1$ and $q-1$. The method works when $p-1$ (or $q-1$) is powersmooth for some "small" $B$ (choosing $B$ as $64$ bit number isn't that practical - the expected runtime of the algorithm is $O(\log^2(n)B \log(B))$).

In your question you wrote $r_0$ and $s_0$ have less than $64$ bit. If it is actually much smaller, the $p-1$ method will become viable.

Regarding the numbers in the comment: Those are $6\cdot 64 = 384$ bit primes? That is not an acceptable length for RSA - if that was your intention. According to the latest recommendation on keylength.com, today's fatoring moduli should have $2000$ bits at least, meaning you need primes with $1000$ bit each.


Message lengths with AES CTR mode? Im working on my own AES implementation as a personal educational exercise (not for production use), and a book im using as a resource states:

  In the case of CTR, we are merely XORing the output of the cipher
  against the plaintext. This means there is no inherit reason why the
  plaintext has to be a multiple of the cipher block size. CTR mode is
  just as good for one-bit messages as it is terabit messages.

I dont understand the author's statement. In my implementation im planning on having a 16 byte IV/counter, with 12 bytes being the random IV, and 4 bytes for the counter. In pseudocode, something like this:

byte [] CTR_encrypt(byte [] key, byte [] plainText){
    byte [16] IVAndCounter;
    nPlainTextBytes = plainText.getLength();
    int blockCount = ceiling(nPlainTextBytes / 16)
    for(int i = 0 ; i < blockCount ; i++){
        byte [???] cipheredIVAndCounter = AES(key, IVAndCounter);
        IVAndCounter++;
        byte [???] cipherText = cipheredIVAndCounter XOR plainText;
        byte [???] cipherTextComplete = cipherTextComplete + cipherText;
     }
     return cipherTextComplete;
}

I understand why why you wouldn't have to pad say the last block of plaintext, that might not be 128 bits long, but you still have to divide the plaintext into 128 bit blocks in order to XOR it with the 128 bit ciphered IV/counter don't you? You cant just XOR the 128 bit ciphered IV/counter with the whole plaintext, as that would leave much data unencrypted? That is, the plaintext, must be 128 bits or less for CTR mode?

Maybe im missing something. I looked at this question: Why doesn't CTR mode require blocking? , but still dont get it, and feel if anything more confused after reading it.

Well, lets try to take a concrete example:

Suppose that you have a 142 bit message that you need to encrypt with CTR mode.  What do you do?

Well, you generate the first 128 bit block with AES; you take the first 128 bits of the message, exclusive-or the two, and that's the first 128 bits of the ciphertext.

Then what?  Well, you have 142-128=14 bits of plaintext left.  So, what you do is generate the second 128 bit block with AES; you then take the first 14 bits of that, exclusive-or that with the 14 bits of plaintext, and that gives you the last 14 bits of the ciphertext.  And, what do you do with the remaining 128-14=114 bits of AES output?  Well, you discard it -- you don't need it.

If the decryptor does precisely the same logic, he will transform the 142 bit ciphertext into the original 142 bit plaintext.

Does this make things clearer?


Analysing communication complexity of a protocol My question is more about the practical side of designing crypto. protocols and it is related to complexity. So, if you think it's irrelevant to this forum please kindly let me know and I will remove the question.

In many crypto. protocols the communication cost is very important. In the following, I consider a client-server protocol where the server computes a single value and sends it to the client. Assume the protocol requires modular arithmetics at a server-side on a finite field of size 120 bits, i.e. $\mathbb{F}_p$, where $|p|=120-bit$. Assume we have improved the previous protocol and now we can work on a smaller filed, e.g. $|p|=80-bit$.

As we know we cannot say the communication cost has been reduced by $40$ bits, as the value can be $1$ or  $119$ bits value, because it involves a modular operation.

Question: How do we analyze/argue the communication improvement of the above protocol?

(Revised based on poncho's comment.)

If p is of 120-bit length, then any field element should better be sent with 120 bits. If you want to send, say 1, with a 1-bit message, then this reveals the element's length and adds the computation complexity of constructing variable-length messages for different elements. Besides, only half of the field elements may have leading 0s, so sending messages with variable lengths does not save much communication bits.

As for the communication complexity, it depends on what message you are sending and may not be linear to the field size.


Verifiable, Distributed Secret Santa Assignments My family was planning a secret santa and I thought about how I might write a little web app to dole out these secret assignments. But the downsides to this approach are obvious: there's no way for the users to know that I'm a) generating the results randomly and b) not snooping on the (secret) assignments myself.

In the real secret santa, there's no central authority giving out pieces of the assignment. Rather, there's a process by which each user draws names out of a hat and is trusted to redraw if they pick up a name violating one of the constraints (themselves or sometimes a spouse). While drawing, each user is trusted/observed to not be peeking into the hat and only redrawing under invalid conditions.

So my question is: under a message-passing framework, what scheme requires the minimal amount of trust, but produces a valid game where nobody knows the other assignments?

The closest I've been able to achieve is a ring system where a arbitrary starting client draws a random, valid assignment for themselves and then sends that assignment to the next one in the ring. Then this user randomly draws a valid assignment which is not in conflict with the previous assignment, ORs those two together and then sends it off to the next client. This could be repeated until a valid total assignment is generated (some assignments become invalid towards the end eg: the user at the end receives only one name: their own).

This is pretty sub-optimal though as the first and last assignments can be computed by the second and second-to-last users respectively. In addition, each user must be trusted to

Draw random names
Keeping the first valid assignment
OR-ing their assignment with the previous assignments and sending it off

I'd say the 2nd and 3rd are shared with the physical game (you're trusted not to throw multiple names in, take multiple names out etc...) but it's the 1st condition which I can't seem to eliminate (or verify).

Forgive me if this is a silly question, but I had fun pondering this while laying in bed for a few minutes and wondered if someone else might have any insights.

Thanks!

Reform the problem. Instead of each participant picking their givee (which they give to), have them select a giver (which they receive from).

Each participant randomly generates a number (appropriately large) and anonymously submits it (e.g., via the tor network) to the site. This number represents them as giver.
After all participants have entered, the site publishes the list and participants (1 at a time, in no particular order) select (and remove) a random number from the list, linking it with their public name as a recipient to the giver-id.
After all participants have selected a giver-id for themselves, the validity criteria is evaluated: Each participant observes the specific co-participants with whom they conflict (i.e. immediate family members). If a conflicting co-participant possesses the observer's giver-id, that observer anonymously (via same channel as in step 1) registers a conflict.

If no conflicts occur, each participant now knows to whom a gift should be given: the co-participant possessing their giver-id.
If one or more conflicts occur, start over at step 2 with the restriction that participants cannot chose the same giver-id as before.
If all combinations are exhausted, start over at step 1 by re-choosing giver-ids.

The probability of success and/or expected iteration count is left as an exercise for the reader.


Implementing forward secrecy in OpenPGP with public key authentication I am trying to consider the feasibility of implementing an encrypted file sharing system, which both provides forward secrecy but also allows public key verification. I am stuck on the marriage between these two requirements that hopefully someone can help me out with.

In order to provide forward secrecy, I think a new random keypair should be generated for every file transfer request rather than two users sharing long-term public keys in advance. That way, if a private key for a particular file share is somehow compromised, it would only compromise that one file and not all of the files ever sent from that user.

However, the creation of a new keypair for every file share introduces a problem with public key verification. Traditionally speaking, the fingerprint of a public key should be verified in person and would remain verified for the lifetime of the keypair. If a new keypair is generated for every file share, then that means each new public key needs to be verified in person, which is infeasible.

Is it possible to utilize unique keypairs for every file share for forward secrecy while also securely verifying a public key is sent from the correct user only once?

Note that the system is meant for asynchronous file transfer, meaning the encrypted data would be uploaded to the cloud temporarily until downloaded by the recipient. However, file share requests would include a mandatory expiration date.

I'm going to describe two options that you have. There may be more that I don't know about.

The first is to use long-term signing keys to sign public diffie-hellman keys. Upload a bunch of those to the cloud. Then when someone wants to share a file with you, they:

download your "next" signed public diffie-hellman key
verify the signature using OpenPGP, abort if it fails
generate their own new public diffie-hellman key
use your "next" key to generate a shared secret key (using their private diffie-hellman key), encrypt the file with that (you can actually use OpenPGP for this too, it would be the symmetric key for encryption)
sign their new public diffie-hellman key with their long term secret (using OpenPGP)
upload their signed public ephemeral diffie-hellman key, an index describing which of your temporary public keys they used, and the encrypted message
delete their new public diffie-hellman key, etc.

When you come along later to download the file, you:

download everything they uploaded in #5
check the digital signature using OpenPGP, if it fails abort
use your temporary private key for the given index to compute the shared secret key
decrypt the file
delete your temporary private key, their signed temporary public key, etc.

This is basically what Open Whisper Systems does for encrypted text messages.

Your other option is to throw away OpenPGP and do what is described in A Forward-Secure Public-Key Encryption Scheme and discussed in this answer*.

*Okay, that answer does mention my first proposal too as a "trivial (and hence awful) solution". I've added more detail and the link to Open Whisper Systems. Since Open Whisper Systems is doing it, it can't be too awful, right?


Factoring two RSA modulus with known $|p_1 - p_2| < \ell $ I have two 1024bit RSA modulus $N_1 = p_1q_1$ and $N_2 = p_2q_2$ such that $0 <|p_1 - p_2| < \ell$, and $\ell$ is at most 64bit integer. Can I factorise $N_1$ and $N_2$?
What's the answer when $p_1$ and $p_2$ are same $\alpha$-bit primes?

Outline of a elementary attack:

if $\mid p_i-q_i \leq 2^s$, we can write for each $p_i=a.2^s+\tau_i$, with  $\tau_i \leq 2^s$, and we can imagine that if we determine the integer a, we can factor $N_i$ by a brute force attack.
We know that $p_i$ have exactly the same bit size and if $N_i$ have exactly the same bit size (n=1024, 2048, ... s=64), the sizes of $q_i$ could differ by at most one.

Let $r=\frac{a.2^s+\tau_1}{a.2^s+\tau_2} \approx 1 + \frac{1}{a} \pm \epsilon$.
And $\rho=\frac{N_1}{N_2} \approx (1 + \frac{1}{a} \pm f(\epsilon))\times \frac{q_1}{q_2}$ is a rational number which can be determined with a infinite precision.

Then by the examination of the bit of this ratio we can get information on the unknow number a, and hope to success in the factorisation Pb, in complexity less than the general know attacks.

Probably with the help of LLL algo we can enhance the attack.


What is the most efficient 1-out-of-N Oblivious Transfer construction described in current literature? I have been studying Oblivious Transfer for my bachelor's thesis and have been surprised at the number of variations of OT.
From what I've read so far, the constructions proposed by Naor and Pinkas in "Efficient Oblivious Transfer Protocols" and "Oblivious Transfer and Polynomial Evaluation", as well as Tung Chou and Claudio Orlandi's construction proposed in "The Simplest Protocol for Oblivious Transfer", but I am not sure.
I will continue to research this topic and any feedback is appreciated.

It depends if you want many instances (like 1 million) of OT, or just a few.
For a small number of OTs, I would recommend looking at our very recent paper:

McQuoid, Rosulek, Roy: Minimal Symmetric PAKE and 1-out-of-N OT from Programmable-Once Public Functions, CCS 2020.

We're not aware of other protocols whose communication is independent of $N$.
For a large number of OTs, you would use some kind of OT extension approach. The leading OT extension protocol for 1-out-of-N is:

Orrù, Orsini, Scholl: Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection, CT-RSA 2017.


How to choose the integer m in the general number field sieve (GNFS)? Given an integer you want to factor $N$, GNFS starts by selecting a monic irreducible polynomial $f \in \mathbb{Z}[X]$ and an integer $m$ such that $f(m) \equiv 0 \text{ mod } N$. In practice, if $m$ is chosen first then $f$ can just be chosen to be the $m$-base expansion of $n$, which is simple to compute. But how is $m$ chosen relative to N?

For anyones who's interested - From this paper

http://scholar.lib.vt.edu/theses/public/etd-32298-93111/materials/etd.pdf

I found that it's best to find the degree of the polynomial you're going to be using based on the number of bits in $N$. Let k = $log_2N$ Briggs gives experimental bounds

$d= 5$ for $k \geq 110$

$d= 4$ for $80 > k > 110$

$d= 3$ for $50 > k \geq 80$

And doesn't say for $k \leq 50$, probably because GNFS is not the fastest for numbers that small.

Then you pick a $m$ such that $m^d$ is close to $N$. Then you find the base $m$ expansion of $N$ and obtain $f$ from that. This guarantees that $f(m) \equiv 0$ mod $N$


Is the use of a 4-round Blake2b permutation in OPP justified? The  MEM-AEAD construction uses a 4-round Blake2b permutation in masked Even-Mansour mode as a (tweakable) block cipher.

4 rounds of the Blake2b permutation are already broken to my knowledge.  Why are the designers justified in their choice?

4 rounds of Blake2b is essentially equivalent to 8 rounds of ChaCha in terms of complexity (a Blake2 round is close to a ChaCha double-round), and that has not yet been broken. Like Richie Frame wrote in a comment, NORX also claims to get away with 4 Blake2 rounds.

One reason ciphers get away with less is that in hash functions all inputs are known and (except for constants) under the attacker's control. In ciphers the key is secret and, unless you take into account related-key attacks and such, not under the attacker's control.


Using ECDSA keys for encryption I know that ECDSA is used for signature only, but I wonder if I can use the public/private Elliptic Curve keys for encryption too.

I have ECDSA SSH public keys and I wonder if I can use them to encrypt data that only the matching machine could decrypt, writing the proper software.

Pointers welcomed.

Of course you can use Elliptic Curve cryptography to do public key encryption, that is, a method with a public key and a private key; anyone with the public key can encrypt, but only someone with the private key can decrypt.

One way would be to use the Integrated Encryption System.  It's does most everything for you (allowing the encryption of arbitrary sized plaintext efficiently, and throws in an integrity check as well).

However, in your case, I do see two potential pitfalls:

If all you got is some software that verifies an ECDSA signature, I don't know how that could be used to generate ECIES ciphertexts - or any other type of ciphertext.  Something that verifies a signature may only produce one bit of output ("it verified" or "it didn't"); it does not need to export any of its internal computations.  On the other hand, if you do have something that does a 'point multiplication' - and you don't mind putting together everything else ECIES needs to run - this may not be an issue for you.
I also wouldn't recommend you use their existing ECDSA keys with that scheme; it doesn't look like it should cause any weaknesses. I  mean that I don't believe that an attacker could send them a 'ciphertext' that, if they decrypt it and reveal the plaintext, that it would enable the attacker to generate an ECDSA forgery; I don't believe that someone could ask for a specific message to be signed, and use that signature to decrypt an ECIES-encrypted message); it however still makes me nervous.  Good crypto hygiene says to use a key for only one purpose (unless there's a proof somewhere that it is safe for both uses).

Instead, if possible, I would suggest that the devices create a separate encryption key; generating EC public/private key pairs are cheap.


Can Key-Encryption Key (KEK) be symmetric? This from Cryptography course from Coursera:

Key wrapping or encapsulation using a KEK can be accomplished using
either symmetric or asymmetric cipher

For my information KEK solves the key distribution issues with symmetric keys, so only the involved party can decrypt the cypher with their private key, but doesn't using symmetric KEK for distributing symmetric session keys raises the same distribution issues?

Yes, and Key-Encryption Keys often are symmetric. When they are, they do not bring the benefits of asymmetric cryptography; in particular, anyone with the KEK and passively eavesdropped ciphertext can decrypt the distributed keys. That does not make use of symmetric KEK pointless:

KEK would typically be distributed, stored and used with more precautions (procedural checks, maximum volume encrypted..) than the keys they encipher. Therefore, even if compromise of one of the distributed key was likely (e.g. because some attack has a low probability to recover a distributed key, and many keys are distributed), that won't compromise the other distributed keys or the material they protect, thanks to the key distribution under KEK.
KEK can be long-lived (year) when the keys it enciphers can be short-lived (day). Therefore, the serious inconvenience of secure distribution of the KEK (e.g. by trusted courier) needs to occur only seldom, and other keys can be distributed electronically, and frequently. Frequent change of keys not only reduces the impact of a key leak (see above), it might drastically reduce it's probability to occur (e.g. in attack scenarios that requires many uses of a given key to succeed).


Why is the discrete logarithm problem assumed to be hard? This might be a quite stupid question: since a naive brute force algorithm to solve the discrete logarithm problem will only take O(n) time for a group G with order n, why is it assumed to be hard to solve? Doesn't hard mean no polynomial algorithm to solve in the context of cryptography?

While $O(n)$ is linear in the order of the group, what matters is actually the computational difference between the exponentiation and the discrete logarithm. The exponentiation is not in $O(n)$ but instead in $O(\log(n)) =  O(|n|)$ (e.g. expoentiation with square and multiply has $|n|$ multiplications and at most $|n|$ squaring operations).

Therefore, the basic consideration for $n$ should not be the number of group elements, but its logarithm (which is linear to the length of the numbers. In order to avoid the question: This is valid for any numeral system, regardless of its base). So if we have numbers of a group $\mathbb{G}$, we should set $n=\log_2|\mathbb{G}|$, and brute force algorithms require $O(2^n)$ operations.

Short version with less algebra:

Encrypting or signing something uses exponentiation as operation, and there are algorithms with complexity linear to the length of the numbers (in binary representation), and let's call the length $n$. If you want to test all possible values (aka brute force), there are $\approx2^n$ values to test, and this is exponential in the parameter $n$.