In W-OTS, is it trivial to forge smaller N values? Just read about W-OTS. Since the signature is the private key hashed 256-N times, is it trivial to forge a signature with a smaller value for $N$ when having access to original signature? I.e. just hash it one more time and it represents 9-1, etc.

W-OTS has a checksum that ensures that kind of attack doesn't work.

In essence, the checksum is the sum of the value of every other component subtracted, so that if you hash one component one more time, you need to find a pre-image of a component of the checksum.

Basically, it looks a bit like this:

[ - | - | - | down | checksum up ]

Related: https://crypto.stackexchange.com/a/63903/36960


Probability of Vigenere cipher I am trying to figure out this quiz question on a course I am doing but keep getting it wrong.

  Consider the Vigenere cipher over the lowercase English alphabet,
  where the key can have length 1 or length 2, each with 50%
  probability. Say the distribution over plaintexts is Pr[M='aa'] = 0.4
  and Pr[M='ab'] = 0.6. What is Pr[C='bb']? Express your answer to 4
  decimal places with a leading 0, i.e., if your answer was 1/2 then you
  would enter 0.5000 (without a trailing period).

The way I reasoned was as follows:
Probability P1 where m=aa and key is of size 1 = 1/26 * 0.4
Probability P2 where m=aa and key is of size 2 = 1/26*1/26*0.4
Probability P3 where m=ab and key is of size 1 = 0
Probability P4 where m=ab and key is of size 2 = 1/26*1/26*0.6

The answer (I thought) was P1 + P2 + P3 + P4 = 0.0169

This is apparently wrong. Can anyone guide me, please?

I'll assume the Vigenere cipher is defined to encrypt per $c_i\gets m_i\boxplus k_{(i\bmod l)}$ where $c_i$ is a ciphertext letter, $m_i$ is a plaintext letter, $k_i$ is a key letter, $l$ is the length of the key, $\boxplus$ is the Vigenere table of dimension 26×26. I'll note $\hat k_i=k_{(i\bmod l)}$.

It is assumed
$$\begin{array}{rlcrl}
\Pr[l=1]&=\frac1 2&\quad&\Pr[l=2]&=\frac1 2\\
\Pr[m_0=\mathtt a\;\wedge\;m_1=\mathtt a]&=\frac2 5&\quad&\Pr[m_0=\mathtt a\;\wedge\;m_1=\mathtt b]&=\frac3 5
\end{array}$$
It is asked $p=\Pr[c_0=\mathtt b\;\wedge\;c_1=\mathtt b]$. That is
$$p=\frac2 5\Pr[\hat k_0=\mathtt b\;\wedge\;\hat k_1=\mathtt b]+\frac3 5\Pr[\hat k_0=\mathtt b\;\wedge\;\hat k_1=\mathtt a]$$

Unfortunately, the problem statement is unclear about the distribution of key. We can reasonably assume that each of the possible $k_0$ has probability $\frac1 {26}$, but what about $k_1$ when $l=2$? It is reasonable to assume one of

Each of the possible $k_1$ has probability $\frac1{26}$. That yields
$$p=\frac2 5\left(\frac1 2\frac1{26}+\frac1 2\frac1{26}\frac1{26}\right)+\frac3 5\left(0+\frac1 2\frac1{26}\frac1{26}\right)=\frac{57}{6760}\approx0.0084$$
(rounding to the nearest, that is down)
Each of the possible $k_1\ne k_0$ has probability $\frac1{25}$. That yields
$$p=\frac2 5\left(\frac1 2\frac1{26}+0\right)+\frac3 5\left(0+\frac1 2\frac1{26}\frac1{25}\right)=\frac{53}{6500}\approx0.0082$$
(rounding to the nearest, that is up)

Note: Bet on 1 to maximize the probability of scoring a correct answer, even though 2 is the less unsafe cryptographically.

The question's attempted resolution has reading 1, but each of the probability that it sums is missing the multiplication by the probability that $l$ has the value considered.


how to calculate the non linearity of each element of s box? I want to learn how to calculate the elementwise noninearity of an sbox. I know how to calculate the ANF, and how to create the s box. Now I wanna learn how to calculate the nonlinearity of s box elements "belement.before n after shuffling elements."

The answer to How does one practically calculate the non-linearity of a multi-output boolean function like the AES s-box? describes explicitly how to do this both for single output bits and the whole output vector of the sbox.

If you have the ANF of an sbox output bit, you can obtain its hadamard transform from there by using the mobius transform. See my answer to the question
Generate ANF from SBox for information on the mobius transform.

The weight of the lowest weight nonzero hadamard coefficient is equal to the nonlinearity.


DES 48-bit round keys replaced with 48-bit block keys In a variant of DES with a 48*16 = 768-bit key, the sixteen 48-bit round keys scheduled for successive rounds in the encryption process for DES are replaced in this variant by successive 48-bit blocks of the 768-bit key.

What are the weak keys for this variant of DES, i.e. the keys for which encryption and decryption give the same transformation on input blocks?
What are the semi-weak key pairs, i.e. the pairs $k_1, k_2$ of keys for which encryption with $k_1$ is the same transformation as decryption with $k_2$?

Let the DES-variant's key $k=sk_0|sk_1|...|sk_{15}$, where each $sk_i$ denotes a 48-bit subkey and "|" concatenation. Due to the Feistel nature of DES, a sufficient condition for $sk_i$ is that for $i \in [0,15]$, subkeys $sk_i = sk_{15-i}$. They will work as each others' complements and encryption will become identical to decryption. There will be $2^{48*8}=2^{384}$ such sets, or keys $k$. Relatively speaking this is still far less than the number of weak keys in original DES, due to the large number of freely selected key bits.
The semi-weak key definition makes sense only in the original DES, where the round keys depend on the secret key: both the definition of weak and semi-weak keys aim at producing identical round keys for encryption and decryption; the weak keys are sufficient to accomplish this by themselves, as semi-weak keys come in sets.

P.S. I have hard time imagining any other purpose for this kind of cryptosystem than purely educational


Why is it so hard to make longer hashes? I was reading this answer about why there is no such thing as a SHA-1024 hash:

SHA-2 was built with state and word sizes to meet the security requirements on commodity computers (x86 and Alpha), which use 32 and 64-bit maximum CPU word sizes for general purpose registers. This meant that the state was built with 8-words to meet the 2 most common security requirements.
Support of a larger digest would either require the core compression function to be different (as there would need to be more word inputs) or a larger word size, which did not exist (and still does not) except in specialized processors or SIMD registers (without appropriate instructions).

Why can't SHA-512 or SHA-256 simply be reused instead to create a longer hash, eg. by concatenating hash(string) and hash(string + 1)? Does this pose a security concern, speaking of hashes in general?
I have little knowledge of the internals of hashing algorithms, but I think that if it takes an average time T to find a collision on hash(string), it should take an average time T^2 to find a collision on hash(string) concat. hash(string + 1).

That article is talking about the core function and state size. It's easy to get a larger output using a whole range of instructions. Using a counter, like your example, does indeed constitute a correct way of generating more output. It's extensively used in constructions for creating a pseudo random function (CSPRNG or DRBG) or key derivation function (KDF).

The problem is that if you want to also have 1024 / 512 bit security you'd need to use a larger state. In that case you'd need a different construct, or you'd have to use 128 bit instructions. Your example doesn't use a larger state and therefore is unlikely to provide full 1024 / 512 bit security. Currently however 128 / 256 bit security is deemed plenty, so there is very little reason to go that way.

If you want to have a hash function with the same security and still larger output, you might have a look at the SHA-3 XOF's: SHAKE-128 and SHAKE-256. Due to the construction of the sponge it's easy to generate more output while the internal state (and thus the security) remains the same. It's basically still SHA-3, it doesn't even need alteration of the core function nor an external construction using a counter.


Which algorithm would be ideal for ephermal key generation followed by DH key exchange? Bob and Alice, both generate a temporary public key pair each using X algorithm on their individual PC.
After being authenticated by a third party, they use the DHE to come to get a common symmetric key; This key is used for the encryption of messages sent between them for that session. After the session is over, all the mentioned keys are forgotten.

My question primarily is what would be an appropriate algorithm 'X'
Also, if there is a vulnerability in the above presented scenario, kindly mention it.

Using ECDHE as an example, the steps are like this,

The client sends supported named curved list.
The server chooses a curve and generate key-pair, and sent back curve type and public key.
The client uses the server curve type to generate key-pair, and send back curve type and public key.

Now, both client and server can generate same secret(i.e. pre-master secret in SSL)


ElGamal in private set intersection: how to handle negative numbers? I am trying to implement the Efficient Robust Private Set Intersection using Additive ElGamal.

For this, from the client side, my inputs are $C = \{1, 2\}$. So, the polynomial is $(x-1)(x-2)$ which is $x^2-3x+2$.

The next step is to encrypt the variable coefficients which are $1$, $-3$, $2$.

Can someone tell me how to use ElGamal for encrypting negative numbers. If there is an example which one can run from Client and Server side, it will be really helpful.

I use the notation introduced in the paper: The parameters of ElGamal are $(G, q, g)$ where $q$ is prime, $G$ is a cyclic
group of order $q$ and $g$ is a generator. In the paper, the authors use "exponential ElGamal" such that they have an additive homomorphism, i.e., the message is
represented as "exponent" of $g$, i.e., as $g^m$. With $h=g^x$
being the public key a ciphertext of a message $m\in Z_q$ is $(c_1,c_2)=(g^y,h^y\cdot g^m)$ and it is clear that by componentwise
multiplication of two ciphertexts for messages $m_1$ and $m_2$, the additive homomorphism gives a ciphertext for $m_1+m_2 \mod q$.

Note that the message space is $Z_q$ and we are working with integers modulo $q$, i.e., the set $\{0,\ldots,q-1\}$.

Now how to handle negative integers $-x$?

There are two ways how you can see this:

If for $-x$ that the absolute value of $x$ is in the set $\{0,\ldots,q-1\}$, i.e., you have that $0\leq |x|<q$.
Then, you can view $-x$ as the additive inverse of $x$ in the group $(Z_q,+)$ which has order $q$. This means $-x$ is an element $a$
for which it holds that $x+a\equiv 0 \pmod q$. Consequently, the value of $a$ is $p-x$.
For example: Let $q=5$ and we want to know $-2$, i.e., the additive inverse of $2$ in $Z_5$, then we have $-2=5-2=3$, since
$2+3\equiv 0 \pmod 5$, so $-2$ is equal to $3$.

Now what if the absolute value of $x$ is not in the set $\{0,\ldots,q-1\}$? For instance, how to handle $-16$ in case of the integers modulo $5$?.

We also can view integers modulo $q$, i.e., the set $\{0,\ldots,q-1\}$, as a set of representatives of the $q$ residue classes modulo $q$.
More precisely, $0$ is a representative for the class $[0]$ of all integers having remainder $0$ when divided by $q$, $1$ a representative for class $[1]$, etc. If you encounter a negative integer as
defined above, then you simply add $q$ until the value lies within the set $\{0,\ldots,q-1\}$ since this will obviously not change the class.

Back to our example, this means that given $-16$ you add $5$ and find that $-16+5=-11$, $-11+5=-6$, $-6+5=-1$ and finally,
$-1+5=4$. Consequently $-16\equiv 4 \pmod 5$ and you can represent $-16$ as $4$.


End-to-end photo storage I've been tasked with developing an app that will need to store photos a user takes securely, and I've been struggling to think up a method to do this.
What I was thinking so far is as follows:

When user first logs into the application, input their password along with a salt (stored in a database) to a key-derivation function to generate a hash
Use this hash to encrypt an AES key
Store this on a database

This way, when a user logs into the app, they can request the encrypted AES key and decrypt it by producing the same hash produced from their password.
Using this AES key, they can encrypt photos before sending them to the server, and decrypt them upon receiving them back.
Is this a viable method? Is there a better way to do it?
Any help would be appreciated.

What I was thinking so far is as follows:

When user first logs into app, input their password along with a salt (stored in a database) to a key-derivation function to generate a
hash
Use this hash to encrypt an AES key
Store this on a database

Firstly, make sure that the user's password has good strength. In general, this is the weakest point even there are strong encryption methods. The usual advice is to tell/teach them to use dicewire method (see in xkcd 936). This will make the passwords have good strengths. If the user's password is weak then password cracking methods will break the encryption; John the Ripper password cracker or the Hashcat searches. It is ciphertext only attack, however, the file structure of the image files will help to determine the correct key.
You can use the password-based key derivation like PBKDF2, or, better use Argon2 as the winner of the password competition in 2015, to derive a key with a random 256-bit salt for each file. The random salt can be appended to the encrypted file. Prefer the Argon2 if possible. You can also use HKDF to derive the keys.
A crucial part of such an application is that the user can forget their passwords. In this case, all of the photos are lost. The user must that countermeasure for themselves, write somewhere, use keypass, etc. The other mechanism by your application depends on the environment of the application and the risks.
For the encryption method use AES256-GCM* or better prefer ChaCha2-Poly1305 since it is easier to use than GCM. They are authenticated encryption methods that will provide you Confidentiality, Integrity, and Authentication. For those, you need to derive a IV/nonce and that can be randomly generated since you generate a new key for each file. And never ignore the tag mismatch error. If your application is an image processing application that stores the files on the cloud you need to be careful when you upload the modified file. If the key and the IV are the same then an observer can leak information from the differences.
If you don't want to use a new key for each file, then you need to be careful about the IV reuse. In this case, the nonce misuse resistant scheme SIV can be used with AES-GCM-SIV.

* Although AES-128 is secure, prefer AES-256 against the multi target attacks


Curve25519 Specification The Curve25519 is defined over the prime $2^{255}-19$ with $A = 486662$, so that the curve equation is: $y^2 = x^3 + 486662x^2 + x$

I'm trying to understand, why the parameters are what they are.

First of all the Prime. I already have some ideas from the Bernstein Paper, why he chose this prime. Can someone say, if one of them is false, or if i'm not mentioning an important point?:

Faster field operations, when a prime is close to a power of 2
no space wasted, when having a key length close to $32 \cdot k$ for any $k$
pretty high security level because of 255 Bit key length (not sure, but is it equal to a 15000 Bit RSA system?)

Bernstein described the choice of the prime pretty well. But i dont unterstand why he chose A = 486662. I read his reasons for that choice, but i simply don't understand them. Can someone explain it to me, on a more basic level?

Edit:

I tried to understand the choice of 486662 an hopefully got questions that help me understand it:

How can a subgroup be created by a point ( So the base points creates a subgroup, which has a prime order. But this order is also the order of the curve25519. I'm a bit confused by that )
So the order of the subgroup is a prim, but the order of the Curve25519 is also a prime. I dont understand how A makes a curves, which has the order ${4 \cdot n, 8 \cdot n}$, when the order is in fact a prime
What are the attacks, that can't be used, when A is chosen this way? ( I think: only small subgroup attacks, e.g. Pohlig–Hellman. But Bernstein wrote in his paper, that there are various attacks )

From the paper:

  I selected (A − 2)/4 as a small integer, as suggested by Montgomery, to speed up the multiplication by (A − 2)/4

The smaller the value (A-2)/4 is, the faster is the multiplication by that value (which is required by the point doubling formula).

So basically the curve was found by incrementing the A value, restricting to the values where (A-2)/4 is an integer, until it generates a curve with order $4n$ or $8n$ where $n$ is prime (and some other criteria described in the paper: the twist order should be in the same format; and $n$ should be larger than $2^{252}$ so that the private key can be generated by simply randomly filling a byte buffer and not having to bother with the case where the private key is equal to the curve order).


Instead of sending a set of random values, send a key for a PRF Some Protocols require one party to send $n$ random challenges (or random values) to another party. For communication efficiency purpose, one can pick a random key for a pseudorandom function, and send only the key to the other party, instead. Given the key and the function, the recipient can generate $n$ (pseudorandom) values locally.

In here (on page 5) it's stated that we cannot prove it in the standard model but can we can do it in  random oracle model. However, in here (on page 12-13) it is said we can use block cipher in the counter mode to do that. So it's a bit confusing.

Question: Why cannot we use standard primitives and assumptions to construct a provably secure scheme described above?

It depends very much on what you require from the random values that are sent. If they need to be random (pseudorandom) then sending the key is a problem. However, if you just need unpredictability, then this may be enough. Bottom line, there is no one answer. It depends on the protocol and requirements, and often is only apparent when doing a formal security proof.


Building multiple keys from the same input using a KDF Let's say I have a single secret with high entropy, S, for the entire application. I want to generate keys K1, K2 for 2 different users of the app. I run:

K1 = PBKDF2(S, salt1)
K2 = PBKDF2(S, salt2)

where each salt is some 128 bit random number.

Is this a safe construction or do KDFs (or PBKDF2 specifically) have any properties that user 1, knowing K1, could infer any part of K2?

EDIT:

Assume a non-broken hash and a sufficient number of iterations for the KDF

Assuming you aren't using a completely broken hash function (speaking of which, what hash and iteration counts are you using? Are they dynamically selected, and if so how?), what you're doing should work.

More specifically, assuming user 1 knows K1 (their own derived key), salt1 (the salt used to derive K1), and salt2 (user 2's salt), but doesn't know S or K2, they should not be able to derive K2 (or S, which would let them get K2 if they know salt2).

With that said, I can't really recommend this approach; it's not really the way KDFs are specifically meant to be used, and adapting cryptographic functions to new uses is often dangerous. Their security properties are not always what you intuitively think they are.

For example, to a naïve understanding of hash functions, knowing the digest of some blob B (without knowing B), and knowing the suffix X that gets appended to B, should not be enough for you to know the digest of concat(B, X). That is, people usually assume that if you don't know the entire input to a hash function, you can't possibly predict the output... even if you know the output of a different input, and know what change was made to that output (in this case, concatenating a suffix). However, due to length extension attacks, it sometimes can be possible to know what the digest will be after appending a known suffix, even if you don't know the original message.

I don't know that anything similar applies to PBKDF2 (or any other KDFs) but I'm still leery of using them in an unusual way. The purpose of the salt is so that, even if two users unknowingly use the same password, you can't tell it's the same password because the derived keys will be different. If you know from the start that the passwords are the same, I don't believe the function is known to guarantee that no additional information could be derived. Maybe it does, maybe it only does with certain hashes, maybe it doesn't... but I don't know, and I don't know if anybody has studied it.


What does "export grade" cryptography mean? And how is this related to the Logjam attack? I am doing some research on the Logjam attack, and I need help in learning some terms that are new for me.

What does "export grade" cryptography mean? And how is this related to the Logjam attack?

"Export grade" cryptography is a result of The Crypto Wars. Laws were passed in the United States that resulted in the crippling of encryption software that was distributed outside of the United States. This section from wikipedia explains it well enough:

  The longest key size allowed for export without individual license proceedings was 40 bits, so Netscape developed two versions of its web browser. The "U.S. edition" had the full 128-bit strength. The "International Edition" had its effective key length reduced to 40 bits by revealing 88 bits of the key in the SSL protocol. Acquiring the 'U.S. domestic' version turned out to be sufficient hassle that most computer users, even in the U.S., ended up with the 'International' version,[7] whose weak 40-bit encryption could be broken in a matter of days using a single personal computer. A similar situation occurred with Lotus Notes for the same reasons

The 40-bit limit was for symmetric ciphers, where there is no (known) attack better than trying all $2^n$ keys. Asymmetric algorithms like DH and RSA need larger key sizes for the same security; see e.g. How much computing resource is required to brute-force RSA? and Security strength of RSA in relation with the modulus size . At the time 512-bit RSA or DH was rated equivalent to 40-bit symmetric, and thus export of those algorithms was limited to 512 bits. (DSA was rated the same, but was not limited because it is not an encryption algorithm.) This is why weakdh.org states that:

  The Logjam attack allows a man-in-the-middle attacker to downgrade vulnerable TLS connections to 512-bit export-grade cryptography.

Ultimately, some software was required to be written using key sizes that were understood to be breakable; export grade cryptography refers to this form of an algorithm that uses a reduced and breakable key size. The Logjam attack works by tricking the TLS exchange into using crypto that is weaker and potentially breakable.


What exactly is a negligible (and non-negligible) function? The mathematical definition of neglible and non-neglible functions is fairly clear-cut, but  why they are important and how they are used in cryptography?

In perfectly secret schemes like the one-time pad, the probability of success does not improve with greater computational power. However, in modern cryptographic schemes, we generally do not try to achieve perfect secrecy(yes governments may use the one time pad, but this is generally not practical for the average user). In fact, given unbounded computational power, all of our non-perfectly-secret schemes are insecure(also note that for public-key cryptography, perfect secrecy is unachievable using classic cryptography so all schemes are insecure against unbounded computational power). Instead, we  define security against a specific set of adversaries whose computational power is bounded. Generally, we assume an adversary that is bounded to run in time polynomial to $n$, where $n$ is the security parameter given to the key generation algorithm(more precisely, the key generation algorithm is given input $1^n$ so that $n$ will be its input size and its output--the key--will be polynomial in the size of its input.)

So consider a scheme $\Pi$ where the only attack against it is brute force attack. We consider $\Pi$ to be secure if it cannot be broken by a brute force attack in polynomial time.

The idea of negligible probability encompasses this exact notion. In $\Pi$, let's say that we have a polynomial-bounded adversary. Brute force attack is not an option. But instead of brute force, the adversary can guess (a polynomial number of) random values and hope to chance upon the right one. In this case, we define security using negligible functions: The probability of success has to be smaller than the reciprocal of any polynomial function.

And this makes a lot of sense: If the success probability for an individual guess is a reciprocal of a polynomial function, then the adversary can try a polynomial amount of guesses and succeed with high probability. In sum then, if the overall success rate is $1/poly(n)$ then we consider this a feasible attack and the scheme is insecure.

So, we require that the success probability must be less than the reciprocal of every polynomial function. This way, even if the adversary tries poly(n) guesses, it will not be significant since it will only have tried:

$$\mathit{poly}(n)/\mathit{superpoly}(n)$$

As $n$ grows, the denominator grows far faster than the numerator and the success probability will not be significant.

Edited to add Here is an informal argument that may make this clearer: To see that the notions of superpolynomial brute force attack and negligible probability guessing are equivalent, consider a scheme with $K$ possible keys.

Brute force attack on the key set runs in $K$ time. Moreover, the probability of choosing a key at random and it being the correct key is $1/K$. Now, if $K$ is polynomial in $n$, (the security parameter), then this scheme can be brute forced in time $K = \mathit{poly}(n)$. Moreover a random guess succeeds with probability $1/K= 1/\mathit{poly}(n)=\text{non-negligible}$
and the scheme is by both definitions insecure.

To secure the scheme then, we want to make brute force run in superpolynomial time. In other words,$K$ must be superpolynomial in $n$. Well then, the probability of guessing correctly on a single guess is $$1/K=1/\mathit{superpoly}(n)$$ and this is by definition negligible probability.

Although informal, I think this last part motivates the use of negligible functions in security proofs.


Safe generator for ElGamal signature What are the properties a generator $g$ should have to be secure for ElGamal signatures (original scheme)?

I am aware that it is poorly chosen and not secure when $g|p-1$ or $g^{-1}|p-1$, where $p$ is the large prime so that $g$ generates $Z_p^*$ and $g$ has maximum order (that is, $p-1$).

Are there other properties one should consider? Additionally, should $g$ be picked randomly over $[1..p-1]$ or is it safe to choose it to be a small integer to start with?

First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of $\mathbb{Z_q}$ in which CDH is believed to be hard but DDH is apparently tractable.

Let $p = 2p_1 + 1$ where both $p$ and $p_1$ are prime. Let $Q_p$ be the subgroup of quadratic residues in $\mathbb{Z_p}$. $Q_p$ is a cyclic group of prime order itself in which DDH assumption is believed to be hard. This group and some other groups in which DDH problem is intractable are mentioned in this paper by Dan Boneh.

Any randomly chosen primitive element in $\mathbb{Z_p}$, say $g$, to the power of two ($g_1=g^2$) is a 'safe' generator for the subgroup of quadratic residues in $\mathbb{Z_p}$ (it is defined above as $Q_p$). A primitive element of $\mathbb{Z_q}$ is an element which are relatively prime to $p$. ($gcd(g,p)=1$)


NTRUSign (considered broken) as a one or few time PQ signature scheme As many know, original NTRUSign is considered broken as signatures leak information about the private key.

It takes a number of signatures to accomplish a break though, with the original break paper claiming a few hundred.

Could this signature scheme still be used as a one-time or few-time signature scheme? What would its security be in this case? The advantage over WOTS would be that it's faster.

To quote RFC4270

  There is an old saying inside
     the US National Security Agency (NSA): “Attacks always get better;
     they never get worse.”

One of the main reason people avoid cryptographic protocols with known attacks is the above wisdom. Essentially, the attacks show there is an intrinsic weakness in the protocol, and often following works improve the effectiveness of the attack. If you really want to use a protocol with known weaknesses, you need both

to have good reasons to think the possible improvements on known attacks won’t come close to parameters were it would destroy your security. In your case it means being sure that there is no way to improve the number of signatures needed to the attack from a few hundred to a few, or at least that no one will find one in the relevant time frame.
to gain a very strong advantage, like speed.

Since the main practical interest of NTRU signature protocols is their post quantum security, it means that the time scale considered for improvement of attacks the decades needed for your adversaries to have a quantum computer useful for cryptanalysis (otherwise, use RSA !). Given past history of cryptanalysis, I really do not believe one could have any assurance more effective attacks against NTRUsign won’t be found over the next two decades !


Why does it matter for a signature scheme to be without random oracles? There is a profusion of articles proposing signature schemes without random oracles (see for yourself). What does that mean, and why does it matter?

A "random oracle" is essentially a perfect hash function. It's a device that takes a message of any length and maps it randomly to a message of a fixed length such that the same input always produces the same output. Random oracles don't exist. For algorithms that require them, cryptographic hash functions are used instead. However, cryptographic hash functions are not really random oracles and any flaws in the hash function could translate into vulnerabilities in the signature scheme.

The simplest way to make a signature scheme is to begin by hashing the thing you need to sign to a fixed length. Since signature schemes generally aren't also trying to design hash functions, they just assume a random oracle to perform this function and then they demonstrate their security properties assuming a random oracle is used.

Signature algorithms that don't require random oracles don't require you to hash the thing you are signing. They operate on a message of arbitrary length, reducing it to a fixed-length signature as part of their own operation. Because you don't have to substitute a hash function for a random oracle, there is no risk that the hashing function will add new vulnerabilities to the signature scheme.

For example, say you have a signature scheme that requires a random oracle, and the signature scheme has been proven to have no vulnerabilities. You use MD5 as the random oracle. Oops, we can now generate MD5 collisions, so someone can now forge two different messages that have the same signature too easily. All the security properties of the signature algorithm aren't going to help you because the hash function isn't a random oracle and introduced vulnerabilities a random oracle (since it's theoretically perfect) doesn't have.


How to roll my own hardware RNG? I am considering building a hardware RNG myself using cheap parts. Is this a good idea and safe enough?

Random sources: amplified Zener noise from one randomly chosen 1N4728A Zener diode and amplified reverse current of a randomly chosen SS9014 transistor.
Random stream generating: The two amplified signals are further amplified and biased with one LM324 chip and sent to analog input pins of an Arduino, and the full 10-bit ADC readings are used as the random source.
Whitening and stream mixing: how to do this on the Arduino's ATmega328P microcontroller?
Uplink: USB Serial.

Anyone have knowledge on how the whitening and stream mixing can be done? And how to evaluate the security of this system?

The question fails to mention a functionality that must be part of any secure True RNG (as the question aims to build): supervision.

Supervision is responsible to detect a failure of the "Random sources" or "stream generating" stages (hereafter unconditioned source), and in that event reliably prevent use of what the "Whitening and stream mixing" (hereafter conditioning) outputs.

Experience and reasoning show that effective supervision is of paramount importance for security. Wear, build defects, and deliberate attacks against unconditioned sources result into sources that e.g. output a stream of constant bits, or that repeat in a very short cycle, or that reproduce the noise on the power supply, or can be controlled by an adversary beaming smurfons. Should this happen, the conditioning would produce apparently random output that

Stands a fair chance to be the same from one use to another. This is the archetypal disaster leading to private keys being identical on many devices (thus not secret as they should), or otherwise vulnerable (example: smartfacts) even without knowing the details of the RNG
Or at least, is vulnerable to attack by one knowing the conditioning, and able to guess the output of the unconditioned source, perhaps by influencing it.

True RNG supervision comprises a test that determines misbehavior of the unconditioned source, and the mechanism (alarm management) acting upon that (like: inactivate everything until the next power cycle). FIPS 140 uses the name "power-up test" and did not mandate further supervision, but the need for supervision actually extends to whenever the RNG might be used: failures and attacks are not bound to strike at power-up!

Supervision also faces a functional requirement of not generating false alarms at a rate that would hamper use of the device. This makes statistical random number generator tests (or at least, their usual parametrization) ill-suited to build supervision. That's because such tests are typically designed to have a quantified and sizable probability of failure for a truly random input, when even 0.01% failure is typically intolerable for mass-produced devices without human operator. Moreover, a practical test must tolerate whatever deviation from uniformly random is expected from its unconditioned source when healthy, and that's heavily dependent of the unconditioned source.

The imperious necessity to tailor supervision to source has been overlooked. Until a change notice in late 2002, FIPS 140 mandated tests (in particular monobit and poker tests) that could not tolerate a small bias or bit cross-correlation. Conformance of a practical device required pre-conditioning of the unconditioned source, in turn making the test less effective, and totally ineffective for a cryptographically strong pre-conditioning. Because FIPS 140 has long been the only public standard specifying test of TRNGs, that mistake is deeply entrenched in literature and standards on secure TRNGs.

A modern, minimal practical approach fro a secure TRNG with supervision as above:

A theoretical model of the unconditioned source must be made, including a target min-entropy rate $r$ (a quantity without unit, in range $(0,1)$, specifying how much true entropy there is per bit output).
The conditioning must be cryptographically secure under the hypothesis that the unconditioned source meets its target $r$. That could mean feeding a Cryptographically Secure Pseudo Random Number Generator $256/r$ bits before it can output anything.
The test in the supervision must catch, with high likelihood, any failure mode of the unconditioned source that can be anticipated to occur according to the model and would bring the unconditioned source below its target $r$; and then prevent use of the output of the conditioning.
Yet the availability of the output must match operational requirements.

There may be other requirements, like detecting a failure/attack of the conditioning, recovering from compromise of the conditioning's state.. that complicate the conditioning.

Rough sketch for an appropriate model and conditioning in the question's context: we can model the hardware (when working properly) as a noise source followed by a 10-bit ADC at frequency $2f$ usable to digitize signal from DC to a certain upper frequency commensurate with $f$, with the source noise having an average voltage excursion of say 1/32 full scale at that $f$ (for some loose definition of that). The ADC is 10-bit, with a specified non-linearity of 4 steps.

Thus when things are working properly, each pair of 10-bit samples (drawn over an interval $1/f$, or more due to, say, interrupts) carries at least $10-\log_2(32)-\log_2(4)=3$ bits of entropy ($r=\dfrac3{20}$ when we count bits output by the ADC). This means we are confident that $256/r=2707$ bits or 271 samples have 256 bits of entropy. We take a factor of two for leeway in the (currently unspecified) test, and use 342 samples, that is 748 bytes when representing a sample as 2 bytes. Acquires that, hash it with SHA-256 (quite easy on an Arduino), and we have 256 bits that we can affirm indistinguishable from random, if our source including ADC is not defective (that is, meets at least half its target $r$) and the program is running correctly.

Note: We are talking of a sampling rate $2f$ about 10kHz according to this. The LM324 is rated at about 1MHz Gain×BandWidth Product @5V, thus up to a gain of roughly 100, that amplifier is unlikely to limit the bandwidth.

Note: I have intentionally grossly oversimplified and ignored large constant factors, but (I hope) erred on the safe side (lowering $r$), except for the "1/32 full scale" assumption which depends on the unstated schematic.

As often, defining the test is the hard part (to be continued).

We can't define a useful test of an entropy source without some model thereof. Argument: Assume a Cryptographicaly Secure Pseudo-RNG. Seed it once by a fixed constant. By definition of Secure in this context, the output is practically indistinguishable from truly independent random bits without knowledge of the constant. This is an insecure source, since it is easily predictable for one knowing the fixed constant. Yet no test exists able to give any indication of this.


Alternatives to simple bit-measured security for ciphers For a cryptographic primitive, we usually see the security level measured in bits, where n-bit security means that the attacker would have to perform $2^n$ operations to break it.
For key-derivation functions, we often see functions that deliberately use large amounts of computation or memory in order to make them computationally expensive.
However computational expense seems to be rarely discussed when comparing the security level of ciphers.
My assumption: It would seem logical that a cipher that cannot be run in parallel is (in some ways) more secure compared to one which can.  Or two ciphers with equal security levels are not truly equal if one of them runs a billion times quicker on a supercomputer.
Questions

Is my assumption misguided?
Are there any alternative approaches to measuring cipher security that takes into account the computational expense of the algorithm? If not, why not?

My assumption: It would seem logical that a cipher that cannot be run in parallel is (in some ways) more secure compared to one which can. Or two ciphers with equal security levels are not truly equal if one of them runs a billion times quicker on a supercomputer.

Is my assumption misguided?

A cipher with $n$-bit security means that there are $2^n$ keys to choose as an encryption key. If we can iterate the key, that is always possible, then we can start to brute-force in parallel. Therefore, this not a good premise.
A cipher can be faster than others like Rijndael was faster than MARS and that is one of the reasons for the choice of Rijndael as  AES. We still consider the $n$-bit security as the number of possible keys. When comparing the attacks on the cipher we consider how the attack faster than the brute-force. So we compare the brute-force time - the running time of the one encryption times the number of keys -  vs. the time of the attack. The first one is easy but still depends on the platform, the second one can be hard since the attack can depend on many parameters and the measure may not be easy.
For example, in the Improving the Biclique Cryptanalysis of AES article Tao et. al considered the actual computation of running a brute force in all details and compared their attack in the same detail level to compare the success of the attack.
On the other hand, the factoring attacks use Landau notation to express their complexity.
If there is a faster attack we consider this as the encryption algorithm is broken. This still doesn't mean that it is broken practically. Consider AES256 has attacks but they are not feasible. Also, the attack may require too much random memory access that can severe the computation time. Therefore, it is totally dependent on the attack.

Are there any alternative approaches to measuring cipher security that takes into account the computational expense of the algorithm? If not, why not?

We don't consider the computational expense of the algorithm as a weakness, indeed it is greatness. Who doesn't want a fast and secure algorithm instead of slow and secure? Time is Money, area cost is money. In the and we want the cipher to resist all attack to be secure $n$-bit ciphers.
If we consider the security against all possible attacks than this is a huge list of the attacks

Linear attack security
Differential attack security
Algebraic attack security
The number of required known-plaintext
The number of required chosen-plaintext
Multi-target security.
Possibility of running parallel
Quantum security
Memory requirements
...

Consider the linear and differential attacks on DES. They are faster on the computation requirements but required known-plaintext and chosen-plaintext
for the attacks are so huge that they were not practical. Even today, the fastest attacks implemented on the DES are based on brute-force.
Therefore, it is not an easy job to put a metric. The real metric is the implementation and comparison with the brute-force. If this is not possible, and it is not most of the time, either a complexity analysis is preferred or detailed as in AES attack.


Does a partial preimage attack imply a preimage attack? Let's assume we have an $n$-bit hash function and a $b$-bit partial preimage attack that is faster than brute force. Does this imply a faster than brute force preimage attack on the whole hash?

It seems that it does, because if you run the $t<2^b$ time partial preimage attack on an input you have a $2^{b-n}$ chance of finding a full preimage, which is better than the chance with a brute force attack in that time.

On the other hand, if you run it on $2^{n-b}$ inputs you expect one of them to find a full preimage and this takes $t \cdot 2^{n-b} < 2^n$ time. However, with that many inputs a brute force attack would find one of them in just $2^b$ time, which is better unless $b>\frac{n}{2}$ and the partial preimage attack is very fast. (Complicating matters further, some of the inputs may have the same partial hash, not sure how to take that into account.)

I am trying to figure out what assumptions can be made about preimage attacks when considering the truncation of an arbitrary $n$-bit secure $n$-bit hash.

It depend on what notion of preimage resistance you mean, and on whether the preimage attack applies to only a tiny class of images or whether it works uniformly on all of them.

Fix a random hash family $H\colon \{0,1\}^{4b} \to \{0,1\}^{2b}$.  Define

\begin{equation*}
  H'(x) = \begin{cases}
    0^b \mathbin\Vert H_b(x), & \text{if $x$ starts with $1^{2b}$;} \\
    H(x), & \text{otherwise.}
  \end{cases}
\end{equation*}

Here $H_b(x)$ is some $b$-bit truncation of $H(x)$.  How does the obvious cheap preimage attack on $H'_b$ translate to the cost of a preimage attack on $H'$?

The everywhere preimage resistance (ePre) of $H'$ is at most half the bits of that of $H$, because there exists an image $y$—namely, any string starting with $0^{b}$—such that there is a known random algorithm $A_y(H')$ making $q$ queries that can find a preimage with probability $O(2^{-b} q)$ much higher than the generic $O(2^{-2b} q)$.

That is, we have an extremely cheap preimage attack on $H'_b$ for the image $0^b$ which translates to a cheaper-than-generic everywhere preimage attack on $H'$ because there exist images, namely those starting with $0^b$, for which we can find preimages at substantially lower cost than generic.
But this has negligible impact on the always preimage resistance (aPre), or just unqualified preimage resistance (Pre).  There are random algorithms $A_{H'}(y)$, for always preimage-resistance, or $A(H', y)$, for (unqualified) preimage-resistance, with conditional probability $O(2^{-b} q)$ of finding preimages given that $y$ lies in a certain class of image—but the probability of being challenged with such an image $y$ is about $2^{-b}$.

That is, although we have an extremely cheap preimage attack on $H'_b$ for the image $0^b$, it doesn't help us to find a preimage for a uniform random challenge image because the probability of being challenged with an image that starts with $0^b$ is negligible.


Can Montgomery ladder multiplication be used with secp256k1? While reading about Elliptical Curves and ECDSA, I found a paper ECDSA Security in Bitcoin and Ethereum: a Research Survey by Hartwig Mayer. On page 6, the authors say:

  The curve secp256k1 does not allow the Montgomery ladder
  implementation.

Is this true? And if so, why? I don't see why Montgomery methods wouldn't be usable with secp256k1.

The Montgomery ladder, in particular Montgomery's fast doubling and differential addition formula in $(X : Z)$ coordinates on p. 261, works only for curves which admit a Montgomery form $B y^2 = x^3 + A x^2 + x$.  Any curve over a field $k$ with a Montgomery form necessarily has a point of order 2 among the $k$-rational points, namely $P = (0, 0)$: the negation map sends $(x, y)$ to $(x, -y)$, so since $-P = (0, -0) = (0, 0) = P$, we must have $[2]P = P + P = P - P = \mathcal O$.

secp256k1 is the curve $y^2 = x^3 + 7$ over the field $\mathbb F_p$ where $p = 2^{256} - 2^{32} - 977$.  Its group of $\mathbb F_p$-rational points has large prime order, so by Lagrange's theorem it has no points of order 2, and hence it does not have a Montgomery form.

That said, there is a much slower single-coordinate ladder that encourages constant-time arithmetic, namely the Brier–Joye ladder, which works for any short Weierstrass curve $y^2 = x^3 - a x + b$ including secp256k1.  It is so much slower that the standard variable-time addition chains for short Weierstrass curves are tempting, which is why SafeCurves recommends, for Diffie–Hellman protocols, the use of $x$-restricted DH functions in Montgomery curves instead to avoid a conflict between efficiency and security in implementation.

This doesn't matter as much for signature, which is what Bitcoin etc. use secp256k1 for, because most signature schemes—ECDSA as used by Bitcoin and Ethereum, and by those who are forced to comply with bureaucratic standards; EdDSA as used by everyone else—involve the $y$ coordinate, which neither ladder computes; fixed-base-point scalar multiplication, which can be done faster than variable-base-point scalar multiplication; and multiple-point scalar multiplications, which can be done faster than multiple single-point scalar multiplications.  There are signature schemes computed with single-coordinate ladders, such as qDSA, but these are a little exotic and not much used—certainly not in Bitcoin or Ethereum!


Can this key revocation scheme using hierarchical deterministic keys work? Assume I am working with crypto that supports hierarchical deterministic key generation, Bitcoin/Ethereum keys using secp256k1 is one example.

There is a decentralised key registry where users register their public keys for use and other users retrieve those public keys for verificaton. A similar setting could be a blockchain where users transfer coins to other people's public keys.

Now I want to support key revocation as if a user's private keys are stolen he can revoke corresponding public keys. The idea is that the user uses hierarchical deterministic key generation. The parent key is heavily guarded in maybe in a cold storage and its children keys are used for regular usage. It is the child public keys that are put on the registry.
You use a knowledge of a parent (private) key to prove control over child keys to the registry and ask the registry to revoke child keys. The registry will verify that the child key is indeed derived from the parent key (can be done using this) and the revoker has the parent private key.

eg. Alice generates a parent keypair $A$ with secret and public keys as $A_s$ and $A_p$ respectively that it never uses apart for child key generation and keeps in a very secure storage. Now whenever Alice wants to create a new child key, it uses the parent key $A$. Say it 2 child keys based on keypair $A1$ ($A1_s$, $A1_p$) and $A2$ ($A2_s$, $A2_p$). Now it loses  the wallet containing $A1$ and $A2$. Alice will not provide a signature to the registry using the private key $A_s$ and asking the registry to revoke $A1$ and $A2$. The registry checks that $A1$ and $A2$ are derived from $A$ and hence revokes.

UPDATE:
As the answer below shows, this scheme is not useful as revoking a child key enables the possesor of any child private key to know the parent private key.

One problem I can foresee with such a scheme is that when you know a parent extended public key and any non-hardened private key descending from it, you can easily compute the parent extended private key.

This is true because non-hardened public keys are of the form :

  I = HMAC-SHA512(Key = cpar, Data = serP(point(kpar)) || ser32(i))
  then you split I into two 32-byte sequences, IL and IR
  and the child key ki is: parse256(IL) + kpar (mod n)
  the chain code ci is IR, which is part of the extended public key
  and finally you can compute the child public key either by computing point(parse256(IL)) + Kpar
  or by computing point(ki), both are equivalent

So, as you can see, the child private key is the parent private key plus 256 bits of the computed HMAC-SHA512 using the chaincode of the parent private key (which is not a secret) as the HMAC key and, importantly, hashing the public key that corresponds to the extended parent private key along with the child key index.

This basically means that an attacker stealing a non-hardened private key (which you would then like to revoke using the parent private key to authenticate with the registry) could see the extended public key you used to authenticate with the registry if this is public, and from there derive the parent private key you've used to authenticate with the server.

Now, the attacker and the registry both can derive the child public key from the extended parent public key using:

  I = HMAC-SHA512(Key = cpar, Data = serP(Kpar) || ser32(i))
  then split I into two 32-byte sequences, IL and IR
  The child key Ki is point(parse256(IL)) + Kpar, just like above.

But that also means that the attacker can compute the index value "parse256(IL)" and subtract it to the child non-hardened private key (which she stole) to recover the parent private key:

  kpar = ki - parse256(IL) (mod n)

thus effectively allowing the attacker to revoke herself all other child keys derived from that parent key on the registry.

A way around it might be to say that when you register on the registry, for each child key, you register a different parent public key (which would be a hardened key), and that this key can then be used to revoke that child key, but only that child key...

I'm not convinced this eases the pain compared to having a certificate to sign your keys and allowing you to revoke them à la PGP, but with this method at least you're using only HD keys, as you seem to want.

So, in the end, this could work from what I can tell, as long as you take care to handle this caveat correctly.


Multiple XML files and known-plaintext attack I have created an app which collects data in sets which may contain up to 20000 XML files of an average size of about 5 KB, and all with the same header and XML structure, so that only the data they contain differ.

For certain reasons I've decided to encrypt these XML files so that the data they contain cannot be exported without my consent. Problem is that the current users of the app already have a lot of unencrypted XML files and after these have been encrypted (they're required to be in order to use future versions of the app) they may still have backups of the unencrypted XML files, which I can't do anything about.

But that also means that they have the means for doing a known plain-text attack, in order to extract the key and thereby have access to also export the content of encrypted XML files added in the future. So I want to ensure that they're encrypted in a way that makes this if not impossible then at least very difficult.

As I understand from reading posts here, AES should be safe against known-plaintext attacks in a case like this, if it's correctly implemented. So I'm trying to encrypt the files using AES. I just want to be sure if I'm doing it correct, and hope someone here can tell me.

I'm using the code listed here:

Simple AES byte encryption and decryption routines in C#

and a 64 byte key with a 32 byte salt/IV. Same key and salt for each file. I've set iterations to 4096 as a higher number will slow things down too much.

I can create a unique key or salt/IV for each file as there is a unique ID connected with each XML file but it will complicate things a lot and in rare cases the ID for a file may change (beyond my control), so I want to avoid it if possible.

First, don't use AES directly.  AES itself is a pseudorandom permutation family, and if you don't understand what that means, then it's not a good fit for your application.

What you should do is use an authenticated encryption scheme (with associated data), or AE(AD) scheme for short.  Popular examples are AES-GCM, NaCl crypto_secretbox_xsalsa20poly1305, and AES-SIV.  Then pay attention to the security contract so that you understand what your obligations are in the application, and what security properties it affords you in exchange:

With AES-GCM, you are obligated (a) to choose a secret key uniformly at random, (b) to provide a unique 96-bit nonce for each message you want to encrypt, and (c) to never reuse the nonce with the same key.

The nonce must be derived from context, e.g. a message sequence number, or stored alongside the message, so that the decryption side of your protocol knows it.  You must not pick the nonce at random, or you must use the key for no more than than $2^{32}$ messages.  Messages must be no longer than one terabyte, $2^{40}$ bytes.

In exchange, you are guaranteed that an adversary without knowledge of the secret key learns nothing about the plaintext of each encrypted message (even if they know all but a single bit of the plaintext, the ciphertext does not inform them of that single bit) and cannot forge ciphertexts you did not already furnish.  If you reuse a nonce, all is lost.

(The exact bound on the safe number of messages is squishy.  A panel of crypto nerds could litigate endlessly over what the limit should be.  Do you want to play games with squishy balls of crypto you don't understand, or just play it safe?)
With NaCl crypto_secretbox_xsalsa20poly1305, you are obligated (a) to choose a secret key uniformly at random, (b) to provide a unique 192-bit nonce for each message you want to encrypt, and (c) to never reuse the nonce with the same key.

The nonce must be derived from contxt, e.g. a message sequence number, or stored alongside the message, so that the decryption side of your protocol knows it.  You may pick the nonce uniformly at random.  You may encrypt up to $2^{64}$ messages each of up to $2^{72}$ bytes apiece, which is more bytes than you will ever have in your lifetime even if you never bother to chew.

In exchange, you are guaranteed that an adversary without knowledge of the secret key learns nothing about the plaintext of each encrypted message (even if they know all but a single bit of the plaintext, the ciphertext does not inform them of that single bit) and cannot forge ciphertexts you did not already furnish.  If you reuse a nonce, all is lost.
With AES-SIV, you are obligated to choose a secret key uniformly at random.  You may additionally supply a 128-bit nonce, even at random.  You must not use the key for a total of more than $2^{48}$ bytes.

In exchange, you are guaranteed that an adversary without knowledge of the secret key learns nothing about the plaintext of each encrypted message (even if they know all but a single bit of the plaintext, the ciphertext does not inform them of that single bit) except that if the nonce is repeated or not supplied, the adversary will learn when a message is repeated or not.  You are also guaranteed that the adversary cannot forge ciphertexts you did not already furnish.

(The limit on bytes here is also squishy.  What have we learned about squishy balls of crypto?)

There are other considerations about the AES ones versus the XSalsa20/Poly1305 choice: software implementations of AES and GCM are either vulnerable to cache-timing attacks (vast majority), or unusably slow (you are not likely to encounter these); guaranteeing that you can rely on a hardware implementation of AES and guaranteeing that your software stack uses the hardware implementation of AES that is available is a nontrivial auditing task.


Is there a cipher that avoids double bigrams? Are there any known ciphers that whose ciphertext (given any plaintext) avoids bigrams of the form "aa, bb, cc, etc."?

What about known ciphers that make bigrams of form "aa, bb, cc, etc." rare compared to other bigrams?

I understand that it is easy to construct a cipher that does this, but I am wondering if there are any in the literature that have this property.

The Playfair cipher would partially avoid this in that it does not encipher two letters that are the same. So the letter pair "LL" would be enciphered as "LX" "L_" (or sometimes just "LX"), producing different ciphertext letters for each pair.  It would allow ciphertext letter repeats of the form "AB BC" where "AB" is one pair of letters that are enciphered together, and "BC" is the next pair of letters that are enciphered together.  Indeed, this would occur when enciphering "at ta" (such as in "attack").

Looking at a list of classical ciphers, I don't see any others that would even avoid double letters to that extent.

You may want to look here which discusses the frequency of double letters in bigram frequencies.  In particular, "LL" is the most common double letter bigram in English, and  occurs 0.577% of the time, and only "LL", "SS", "EE", "OO", and "TT" (and almost "FF") beat the random bigram frequency of 0.148%.  I'm not sure if this counts repeats of the form "at the" or not.  So if the bigram frequency depends on the plaintext, double letters bigrams would generally be less common than other bigrams.

Another factor that probably comes into play is that "aa" is more noticeable than "ax", even if the frequencies are the same.


Difference between MPC and outsourced computation I am reading an introductory paper on multi-party computation (MPC), and it makes a distinction between outsourced computation and MPC.

  In an outsourced computation, one party owns the data and wants to be
  able to obtain the result of computation on that data. The second
  party receives and stores the data in an encrypted form, performs
  computation on the encrypted data, and provides the encrypted results
  to the data owner, without learning anything about the input data,
  intermediate values, or final result. The data owner can then decrypt
  the returned results to obtain the output.

After reading this, I  found outsourced computation and its difference to MPC is not quite clear. In MPC, parties can send their encrypted data to a trusted third-party to compute a result that then gets delivered back to them. This seems like what was described above, no?

My thoughts to justify the difference include:

Perhaps outsourced computation only involves two parties, the data provider and the data processor
Perhaps outsourced computation does not require the individual to send encrypted data to the second party

In summary, what is the difference between MPC and outsourced computation?

About outsourced computing: under a security viewpoint, there is no challenge in trusting a thirty party and give him all responsibility on doing the task in secrecy and return the output the the parties. Trust a central party is all everyone doesn't want. So security isn't a problem when you trust someone.

Secure multi-party computation: in the most classical view, with secure MPC we have n parties entering their correspondent inputs (in secrecy), and get their correspondent output(s) (when it is the case) (in secrecy). The challenge here is the inexistence of a trusted party, and all we want is that a protocol makes the role of that trusted party, giving the guarantees that trusted party could provide.

For example, we can consider some security level of a digital version of an election: think about some computer that we can trust, in a hypothetical idealized world, realizing the election function. Your challenge is: how can you construct a (distributed) protocol that runs among the parties, and that gives all the security guarantees that trusted computer could provide to the electors.


How to do division using Beaver Multiplication Triples It is very straight-forward and intuitively to achieve addition, subtraction and even generalized polynomial using Beaver's Multiplication Triples. However division seems difficult to achieve on two secret-shared values (each with precision $f$).

Assuming the case of secure two-party computation, there are two secret values

$$[a]\leftarrow\{0,1\}^n, [b]\leftarrow\{0,1\}^n$$

And we want to securely compute

$$c= \Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor$$

where $c$ is an integer.

So my question is : How to design a such division protocol, or is there any papers? Thanks a lot.

There exists a number of general multiparty protocols that can securely compute any function. Some of these, for instance SPDZ and this one, use Beaver triples. These protocols can compute integer division, since integer division is a function.

However, using general multiparty protocols may not be the most practical or efficient. So there has also been some research in specialized protocols for integer division. There is e.g. a paper describing a secure two-party protocol for integer division here. The "related work" section in that paper contains references to other integer division protocols for more than two parties. I'm not sure any of these protocols use Beaver triples, though.


Safe to use 32 bytes of a 64 byte key? Sorry in advance as I am not very skilled in crypto. I am a software developer trying to create secure applications.

I have implemented a diffie-hellman key exchange between client and server. The library I am using only lets me create a minimum size key of 64 bytes (512 bit).
During transport messages will be encrypted with an AES-256 cipher. This takes a maximum key of 32 bytes (256 bit).

Is it safe to use the first 32 bytes of the diffie-hellman generated key or does this create a hole in security?

I may be completely incorrect so please forgive me; AES-256 is a standard widely used encryption algorithm today and using a 32 byte key is secure. I didn't just wan't to the approach that "Because it works it must be secure"

Currently we do not think that 512 bit DH is secure. You can look for more secure parameters (i.e. above 1280 bits at the very least) is secure. Secure key sizes can be found at keylength.com. For DH you can e.g. look at the NIST recommendations for "Discrete Logarithm" (the underlying mathematical problem that is the base of DH-based cryptography).

Using Diffie-Hellman as base for AES-256 is a bit misleading, as it is not likely that your DH provides the same level of security as AES-256. As you can see in the tables DH requires a 15K key size (!!!) to reach the same security level. Claiming a security level of 256 bits would be unfair (but read the next section)

What DH generates is a shared secret. This shared secret has a lot of pseudo-randomness. As such it can be used directly by using the leftmost (or rightmost, but leftmost is more common) bits of the shared secret as a key. More information here (note the author of the question!). This is however not considered good practice, as you preferably do not want to have any bias of bits in the secret (AES) key.

So commonly we use a key based key derivation function (key based KDF or KBKDF) to condense (or extract) the pseudo-randomness of the master secret into one or more keys. That way each bit of the key depends on each and every bit of master secret material and removes any possible bias in the bits of the resulting secret key.

Quite often cryptographic API's offer combined key agreement / key derivation functions where a KDF is already used upon the result. Sometimes that means indicating a hash function, which is then used as (only) primitive within the KDF. The compression functionality within a hash is, as you might imagine, perfect for condensing the pseudo-randomness.

If you do not use a KDF then you might want to use a 256 bit AES key as it will have at least 247 bits of pseudo-randomness, as specified in the answer on my question. A 128 bit key will have less than 128 bits after all.


modified substitution permutation networks I have a model of substitution permutation networks, modified as follows:

instead of iterating $n$ times a round(each of which is composed of the key mixing phase,
substitution S-BOX) and permutation), I apply the key mixing phase to the input $n$ times, followed by $n$ substitution, followed by $n$ permutation.
What can I say about the security of this model?

Your construction is completely insecure: a single known plaintext / ciphertext block pair is sufficient to decrypt all blocks encrypted with the same key.

Specifically, let me write your block encryption function $E_K$ as $$c = E_K(p) = P^{(n)}(S^{(n)}(p \oplus K_1 \oplus K_2 \oplus \dots \oplus K_n)),$$ where $p$ is the plaintext block, $c$ is the corresponding ciphertext block, $S^{(n)}$ and $P^{(n)}$ denote the $n$ times iterated substitution and permutation steps respectively, $K_1$ to $K_n$ are the $n$ subkeys derived from the encryption key $K$ by the key schedule, and $\oplus$ denotes the linear subkey mixing operation (i.e. normally bitwise XOR).

Since the substitution and permutation phases are invertible and independent of the key, I can just apply their known inverses $P^{(-n)}$ and $S^{(-n)}$ to the known ciphertext block $c$ to obtain the intermediate value $$x = S^{(-n)}(P^{(-n)}(c)) = p \oplus K_1 \oplus K_2 \oplus \dots \oplus K_n.$$  XORing this with the known plaintext $p$ then gives me the bitwise XOR of the subkeys $$\tilde K = p \oplus x = K_1 \oplus K_2 \oplus \dots \oplus K_n.$$  Clearly, given $\tilde K$, I can now decrypt any ciphertext block $c'$ to the corresponding plaintext block $p'$ as $$p' = S^{(-n)}(P^{(-n)}(c')) \oplus \tilde K.$$

The same attack works with trivial modifications also if the key is mixed with the plaintext e.g. using modular addition instead of bitwise XOR.  Indeed, all it really needs is for the operation $\oplus$ to be associative and invertible.

Furthermore, even if the subkeys were somehow combined with the plaintext in some weird way that was not trivially invertible, we could still use the approach outlined above of first inverting the unkeyed substitution and permutation steps, leaving only the key mixing steps, and then focusing our cryptanalysis efforts on that.  So, in effect, the substitution and permutation steps in your construction provide no cryptanalytic strength whatsoever beyond that provided by the key mixing step alone (which for normal key mixing methods, like bitwise XOR or modular addition, is essentially zero).

In fact, this is why normal substitution–permutation ciphers like AES both begin and end the encryption process with a key mixing step: any unkeyed substitution or permutation steps before the first key mixing step or after the last one would contribute no additional security to the cipher, since an attacker could just invert them even without any knowledge of the key.


Why do Edwards curves protect against side-channel attacks? From Wikipedia:

  One of the attractive feature of the Edwards Addition law is that it is strongly unified i.e. it can also be used to double a point, simplifying protection against side-channel attack.

Could you explain with more detail how an explicit doubling can protect against side-channel attacks?

Some formulas like the usual short Weierstrass addition formula for curves over fields of characteristic ${>}3$, involve terms like $$\frac{y(P) - y(Q)}{x(P) - x(Q)}$$ which don't work when $P = Q$.  So to reliably add two points, you have to write logic like:

if P == Q:
    return doubling_formula(P)
else:
    return addition_formula(P, Q)

This conditional may take a different amount of time depending on potentially secret points $P$ and $Q$.  Even if doubling_formula and addition_formula take exactly the same amount of time, the machine may take a different amount of time depending on which way the branch goes because it may predict one way and take more time if the prediction is wrong, or it may have different effects on CPU caches depending on which branch is taken.  In general, CPUs do not keep branch conditions secret.

One way to do this is to compute both doubling_formula(P) and addition_formula(P, Q) and then choose between them with arithmetic like (d & m) | (a & ~m) where d is the outcome of doubling, a is the outcome of addition, and m is all 1 bits if $P = Q$ and all 0 bits if $P \ne Q$.  But this costs more to compute because now you have to compute the addition formula and the doubling formula, even if you're going to use the result of only one of them, whenever you want to add two points.

The Edwards addition formula, in contrast, does not have any such terms, and it works for all pairs of points, even if $P = Q$.  Consequently you don't need to write conditionals and you don't need to spend the cost of computing multiple different formulas.  But it only works for some curves like edwards25519; it doesn't work for, e.g., secp256k1.

(While there are complete addition formulas for arbitrary curves, they are considerably costlier than the Edwards addition formula, so like the do-every-branch-and-select-with-arithmetic approach, they present a conflict between performance and security.)


Security defined with space complexity My question is about security defined through space complexity. Suppose I have an encryption function $C=E(K,P)$ for which it can be proved (algebraically) that given $P,C,$ the possible keys which match the equation belongs to a set $S(P,C)$ of exponential size but $$|S(P,C)|\ll O(2^{\ell(K)})$$ where $\ell$ is the key length.

Then the key can be verified in parallel in polynomial time breaking the scheme in polynomial time by parallel computation but far better than brute force search. If no other estimate of $S(P,C)$ of smaller size is known, can this be considered a secure scheme? In such a case can the security be be considered weak if $|S(P,C)|$ can be shown to be bounded by sub exponential size?

Firstly, I assume you use the $\ll$ not as in number theory where $f(\ell)\ll g(\ell)$ means $f(\ell)=O(g(\ell))$ but as much less than, which usually means $$f(\ell)\leq \frac{g(\ell)}{h(\ell)}$$ where $h(n)$ is some increasing function of $\ell.$ The crucial question is how fast is $h(\ell)$ growing?

To break the cryptosystem in parallel polynomial time, you need an exponential number of processors, unless $h(\ell)$ is itself growing very fast in $\ell.$ In fact this argument could apply to any cryptosystem which is considered secure, such as AES, for example. And this is NOT far better than brute force, it is just parallel brute force in the presence of the obvious embarrassing parallelism in the key space, since you need to deploy an exponential number of processors, as in the EFF key search attacks on DES.

What I am trying to say, not very well, is that any secure cryptosystem is insecure under parallel computation to some extent. So I'd say in answer to your first question, this is not a real weakness.

As to your second question, yes, if $S(P,K)$ is subexponential in size, this is a real weakness.

And finally, since you are talking algebraic attacks, presumably you have an algebraic specification of what $S(P,K)$ looks like, which you can use in your attacks.


Execution speed of AES_128 GMAC operation I have read about the speed performance of AES_128_GCM on specific processors Intel and AMD that support AES New Instruction set. As compared with CMAC and HMAC is it relatively slow for other processors such as ARM9 board or cryptographic hardware?

GCM is sometimes called a 1.5 pass AEAD cipher, where the CTR encryption counts for 1 and the GMAC counts for 0.5. So you would indeed expect it to be faster than encryption + CMAC and HMAC with regards to the amount of CPU instructions.

That is: as long as the encryption is using AES for both solutions. GCM requires a 128 bit block cipher while CMAC and HMAC could also work with a fast stream cipher.

If the hardware however doesn't support 32 bit multiplications the speed may drop significantly, so it's not that great on embedded processors with a 8 or 16 bit ALU. ARM however is 32 (for ARM9) or 64 bit so it should be relatively fast on one.

Note that there may be rather big differences with regards to implementation. It's definitely recommended not to take anything for granted and test which authenticated cipher is fastest in practice.


I have a new cryptography algorithm, what should I do? I created a new, unknown symmetric encryption algorithm. It looks like it's very fast and can be useful. I'm kind of independent researcher, hobbyist. Since years I'm interesting in Kakutani's problem and it's generalizations. And that's why I was abble to create it. I'm not a matematician with academic degree, what's more I even can not programming (I know only total basics of C), but I am very involved on the subject of the Kakutani's problem and its generalizations, I have known and read all major scientific publications since years ago on this topic. Here is an example of hash function which can be done with Kakutani's sequences and it's generalizations:
https://arxiv.org/pdf/1801.05079.pdf
As you can see it is possible to made a brilliant cryptographic/hash algoritm based on these functions, if you know how to use them. In recent years, more and more scientists are beginning to see the cryptographic potential in this field of mathematics (Kakutani's problem). So it's not just some easy topic, another stupid algoritm, it is based on one of the biggest unsolved math problem. Someone who will create algoritm based on pseudorandomness of Kakutani's sequences (and generalizations) can probably create very strong cryptographic tool.
Algoritm like this (I mean this one which I created) requires testing in couple areas (confusion and diffusion, differential cryptanalysis and so on), but I do not know cryptography so well to do this on my own (even don't know how to start). Simultaneously I have strong believe that my algoritm is something valuable and interesting.
What should I do? Do you think that such algorithm can be commercialized or it is possible to somehow made a profit on it (I also thought about a patent)? Like I said, it looks like algoritm runs faster than AES but I'm not abble to check everything on my own, for example confusion and diffusion of this algoritm is still a mystery to me (but I hope that algoritm will pass all tests). Maybe some of you guys work in cryptography and can give me some advice? Or maybe should I publish it somewhere on the internet and forget about profits or even authorship (because what can I do as nobody in the cryptographic industry)?

Do you think that such algorithm can be commercialized[...]?

This is very unlikely. AES is fast enough for most applications and where it isn't one usually uses (the cheap) hardware acceleration to fix that. Other common scenarios have the usually fast enough for them ChaCha stream cipher. This only leaves true edge cases on ultra-low power devices but this has active research going on with free schemes and some efforts from NIST, so a scheme with no proper analysis will not impress / interest most people.

  [Is it] possible to somehow [make] a profit on it (I also thought about a patent)?

Patenting a cryptographic algorithm has a great history of seeing it being unused for at least the lifetime of the patent and potentially afterwards as well due to standardization and implementations having already chosen other schemes which are good enough. Examples of this are the OCB mode of operation which is faster than most other known authenticated encryption algorithms but has seen little use due to patents and Schnorr signatures which are only now seeing standardization - after the patents expired which in fact prompted (EC)DSA to be created to avoid the legal issues.

  it looks like algoritm runs faster than AES

Without proper security analysis speed claims will likely not be interesting. After all 4-round AES also runs faster than AES but is somewhat easily broken.

  Maybe some of you guys work in cryptography and can give me some advice? Or maybe should I publish it somewhere on the internet and forget about profits or even authorship (because what can I do as nobody in the cryptographic industry)?

While some active users here do work in cryptography, note that Crypto.SE does not accept questions to analyze non-trivial primitives as this cipher most likely would be. Publishing it and hoping someone will have a look at it because they find it interesting may be your best bet (sci.crypt and reddit's /r/crypto may be starting points for advertisement) though paying a professional cryptographer is the only "sure" way to get proper attention at the scheme.

Having a reputation in the academic community for cryptanalysis would indeed also help in getting more interest - especially as good schemes by people without reputation are indistinguishable from bad schemes by people without reputation with the latter being far more likely. Additionally most people don't react too well to their pet project being broken which means such analysis takes a lot of time and yields no satisfying result for anybody involved most of the time which is why most people don't do it (for free).

What could make this scheme potentially interesting is if it had a security reduction from (S)PRP security to some known / proven pseudorandomness result of the Collatz problems - but even then probably mostly for theoreticians.


AES - Finite Field Multiplication on 8 Bit Platform Section 4.1.1 "Finite Field Multiplication"(page 53) of "The Design of Rijndael", it states

How the equation 4.1 has been formed and transformed into equation 4.2?

In section 2.1.6 "Polynomials and Bytes"(page 15), equation 2.27 and 2.28, highest power of x is 7, whereas in above equations 4.1 and 4.2, it is 8. How?

In next line it states

  The multiplication by 02 is denoted xtime(x). xtime can be implemented
  with a shift operation and a conditional XOR operation.

From Equation 2, it seems all values have been given left circular rotation by 1 bit, but what is Conditional XOR? How this multiplication can be implemented with a shift operation and a conditional XOR operation?

I. Polynomial representation
$b_7b_6b_5b_4b_3b_2b_1b_0$ represent the polynomial in $\operatorname{GF}(2)[X]$: $b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0x^0$ .
$\texttt{02}$ is $\texttt{00000010}$ thus $0x^7+0x^6+0x^5+0x^4+0x^3+0x^2+1x^1+0x^0 = x$.
$b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0x^0 \cdot x = $
$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0$
or $b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}$
that is equivalent to $b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1 = b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}$
II. Modulo reduction by $x^8 + x^4 + x^3 + x + 1$:
This leads to two problems:

you have a loss of information: you cannot invert the S-box (which would be anoying in the case of AES)
the upper bit does not fit into the byte

That is why there is the $\bmod m(x)$.

In the specification of Rijndael, we consider the bytes as polynomials. Byte addition is defined as addition of the corresponding polynomials. In order to define the byte multiplication, we use the following irredutible polynomial as reduction polynomial:
$m(x) = x^8 + x^4 + x^3 + x + 1$. (2.29, p.16)

Thus we will reduce $b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0 \mod m(x)$.
Remark that:
$x^8 + x^4 + x^3 + x + 1 \equiv 0 \mod m(x)$
by $a \equiv c \mod m \iff a - b \equiv c - b \mod m$ we have
$x^8  \equiv - x^4 - x^3 - x - 1 \mod m(x)$
because $-1 = 1$ in $\operatorname{GF}(2)$
$x^8  \equiv x^4 + x^3 + x + 1 \mod m(x)$
Thus (going back to our previous equation):
$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0 \mod m(x) = $
$b_7(x^4 + x^3 + x + 1)+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1= $
$b_7x^4 + b_7x^3 + b_7x^1 + b_7x^0+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1= $
grouping by power this leads to:
$b_6x^7+b_5x^6+b_4x^5+b_7x^4 + b_3x^4+b_7x^3 + b_2x^3+b_1x^2+b_7x^1 + b_0x^1+b_7x^0= $
in other terms:
$b_6x^7+b_5x^6+b_4x^5+(b_7 + b_3)x^4+(b_7 + b_2)x^3+b_1x^2+(b_7 + b_0)x^1+b_7x^0$
III. $\ll$ and $\oplus$
Addition over $\operatorname{GF}(2)$ is equivalent to a XOR ($\oplus$) thus we find the previous formula:
$b_6x^7+b_5x^6+b_4x^5+(b_7 \oplus b_3)x^4+(b_7 \oplus b_2)x^3+b_1x^2+(b_7 \oplus b_0)x^1+b_7x^0$
In the end the multiplication of $b_7b_6b_5b_4b_3b_2b_1b_0$ by $\texttt{02}$ can be seen as:
$(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus \texttt{000}b_7b_7\texttt{0}b_7b_7$
or with a conditional XOR:
$(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus b_7\cdot(\texttt{00011011})$


Statistical (innefective) Fault Attacks on DES I read this paper: Exploiting Ineffective Fault Inductions on Symmetric Cryptography.

I was wondering if the same idea is applicable for DES. I know both algorithms are symmetric but the idea is not the same.

I thought if an attacker shot the left part of the penultimate round, but the final permutation on the Feistel function is a problem for me.

Does anyone have some information about this topic?

In case you are still wondering, the answer to this question is "Yes".
DES can also be targeted by the same sort of attack.

This was actually already almost entirely done against DES in a paper from 2006, by F. Amiel, C. Clavier and M. Tunstall called "Fault analysis of DPA-resistant algorithms", you can look at section 6 and the next ones, in which they show that both known and unknown faults against the S-Boxes of DES can lead to a full key recovery. What they did not cover is the case where you have a fault countermeasure in place, either a detection or an infective one.

Now, if you have some fault countermeasure, but are able to target specific location of your S-Boxes, then performing this attack remains easy. But, if you are in the unknown fault setting, with fault countermeasure, you'll need to use the same statistical tools as in the SIFA paper, but would eventually also be able to recover the key. It just needs some tweaking.


Is H(k||length||x) a secure MAC construction? If $H$ is a typical secure hash function, then $(k,x) \mapsto H(k \mathbin\| x)$ is not a secure MAC construction, because given a known plaintext $x_1$ and its MAC $m_1$, an attacker can extend $k \mathbin\| x_1$ to a longer message with the same hash.

Is $(k,x) \mapsto H(k \mathbin\| \mathrm{len}(x) \mathbin\| x)$ (where $\mathrm{len}$ unambiguously encodes the length of $x$) a secure MAC construction? Obviously it's inconvenient because you can't treat $x$ as a stream, but is there a known security weakness, or is this known to be as strong as HMAC?

This construction is not secure. It was proposed in this paper in a quick sentence for possibly fixing the insecure secret prefix construction from the other question: $\mathcal{H}(k||m)$. The author then proposes and analyzes an enveloping method: $\mathcal{H}(k_1||x||k_2)$.

An attack involving finding an internal collision applies to $\mathcal{H}(k||\ell_m||m)$. It is a bit complex, but if you are curious, it is "Proposition 4" in this paper (also see section 4.1, 1st paragraph). The authors also note that the construction involves additional assumptions on the hash function than the standard ones (collision-resistance, (second) preimage resistance). It is not as efficient of a break as the length-extension attacks on the other construction but it is theoretically a break relative to the security of HMAC.

I will also note that "unambiguously" encoding the length could be problematic. For example (using base 10 for readability), if I hash m=08 with length=2  and some k, then a length extension attack may find m=0896346218569465994320 which could be interpreted as length=20 and m=896346218569465994320. One fix to unambiguously delimiting the length from the message is to fix a certain number of bytes for the length, but you now no longer have a MAC that accepts arbitrary-length inputs.

In conclusion, the HMAC construction is very simple, accepts arbitrary length inputs, and does not rely on an encoding scheme to work.


Random session key + predictable IV I'm using Blowfish in a toy Diffie-Hellman communications scheme. Random session keys are generated for each connection.

In this case I can simply feed a null array to the IV right? The same plaintext would never be encrypted with the same keystream.

If you use CBC mode and your communication protocol looks like SSL, then you may have trouble. In SSL 3.0 and TLS 1.0, the IV for each record is the last block from the previous IV; this implies that an attacker who can both inject some data of his own in the stream, and observe the outcome, may know the IV for the next record and choose his data accordingly. This is the basis for the BEAST attack: that attack context turned out to be realistic when the client is a Web browser.

In all generality, a decent communication protocol should provide both confidentiality and integrity, which means that your data should use a MAC. Combining symmetric encryption and MAC properly is known to be tricky and a good method is to use an encryption mode such as GCM or EAX which does both jobs. A nice point here is that these two modes don't require a random IV, only a non-repeating IV.

This leads to a communication protocol where the initial key exchange (say, your Diffie-Hellman) produces an initial shared secret, which is expanded into two symmetric keys, for the two directions of communications (this "expansion" can be as simple as hashing the initial shared secret with SHA-256, and splitting the 256-bit result into two 128-bit halves). Then both client and server send a sequence of "messages" to each other, using as IV the sequence number of each message (first message from client to server uses as IV the value 1, second message uses the value 2, and so on).

Note that GCM and EAX rely on AES. You can adapt them to any 128-bit block cipher. Usage of block ciphers with 64-bit blocks, like 3DES or Blowfish, is not recommended nowadays, because security of many encryption modes tends to break down when encrypting $2^{n/2}$ blocks with the same key, when blocks have size $n$ bits. For 64-bit blocks, the threshold is around 30 gigabytes, which is not that much.

If your protocol is single-record (after the key exchange, each party sends a single message, which is encrypted in one go, avoiding any BEAST-like issue), then a fixed IV is acceptable, since the key will be used for a single encryption run. However, it would be equally acceptable to derive from the shared DH secret a symmetric key for encryption and the IV; this is what SSL/TLS does (or at least did prior to version TLS-1.1): see the standard, section 6.3.


Why is the security level defined by $\log _{2} \inf \{ t_{i}/\varepsilon_{i} \mid i \in I \}$ In public-key cryptography, the security level indicates the strength of an adversary in breaking a scheme or solving a problem, which can be seen as the time cost of breaking a scheme or solving a problem. Generating a scheme with a security parameter $k$ does not mean that this scheme has $k$-bit security. The real security level depends on the mathematical primitive and the scheme construction.

  Suppose all potential attack algorithms to break a proposed scheme have been
  found with the following distinct time cost and advantage

  $$\{ (t_{i},\varepsilon_{i}) \mid i \in I \}$$

  Let

  $$2^{k^*} = \inf \{ t_{i}/\varepsilon_{i} \mid i \in I \}$$

  Then we sat this scheme is $k^*$-bit security.

My question is why the form is $t_{i}/\varepsilon_{i}$?

Of course the security level depends on the time cost $t$ and the advantage $\varepsilon$. I assume that

$$2^{k^*} = \inf \{ f(t_{i}, \varepsilon_{i}) \mid i \in I \}$$

Thus, there are some basic properties of $f$.

P1. For $t_{2} > t_{1}$ and $\varepsilon_{2} > \varepsilon_{1}$, $f(t_{2}, \varepsilon_{1}) > f(t_{1}, \varepsilon_{1}) > f(t_{1}, \varepsilon_{2})$. If we assume that $f$ is smooth, then we can let $df/dt > 0$ and $df/d\varepsilon < 0$.

P2. For every attack algorithm,  $f(t, \varepsilon) \leq 2^k$.

P1 and P2 hold true if we let $f(t,\varepsilon) = t / \varepsilon$.

However, there are may functions that satisfy these properties. And I think $f$ should also satisfy more properties.

For example, given an attack algorithm $A$, for the trivial modification of $A$, the value of $f$ should be the same.
Let $A_{n}$ be an algotithm that calls $A$ for $n$ times, $A_{n}(x) = 1$ if and only if there are more than $n/2$ times that $A(x) = 1$.
We know that
$$\frac{t_{A_{3}}}{\varepsilon_{A_{3}}} = \frac{3 t_{A}} {3\varepsilon_{A}/2} \neq \frac{t_{A}} {\varepsilon_{A}} $$

I try to explain the "trivial modification" more clear. If there is an oracle machine $M$ which is independent on the scheme, then I think $M^{A}$ should be a "trivial modification" of $A$. I believe that the power of $M^A$ should not be stronger than $A$. However, I do not know how to define the oracle machine $M$ in a formal way. So, I give above example of $M$ such that $M$ asks oracle $A$ for $n$ times and the output of $M^A$ only depends on these $n$ answers. We do not care about the specific attack algorithm $A$ is (and whether $A$ has the accesses of some oracles.)

The value $t/\epsilon$ is the expected amount of time required for an attacker to "win". E.g., if he has a 50% $(\epsilon = 0.5)$ probability to guess a key in $t = 10$ seconds, then the expected length of time for him to guess the key is $t/\epsilon = 10s/0.5 = 20s$

The example you provided is a bit unspecified, and it's not clear to me that $A_3$ is a "trivial modification" of $A$, what a "trivial modification" means, or why we would expect a "trivial modification" to retain the security of the original.

To be more concrete consider two examples:

First, a blockcipher $E$ with 128 bits of security (for simplicity, 128-bit keys and 128-bit blocks). Then $E'_{k1,k2}(x) = E_{k1}(E_{k2}(x))$ could be considered a "trivial modification" of $E$ and has, as you say, pretty much the same security level --- in this case, 129 bits due to a meet-in-the-middle attack.

On the other hand, if you view the blockcipher $E$ as a PRF, then the "trivial modification" $E'_{k1,k2}(x) = E_{k1}(x) \oplus E_{k2}(x)$ has significantly more security --- we've gone from ~64 bits of security (generic birthday-bound attack) to ~85 bits of security (c.f "The sum of PRPs is a secure PRF" by Stefan Lucks).

So in the absence of more specific information about your $A_3$, it's entirely reasonable that $A_3$ may have either about the same, significantly more, or even significantly less security than $A$.

A final note I don't know what text your definition comes from, but although it's a completely reasonable definition for "bits of security" --- a term often used informally --- it's a bit incomplete since it doesn't account for possible limits to the number of queries an attacker can make, or the amount of pre-computation he could perform before being provided with oracle access.


Encoding of the message in Regev encryption In public key encryption from LWE, we do the following steps

$\textbf{PKE.KeyGen($1^n$)}$ takes as input the security parameter n, samples $A \leftarrow \mathbb{Z}_p^{n \times m}$ and $\textbf{e} \leftarrow \chi^m$, and outputs a key-pair $(pk,sk)$ where $sk = s \in \mathbb{Z}^n_q$ and $pk = (A,s^T\cdot A + \textbf{e}^T)$.
$\textbf{PKE.Enc($pk = (A,b^T),b$)}$ takes as input a public key $(A,b^T)$ and a message $a \in {\{0,1}\}$, samples a short vector $r \leftarrow {\{0,1}\}^m$, and outputs a ciphertext $(A\cdot r,b^T\cdot r + a \cdot \lfloor\frac{q}{2}\rfloor)$.

If we now assume that the secret $s$ is a matrix instead of a vector, how can we deterministically encode the message $a$ so that we can recover it during decryption? The error term will also be a matrix in this case where each column is chosen independently of the other from some error distribution.

I think there are are several ways to do that. For instance, the "BGV-like" way is to embed the bit $a$ in a vector $\vec{a} = (a, 0, 0, ..., 0)$.

Then, the encryption is quite the same: $a \mapsto (Ar, Br + \vec{a}\lfloor \frac{q}{2} \rfloor)$. And to decrypt, you can subtract $SAr$ from the second component to get $v := Er + \vec{a}\lfloor \frac{q}{2} \rfloor$. Then, notice that $v$ is a vector whose the first entry is $er + a\lfloor \frac{q}{2} \rfloor$ where $e$ is the first row of $E$. Therefore, if you take the first entry of $v$, you get the same that you have in the original scheme and you can proceed as before.


Is this JS library using openssl genrsa -rand improperly? pem, a JS wrapper around openssl, has the following code in it:

var params = ['genrsa',
    '-rand',
    '/var/log/mail:/var/log/messages',
    keyBitsize
];

Am I correct in thinking that that is an improper usage of the -rand option (poor entropy = bad seed for random number generator)?

Cause this dude just closed the issue thinking it's OK, and if he's wrong, it'd be nice if someone could explain in better detail than I can why what he is doing is unsafe.

If I'm mistaken and it is safe, I'd be curious to hear why.

Thanks Cryptography StackExchange!

I ran the command under dtruss on OSX, with it pointing to a static file. Even then, it appears to use this as an additional source of randomness to /dev/urandom.

It's distasteful and almost certainly pointless. But assuming it only mixes the data into an already cryptographically-secure source of randomness, it's not actively harmful. That said, I can only see the syscalls being made — it's possible this is not what's happening at all under the hood.


Trying to find an algorithm to share portions of a key with multiple people Sorry if this question's a bit basic, but I don't know of any way to ask it concisely enough for a search... What I'm looking for is a proven means of doing the following:

Create x number of strings so that any combination of at least y of those x can be used to recreate a message.

For example: if I have "this is my message" (the message), I'd like to split it up in some way where I can give 10 people (x) part of the message, but ensure that the message can be reconstructed accurately as soon as any 7 of those people (y) combine their individual components.

In reality this message would be a public key for encryption, although I don't see how that would really matter. Ideally, both x and y would be as variable as possible (one algorithm/approach which works when x=10 and y=7, as well as when x=50 and y=1, as well as when x=5 and y=5, etc).

What you are looking for is called secret sharing. It is a well studied problem and you should be able to find lots of information now that you know what to search for.