RSA Encryption Time with Different Block Sizes I was working on encrypting a few files on my computer and I was using OAEP for padding with RSA. I noticed that it was taking a long time to encrypt some of my files with a small block size, so I tried to encrypt the same files with a much larger block size and it finished encrypting incredibly fast. I was thinking that the number of encryption cycles since there were so many blocks and/or the amount of padding used could be the reasons why it was so much lower when I tried to encrypt the files with small block sizes. Does the number of encryption cycles and/or amount of padding used from smaller block sizes compared to large block sizes impact the time. If so, why is this? If there are other reasons too as to why RSA with OAEP encrypts files much faster with larger block sizes compared to smaller block sizes, I would love to learn more about that!

Disclaimer: I completely understand that RSA is NOT meant for file encryption, I am just trying stuff.

Thank you in advance for any logic behind this that you can provide.

The maximum payload for each encryption using RSA OAEP is displayed here. For any message up to that size a complete RSA operation needs to be performed. Of course, if you encrypt each byte separately then you won't get much performance, and your ciphertext will expand enormously. You need to make sure that you use the entire possible payload for each encryption.

Encryption for RSA is a relatively fast operation compared to decryption. The RSA public exponent is generally kept small (and to a specific value with just two bits set, 65537 or 0x10001 in hexadecimals, often called F4). So encryption may still be pretty fast even with larger key sizes. Key generation and decryption however will take much more time. As the relative OAEP padidng overhead is also much lower for larger key sizes, I'd expect the encryption speed to initially grow and then quickly degrade again when the RSA modulus start to get really large. Decryption speed will have degraded long before that in all likelihood. For generation of 16,384 bit key pairs I definitely suggest to use a fast CPU....


Relations between Number theory/Algebra and Lattice based cryptography I am an intern (I started yesterday) in a research lab on lattice based cryptography and I have a more mathematical background, in particular algebra.

I would like to know what type of algebraic problems intervene in lattice based cryptography?

I am supposed to do a phd and I would like to work more on algebraic aspects of cryptography, but I have no idea where to look at.

Studying lattices (and lattice-based schemes) does not necessary involves algebraic number theory (or other somehow advanced topics). The security reductions uses more aspects of complexity theory and probabilities. And the algorithms to solve lattices problems (for instance, to solve SVP, CVP, BDD, etc), in general, use more linear algebra.

I think you should check the structured versions of lattice-based problems (like RLWE and RSIS). For instance, the description of RLWE typically involves Cyclotomic number fields and the their rings of integers.

The manual A Toolkit for Ring-LWE Cryptography can be a good starting point.

But even if they use a lot of concepts from Number theory and Algebraic Number Theory, they are not necessarily based on problems studied in these fields (the security of schemes based on ring variants of LWE and SIS relies basically on the assumption that SVP and other lattice problems are still hard over the lattices generated by such structured problems... e.g. ideal lattices).

One problem that is maybe more related to algebra but is also studied in cryptography is the problem of finding short generators of principal ideals. You can easily find papers about it. For example, this one: Recovering Short Generators of Principal Ideals in Cyclotomic Rings.


CMAC - how is ambiguity resolved? To avoid the dummy padding block, CMAC uses 2 separate keys K1 & K2. If padding is required, the final block is padded & then XORed with K1. If no padding is required, then it's XORed with K2. I understand how this avoids the extension attack. However, at the verification side, how does Bob know whether the final block was XORed with K1 or K2?

However, at the decryption side, after decrypting the final block, how does Bob know whether the final block was XORed with K1 or K2?

CMAC is not an encryption scheme but a MAC - and more precisely a PRF - by design. As such the input you get during authentication is a subset of the input you get during verification. In particular during authentication you get the message and the key $(k,m)$ and during verification you additionally get a transmitted authentication tag $(k,m,\tau)$.
Verification then works by computing the MAC on $(k,m)$ yourself and checking the result against $\tau$. As you now have the message to be authenticated yourself you can use the same decision strategy as the original signer to decide which key to use for the final block.


Is there a possibility to create a public key block cipher? Why there is no public key-based block cipher? It is known that the block ciphers are symmetric-key encryption. However, what is the motivation to not design a public key encryption that encrypts blocks of bits?

Let's make a list of reasons why public "block ciphers" are generally not used:

asymmetric ciphers expand the ciphertext compared to the plaintext, rather than being a permutation of a block of bits;
asymmetric ciphers require a lot more processing power;
asymmetric ciphers require a lot more state;
asymmetric ciphers are more vulnerable to side channel attacks (as they are based on big number arithmetic rather than binary operations on smaller words);
asymmetric ciphers are more vulnerable against attacks using quantum computers;
normal block cipher modes do generally not apply to asymmetric ciphers;
because of 2 & 3, (full) hardware acceleration is generally less common for asymmetric ciphers.

I've left the word "generally" out of above reasons, but that may have to be inserted in each reason. There may be asymmetric ciphers that violate one or more of the rules displayed above.

Hybrid cryptography - where asymmetric / public cryptography is combined with symmetric / secret key cryptography - is rather easy to implement. So there is simply not much need for modes of encryption that use an asymmetric cipher for larger messages.

Modes such as ECIES or RSA-KEM are easy to describe and implement. Their main drawback is that the symmetric cipher mode of operation is generally not standardized.


What is the purpose of having a one-way function also be a permutation on it's on domain? From a cryptographic sense, what value is added from setting the domain to be the image in the mapping?

A one-way permutation (OWP) is more structured than a one-way function, and hence a stronger object. This makes the task of constructing higher cryptographic objects from OWPs easier and also, at times, leads to more efficient constructions. For example, consider pseudo-random generators (PRGs): it is quite straightforward to construct a PRG from a OWP; but constructing a PRG from a OWF took a lot more effort -- you can read more here.


Computing/using RSA modulus without knowing its factors There are some protocols, e.g. this, that require parties to compute/use RSA modulus: $N$ without knowing it's factors or $\phi(N)$.

One way of doing it is to use a trusted party.

Question: Is there any other way of generating/using $N$ in the above schemes without using a trusted party? (If yes, can you refer me to some papers)

It is possible to do this with secure multiparty computation. There are several papers about this problem, but the most recent state of the art is:

  Tore Kasper Frederiksen and Yehuda Lindell and Valery Osheter and Benny Pinkas: Fast Distributed RSA Key Generation for Semi-Honest and Malicious Adversaries


How to derive a hash function from another hash function? Problem: Hash functions derived from another hash function (4 marks) Suppose that $H:\{0,1\}^* \rightarrow \{0,1\}^n$ is a collision resistant hash function. Define a new hash function by $G:\{0,1\}^* \rightarrow \{0,1\}^n$ such that $G(x) = H(H(x)).$ Prove tht $G$ is also collision resistant

I'm trying to figure out how to solve this, apparently, it's hashing the hash value itself. So G has two rounds of hashing the original message x. I tried searching for the relationship properties that I could use to achieve this

Collision resistance implies 2nd-preimage resistance
If the output values of  are uniformly distributed, then collision resistance implies preimage resistance
If the output values of  are uniformly distributed, then 2nd-preimage resistance implies preimage resistance
Preimage resistance does not imply 2nd-preimage resistance
2nd-preimage resistance does not imply collision resistance

But I didn't find anything I could use, I'm really having trouble, so I'd appreciate any help.

The main conceptual trick here is the one used over and over in cryptography proofs, known as "reduction". Suppose that you have a problem $A$, which is assumed to be a "hard problem". You want to show that another problem $B$ is also a "hard problem". To do that, you imagine that you have some machine or system that can solve $B$; and from that machine or system, you build a solver for problem $A$; that new solver uses the solver for $B$ as an elementary block box. If you can do that, i.e. solve $A$ as long as you have access to a solver for $B$, then this shows that solving $B$ must be hard: an easy solver for $B$, used in your construction, will become an easy solver for $A$, which contradicts the hypothesis of $A$ being a hard problem.

I'll take an example with square roots modulo a big non-prime integer. This is an example meant to explain how a problem $A$ is reduced into a problem $B$, and vice versa. To follow this example, you don't need to fully understand the details of the involved algebra; what matters here is that we make solvers for some problems based on solvers for other problems.

Suppose that you have $n = pq$, where $p$ and $q$ are two unknown and big prime integers; you only have their product $n$. Finding $p$ and $q$ from $n$ is a hard problem; it is called integer factorization, and mathematicians have looked for efficient ways to do that for more than 2500 years, and they still don't know how to do it for large integers (current record is for a 768-bit integer $n$). This integer factorization is the problem $A$. We assume that it is hard.

Now consider the problem $B$: from an integer $x$ such that $1 < x < n$, find an integer $y$ such that $y^2 = x \bmod n$. This is basically finding a square root of $x$ modulo $n$; about 1/4th of integers $x$ in the $1..n-1$ range admit square roots, and if $x$ has a square root, then it will (usually) have four distinct square roots. We want to show that, in all generality, $B$ is a hard problem.

Suppose, then, that you have some system $S$ that can find a square root for any input $x$ (for any $x$ that has square roots, that is). We can then build a new system, that uses $S$, and can be used to factor $n$. It works in the following way:

Generate a random value $k$ in the $q$ to $n-1$ range.
Compute $t = k^2 \bmod n$.
Invoke the system $S$ on $t$. We build that $t$ as a square, thus it has square roots, and we already know two of them, which are $k$ and $n-k$. The system $S$ will return one of the four square roots of $t$; let's call it $u$.
If $u = k$ or $u = n-k$, we were unlucky. This happens half of the time. Start again with a new random $k$.
Otherwise, compute the Greatest Common Divisor of $n$ and $u+k$. This GCD will be either $p$ or $q$ with very high probability.

This algorithm shows how to factor a big integer $n$, provided that a square root extractor (system $S$) modulo $n$ is made available. Since integer factorization is hard, this should not be feasible.

The same concept works in the other direction in that case. What the algorithm above shows is that extracting square roots modulo $n$ cannot be easier than factorizing $n$. In the other direction, we can show that factorizing $n$ cannot be easier than extracting square roots modulo $n$: suppose that you have a machine or system $F$ that can factor big integers. Now, given an integer $n$ and an input $x$ for which you are challenged with finding a square root, you can do the following:

Call $F$ on the integer $n$ to get its factors $p$ and $q$.
Compute the square roots $y_p$ and $y_q$ of $x$ modulo $p$ and $q$, respectively. Modulo a prime, square root extraction is easily done with the Tonelli-Shanks algorithm.
Recombine $y_p$ and $y_q$ into a square root $y$ for $x$ modulo $n$, using the Chinese Remainder Theorem.

Thus, if you can factor integers, you can extract square roots. Therefore, integer factorization cannot be easier to do than extracting square roots: whenever you find an efficient way to factor integers, the algorithm above can be used to turn that into an equally efficient way to extract square roots.

Since integer factorization is not harder than extracting square roots, and extracting square roots is not harder than integer factorization, then both problems are equivalent. In particular, they must be either both hard, or both easy (in practice, as far as we know, they are both hard).

Now back you your problem of hash functions. You have a given hash function $H$, and it is assumed to be collision-resistant. This means that the "problem $A$" is about finding a collision for $H$: find $m$ and $m'$ such that $m \neq m'$ but $H(m) = H(m')$. The exercise supposes that problem $A$ is hard.

Now, problem $B$ is about the collision resistance of $G$: you are challenged with finding $m$ and $m'$ such that $m \neq m'$, but $G(m) = G(m')$. The goal of the exercise is to show that $G$ is collision-resistant, i.e. that problem $B$ is hard.

Therefore, the way to do it is to make a reduction: you first suppose that you have a solver for $B$, i.e. a way to make a collision for the hash function $G$. You want to show how you can use such a solver in order to make a solution for problem $A$, i.e. finding a collision for the hash function $H$. By describing such a method, you show that finding a collision for $G$ cannot be easier than finding a collision for $H$. Since $H$ was supposed to be collision-resistant, it follows that $G$ is also collision-resistant.

All you have to do, therefore, is to find out how a collision for $G$ can be turned into a collision for $H$ (and that I leave as an exercise, because the whole point is to have you find it by yourself).


Encrypting text file line by line with stable encryption I want to store files in a secure manner (i.e. no one should be able to decrypt the contents of the file without the secret key) but I also want a diff tool to be able to show me which lines changed (let's assume that you can't learn anything about the content of the file by seeing which lines have changed).

The idea is to encrypt each line individually and convert the result to hex or BASE64 and then write each line into one file. A line with a certain content should always return the same output, no matter where it is in the file.

Specifically, I want a version control tool like Git or Mercurial to be able to efficiently handle the files as text. At the same time, a (self written) UI should be able to show a decrypted diff without the need of decrypting the data inside of the version control tool (git diff would show me the line numbers which I could then decrypt in my app to display them myself).

Is that possible? Do you know where I can find more information how to do this?

Yes, it's possible. Encrypting each line independently, like you suggest is the way to go.

Most likely you will want to use a symmetric encryption algorithm independently for each line – i.e. have a new unique IV/nonce per line. That's the simplest to implement. However, it means every line is up to 128 bits longer. If you can't live with that, you practically have to either sacrifice some security (e.g. use ECB mode without semantic security) or have changes to one line affect nearby lines as well.

One question to consider is whether to use authenticated encryption to guard against an attacker being able to modify the file. This is usually the way to go, but if you have something that ensures integrity at a higher level in your setup (signed tags/commits, say), you could afford to skip it.

For authenticated encryption you need to further decide whether you want a single MAC for the whole file (slower, since it needs to be recalculated after every modification) or one per line (which takes even more space).

In practice, I would go with AES for encryption. (Either 128-bit or 256-bit keys – doesn't matter much in practice.)

If you can live with the extra space it requires, the absolute simplest from an implementation standpoint (when you have a library that supports it), is to use AES in GCM mode. You get both encryption and authentication in one, and the only requirement for IVs is uniqueness. Each line will be up to 256 bits longer (when using 128 bits for both IV and auth. tag).
If you have authentication already, I would go with AES CTR. If you know the file will never have more that $2^k$ lines through its lifetime (counting each version of each line) you could store a $k$-bit value per line instead of a full 128-bit IV. You will need to make sure you never reuse a counter value in any case, including different "forks" of the file.
If you need a MAC for the file, you can do the above and append an HMAC.


RSA was rejected by which journal? Is it true that first time RSA algorithm  was rejected by a journal?

The paper you link to in your comment is a fictional paper where the author (inspired by experiences with reviews he got for his own papers) imagines how negative reviews to groundbreaking papers could have looked like. So its just fun ;)

AFAIK the RSA paper has never been rejected (but the very first paper of Ralph Merkle on public key crypto got rejected, as already mentioned in the comments).


Is it safe to exchange cryptographic salt and initialization vector in messages? I have a client which does the following:

salt = randomBytes(16)
iv = randomBytes(16)

// secret is a user-specified passphrase
key = pbkdf2(secret, salt)

message[0] = salt.toHex() + iv.toHex()
message[1..n] = encrypt('message content', key, iv)

// to notify server that message stream is ended
message[n+1] = end_message

I'm wondering if it is safe to send both salt and iv to the server like this?

The server does:

if(count == 0) {
  salt = message[count][0..15].toBytes()
  iv = message[count][16..31].toBytes()
  count++
  return
}

if(message[count] === end_message) {
  log(output)
  count = 0
  output = ''
  return
}

// for every subsequent message until end_message
key = pbkdf2(secret, salt)
output += decrypt(message[count++], key, iv)

AES-256-CTR is the encryption used.

The answer is yes. There is no problem with sending the IV in the clear. So, this is fine. Likewise, the salt is not there to add entropy so this is also fine.

Having said that, I understand from the code that the application is not using a uniformly distributed (and so high entropy) key. This is a problem and very bad, since it is easy to carry out a brute-force search over the password space. In practice, this is extremely effective.

The salt helps a little bit since it makes it impossible to prepare a time/space tradeoff attack (often called a Rainbow table attack, since this is one instance of the attack). However, it still will not be secure unless a very high entropy key is used.

Another thing which is very strange (and a bit out of scope so I'll refer to it anyway) is that the server is regenerating the key for every block. This is really inefficient (both the key derivation costs and the key schedule for AES is run every time).


Where are the DH parameters in a Server Exchange Message? In a Server Key Exchange message, isn't it supposed to send both the public key's parameters which are for DH: the g(generator) and p(modulus), but the message only contains one public key called Pubkey: so is that the g, p or both, or is there a fixed variable like there is for the RSA public exponent which is 2^16+1? And where is g^e mod p?

From the screenshot:

EC Diffie-Hellman Server Params
Curve Type: named_curve
Named Curve: secp256r1
Pubkey: ...
Signature: ...

This tells us the following: You used a key exchange with ECDHE. They key exchange used P-256 (the elliptic curve, aka secp256r1) and the given value describes the public ECDH key and the signature on this value.

The paramters you are looking for are hard-coded for P-256 and documented in several places (for example in this PDF). The $g^e\bmod p$ you're looking for is the Pubkey which is mentioned in the screenshot.


Is it possible to have a PAdES signature with only a timestamp? Is it possible to have a PAdES signature which only contains a timestamp from a TSA? Does this prove the content of the PDF was unaltered since timestamping?

Or is the timestamp calculated on a digital signature and does it only provide valid proof for time?

Short answer: No. If you look at the PAdES specification, it is clear that each profile relies on at least one normal signature.

Longer answer: A timestamp and a signature serve different purposes. While a trusted timestamp does ensure the integrity of the data (alongside a notAfter date) it does not say anything about the authenticity of the the document itself, anyone can request a timestamp for any document.

The purpose of a normal signature (and PAdES is a signature standard) is to authenticate the author or issuer of a document.


Non-iterative cryptographic hash functions Consider the following cryptographic hash function $H$ which maps a message $m$ of variable size to $b$ bits:

$$H:\{0,1\}^{*} \mapsto \{0,1\}^b$$
$$y = H(m) = SPRP(IV||m||padding)\mid_{b}$$

, where: $$SPRP:\{0,1\}^n \mapsto \{0,1\}^n,\\
|m|+|IV|+|padding|=n,\\
|IV| = b.$$

Such a hash function could be considered non-iterative since, unlikely an iterative hash function, no entropy is discarded until truncation in the last step. While such a function has the disadvantage of not being streaming, it does have the nice property that finding a multicollision[0] is much harder than in iterative hash functions.

What other non-iterative hash function have been developed?
Is there another name for this as non-iterative doesn't seem to be a
good search term?

Edited to add a more formal definition: An iterative hash function is any hash function in which some the message can be compressed independent of the entire message.

A hash function $G$ is iterative iff:
$$\exists\ f\ h\ \pi, \forall m:\\
\pi(m_1||\ m_2)=m\ \ \ \wedge\\
|f(m_1)|<|m_1|<|m|\ \ \ \wedge\\
h(f(m_1),f(m_2)) = G(m)$$

A non-iterative hash function is any hash function for which it is impossible to compress any bits of the message without access to the entire message.

A hash function $H$ is non-iterative iff:

$$\not \exists\ f\ h\ \pi, \forall m:\\
\pi(m_1||m_2)=m\ \ \ \wedge\\
|f(m_1)|<|m_1|<|m|\ \ \ \wedge\\
h(f(m_1),f(m_2)) = H(m)$$

YMMV, the above definition is not a standard definition and exists to explain what I mean by non-iterative.

[0]: Antoine Joux, Multicollisions in iterated hash functions, 2004

Per my comment, I'd like to suggest a definition for "non-iterative hash function", and propose some constructions that fit the definition. I will also suggest an alternate name (though it may not help much with searching for papers on the topic).

Let $\mathcal{M}$ be the message space of a hash function, e.g. $\mathcal{M}=\{0,1\}^{*<\ell}$, the set of all binary strings of length less than $\ell$ for some $\ell \in \mathbb{N}$.  Let $\mathcal{D}$ be the 'digest space' (codomain) of a hash function, e.g. $\{0,1\}^b$ for some constant $b$.  I will use subscripts to denote which hash function is associated with a given message space or digest space.  Also, let $subseq_y(x)$ be a function that takes binary strings of arbitrary length and outputs a fixed subsequence of the string of length $y$ (e.g. truncation of the string to its first $y$ bits, or outputting only every third bit up to bit $3y$, etc).

A hash function $H(x)$ with digests of length $b$ is "non-iterative" or "uncompressible" if and only if there exists another function $G(x)$ such that:

$\mathcal{M}_{H(x)}\subseteq\mathcal{M}_{G(x)}$,
$|\mathcal{M}_{G(x)}| \le |\mathcal{D}_{G(x)}|$,
$G(x)$ is injective - no two distinct messages in $\mathcal{M}_{G(x)}$ map to the same digest in $\mathcal{D}_{G(x)}$, and
For any message $m \in \mathcal{M}_{H(x)}$, $H(m) = subseq_b(G(m))$.

Note that a hash function need not be cryptographically secure to be non-iterative by this definition.

The construction in the question meets this definition:  In that case, the function $G(x)$ is simply $SPRP(IV||m||padding)$, without truncation.

As described in my comment, another construction is to truncate an injective Random Oracle.  Unlike the permutation-based construction, this doesn't have a fixed limit on the message space size (or digest size) defined by the blocklength of the underlying $SPRP$, and yet is just as "non-iterative" or "uncompressible".

As a concrete instantiation of a "non-iterative" or "uncompressible" hash function with no limit on the message or digest lengths, I propose an 'expanding sponge' function.  This is just like an ordinary sponge function, but with two differences: 1) instead of using a fixed size permutation it uses a (keyless or fixed key) variable-length blockcipher (like the BEAR blockcipher), and 2) at each step during the absorption phase, instead of xoring the message blocks into the state, it concatenates the next message block with the state; i.e. $S_n$, the state at step $n$ is equal to $\mathcal{E}(S_{n-1}||m_n)$, where $\mathcal{E}(x)$ is encryption with the variable-length blockcipher.

Edit to clarify: For this expanding sponge function, the injective function $G(x)$ that makes this construction "uncompressible" has the same absorbing stage as $H(x)$, but during the squeezing stage $G(x)$ outputs the entire state at each step instead of only part of the state.  The output digest of $H(x)$ is thus a subsequence of the output digest of $G(x)$.  $G(x)$ is of course trivially insecure, in the sense that one can easily invert the function to find the preimage of any digest.

Note that this construction is in a sense 'iterative', in that it breaks messages up into blocks (with padding at the end if necessary) and absorbs each message block in turn one at a time using repeated iterations of the same variable-length blockcipher.  But, there is no possibility of collisions in the internal state (any two distinct messages will generate distinct internal states).  Of course, the internal state will balloon to the size of the message once it is done absorbing.  But that is the price of collisionless internal states.  For this reason, I propose "uncompressible" rather than "non-iterative".


What is the most secure hand cipher? By "hand cipher", I mean a symmetric cipher for which encryption and decryption can can both be performed with a pencil on graph paper, consuming about 10-20 seconds per character by a proficient user. Additional simple tools, e.g. a deck of cards or a multiplication table, may be used to expedite the process. No mathematical proficiency is required other than mental addition, subtraction, and maybe multiplication.

Basically, it should be a cipher that someone of average mathematical abilities can master, and it should require no digital technology or cryptographic tools that cannot be constructed out of paper.

For example, four-square in CBC mode seems secure to me because CBC is a well established mode of operation and four-square seems to be a good block cipher as it accommodates large keys and seems to produce a random-looking output. However, the fact that four-square in CBC was never widely adopted before digital encryption became a consumer technology leads me to believe that someone broke the cipher and thus discouraged people from using it.

So is there any hand cipher that the best supercomputers would take years to cryptanalyze? If not, then for which hand cipher is the best known attack the most complex?

Solitaire by Bruce schneier is probably your best bet.  It has a few issues but it will work well for most things.  It ends up having a small bias, but it takes about 15 seconds per character after the initial key stream has been generated.

It is not nearly as widely studied a field as most people are assumed to be able to get a computer or other computation device.  The only other one I can think of is VIC.  It is based on a lagged Fibonacci generator which is a bit of a different place to start from. See this other answer for more details on that cipher.

I'd strongly suggest looking long and hard at Solitaire. It has really a cool design.


Choosing rings for PLWE In [ELOS15], the authors give an attack on RLWE, and claim that "the hardness of Ring-LWE is...
dependent on special properties of the number field" chosen; whereas, responding to prior attacks on RLWE (including the one cited above), in [P16] the author claims that 'the rings themselves are not the
source of insecurity in the vulnerable instantiations.' Which is the case? Are certain rings (uniquely?) vulnerable to certain attacks, or is it merely the parameters chosen which make a construction insecure (e.g. a poorly chosen error distribution)?

Section 4 of [P16] is perhaps the key section to read. I quote it below:

We stress that all these insecure instantiations—excepting [EHL14], for which the following conclusions still apply—are for the “non-dual” version of Ring-LWE with spherical Gaussian errors relative to $R$ (in the canonical embedding). By contrast, the definition of Ring-LWE from [LPR10], and the instantiations having worst-case hardness, involve spherical errors relative to the dual ideal $R^\vee$ (see Section 2.3.2).  When the insecure and hard instantiations are transformed to be directly comparable, the resulting error distributions turn out to have very different widths and shapes. We return to this point in Section 5, where we show that the hard instantiations are immune to the attacks from Section 3

In fact, this can be understood to be the key difference between Ring-LWE and Poly-LWE --- whether LWE samples:
$$(a(x), a(x)s(x) + e(x))\in\begin{cases}R_q\times R_q^\vee & \text{RLWE}\\ R_q\times R_q & \text{PolyLWE}\end{cases}$$
Note that these are almost equivalent. In particular, at the end of section 2 of [P16] there is a heading called Equivalence of dual and non-dual forms where it is shown that they are equivalent up to the resulting choice of error distribution. And for power-of-two cyclotomics, it is known that this change is multiplication by a small constant, i.e. by a transformation that simply scales the covariance matrix of the underlying error distribution. In general the distributions are related by a certain linear transformation, but it need not be this simple.
[P16] points out that this means that the attacks on weak instances of PolyLWE are implicitly attacks on RLWE, and that the attacks are induced by not accounting for the aforementioned change in the underlying error distribution (which does vary depending on the underlying choice of ring).
This means on the RLWE side of things, the error was too small, so the worst-case to average-case reduction was not valid (and therefore the PolyLWE attacks do not imply IdealSVP algorithms, as you might have otherwise expected).


How to choose key from string? do you know any methods for choosing specific position in text for a key?

Background:
Lets suppose, that I want to encode message to friend: Text1 (not too long - max 1000 chars).
I have made publicly available string of 1000 random characters before (RandomText).
Now I want to encode my Text1 in this way:

1) Take part of message (e.g. 10 characters)
2) select key from RandomText (at specified position)
3) encode (it does not matter what is the algorithm)
4) process another part of message with next key.

After encoding I have 100 parts encoded with 100 keys.

My question is - are there any known methods (e.g. ever used in history) for selecting specified positions in point 2)?

e.g. the simplest would be:

nextKeyPosition = previousKeyPosition + someConstant

or

nextKeyPosition = previousKeyPosition + someConstant + someFunction(previousEncodedText)

or anything else.

My question is - are there any known methods (e.g. ever used in history) for selecting specified positions in point 2)?

Your construction is quite similar to the Running Key Cipher, which is soemtimes considered a variant of the Vigenere cipher. There they just start at one position and use all subsequent symbols as keystream.

  ... He told me that he thinks that such ciphers were used during WWII

As far as I know, in WWII rotor machines were the primary way to encrypt in WWII, including the well-known Enigma. By that time, classical ciphers were pretty much out of fashion already, because e.g. the Friedmann test (see link to Vigenere cipher) was invented in the 1920s, and frequency analysis has been known since the 9th century. So no, by that time encryption schemes had passed that stage already, although surely some people were still using it. Just like today some people use ciphers, which are known to be broken.

But considering the security of your scheme: If you use a keystream from a book, frenquency analysis will break that. Using e.g. only every 50th word from a book does not help, you are still linked to the characteristics of a language. If you use truly random keystreams, you are only on the safe side as long as that keystream is unknown to the attacker. If you publish those strings somewhere on the internet, you are relying on the attacker not knowing that.

The main aspect about classical ciphers in a pen-and-paper scenario is that you can actually do it without spending hours and hours for encrypting/decrypting short messages. Contrary to popular opinion, adding complexity does not automatically add security. But pretty much always it adds effort for the regular encryption and decyption. Therefore, I would suggest using one of the usual classical ciphers instead of trying to invent something new. E.g. the Vigenere cipher with long keywords (such that the message is maybe just 3-5 times the length of the keyword) works quite well, since frequency analysis doesn't work very well if there are very few letters corresponding to each letter in the keyword.

And a final note: If you assume the attacker uses a computer, classical ciphers offer basically zero security.


Does character encoding change entropy? This is a question I've been wondering for a while.

Technically these two strings have the same entropy I believe:

fkfnajkfkg%gsddg£5ER£%££££

0110011001101011011001100110111001100001011010100110101101100110011010110110011100100101011001110111001101100100011001000110011111000010101000110011010101000101010100101100001010100011001001011100001010100011110000101010001111000010101000111100001010100011

both 256bits...

My question is, does character encoding affect entropy?

If generated at random, do both the ASCII and binary strings have the same entropy as passwords?

If 256bits is good as an AES key, it's also good as a password right?

I guess a similar question is does hashing a 'weak' password give a lower entropy string than a 'strong' password, consider this:

Blake2B(password) = 7c863950ac93c93692995e4732ce1e1466ad74a775352ffbaaf2a4a4ce9b549d0b414a1f3150452be6c7c72c694a7cb46f76452917298d33e67611f0a42addb8

Blake2B(fkfnajkfkg%gsddg£5ER£%££££) = 03e7415fa598e9062cfd9e3cd269ca618b38b3543501e197b6c095b8749d782234e82779a2e4b489fd9c3b002734763ee3b867835e1a2232a37bf89ef8606d09

Are,

7c863950ac93c93692995e4732ce1e1466ad74a775352ffbaaf2a4a4ce9b549d0b414a1f3150452be6c7c72c694a7cb46f76452917298d33e67611f0a42addb8

and

03e7415fa598e9062cfd9e3cd269ca618b38b3543501e197b6c095b8749d782234e82779a2e4b489fd9c3b002734763ee3b867835e1a2232a37bf89ef8606d09

the same entropy?

If I hadn't told you the first was the hash of password and the second the hash of fkfnajkfkg%gsddg£5ER£%££££, would it change your view?

I also suppose there is a difference between brute forcing a password which is 256bits, and one which is 256 ASCII 1's or 0's, which would be more than 256bit.

Technically these two strings have the same entropy I believe:

We cannot tell how much entropy is in a string by looking at it, as it depends on how it is generated and if the values cannot be predicted by other means. For instance, you just posted these strings on this site, so they would not contain (almost) no entropy when used as keys.

Your strings just represents a bit string, possibly of the same size - as you presume, depending on the actual encoding (I don't know the encoding used for the first string, and I can only assume binary digits for the second string). And those bits may contain entropy.

  My question is, does character encoding affect entropy?

No, it doesn't as the character encoding is just about the representation of the bits, not the actual value of the bits. The entropy is present in the value of the bits.

  If generated at random, do both the ASCII and binary strings have the same entropy as passwords?

Yes, assuming that the alphabet is not larger than expected.

  If 256bits is good as an AES key, it's also good as a password right?

No, because normal humans cannot remember such large strings. You could store them in a password manager though, and then 256 bits of entropy is plenty, if not overkill. Generally we don't need password sizes or keys over 128 bits - as long as quantum computers don't come of age anyway.

  I guess a similar question is does hashing a 'weak' password give a lower entropy string than a 'strong' password, consider this:

No, now the value of the bits of the input string contain less entropy, so this isn't comparable at all. The entropy is not expanded by the password hashing algorithm, so the earlier hash contains less entropy than the latter hash.

  If I hadn't told you the first was the hash of password and the second the hash of fkfnajkfkg%gsddg£5ER£%££££, would it change your view?

No, because a dictionary attack would almost immediately find the first hash.

  I also suppose there is a difference between brute forcing a password which is 256bits, and one which is 256 ASCII 1's or 0's, which would be more than 256bit.

That depends. Let's assume that all the security is in the password or key. In that case we work with Kerckhoffs principle, and we assume that we know how the password is encoded. In that case there is no difference.

Of course, a real world attacker may not work that way. You may use your password for a generic store, and an attacker may not try your particular encoding.

Most humans are terribly bad at remembering 256 ones and zeros. There may be other technical difficulties in entering such a long string of characters as well (screen space, remembering where you are in the string, stealing clipboard contents etc. etc.).


What does NSA mean by 'Analyzable'? Recently NSA published two new algorithms, Simon and Speck. In the abstract they say

  The aim of SIMON and SPECK is to fill the need for secure, flexible, and analyzable lightweight block ciphers.

so as the question title says, what does 'analyzable' mean? BTW I found the publication through Schneier's blog post about it.

I haven't had time to read the entire document but haven't found any other references to that particular word. Do they mean the algorithms are easy to be 'proven secure'? Or is it something else? To conclude, this question does invite some degree of discussion, if you feel it doesn't comply with the site's policy, please flag it down. Cheers

Analyzable in this case means "simple to study".

If your cipher consists of a small function that mixes a few things together, and then you repeat that often then your cipher is more easily understood and more easily fit into previous research knowledge than a overclomplicated large design. This is the case with Simon and Speck.

Being easy to analyze is a good property for a strong cipher. If people fully understand it and fully checked everything and still couldn't find a weakness then it adds confidence in the cipher. A more complicated design is more likely to have a "hidden weakness" - because more things can go wrong.


Is it theoretically possible to create an unbreakable cipher? I know this question might sound strange, but is it theoretically possible to create an unbreakable cipher if we don't consider bruteforce? Some of us believe that it is possible to create ciphers and hash algorithms that are unbreakable (like when people said that we'd never run into an MD5 collision in the lifetime of the universe), but get broken in a couple of decades time (MD5 collision can be created on a modern PC in minutes). Others (including me) think that it's impossible. I believe that it is near impossible to create an unbreakable cipher, but I don't quite understand why.
Sure, computing power increases, and transistors double in count every year, but is a cipher really just a bodyguard that has a limited lifespan and dies when computing power increases? With quantum computing (I'll refer to it as QC) rapidly growing, many algorithms such as RSA and AES are becoming vulnerable.
I know, AES256 is safe against QC for now, but in the long run, it'll only get weaker and weaker until it is broken. But why (don't consider bruteforce because hashes take care of that)?
The logic behind cryptography is math, and math is getting more complex (Calculus, modern math, etc). When DES was created, there was no Shor's algorithm or Grover's. As time went on, math advanced, as did technology, and thus Shor's and Grover's algorithms are created. These discoveries weaken ciphers like AES by not a lot, but when they pile up as time goes on, it greatly weakens them.
Is it just impossible to create a cryptographically secure cipher that is strongly rooted in math and designed so that no advance in QC/math will weaken it? If we gathered the world's best cryptographers, gave them telepath (just for example), and gave them 1 billion dollars to create a cipher, would it always be able to be cracked?
I read this SE question and quickly came to the conclusion that it's a scam and just for views, but I'm sure many people believe it. I would like to know if ciphers can be unbreakable and if they can't be unbreakable, why they can't.

Some of us believe that it is possible to create ciphers and hash algorithms that are unbreakable (like when people said that we'd never run into an MD5 collision in the lifetime of the universe), but get broken in a couple of decades time (MD5 collision can be created on a modern PC in minutes).

MD5 or any other hash function is not proven to be secure. MD5 has already 128-bit output that has 64-bit collision security bound that was low even 2000s. As  "Attacks always get better; they never get worse" and we expect new attacks as time goes. Despite this, consider AES-128 still secure after 20 years. The only practical attack is the multi-target attacks that are applicable to all block-cipher. The easy mitigate is to use 256-bit key that is already the golden industry standard.

Sure, computing power increases and transistors double in count every year, but is a cipher really just a bodyguard that has a limited lifespan and dies when computing power increases? With quantum computing (I'll refer to it as QC) rapidly growing, many algorithms such as RSA and AES are becoming vulnerable.

Classical computer power is limited, there is no way for classical computers to break 256-bit block cipher just by brute-force. Even for AES-128, the collective powers of Bitcoin miners need around $2^{34}$ years to brute force 128-bit AES. As said before for 128-bit the multi-target attack is the real attack and not for 256-bit.
Shor's algorithm can break the RSA and some ECC. There is a secure ECC system like the Isogeny to be considered secure against QC.

I know, AES256 is safe against QC for now, but in the long run, it'll only get weaker and weaker until it is broken. But why (don't consider bruteforce because hashes take care of that)?

In the case of Block ciphers, the Grover can provide at most quadratic speed up and this is proven to be the lower bound. Therefore 256-bit block cipher is safe against Grover's algorithm.
Unless there is a new breakthrough result in QC, we can create a cipher safe against them. See NIST competition on post-quantum cryptography and target security level, or see the Ella Rose's answer on QC

The logic behind cryptography is math, and math is getting more complex (Calculus, modern math, etc). When DES was created, there was no Shor's algorithm or Grover's. As time went on, math advanced, as did technology, and thus Shor's and Grover's algorithms are created. These discoveries weaken ciphers like AES by not a lot, but when they pile up as time goes on, it greatly weakens them.

Is it just impossible to create a cryptographically secure cipher that is strongly rooted in math and designed so that no advance in QC/math will weaken it? If we gathered the world's best cryptographers, gave them telepath (just for example), and gave them 1 billion dollars to create a cipher, would it always be able to be cracked?

It is well-known that the One-Time Pad has information-theoretic security so that no one can break the cipher as long as it used correctly. The key needs to be generated uniformly randomly, the key size must be at least the message size, and the key never to be used again. Then you have the

key distribution problem that you need to solve if you want to communicate. That is a huge problem in the modern world.
key storage problem if you need to encrypt your files. It is the chicken-egg problem.

Therefore, the cryptographers for a long time concluded that instead of the informationally secure cipher, we should use a computationally secure cipher that is achievable with shorter keys. The cryptography is mature enough that we can calculate the security of a system in the foreseeable future. See keylength.com for such predictions.
On the plus side, we can use a key more than once with the help of nonce/IVs.
In today's Cryptography, the usual problem is not the cipher but the human factor;

The deliberately inserted backdoors, DUAL_EC_DRGB
incorrect implementations of PKCS#1 v.5 padding of RSA
leaking messages that are considered not harmful like in Padding Oracle attacks on the CBC mode.
The TPM's fail
Using low entropy to generate the system randoms,
Attack on Facebook's message Franking
are some of the examples.

Others (including me) think that it's impossible. I believe that it is near impossible to create an unbreakable cipher, but I don't quite understand why.

Unbreakable == no limit on the attacker's power then you turn back to Information Theoretically secure cipher as OTP and you will be fine!
Take AES, except for the side-channel attacks, it is secure. It is considered as PRP but no one has shown that is the case or not.
We consider the security against the attack model. If you say you have the unbreakable cipher then I can say my attack model is xkcd-538

Or should we say once you connect your PC to the internet is it no longer secure?
A nice read of Mitnick's book The Art of Deception: Controlling the Human Element of Security

I read this SE question and quickly came to the conclusion that it's a scam and just for views, but I'm sure many people believe it. I would like to know if ciphers can be unbreakable and if they can't be unbreakable, why they can't.

Prof. Lindell is already debunked that there. If people want to believe then we cannot do anything at all for them.
Sure, there will attack the ciphers that are faster than the brute-force and we act according to it.  AES-256 has attacks faster than 256-bit key search, however, these attacks are not practical.
We cannot prove that a cipher is unbreakable since we don't know all possible attacks. The Ideal-Cipher-Model is theoretic and one can create hash algorithms from an ideal-Cipher to be known secure but when instantiated they can be broken.
Theoretically, we can build an ideal cipher; for example, consider a 128-bit key and 128 bits block size. For each key, there are $2^n!$ possible permutation to select randomly and we need to select $2^{128}$ among them uniform randomly. We can represent each permutation with a table of $2^{128}$ rows and each row contains 128-bits of information. Therefore we need to store $2^{272}$ bits and if we generate each bit with random then this is not practical to generate and store. In the realization, this is neither practical in space, and there is the difficulty of secrecy and uniformity of the physical randomness. In contrast, modern cryptography easier to understand which helps to easy to analyze and control the security.
In short; we act on what we understand and analyze and control our assets according to the foreseeable future, not something that we cannot easily understand and analyze.


Optimal memory-hard KDF parameters when faced with small, slow memory I am developing for a low-power embedded system. It has two ARM9 processors at 48 MHz each. One of the processors has access to 6 MiB of "fast" memory as well as access to 26 MiB of "slow" memory. The other processor does not have direct access to memory, so it's going to be pretty much useless in this scenario (I keep it halted). The fast memory timings are complicated, and memory timings change based on whether it's a read or a write, and whether memory access is sequential or not, as well as whether accesses are 16 or 32 bits. The slow memory is much slower, but is consistently slow.
I need to implement a KDF on this system. I considered Argon2, but I do not know how to decide if it's better to run many passes on the "fast" memory, or a few passes on the "slow" memory, or some combination of the two. How do I decide what the optimal parameters are for a memory-hard KDF if the memory is going to be significantly slower than typical systems? Or is memory-hardness a losing game in this scenario and I should just use PBKDF2 (in which case I could make use of both CPUs)?

Update: I write this a little late (long after I finished this project, but reading the datasheet for another ARM-based device reminded me), but I ended up going with bcrypt in a region of very fast memory called the TCM (Tightly Coupled Memory), which can be accessed at the full speed of the processor. This allowed me to use the second processor simultaneously for improved security despite it not having full access to memory, since it has its own TCM region independent of the other processor. The following pseudocode is roughly what was done to turn password into result:
(CPU 0) hash_0 := tcm_bcrypt(password || 0x0)
(CPU 1) hash_1 := tcm_bcrypt(password || 0x1)
(CPU 0) result := hash_0 ^ hash_1

It depends. There is no answer that is the only right one.

Increasing the memory for Argon2 increases also time needed to process it. Test your system, what is the correlation. May be increasing memory usage 2x will reduce the performance not 2x but 6x or 10x.
It depends on design/architecture of your system. Namely, do you need to use Argon2 in every single request or only in some requests, let say in 1% of requests? In the 1st case high usage of Argon2 will cause high power consumption. Then, considering you have a lowe-power system, the solution should be preferred that uses CPU less, i.e. less iterations and slow memory. In the 2nd case both approaches are possible. Launch the desired number of parallel requests and check with which parameters you get the desired response times - when you use slow memory and less iterations or when you use fast memory and more iterations.
How important is that your system is low-power? If it is very important to consume as little power as possible, and if you have to use Argon2 in every or in many requests, then the approach with less iterations and more slow memory can be preferred. Again, first test how much more power (the total power of your system, not only CPU) is used if you use more memory.

I would assume that A) little power consumption is very important, B) that increasing used memory increases used power non-proportionally less, C) there are only a few simultaneous requests and parallel processing is not important. Then I would prefer to use more memory for Argon2, means slow memory, and less iterations.

Regarding combination of two: I would suggest not to do that. Why? Suppose you decide to spend 50% of time many iterations with the fast memory and 50% for less iterations with slow memory. If an attacker has fast memory, then for brute forcing he run many processes in parallel for your part with many iterations. Since the 2nd part is very quick, the attacker will not need as many processes for the 2nd part as for the 1st part. That's why the 2nd part (with more memory) will be for an attacker of no much importance and effectively brute forcing and protection will depends on your 1st part. It means that the 2nd part of your 2-step scheme will be more or less waste of resources. In other combination, it can be that brute forcing the 1st part is for attacker much cheaper than the 2nd part. Means, in such case the 1st step you would do would be wasting of resources and protection will depend on the 2nd step only. Where as if you decide for one step only, the attacker will have to repeat exactly this combination always, and no of your resource will be wasted.

Resources for brute forcing: Consider also the resources needed to brute force your passwords. Suppose you use password of 15 chars which means ~6bit x 15 =~90 bit =~10^30 passwords to try. To keep it simple, suppose 1 iteration of Argon2 with 1K memory costs 1FLOP (actually much more). The most powerful supercomputer Sunway TaihuLight can give about 10^17 FLOPS. To brute force your password it would needed 10^13 seconds =~ 10^5 years = 100 000 years. If you use all super computers in the world, this would be not more than 100 of its size. Means, with all super computers in the world would need 1000 years to brute force such password.

What can you do for protection? Make sure passwords are long enough and complex enough, better - that they are more or less random. If users use words from a normal dictionary with small modifications or use random but short passwords, the entropy will be small and one doesn't much resources to brute force it. If you enforce proper password policy, even a small number of iterations and a small amount of memory can be quite sufficient to make your system very secure.


Running time of Shamir's secret sharing scheme Let $p>n$ be a prime number. The key steps in the $(t,n)$ Shamir's secret sharing is as follows:

Steps of dealer:

Choosing $s \in \mathbb{Z}_p^*$
Selecting $b_i \in \mathbb{Z}_p^*$ for polynomial $g(x)=s+\sum_{i=1}^{t-1}b_ix^{i}$
Calculating $s_i=f(i) \mod p$ /* assume that $i$ is the participant $P_i's$ public id.*/
Distributing shares accordingly.

Participants step:

Applying Lagrange polynomial interpolation to get s.

Running time analysis:

Steps of dealer:

$O(1)$
$O(t)$
$O(t)$
$O(t)$

Participants step:

$O(t)$

Is the running times of corresponding steps true?

So, is overall time complexity $O(t)$?

I did not found any where over internet discussing running time of Shamir's secret sharing scheme. Is my analysis correct? Refer me any source or explain briefly the running times of steps involved.

Is the running times of corresponding steps true?

No.

Step 3 of the dealer has to be executed $n$ times (once for each party) with each execution taking $O(t)$ time. So it must be $O(t\cdot n)$.
Step 4 of the dealer needs $O(n)$ to distribute each share to every party.

I count $O(t\cdot n)$ as the overall time complexity for the dealer. Of course, you can make it more specific, because the time of all calculations depends on the size of $p$.


What is the difference between KDFs for key derivation vs password stretching? This was mentioned in the comments to another question:

  To clarify: This is about key-stretching KDFs. Not the kind for
  diversifying keys (eg. HKDF)

and

  There are two kinds of KDF, the slow, strengthening kind fed by a
  password(e.g. PBKDF2), and a fast one that only derives secondary keys
  from a master key(e.g. HMAC). The second one obviously shouldn't be
  used for password hashing.

Now Wikipedia on HKDF seems to think that it is exactly suitable for things like stretching keys:

  2./ To "expand" the generated output or an already reasonably random input such as an existing shared key into a larger cryptographically
  independent output, thereby producing multiple keys deterministicly
  from that initial shared key, so that the same process may produce
  those same secret keys safely on multiple devices as long as the same
  inputs are utilised.

Basically, what I would like to know is where exactly the differences between these two classes of KDFs lie. They both need to produce random looking output and cannot be invertible.

Deriving multiple keys from a strong source key material (which is what HKDF is for) is not key stretching.

The important bit from from the Wikipedia excerpt is this one:

  2./ To "expand" the generated output or an already reasonably random input such as an existing shared key into a larger cryptographically independent output, thereby producing multiple keys deterministicly from that initial shared key, so that the same process may produce those same secret keys safely on multiple devices as long as the same inputs are utilised.

As CodesInChaos' comment on the original post you referenced states, there the two types are "fast" and "slow".

Fast KDFs are designed to securely derive multiple keys from source key material that is already strong, with high entropy.  HKDF is one of these.

Key-streching or password-stretching is a term used to indicate the the source key material is weak, or low entropy, and a slow KDF needs to be used to create a key while simultaneously protecting (as best it can) the low entropy source material.  PBKDF2 is one of these.

If you attempt to use a fast KDF (like HKDF) with low entropy source material like a password, you create similar problems to those you have with using fast hash functions to protect passwords for authentication. Because passwords are predictable, the ultimate set of hashes (or keys) that will be created from will be much smaller than the full keyspace.  A fast KDF would let an attacker test far too many candidates far too quickly, making it much more likely that the correct key will be discovered, and so is not in fact suitable for key-stretching.


Correctness of ideal protocol of MPC in presence of malicious adversary In presence of malicious adversaries in ideal protocol of Multi Party Computation, how can honest parties get the correct output?
i.e., corrupted parties modify their inputs and give to the trusted party. Trusted Party computes the function by taking honest party inputs and modified inputs of corrupted parties which results in a wrong output.

If the honest parties have commitments to the malicious parties' inputs or [encapsulations generated by honest parties] of those inputs, then the function can be modified to check those.  Otherwise, the value computed by the trusted party "taking honest party inputs

and modified inputs of corrupted parties" by definition results in a correct output.


Security strength EC signature for variable message size I am implementing a system using some sort of 32bytes OTC (One-Time Code) and signing it with ECDSA to get verification of a public key owner.

The key I'm using is secp256r1.

Since the nature of this mechanism is very short-lived (say I will refresh the OTC within 1 minute), I doubt whether I can shorten the OTC in some sense that it still gives acceptable security.

Therefore I would like to know the following as a direction to measure the security strength:

The probability of best attack known to secp256r1 key per trial, with variable "length of the message-to-be-signed"
The expected number of trials to make expected value of success = 1

I'm okay if you just refer some papers or guidance and not doing the calculation here; or any other direction of such measurement.

You haven't specified the signature algorithm, but let's assume ECDSA.

  The probability of best attack known to secp256r1 key per trial, with variable "length of the message-to-be-signed"

The hash over the message is computed as the first step to generate the signature. The size of the message doesn't matter. So the security strength remains at $2^{128}$, i.e. nothing to be worried about.

  The expected number of trials to make expected value of success = 1

It is unclear why the expected value of success should be 1; I'd worry if the chance of success would be $1 \over 2$ as well. I presume it is when you've tried all options for a specific public key, so close to $2^{128}$ (trying all possible start values in Pollards Rho if I'm not mistaken).

This is all rather basic, I doubt if you can find any explicit references for it, because this is just what's assumed.

What this has to do with the size of the input message for the OTP is unclear to me. I'd rather worry about the security of the overall scheme rather than the signature.

If you want to shorten the signatures themselves then you could take a look at the BLS signature scheme. ECDSA has a signature size of 64 bytes for secp256r1 (independent of the message size, as you may now imagine), while BLS may halve the number of bytes required.


Why are co-factors 4 and 8 so popular when co-factor is more than one? For elliptic curve cryptography, I seem to keep coming across curves with either co-factors of 4 or 8 whenever it is a non-prime order group.

Is this a co-incidence? Have we studied ECC for curves which produce cofactor = 3 for example?

Having a cofactor $h > 1$ does not inherently provide an advantage; in addition, it has these small disadvantages:

It reduces the expected effort of an attacker to solve the ECDLog problem by a factor of $\sqrt{h}$ (over a curve with approximately same size group order, and $h=1$)
We then have to worry about "what if the adversary passes us a point that's not in the prime-order subgroup" (and how much of a concern that is depends on where we're using the curve).

Both of these are actually fairly minor; however if we're using the standard Weierstrass curve addition routines, there's no reason to put up with them at all - he can just as easily pick a curve that has $h=1$, and avoid these minor issues.

So, why do we use curves with $h>1$?  Well, that's mostly because we want to use curves from more limited curve families (such as Montgomery and Edwards) and use that point addition logic associated with those equations - both Edwards curves and Montgomery curves always have $h$ a multiple of 4 (as they always has a point of order 4); the advantages of the Edwards  and Montgomery point addition logic is seen to be a good trade-off (compared to the rather minor disadvantages of having $h>1$).

  Have we studied ECC for curves which produce cofactor = 3 for example?

Do you know of a family of elliptic curves that always include a point of order 3?  Do those curves have some advantage over other elliptic curves?


Use signed email as method for deriving encryption key I'm trying to create a solution to decrypt a file at rest on a server by sending an email to a given address and receiving a reply from that address. I'm struggling to see if its possible and haven't identified a methodology yet; so I'm writing to see if such a solution actually exists.

I don't wish to store an encrypted password on the server, I'd like to be able to derive it based on some exchange via email.  Obviously no data sent or received via the email can give away any part of the secret.  I've been thinking along the lines of leveraging the email sender signing the message (either s/mime or pgp) and using that signature as an input to generating the encryption key. (Assume the email public key part is available to the server) But I haven't hit upon a way to achieve it.

End result is that when some server process requires access to the encrypted file it sends an email. The recipient simply replies, signs the reply and sends.  This is then sufficient for the server to derive the key previously setup.

So anyone know of a methodology or solution that implements something like this?

Many thanks.

r.

The email signature would not do exactly what you want, but should prevent a man-in-the-middle attack on performing a Diffie Hellman key exchange through email content.

Client requesting decryption:

Generate random private key $CK_a$
Generate public key $CK_b$
Email $CK_b$ to server along with information on file needing decryption

Server:

Generate random private key $SK_a$
Generate private key $SK_b$
Generate session key $X$ from $SK_a$ and $CK_b$
Encrypt information needed to decrypt using $X$
Email $SK_b$ and encrypted payload to client

Client:
Generate session key $X$ from $SK_b$ and $CK_a$
Decrypt payload with session key, decrypt file

In this example the server is the one with the key to the file, swap server and client if you want the client to have the information for decryption, and the server to not. Other variants of this exchange exist, depending on where the file is located, and who should have access to the file, but since the file is at rest, it is already encrypted with a key that is not going to change.


Randomness and increment of nonce in GCM 2 questions about nonce usage in GCM:

Is it safe to use non-random nonce in GCM? Say I use 0x1 for m1, 0x2 for m2, so on.
How much should a nonce increased for a file? Say I use 0x1000 as a nonce to encrypt a 1000x block size file (128,000bits). Then should the next safe nonce to use for the next file be simply 0x1001, or after addition of the number of blocks used, i.e. 0x2000?

Is it safe to use non-random nonce in GCM? Say I use 0x1 for m1, 0x2 for m2, so on.

It is perfectly safe to use a non-random nonce in GCM, as long as you never reuse a nonce for two different messages.  So, if you use the message count for the nonce, that's fine; if you accidentally forget that you used nonce 0x5 for a message, and use that again, well, that's not so fine.

  How much should a nonce increased for a file?

The file size doesn't matter; use any increment you want (other than 0).  You don't have to increment the nonce more for large files.


How to find the secret key and nonce from two messages encrypted using the same nonce? As far as I understand, nonces must not be reused because their reuse allows public key encryption to be broken.

If I use NaCl's crypto_box http://nacl.cr.yp.to/box.html to encrypt two different plaintexts with the same secret key and nonce, can an observer of these messages recover the secret key and nonce?

If so, how?

P.S. Sorry, tagged as libsodium as there wasn't an NaCl tag.

Short answer: No, the key and the nonce cannot be recovered from a ciphertext.

Longer answer with a big "but":  The encryption in  crypto_box is done using XSalsa20 which is a stream cipher.

All stream ciphers create a Key Stream $S$ and encryption of the message $M$ is then done using XOR addition: $C=M \oplus S$. Since the key steam only depends on the key and the nonce, you will get the same one in case of a nonce reuse.

From the properties of XOR follows, that I'd you add two ciphertexts, you'll end up with the XOR sum of the plain texts $C_1 \oplus C_2$. So if you know any plain text, you can easily recover every other message encrypted with the same key & nonce combination.


CTR Mode and Chosen Plaintext Attacks P.71 of Cryptography Engineeering states "Any weakness in CTR encryption mode immediately implies a chosen plaintext attack on the block cipher." It seems to me that "any weakness" is vague. I'm not quite getting what the author has in mind. Can someone please elaborate?

EDIT:

The purpose of the statement seems to be to highlight the relationship between the security of the block cipher and CTR mode - a break of CTR implies a break in the underlying block cipher (except information leakage and traffic analysis). I don't see how a break of CTR means the break in the block cipher is necessarily of the chosen plaintext variety.

Suppose you know a way to distinguish a message encryption scheme of the form $$\operatorname{CTR}[E_k](n, m) = (E_k(f(n, 0)) \oplus m_0) \mathbin\Vert (E_k(f(n, 1)) \oplus m_1) \mathbin\Vert \cdots$$ for unknown $k$ from a uniform random string with probability better than you would get for CTR mode $\operatorname{CTR}[\pi](n, m)$ of a uniform random permutation.

Here $f$ is a standard injection from nonce/counter pairs to cipher blocks (say, $(n, i) \mapsto n \mathbin\Vert i$ on 96-bit nonces and 32-bit counters), $n$ is a nonce, and $m$ is a message $m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots$.  Note that there is always a generic birthday attack on CTR mode, so the premise is that you have a distinguisher with higher success probability than the generic birthday attack for the same number of queries to the oracle.

How could you use this to distinguish $E_k$ for uniform random $k$ from a uniform random permutation $\pi$?  You are allowed to feed in $f(n, 0)$ and throw $m_0$ into the mix if you know some $n$ and $m_0$ that lets you break $\operatorname{CTR}[E_k]$, for example—it is a chosen plaintext attack.


Fault encryption attack on RSA How to recover plaintext, if we know public key(RSA), correctly encrypted text and text encrypted with faulty public key, where one bit is changed?

It's interesting to mention another type of faulty attack on RSA public modulus. Up to now the majority of research papers are about how to break the system after a fault attack in regular or CRT mode.

An interesting approach (among all the surveys of fault attacks on RSA), is describerd in this paper http://www.normalesup.org/~tibouchi/papers/talk-modulusfault.pdf where the authors try to exploit the CRT combination after a faulty attack on the public modulus. The obtained system is solved by using basic Lattice reduction technics to recover the RSA secret parametrers, which is more powerfull.


Why aren't stream ciphers extremely secure? The way I understand it, stream ciphers are pretty much one time pads off-sourced to a PRNG (the seed is the key that generates the fake one time pad).

So why not just use one or more CSPRNGs (concatenated seeds, xored pad streams)?

Wouldn't breaking such a stream cipher be equivalent to breaking every single CSPRNG used?

Yet we have things like RC4 riddled with vulnerabilities, is it because performance is a concern? There are many applications where it's not, why not have something like I described for those cases?

Yes, stream cipher is to OTP what CSPRNG is to true randomness.

Yes, breaking a stream cipher implemented with CSPRNGs XORed together (each independently seeded) demonstrably implies breaking each CSPRNG (or a side channel).

Yes, there has been less than perfect stream ciphers/CSPRNGs around. I guess that's for a large part because of efficiency concerns, and because their security was adequate for many of the intended uses (RC4 was designed with performance in mind, like 30 years ago; the first commercial use I saw of it was real-time decryption of Adobe Type Library fonts distributed encrypted on freeby CD-ROMs, with each font category unlocked by a 40-bit key).

I guess that we nowadays use single-CSPRNG stream cipher (like AES-CTR, Salsa, ChaCha..) because simplicity and speed are virtues. They are believed extremely secure, except for implementation attacks (penetration of platform, side channel).


Inversion in $GF(2^8)$ AES I was wondering how you would calculate the S-box in AES. I found that you have to calculate the inverse of the polynomials in $GF(2^8)$. I found out that to calculate the inverse, you have to use the Extended Euclidean Algorithm. What I can't figure out is how do you apply this to a polynomial?

One neat trick for the AES Sbox is to use logarithm. In that specific field, the value 3 (0x03) is a multiplicative generator for the non-zero elements. Thus, if you have a "multiplication by 0x03" function, you can compute a mapping $n \mapsto \mathrm{\texttt{03}}^n$ for all $0 \le n \le 254$; this would be an "exponentiation table". From that table, you can make the inverse mapping as another table, which would be a "logarithm tables". By going to logarithms, you transform multiplications into additions modulo 255, and divisions into subtractions modulo 255. In particular, inversion becomes negation.

In Java code, this may look like this:

    /*
     * Make tmp[n] = pow(0x03, n) in the field.
     */
    int[] tmp = new int[255];
    for (int i = 0, x = 1; i < 255; i ++) {
            tmp[i] = x;

            /*
             * Multiply x by 0x03 in the field.
             */
            int x2 = x << 1;
            x2 ^= -(x2 >> 8) & 0x11B;
            x ^= x2;
    }

    /*
     * Make Sbox[] as the inverse table. We use the fact that
     * 1/pow(0x03,n) = pow(0x03,255-n) in the field (since 0x03 is
     * a generator of the multiplicative subgroup of size 255).
     */
    Sbox = new int[256];
    Sbox[0] = 0; Sbox[1] = 1;
    for (int i = 1; i < 255; i ++) {
            Sbox[tmp[i]] = tmp[255 - i];
    }

    /*
     * At that point, SBox[i] contains the inverse of i.
     * Now we apply the affine transform in GF(2).
     */
    for (int i = 0; i < 256; i ++) {
            int x = Sbox[i];
            x |= x << 8;
            x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
            Sbox[i] = (x ^ 0x63) & 0xFF;
    }

This kind of code can be convenient to recompute the S-box and related tables during an initialization process (assuming that you prefer the extra startup cost over the size cost of embedding the tables in the code).

(Of course, table-based AES implementations are not constant-time, you should not do that in practice, etc.)


Is it possible to have interactive decryption? Is it possible to have an encryption and decryption scheme so that decryption is a 2-party process?

For instance, Alice sends an encrypted message to Bob along with the key for that message. Bob, by himself, cannot feasibly decrypt this message. However, with some interactive help from Alice, he can decrypt it. If Bob manages to lose the plaintext after this process, the information gained during the decryption process cannot help him decrypt it again. He must ask Alice for help again.

I could see this being useful in access-control systems or DRM.

Probably not. When Bob at the end of the interaction finally computes the plaintext, it must be a function of everything he has obtained thus far; there's nothing stopping him from running the same computation again, unless you introduce some kind of special hardware or other additional assumptions.

In other words, decryption is deterministic, and we know that deterministic interaction is useless ($\mathbf{dIP} = \mathbf{NP}$).


AES-GCM: What can be done if 'H' is known by an attacker What could an attacker do, if he had access to the value $H = AES(0)$ used for authentication in AES-GCM?

Could the attacker do anything? Add some data in the authentication chain?

Thanks

If the authentication key $H$ is known to an attacker, he could authenticate forged ciphertext and make the receiver believe that it is authentic.

This is very problematic, since the encryption part of the GCM mode is standard CTR mode encryption, which is actually a stream cipher. And like any other stream cipher, it is susceptible to a bit flip attack, where the attacker can alter any bit in the plaintext without actually knowing it.


where to keep the AES keystream? I am trying to implement an AES encryption on my messages in my app and I want to have a different keystream for each "message group". Therefore, currently I am holding the keystreams in the database of the message groups. And the messages get decrypted by the app. However, there is one problem. The app is talking to the server via REST, and I need to get the encryption keys in a secure way. I am thinking of another keystream to encrypt the keystreams of message groups but I don't know where to keep it. Should I keep it in the app?

You should never keep keystreams. You should keep a key, and store an IV or Nonce with the ciphertext. You first need to think about where to store the key, if you store it in the same location or with the same security as your ciphertext, your scheme is meaningless.

Check this answer I just created on Stackoverflow, and learn about key management. This answer on the Information Security site also seems very on topic for you.


AES-GCM recommended IV size: Why 12 bytes? When using AES-GCM, a 96-bit IV is generally recommended. Most implementations I've seen also use 96-bit. However, I'm unsure on where this recommendation or convention comes from.

Let's assume a shorter IV is bad. Assuming all other constraints for IV generation are still met, would using a longer IV necessarily have a negative security impact, or severe performance impact without adding any security benefit?

For instance, an answer in Ciphertext and tag size and IV transmission with AES in GCM mode specifically states

  For GCM a 12 byte IV is strongly suggested as other IV lengths will require additional calculations.

I'm very interested in this statement, but I'm unable to find an explanation on these "additional operations" or other security implications of when using a longer IV. The NIST Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC did not clarify this for me.

So is there any specific reason for everyone using 12 bytes, or is everyone just following convention?

From the proposal of GCM (rewritten if statement):

  if $\operatorname{len}(IV) = 96$ then $Y_0 = IV || 0^{31}1$ else
  $Y_0 = \operatorname{GHASH}(H, \{\}, IV)$.

So there are additional calculations for IV's other than 96 bits. This is why the original proposal has this recommendation:

  96-bit IV values can be processed more efficiently, so that [ed: this] length is recommended for situations in which efficiency is critical.

but also in the security section it is explained that the IV-processing of GCM was not previously taken into account for GHASH:

  Counter mode was suggested in 1979 by Diffie and Hellman [21], and was shown to be secure in a strong, concrete sense by Bellare et. al. [22]. While the proof of security for GCM rests on those proofs, there are some differences. The derivation of the hash key $H$ from the block cipher key $K$, the hashing of the $IV$, and the use of that key for both IV-processing and message authentication are important details.

NIST SP-800 38D has a whole chapter - chapter 8 - dedicated discussing key and IV uniqueness and the maximum number of invocations of GCM.

If the uniqueness of the IV / key combination cannot be met then security of GCM fails catastrophically.

Then again, that goes for any other cipher as well, particularly those build upon CTR mode encryption (which includes GCM, but also EAX, CCM etc.).

My suggestion is that if you've got small but unique IV input that you expand that input yourself to 12 bytes, if possible according to the hints in NIST SP-800-38D: 8.2.1 Deterministic Construction.

If it is not possible to generate a value that is unique and 12 bytes or below then you might want to consider a fully random IV consisting of 12 bytes.


AES-CTR-256 Sub Keys With Encrypted Sub Key Index I was working with some encryption and I decided to put a spin. To preface this would be used to encrypt multiple files.

You start with a key file generated from random data. For example you could generate a 288 byte key file. This file contains 9 sub-keys each 256-bits.

For each file to encrypt you securely randomly select a sub-key from the file. Then you create the header by append 28 bytes of random garbage bytes onto 4 bytes which is the index of the sub-key in the key file. You then use the first sub-key to encrypt this 32 byte header block.

The remainder of the file is encrypted using the sub-key and is placed after the header.

I was wondering if there are any obvious flaws to this approach. My nuonce is going to start at zero.

Would it also be even better to start the nouce using the first byte of the key?

I would advise a different solution.

You either generate a master-key (or key set) or derive one from a user password (e.g. via PBKDF2 or SCrypt). For each file to encrypt you generate a random key (file key) and nonce ad-hoc, and encrypt the file with that key, using an AEAD scheme.

The random file key is encrypted with you master key and put at the beginning of the file. Preferable you should include that encrypted key as authenticated data within the AEAD scheme.

The steps:

Generate random file key and nonce
Encrypt file key with master key (using a key-wrap spec.)
Encrypt the plaintext file data with the file key and using it enc. form as part of the authenticated data (AEAD scheme)
Store nonce, enc. file key and encrypted data as the enc. file

Your solution is dangerous. Using the same nonce with the same key (you only have 9 or so) to encrypt different data will allow an attacker to retrieve information concerning the plaintext data.


Secure private key storage I'm developing application in Java that has to store RSA keys in software for foreseeable future (that is, at least 10 years).

The two most common standards of storing private keys are PKCS12 and JKS (Java Key Store). While PKCS12 supports many different algorithms, even the most secure ones are based on 3DES with SHA1. JKS is even worse as the default is based on MD5 and 3DES.

The Bouncy Castle Java library version of JKS is a bit better as it uses PBEWithSHAAndTwofish-CBC for "UBER" version of its key store format.

Are there any standard formats of private key storage that support encrypting the key pair using AES and SHA-2?

RFC 5958 and RFC5959
seems to be the latest standard for storing encrypted private keys.
It obsoletes RFC 5208, also known as PKCS#8.
My understanding is that AES is one of the many encryption algorithms supported by RFC 5958.

The GNU Keyring File Format is a another standard for a file format that stores private keys using AES-128.

The Gnome Keyring implementation stores private keys using (among other things) AES-128 encryption.
Alas, it doesn't seem to follow any published standard, but perhaps it can be seen as a de-facto standard.
The Gnome Keyring FAQ briefly mentions that sometime in the future (after 2010) it will transition to "a standard way of encrypting the keyring" (PBKDF2) which apparently requires "A new file format" (perhaps one of the above formats?).


How does mutlivariate crypto schemes work? I have been studying multivariate cryptography for post-quantum cryptography lately, but I have a hard time in understanding how these signature schemes work. As long as I see there there is UOV scheme, then Rainbow which is kind of a generalization of UOV scheme, and also there is something called HFEv-.

But how does these signature schemes work? I mean we use some multivariate polynomials, and most of the time the polynomials are quadratic. But how do we actually sign and verify messages (let's say a toy message such as 011101101)? Is there any place where I can find step by step how the algorithms work, and their application to toy examples so as to see how they work?

UOV

The first thing you need to know about UOV is that the input variables are partitioned into vinegar variables $x_1, \ldots, x_v$ and oil variables $x_{v+1}, \ldots, x_{v+o}$. The number of vinegar variables is roughly twice the number of oil variables: $v = 2o$. The name oil and vinegar comes from the fact that oil variables do not mix with other oil variables in the secret polynomials. In fact, every polynomial of the secret key can be described as a quadratic form. For example, let $v=4$ and $o=2$ and $\mathbf{x}^\mathsf{T} = (x_1 \, x_2 \, x_3 \, x_4 \, x_5 \, x_6)$. Then every secret polynomial can be described as:
$$ f_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix}
* & * & * & * & * & * \\
* & * & * & * & * & * \\
* & * & * & * & * & * \\
* & * & * & * & * & * \\
* & * & * & * &  &  \\
* & * & * & * &  &  \\
\end{matrix} \right) \mathbf{x} \enspace .$$
Where the $*$ indicate randomly chosen elements, but the blank spaces indicate zeros. The oil variables, $x_5$ and $x_6$ are not mixed with themselves or each other.

Now, it's also important to know that there are exactly $o$ secret polynomials. The vectorial function whose components are $f_i$ is denoted by $\mathcal{F}$:
$$ \mathcal{F}(\mathbf{x}) = \left( \begin{matrix}
f_1(\mathbf{x}) \\
\vdots \\
f_o(\mathbf{x}) \end{matrix} \right) \enspace .$$
(In our example there are just two components in $\mathcal{F}$.)

The public key $\mathcal{P}$ is generated from $\mathcal{F}$ by composing it with a random invertible linear transformation $S \in \mathsf{GL}_{o+v}(\mathbb{F}_q)$, which is really a square matrix whose inverse exists: $S \in \mathbb{F}_q^{(v+o)\times(v+o)}$. The public key is then
$$ \mathcal{P} = \mathcal{F} \circ S \enspace .$$

In order to sign a document $d$ with hash $\mathbf{h} = \mathsf{H}(d)$, the signer does the following. First, choose a random assignment to the vinegar variables $x_1, \ldots, x_v$. Then the system of polynomial equations $\mathcal{F}(x_{v+1},\ldots,x_{v+o}) = \mathbf{h}$ is a linear $o \times o$ system. Solve it to obtain $x_{v+1}, \ldots, x_{v+o}$ and at this point the signer has the entire vector $\mathbf{x}$. Next, compute the signature $\mathbf{y}$ as $\mathbf{y} = S^{-1}\mathbf{x}$.

In order to verify a signature $\mathbf{y}$, the verifier evaluates the public key in $\mathbf{y}$, and checks if the result is equal to the hash of the document, i.e.,
$$ \mathcal{P}(\mathbf{y}) \stackrel{?}{=} \mathsf{H}(d) \enspace .$$

Notice how UOV uses a linear $o \times o$ system as a step in generating signatures, but how this step generalizes to any quadratic (!) system for which it is possible to find an inverse efficiently. For instance, you can level down recursively and put another UOV system there. This multi-layer approach is called Rainbow.

HFE, HFE-, and HFEv-

HFE-type systems are very different. The first thing you should know about them is that they use univariate polynomials over the extension field. So $\mathbb{F}_q$ is the base field (like in the UOV case). Then pick any irreducible polynomial $f(z) \in \mathbb{F}_q[z]$ of degree $n$, and then you can identify the set of polynomials $\mathbb{F}_q[z] / \langle f(z) \rangle$ of degree smaller than $n$ as a new field, the extension field $\mathbb{F}_{q^n}$, whose operations are polynomial addition and polynomial multiplication modulo $f(z)$. Whenever you have a vector of $n$ values over the base field, say $\mathbf{a} \in \mathbb{F}_q^n$, you can embed this value in the extension field using the canonical embedding $\varphi : \mathbb{F}_q^n \rightarrow \mathbb{F}_{q^n} : \mathbf{a} \mapsto A = \sum_{i=1}^na_iz^{i-1}$. In particular, you can do this with the vector of variables: $\varphi(\mathbf{x}) = X$ and then you have a single variable $X$ over the extension field. Any list of $n$ multivariate polynomials in $\mathbf{x}$ over the base field maps to one univariate polynomial in $X$ over the extension field, and vice versa.

In order to generate a HFE secret key, choose a random univariate polynomial over the extension field $\mathcal{F}(X) \in \mathbb{F}_{q^n}[X]$ with degree at most $D$ and of the form
$$ \mathcal{F}(X) = \sum_{i} \sum_{j} \alpha_{i,j} X^{q^i + q^j} \enspace .$$
In other words, choose the coefficients $\alpha_{i,j}$ uniformly at random from $\mathbb{F}_{q^n}$ as long as $q^i+q^j \leq D$, and set $\alpha_{i,j}=0$ otherwise. Following this structure for $\mathcal{F}$ will guarantee that it maps to a list of multivariate quadratic equations over the base field. In the old days they recommended $D \approx 1000$ but now we understand how to make HFE secure with much smaller $D$, e.g. $D \approx 10$ -- and that will only make the scheme faster! Next, choose two random invertible linear transformations $T, S \in \mathsf{GL}_n(\mathbb{F}_q)$ which are once again really invertible square matrices in $\mathbb{F}_q^{n \times n}$. The secret key consists of $(\varphi, \mathcal{F}, T, S)$. The public key is found by composing these transforms:
$$ \mathcal{P} = T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S \enspace .$$

In order to sign a document $d$ with hash $\mathbf{h} = \mathsf{H}(d)$, the signer proceeds as follows. First, he computes $Y = \varphi(T^{-1}\mathbf{h})$. Then he uses Berlekamp's algorithm to factorize the polynomial $\mathcal{F}(X)-Y$ and find the roots $\{X_i\}$ that make it zero. He chooses one of these roots as $X$ and proceeds to compute the signature $\mathbf{z} = S^{-1}\varphi^{-1}(X)$.

In order to verify a signature, the verifier evaluates the public key $\mathcal{P}$ in $\mathbf{z}$ and checks whether he obtains the hash $\mathbf{h}$ of the document:
$$ \mathcal{P}(\mathbf{z}) \stackrel{?}{=} \mathsf{H}(d) \enspace .$$

Unfortunately, HFE as described up until here turns out to be insecure. In particular, it is vulnerable to a direct algebraic attack involving efficient Gröbner basis algorithms. That's why you need at least one of the modifiers - (minus) or v (vinegar). It makes sense to use both. A good right-hand rule is $a + v + \mathsf{log}_2 D \geq 15$.

Minus means that some polynomials are dropped from the public key. In particular, the decomposition now involves a forgetful operator $\pi : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^{n-a}$ that leaves the first $n-a$ components intact but drops the remaining $a$ ones:
$$ \mathcal{P} = \pi \circ T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S \enspace .$$
In order to generate a signature, the signer has to choose the value of the missing polynomials. This is no problem as a random choice will suffice.

Vinegar consists of adding $v$ vinegar variables. During signature generation, the value of these vinegar variables is also chosen at random, after which what's left to do is to invert the regular HFE system. Instead of finding a solution to the linear $o \times o$ system (as was the case for UOV), now one must find the preimage by factorizing the HFE polynomial.

Reading Materials

In terms of accessible reading materials, I can recommend two things. One, Ding and Yang have a chapter in the 2009 book "Post-Quantum Cryptography". Two, Ding, Gower and Schmidt have a book called "Multivariate Public Key Cryptosystems". Aside from that, the relevant papers good reads because they contain all the necessary information, for example to estimate security. On the other hand, they are a lot denser.


To which game-based security definition is Perfect Secrecy equivalent? We all know the classic definitions of perfect secrecy, being
$$\Pr[M=m|C=c]=\Pr[M=m]$$
and
$$H(M|C)=H(M)$$

But now what I've asked myself:
If we were to remove the polynomial restriction on the attacker, which game-based security definition would be equivalent to perfect secrecy and how would one show this?

Of course I've thought about this myself and it's obvious that known- and chosen-plaintext security is a given as we still can't learn anything new about the plaintext if a scheme is perfectly secret.
Even with chosen-ciphertext attacks I don't see how one could deduce more information on a perfectly secret scheme, given that the challenge ciphertexts would still be independently encrypted.
What I kinda can't grasp though is the reverse direction and of course the formal proof of equivalence.

Perfect secrecy corresponds to semantic security. Or rather, semantic security is an adaption of perfect security for computationally limited adversaries, but a variant of the same definition also works for unlimited adversaries.

In other words, consider a game between an adversary and a simulator. The simulator chooses its key material. The adversary may submit messages and get their encryption in return. He then chooses a distribution over plaintext messages (all of equal length) and a binary predicate $f$, such that the probability that $f(m)=0$ is $1/2$. The simulator chooses a message according to the distribution, encrypts it and sends the challenge to the adversary. The adversary must now determine $f$. His advantage is the difference between his probability of guessing $f(m)$ correctly and $1/2$.

You need to be a bit careful with your encryption oracle and challenge ciphertext encryption, so that key material is only used to encrypt once. Once that it done, it is clear, as you say, that the encryption oracle doesn't help an adversary.

With a small amount of work, it now follows from perfect secrecy that any adversary in this game will have advantage exactly $1$. Also, if any unlimited adversary has advantage exactly $1$, it must follow that you have perfect security.

Note that if you try to adapt chosen ciphertext attacks, no reasonable definition will result in the one-time pad being secure, since it isn't secure against these attacks.


CPA-secure of $\Pi$ implies CPA-security of $\Pi||\Pi||\ldots||\Pi$ Katz and Lindell book claim that from the theorem:

  Any private-key encryption scheme that is CPA-secure is also
  CPA-secure for multiple encryptions.

Follows the fact that:

  If $(Gen,Enc,Dec)$ is a fixed-length ($M_n = \{0,1\}^n$) CPA-secure ES
  then $(Gen,Enc',Dec')$ with $M_n' = (\{0,1\}^n)^{*}$ and
  $Enc_k'(m) = Enc_k(m^{(1)})||\ldots||Enc_k(m^{(s)})$ is also CPA-secure.

Why is it the case?

What strikes me more is that a similar theorem to 1. holds for CCA-security:

  Any private-key encryption scheme that is CCA-secure is also
  CCA-secure for multiple encryptions.

However, the construction does not hold (according to my slides) in the later case:

  Assuming $(Gen,Enc,Dec)$ is CCA-secure with $M_n = \{0,1\}^n$ then one
  can show that $(Gen,Enc',Dec')$ is not CCA-secure.

The proof of (1) is not given in the chapter on symmetric encryption since it requires knowing the hybrid proof technique that is taught in Chapter 7. However, the argument is proven in Chapter 11 for the asymmetric case (see Theorem 11.6 and the proof on page 383). Essentially the same proof holds for the symmetric case as well (except that instead of the reduction $\mathcal{A}'$ on page 385 computing the plaintexts itself for $j<i$ and $j>i$ in steps 2(a) and 2(c) respectively, it asks its encryption oracle to do it and uses the responses).

Regarding CCA security, the proof of multiple encryptions indeed does go through as well. However, unlike CPA security, it does not imply that you can concatenate ciphertexts into one ciphertext. That is, you can encrypt multiple messages, but you cannot encrypt longer messages by concatenating. The reason is that if you encrypt a long message by concatenating ciphertexts (and you call this the new ciphertext) then the attacker can drop the last sub-ciphertext and ask for decryption (it is allowed to ask for decryption since this is not the same ciphertext received).


DES-X , computation load and storage The passage said that the computational load to attack DES-X can be reduced to approximately $2^{(56+64)}=2^{120}$ steps,and  the storage of data sets should be $2^{64}$.

But I can't figure why it is time complexity $2^{120}$ and  the (space complexity) of data sets should be $2^{64}$.

Can somebody help?

Actually, because of DESX works, the meet-in-the-middle attack can be optimized to take $2^{119}$ $DES$ (and no $DES^{-1}$ operations), and no additional storage.

Here is how it works: let us assume that we have three known plaintext/ciphertext pairs $(P_1, C_1)$, $(P_2, C_2)$ and $(P_3, C_3)$.  We know that:

$$C_1 = K_2 \oplus DES( K, K_1 \oplus P_1 )$$

$$C_2 = K_2 \oplus DES( K, K_1 \oplus P_2 )$$

In a standard meet-in-the-middle attack, we would rewrite the first equation as:

$$C_1 \oplus K_2 = DES( K, K_1 \oplus P_1 )$$

and create lists of the two sides (using possible values of $K, K_1, K_2$), and search for common values; the lists (actually, we'd create a list only for the left side, as it's smaller) would account for the additional storage.

However, in the case of DESX, we can simplify this by combining the two equations as:

$$C_1 \oplus C_2 = DES( K, K_1 \oplus P_1 ) \oplus DES( K, K_1 \oplus P_2 )$$

We know the value on the left side; with $2^{119}$ DES operations, we can go through all possible combinations of $K, K_1$ that make this equation work (note: why $2^{119}$ and not $2^{121}$?  Because there are two separate artifacts that allow us to reduce the search space by a factor of two each: the first is the observation if a value $K_1$ makes it work, so does the value $K'_1 = K_1 \oplus P_1 \oplus P_2$; hence if we test one $K_1$ value and it doesn't work, we can skip the corresponding $K'_1$ value; the second is the key complementation property of DES; that is, if $K, K_1$ satisfies the above equation, so will $\bar{K}, \bar{K_1}$; hence if we test one $K$ and it doesn't work, we know that $\bar{K}$ wouldn't either.  So we test the above with $2^{55}$ $K$ values and $2^{63}$ $K_1$ values, and each test involves 2 DES operations, for a total of $2 \times 2^{55} \times 2^{63} = 2^{119}$ DES evaluations).  And, because we're not explicitly making any lists, we don't use any extra memory.

When we find a $K, K_1$ pair that makes this work, we can compute the correspond $K_2$ values, and test it out with our third known plaintext/ciphertext pair; this additional checking is rare (once out of $2^{64}$ pairs tested), and so can be ignored when doing complexity computations.

And, this observation can be extended to show that the attack against DESX can be performed even faster if we have more plaintext/ciphertext pairs.