Is there any compelling or logical reason to use AES-192 over AES-128 but not use AES-256? I have been trying to find a case where AES-192 is used over AES-128 but AES-256 is not used. There are many questions about AES here (I liked this one AES-128/192/256), but from the actual application side, I was unable to determine any cases where AES-192 was used over AES-128.

AES-192 seems to exist because levels of security were desired, but hardware implementations seem to be AES-128 or AES-256.  I did a literature survey on the IEEE and I couldn't find any applications in the hardware space that used AES-192 instead of AES-256, and I could not find anything in the software space, but I did not dive into specific implementations.

Is there any compelling or logical reason to use AES-192 over AES-128 but not use AES-256?

Maybe you can even point me to an example – meaning: some application or implementation where AES-192 is used over AES-128 instead of AES-256?

There is no reason to use a AES-192 if you have access to AES-256 (or AES-128).
This question is completely in line with the following thread:
[Cfrg] A little room for AES-192 in TLS? which resulted in this somewhat conclusion:

Dear all,
the related-key attacks against AES were interesting from an academic point of view as they broke the security claim we made for Rijndael.
However, the attacks require very sophisticated manipulations of the secret key by the attacker. For example, even a protocol that would allow an attacker to add (or XOR) a value of her choice to the key before being used in AES would not allow mounting the attack. If you are interested, you can read the paper Vincent and I wrote "On the related-key attacks against AES" available at e.g. http://jda.noekeon.org/
As for including AES-192 in TLS, I don't see any benefits.
Kind regards,
Joan Daemen

TL;DR: To sum up the only real advantage of AES-192 is the insignificant gain of speed compared to AES-256.


How can I formally verify fuzzy commitment scheme based security protocol? I am currently working on designing a security protocol which involves usage of fuzzy commitment schemes, for. eg Reed-Solomon codes which allows us to tolerate a certain level of error.

I was wondering how one would go about formally verifying a security protocol which would use a scheme such as Reed-Solomon codes.

I searched online, and found out about tools out there such as AVISPA. ProVerify and even Casper/FDR which would help me test security protocols, however they do not seem to work with fuzzy commitment schemes.

This might not be the answer you are looking for, but as you are looking for a formal verification, I would advise you to take a look at Coq. Even though mainly used by Academics, it provides a logical framework and an interface to write formal and interactive proofs.

Based this language there exists some libraries dedicated to cryptographic proof :

CertiCrypt
EasyCrypt (tutorial)

Example of proof :

Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols
Formal certification of ElGamal encryption
Verification of a Cryptographic Primitive: SHA-256

PHD : Formal certification of game-based cryptographic proofs

Other formal tools (interactive provers) can be used such as Isabelle, Agda, Fstar and HOL.
And some more readings :

Computer Verification in Cryptography
Probabilistic Relational Verification for Cryptographic Implementations

Disclaimer: I use Coq on daily basis...


How expensive would running a practical application on full homomorphic encryption be? This is a multidisciplinary question, hopefully I can stay on topic.
It has been published that we can now use (try?) fully homomorphic encryption computation on cipher text inputs. But I'd like to ask how practical it is to use this technology.
So here's a specific question.
If Alice has a one megabyte text file (like some novel). And Bob wants to provide the service of scanning the text and producing a list of the unique words in the file (useful for search indexing). And Bob wants to provide this service without any access to the underlying file. And the parties want to use something like PALISADE or the Microsoft Homomorphic Encryption libraries. Then what rough order of magnitude would this cost in terms of computer memory and retail cost of executing this on some commodity cloud provider?
Are we talking pennies, US dollars, or something exceeding the world GDP?

This will likely be rather expensive. This is because the problem you describe seems like it would be hard to express as a shallow arithmetic circuit, which is a rough estimate of how difficult the computation is with FHE.
In particular, a naive algorithm for solving your problem is:

Instantiate some hashmap
Iterate through your textfile, when you see the character " ", chunk off the previous block of text and add it to the hashmap.
Throughout this, record the last bit of text you chunked off for future use in computing what to chunk
Return the hashmap

This has $O(n)$ complexity, and in practice should be only slightly less efficient than reading the entire array of text. Essentially no part of it translates well into FHE though. FHE evaluates programs on encrypted data where the programs are expressed as circuits (essentially standard programs where the computational path may not depend on the data).
The above program seems difficult to implement as a circuit efficiently. Both of the non-trivial parts of the program (instantiating/using a hashmap, and the iterative "chunking" operation) seem pretty bad for this.
This can be worse if you use a variable-length text encoding such as UTF-8, but even for a fixed-length encoding (such as ASCII) it seems pretty bad.
If you want to get an explicit estimate of the complexity, you would first need to generate some fixed circuit implementing your desired function.
There are some transpilers for "standard" programming languages to arithmetic circuits (this paper describes a transpiler (implemented here) from some subset of C to arithmetic circuits.
I haven't checked if it suffices for this program) that you can leverage to do this, but I won't bother for this answer.
Even some of the more basic parts of the computation (checking if a character is equal to " ") is rather difficult in FHE --- equality testing is difficult to express as a low-degree polynomial, and therefore difficult to express as a low-(multiplicative) depth circuit.
Anyway, I would guess it would cost $\gg\\\$1$.
I don't have order-of-magnitude estimates, but whatever the final number if I doubt you could convince customers to pay it rather than buying their own (trusted) server that they outsource plaintext computations to (this is both more generally useful, is a one-time cost vs a per computation cost, etc).
The big draw of FHE are for computations where:

Buying a trusted server is not an option (say computing functions of data from several mutually non-trusting sources)

"Simple" computations (where simple means something like "is expressible as a low-depth arithmetic circuit", or equivalently "is expressible as a low-degree polynomial").

An example application is that of computing statistical tests on medical data, which is (from my perspective) still the most compelling application of FHE, rather than "renting cloud-compute in a `trusted' way".
Note that there is currently a big push for hardware implementation of FHE, which may change this picture in the near-term.


Prefix property for variable length pseudo-random generators I'm currently working through Katz & Lindell's Introduction to Modern Cryptography. In section 3.4.2, they introduce the definition of a variable output-length pseudorandom generator $G$. The definition of $G(s,1^l)$ is such that the output is of length $l$.

Using such a psuedo-random generator, they define a variable-length encryption scheme (here, called $\pi_{VarPRG}$) in the natural manner for variable length messages:

  Encryption: $Enc:\mathcal{K}\times\mathcal{M}\to\mathcal{C}$ where $C=Enc(K,M)=G(K,1^{|M|})\oplus M$

  Decryption: Inverse of encryption for the ciphertext length $|C|$.

However, they go on to include the side-condition:

  For all $s$, $l$, $l'$ with $l<l'$, the string $G(s,1^l)$ is a prefix of $G(s,1^{l'})$.

They claim this is a "technicality" of proving indistinguishable encryptions in the presence of an eavesdropper for the variable length encryption scheme defined above. After staring at this for the best part of an hour, I am not fully understanding where this subtlety comes into the proof. (It is, after all, a subtlety.)

My first attempt to gain some insight into the problem:

In the proof of $PrivK^{eav}_{\mathcal{A},\pi_{VarPRG}}(l)$ for the encryption scheme shown above, we suppose $G$ is a secure pseudo-random generator and then suppose, for contradiction, that $\pi_{VarPRG}$ is not secure in the presence of an eavesdropper. In other words, there exists some adversary $\mathcal{A}$ for which

$Pr(PrivK^{eav}_{\mathcal{A},\pi}(l)=1)\not\leq \frac{1}{2} + negl(l)$

We proceed by using the adversary $\mathcal{A}$ to build a (probabilistic, polynomial-time) distinguisher $\mathcal{D}$ for the variable output-length PRG $G$, and show that this contradicts the assumed pseudo-randomness of $G$.

All well so far. The adversary $\mathcal{A}$ will, when invoked, output two messages $m_0$ and $m_1$, which one assumes can be different lengths ($|m_0|\not=|m_1|$). At this point, I get stuck:

Where does the subtlety, noted above with regard to the prefix property of $G$ for $1^l<1^{l'}$, come into this?

Recall that Katz-Lindell defines a variable output-length pseudorandom generator as a deterministic polynomial time algorithm G with three properties:

Let $s$ a string and $n>0$ an integer. Then $G(s,1^n)$ outputs a string of length $n$
For all $s,n,n'$ with $n<n'$, the string $G(s,1^n)$ is a prefix of $G(s,1^{n'})$
Define $G_{\ell}:=G(s,1^{\ell(|s|)})$. Then for every polynomial $\ell(\cdot)$ it holds that $G_{\ell}$ is a pseudorandom generator with expansion factor $\ell$.

(I have changed some $\ell$s to $n$s to avoid variable collision).

The second condition is necessary because, without it, this definition does not say anything about the output of $G(s,1^n)$ in the case where $|s|>n$. This is because Katz-Lindell defines a pseudorandom generator (on page 70) to have an $\textit{expansion}$ property-- the output of a pseudorandom generator is longer than the seed--so the above property 3 doesn't (by itself) tell us anything about the case where $|s|>n$.

This is a problem because (as defined on page 63) the first step of the eavesdropping indistinguishability experiment is that "The adversary $\mathcal{A}$ is given input $1^n$, and outputs a pair of messages $m_0,m_1$ of the same length."

The seed used in encryption is of length $n$, so the adversary could choose messages of length less than $n$. Then the messages would be encrypted with the output of $G(k,1^{|m_0|})$ which, as mentioned above, is not guaranteed to be pseudorandom without property 2.

However, it is an easy lemma to prove that a truncation of a pseudorandom string is also pseudorandom. This, together with properties 2 and 3, gives us that all outputs of a variable output-length pseudorandom generator are pseudorandom, and the security proof goes through as normal.


Why an upside down path on the evaluation of branching program on encrypted data? Suggested by Ricky Demer in this post, I am reading the paper "Evaluating Branching Programs on Encrypted Data"(TCC 2007), which uses one-round strong OT protocol to implement homomorphic evaluation of branching program (BP) on encrypted data with succinct ciphertext.

As it says on page 6, the natural way to evaluate a BP is

  The output $P(x)$ of a branching program on an input assignment $x$ ... defined by following the path induced by $x$ from [the initial node] $v_0$ to a terminal node $v_l$ ... The output is the value $\psi_V(v_l)$ labeling the terminal node reached by the path.

Apparently, this is a up-to-bottom process, from the initial node to one of the terminal nodes.

However, the encrypted version of BP evaluation on ciphertext $c$ (corresponding to the cleartext $x$) seems to use a totally different (and which is strange to me) method (on page 11):

  To evaluate $P$ on $c$, the server makes a bottom-up" pass on $P$, starting with the terminal nodes $T$ and ending with the initial node $v_0$ ... at the end of iteration $l$, the initial node $v_0$ is labeled by an OT answer which can be viewed as an (iterated) encryption of the output value $P(x)$ ...

So what's the omitted part of this upside down algorithm (that I should have known), and why?

PS: Another (maybe small) question, am I right to say $P$ of this scheme can be reused, on the contrary to Yao's one-time Garbled Circuit setting?

The "omitted part of this upside down algorithm" is like dynamic programming, since it

computes node values before getting to the point at which those values will be used.

Unlike my original thought, the recursive approach certainly can be better; the canonical

example of that would be using their scheme for PIR. $\:$ However, for the application your

previous question was about, their approach will definitely be better than recursion.

$P$ is just a party's input, so it certainly can be reused. $\:$ However, the resulting

ciphertext can't necessarily be run through the homomorphing process again, since the

group changes with each layer. $\:$ (That is mentioned in the top paragraph of page 16.)


Signal Protocol - Counter over TCP? Signal Protocol uses a counter (discussed in DoubleRatchet documentation) to define how many times KDF has derived a new key (aka a KDF step) which is then sent along with every message for the end client to know how many derivations (steps) he has to do to obtain a decryption key matching the message key which encrypted the message.

Note: it is also used for creating a message mac which is later compared for verification, but since both clients are keeping track of the current counter it should match as long as the order is intact.

This makes sense for protocols that don't have order, but if I am using TCP which keeps order does sending the counter and skipping over messages has any use?

You are confusing TCP packets and Signal messages.

First, TCP ensures the order of packets inside a session. TCP does not ensure the order among sessions. This means that TCP cannot be used to ensure that the Signal messages are received in the order they were sent.

Also, TCP was not build to resit active tempering by a MITM agent, unlike Signal. It would be extremely unwise for Signal to assume that the properties of TCP are reliable.

Moreover, the end client might not keep track of the previous messages: they could be deleted or the client could have been reinstalled on another device (while keeping the secret keys).


Incorporating known ciphertext into new message Which ciphers $c_k$ enable one to define a joining function $f_{c,k}$ such that:

$$
f_{c,k}(c_k(p_1), p_2) = c_k(p_1 + p_2)
$$

That is, the result of joining some known ciphertext $c_k(p_1)$ with a plaintext $p_2$ produces the same ciphertext as the concatenation of the respective plaintexts?  Whilst there is some flexibility to modify $p_2$ (e.g. with padding) it cannot be chosen entirely arbitrarily.

What terminology applies to such cipher/function/messages?

Not sure if this fits your requirement, but, here goes.

Using the homomorphic properties of ElGamal, you could turn $E_{pk}(b_0),E_{pk}(b_1),E_{pk}(b_2),E_{pk}(b_3),E_{pk}(b_4),\cdots,E_{pk}(b_n)$ (where $b_i\in\{0,1\}$, i.e., individual bits), into $E_{pk}(b_0||b_1||\cdots||b_n)$ (where $||$ is concatenation). This is done by using homomorphic scalar multiplication and addition (multiply by 2 then add the next bit, repeat as necessary).

This could be generalized to larger messages (not just individual bits) if Trent is told the lengths of the messages.

Any cipher that is homomorphic with respect to addition could be used.


Variant of the Decisional Bilinear Diffie Hellman problem I am working on a cryptographic scheme and I need to rely on the following problem, which I have nicknamed the "Hybrid Decisional Bilinear Diffie Hellman (hDBDH)" problem:

  Let $e: \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ be an efficient bilinear pairing. Given the tuple $(g,g^x,e(g,g)^y,Q)$ as input, the problem is to decide whether $Q = e(g,g)^{xy}$

First, has this problem already been defined? Now, I want to prove that this problem is equivalent to the DBDH problem. I have the feeling that they are equivalent, but so far I only have that $DBDH \leq hDBDH$:

  Proof: From a hDBDH solver, we can construct a DBDH solver in the following way:

  Input: DBDH tuple = $(g, g^a, g^b, g^c, Q)$

  Output: Return $hDBDH_{\mathsf{solver}}(g,g^a,e(g^b,g^c),Q)$

Now I want to prove the other direction. Any ideas of how a DBDH oracle could be used to solve the hDBDH problem? Any ideas of why it is not possible?

Your problem is stronger than the DBDH problem because any oracle that responds to your query can also respond to DBDH. I think that you must try to reduce this problem to DDH. This means an input $(e(g,g),P=e(g,g)^x,R=e(g,g)^y,Q)$ and the decision whether $Q=e(g,g)^{xy}$.


What's the difference between confusion/diffusion and mode of operation? I understand the concepts of confusion (substitution) and diffusion (permutation).

My understanding of what a mode is that it's an algorithm that lets us encrypt arbitrary message size. i.e. AES is a mode of operation, and confusion/diffusion are what we use to achieve a certain mode.

But that doesn't sound right.

AES is a mode of operation, and confusion/diffusion are what we use to achieve a certain mode.

AES is a block cipher, which replaces one fixed-length block of bits (plaintext) with another fixed-length block of bits (ciphertext) according to the key. A block cipher is not a mode of operation.

Confusion and diffusion are a description of how AES behaves to ensure that given a/many plaintext-ciphertext pairs, you cannot recover the key, as well as given a ciphertext, you cannot recover the plaintext.

"Confusion" basically means that the equations that represent the ciphertext are too complicated and cannot be worked with, while diffusion means that each bit of the plaintext influences many (half) of the bits of the ciphertext. These two properties help to ensure that extracting the key from plaintext-ciphertext pairs is difficult or infeasible.

Since AES only operates on blocks of 128-bits, you require a mode of operation to encrypt plaintexts of size > 128 bits. So a mode of operation is a way of using a block cipher to encrypt (effectively) arbitrary length messages.

Since for a fixed key AES is deterministic, a mode of operation also provides a means to randomize plaintext-ciphertext pairs, so that multiple encryptions of a plaintext cannot be distinguished from each other. This is necessary to properly provide confidentiality of the plaintext.


Timing-Safety in JVM-Languages How is it possible to write timing-safe code in JVM-languages (Java, Scala, Clojure...)?
Is it possible to make libraries like BouncyCastle safe against timing-attacks?

I know that even in C it is very hard to get those things right – and in C you can take a look at the resulting assembly-code and at least predict how your target-CPU will execute it.

In JVM-languages, you don’t know how the JVM will translate your code to machine-code or which runtime-optimizations will be performed.

Edit: I’m not really worried about local timing-attacks but about remotely-exploitable ones.

The theory is: don't try to write timing-safe code in JVM-languages or other essentially-interpreted-but-perhaps-sometime-compiled languages; rather

Use timing-safe libraries called from the comfort of the JVM-language. Typical example: in a JavaCard that passed Common Criteria evaluation to EAL5+ with AVA_VAN.5 augmentation, it is a safe bet that AES (when available) is timing-safe.
Avoid needing timing-safety in the first place when possible. Typical example: rather than attempting to compare an alleged 16-byte value to a reference 16-byte value in constant time, draw a fresh AES key, encipher the alleged and reference value with this AES key (with a constant-time AES implementation), then compare the results using any method at hand.
As a variant of the above, use countermeasures that make timing attacks less efficient, like blinding.

The above tends to work also against side-channel attacks beyond timing, e.g. power analysis.

When market pressure dictates otherwise, options are to make as few as possible relatively safe bets; and check them carefully when one has the luxury of knowing the actual targets. For example, when writing
// compare two byte arrays so that timing does not leak where a difference lies
public static boolean myEqualByteArrays[(byte[] a, byte[] b) {
    int j = a.length;
    if (j != b.length)
        return false; // arrays are not the same length
    int r = 0; // will stay zero until a difference is found
    while (--j>=0)
        r |= a[j] ^ b[j];
    return r==0; // true if and only if the arrays match
}

it is only assumed that

binary operations ^ and | are constant-time (& and unary ~ probably are, too, though we don't need that in this example);
loops won't be exited even when deep analysis of what follows shows that they can.

So far, if I have met anything breaking these assumption, I did not realize it!

Example of things that can't safely be assumed constant-time:

Any use of if, switch..
short-circuit operators && and ||
Logical not !
Array access (e.g. due to cache).
Integer multiplication (including by a constant): some CPUs have multiplication time dependent on one argument; examples include this and this 32-bit CPUs (kudos to the manufacturer for documenting it).
Division, of course (including by a constant).
Operations on larger data types than supported by the combination of the compiler, runtime, and hardware: conceivably, some internal carry might cause a data-dependent timing dependency even in + or -, e.g. of some 64-bit type internally using 32-bit variables. This a bit less to fear for variable addition than increment, which could be implemented or automagically over-optimized at runtime into: increment low half, and if not zero increment high half.
Shift: timing often depends on the shift count.
Right-shift by a constant shift: that can depend on the sign or high-order bit of the shifted argument (that is less likely with unsigned types; and in Java, it is less likely with the unsigned >>> operator than it is with the signed shift operator >>).
The selection operator ?: ; however, in Java, restricting to built-in signed 2's-complement 32-bit type int, a substitute for d = (a==0) ? b : c; might be
// compute the OR of all bits in  a  into the low-order bit of  d
d = (a >>> 1) | a;
d = (d >>> 2) | d;
d = (d >>> 4) | d;
d = (d >>> 8) | d;
d = (d >>>16) | d;
d = -(d&1); // duplicate the low-order bit of  d  over the whole  d
d = ((b^c)&d)^b; // select  b  iff a==0,  c  otherwise
and that technique could be extended to, say, constant-time point multiplication on an elliptic-curve over some binary field, if efficiency is truly secondary.


Noisiest RF band for random number generation I've been looking into the difference between PRNGs and proper RNG techniques. One that I particularly like is the idea of tuning a radio to a certain frequency and bandwidth and just listening to the noise. Every so often (or continuously) pick a sample out of the noise and build a random number out of the samples.

There are a few obvious frequency ranges to avoid for this purpose:

Actual AM/FM radio stations (very predictable, not noisy at all)
TV stations (as above)
Protected RF bands (government, cellular, etc)

Based on noise-generating natural (and digital) phenomena, my question is: what frequency ranges are likely to be the noisiest and thus carry the most entropy for the purpose of a true random number generator?

This is not likely to be a good method to generate random numbers -- at least not on its own, without significant additional analysis.  You need a source of random numbers that is not only noisy, but also unpredictable to an adversary.  It's not clear that radio will meet that need.  If you listen on a FM band, an adversary who is nearby can also listen on the same FM frequency and will likely see something very similar to what you see, so will have a huge leg up in predicting the numbers you generated.

Bottom line: don't try to roll your own random-number source.  It's better to use a time-tested scheme, like a crypto-strength hardware RNG, or /dev/urandom, or a similar crypto-strength scheme.


Is SHA1 secure with such many inputs Z that Z = constant secret X + variable public Y? Let me ask whether SHA1 is designed to be secure for the following case.
You compute each SHA1 of many strings,for example 1 million, where each string is a concatenation of X+Y ,
where X is secret and constant and Y is public and variable.

Thank you in advance.

Answering the question as worded in its body: NO, $\mathrm{SHA1}$ is not designed so that the proposed construction is secure under the stated conditions. The design objective of the $\mathrm{SHA1}$ and $\mathrm{SHA2}$ hashes, as explained by NIST, is that

  it is computationally infeasible to find a message that corresponds to a given message digest, or to find two different messages that produce the same message digest.

and this does not lead to the conclusion that the proposed construction is secure, under any reasonable definition.

In order to answer the (different) question as worded in its title, we need to define "secure". The question is about a construction $F: (X,Y) \to F(X,Y) = \mathrm{SHA1}(X||Y)$. One possible definition of "secure" could be that $Y \to F(X,Y)$ is computationally indistinguishable from a random function for an attacker not knowing $X$ (which implies that $X$ does not leak from examples).

With this wide definition, NO, $\mathrm{SHA1}$ is not secure. It is vulnerable to a length-extension attack, a classical weakness of the Merkle–Damgård construction used in $\mathrm{SHA1}$. An adversary knowing $\mathrm{SHA1}(X||Y)$ can compute $\mathrm{SHA1}(X||Y')$ for some $Y'\ne Y$, on the conditions that $Y'=Y||P||E$; and he knows $E$ and the length of $X||Y$; and $P$ is a specific 65-to-576-bit string depending only on that length. Having many examples of $(Y,\mathrm{SHA1}(X||Y))$ helps the adversary, in that it widens the choices for $Y'$.

To perform this length-extension attack, the adversary can choose $P$ as the 65-to-576-bit string constituting the padding for $X||Y$ when computing $\mathrm{SHA1}(X||Y)$. Then, $\mathrm{SHA1}(X||Y||P||E)$ is computed by starting the normal computation where the block with $E$ starts, with the 160-bit hash state $\mathrm{SHA1}(X||Y)$ rather than the constant specified in $\mathrm{SHA1}$. The attack has very low cost, lower than if the adversary had computed $\mathrm{SHA1}(X||Y')$ directly with knowledge of $X||Y'$.

When the conditions for the length-extension attack are not met (including if the length of $Y$ is fixed, exactly or with a small leeway of +64 bits), or when the objective of the adversary is finding $X$, the construction proposed has considerable cryptanalytic resistance. Up to some limit on the size of $X$, we know no attack much better than brute-forcing $X$. A security argument could be given based on the assumption that the cipher used in the $\mathrm{SHA1}$ round function is secure; but we know that this assumption does not hold at all, if only because of some near-practical attacks on the collision-resistance of $\mathrm{SHA1}$. Therefore I can't quantify the level of resistance better than "AFAIK unbroken for practical purposes", which is not strong enough for a recommendation.

Fortunately, there is a recommendable construct based on $\mathrm{SHA1}$ that is designed to be secure (in the wide definition we considered); this is HMAC with $\mathrm{SHA1}$ as the hash function, $X$ as the key, $Y$ as the message. This construction has a security argument that is not directly harmed by a collision-resistance attack on $\mathrm{SHA1}$. Although the absolute confidence we can have in this argument is the subject of debate and some controversy, it is still very reassuring to me about the security of HMAC, and I am not alone.


Small solutions to modular arithmetic linear congruence Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y \equiv c \pmod p$ with both having at most $N/2$ bits.

What algorithmic approaches can solve this problem? Does it have any known hardness reduction?

You can use lattice reduction to solve this problem.

Pick a large constant $S\in\mathbb Z$ and consider the lattice spanned by the rows of the following matrix:
$$
L = \begin{pmatrix}
S a & -1 & 0 & 0 \\
S b & 0 & -1 & 0 \\
S c & 0 & 0 & S \\
S p & 0 & 0 & 0 \\
\end{pmatrix}
$$

Now the crucial thing to notice is that some pair $(x,y)\in\mathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.

Moreover, some vector of the form $\vec v=(Sz,x,y,\pm S)$ must be part of a short basis, since $\begin{pmatrix}S c & 0 & 0 & S\end{pmatrix}$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $\vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.

Here's a sage transcript that demonstrates this:

sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000                   -1                    0                    0]
[36905883040000000000                    0                   -1                    0]
[ 3736864660000000000                    0                    0          10000000000]
[42949673110000000000                    0                    0                    0]
sage: L.LLL()
[           0        49124        -7835            0]
[           0       -31049       -82479            0]
[-10000000000         2330       -37438            0]
[           0         4276       -42601  10000000000]
sage: (4276*a -42601*b) % p == c
True


calculate ESS IV initialization vector for aes- bc essiv encryption I want to do block level encrypton on my ext4 image file system with aes-cbc-essiv

How can I find/calculate the the ESSIV needed for encryption?

Wikipedia has this documented.

Essentially: Let $\text{SN}$ by the current sector number encoded as a 128-bit integer. Let $K$ be the key used for encryption. Let $\operatorname{hash}(\cdot)$ be a hash function, which is specified in the cipher name.

Now the $\text{IV}$ is computed as $\operatorname{IV}(\text{SN})=E_{\operatorname{hash}(K)}(\text{SN})$.

The relevant code can be found for the key-calculation and for the actual IV.


Brute force attack expected running time I am a bit confused about the expected running times of brute force attacks on different cryptosystems.

So let's assume a key size of $2^n$ bits.

Symmetric key cryptography:

$E(brute)$ = $2^{n-1}\cdot$ comparisons time

So if I understood correctly I need to generate all the possible $2^n$ keys to find the "right" key for sure. Now taken into account the definition of Expected Value of a random variable $X$, that can take the value $x_i$ with $p_i$: $E[X] = \sum p_i \times x_i$. So in our case we can say that $k=2^n$ and $E[X] = \frac{k(k+1)}{2}\cdot \frac{1}{k} = \frac{k+1}{2} \approx 2^{n-1}$.
Cryptographic hashes

Following the birthday paradox analogy and approximating the required time we end up with $E[X] = \sqrt{2^n} = 2^{n/2}$ comparisons.

My confusion comes from public key cryptography and from ECC: in this post ECC is nicely described, but it says that on average you must guess $2^{n/2}$ keys. I don't really understand where this number comes from as you are not searching for a collision as in the case of hashes, but for an exact match.

Well, ECC takes about $2^{n/2}$ time to break because there are smarter ways to attack it than literally trying each possible key separately.

With AES, the best known-attack is to try a key, and see if it works.  If it doesn't, all you've learned is that that specific key wasn't it, only $2^{n}-1$ more to go...

However, with ECC, there are other methods.  For ECC, in general, a public key gives us two elliptic curve points $G$ and $P$; to break it, we need to find an integer $k$ such that $kG = P$ (where $kG$ is point multiplication).

Now, there are $q$ possible values of $k$ (where $q \approx 2^{n}$ is a large prime that depends on the curve); however here is a smarter way to attack it:

Compute a value $r \approx \sqrt{q}$
Generate the $r$ values $P-0G, P-1G, P-2G, P-3G, ..., P-(r-1)G$.  This takes $O(r) = O(\sqrt{q}) = O(2^{n/2})$ time.
Generate the $r$ values $0rG, 1rG, 2rG, 3rG, ..., (r-1)rG$.  This also takes $O(r) = O(\sqrt{q}) = O(2^{n/2})$ time.
Scan through the two lists for a value in common; if we see that $P-iG = jrG$, (for two integers $i$, $j$) then we have $P = (jr+i)G$, and that solves it.  This always succeeds if $r \ge \sqrt{q}$, and this takes $O(2^{n/2})$ time if we use an appropriate hash table.

Total time taken: $O(2^{n/2})$.

This isn't the only way to solve the problem this quickly (there's also Pollard's Rho, which doesn't involve huge tables), however this is the easiest to explain.


Deterministic outputs based on non-connected inputs I am looking for a one way function that can generate outputs deterministically. However, revealing any of the inputs dont allow the person to generate other inputs.
E.g:
lets say we have a list of inputs: $i_{1},i_{2},i_{3},...$ that look completely random and a list of corresponding outputs: $o_{1},o_{2},o_{3},...$ that also look completely random which are each mapped by one way functions: $f_{1},f_{2},f_{3},...$
These outputs can be generated without knowing the inputs so anyone should be able to deterministically generate the outputs (perhaps by knowing a public shared data which is used in the function). But if one of these inputs is revealed, it should not reveal the other inputs.
If it is not mathematically possible, I need a proof for it.

"public shared data" $\:$ = $\:$ the ordered pair whose entries are

[a key for a full-domain statistically injective PRF] and [a signature verification key]

$\hspace{.04 in}f$ is an arbitrary one-way function.

For each positive integer $j$, [$o_j$ is the value of the PRF at $j\hspace{.03 in}$] and [$i_j$ is [[the signature for $o_j$] concatenated with [the string of zeros whose length equals the length of that signature]]]

and $\hspace{.04 in}f_j$ is given by

if $\hspace{.04 in}f_j$'s input has even length and its left half is a valid signature for $o_j$

and its right half is all-zero then output $o_j$ else output $\hspace{.04 in}f$ of $\hspace{.04 in}f_j$'s input.


Symmetric Multi-Key Decryption Is there an encryption decryption scheme in which a group of people are all given different keys, and of which each key can decrypt a file. (I’m not talking about a scenario where a file is encrypted with a single symmetric key, and then the symmetric key is separately encrypted with each individuals public key.)

I’ve read articles about broadcast encryption and multi-trapdoors but I'm unsure if any of these would match the correct scheme so I’m looking for.

You don't have to use any special asymmetric construct. Just give the group keys and encrypt the file with a unique random key and than encrypt the file key many times using the keys of the permitted users.

You can give each user multiple keys some of them shared by relevant groups. To prevent encrypting a file with too many keys. These can even be done ad-hoc, assuming groups repeat themselves. you can create a group key encrypt it with the keys of the members and reuse it if you want to give that group access to another resource later.


Ciphers in CBC mode reveal place of change in plaintext Theoretically, when using a symmetric block cipher in CBC mode, the current block is dependent on the previous block. Suppose one plaintext is encrypted using CBC, and then one bit of it is changed, let's say somewhere in the middle. Then the new ciphertext will change from the middle onward. Would it be better if I used CBC like this?

encrypt plaintext
reverse the ciphertext
continue encrypting (now from finish to start)

That would ensure that one modification to the plain text will change the entire new ciphertext. Right?

Your problem is that if you encrypt two messages which start the same (and change at some point later on) the beginning of the ciphertext will be the same in CBC mode when using the same IV.

Normally you should change the IV every time you encrypt a new message. This is precisely what the IV is meant for - achieving IND-CPA (semantic) security which prevents an attacker from detecting where the the message was changed. Once you do this, your concerns go away, since even two similar messages (say, an old document, and a newer, slightly revised one) will be encrypted with completely different IV's, and hence their ciphertext will be unrelated. And you don't need a two-pass scheme anymore!


Why is RSA-2048 max input 245 bytes? I can see that the message (after padding) should not be 256 bytes because it might be bigger than the modulus of RSA. So I think that the message should be 255 bytes, but I saw posts that says the maximum input is 245 bytes. Why is that?

This is due to RSA with PKCS#1 v1.5 padding, as defined in section 7.2 of RFC 3447 (PKCS#1 v2.1):

2. EME-PKCS1-v1_5 encoding:

      a. Generate an octet string PS of length k - mLen - 3 consisting
         of pseudo-randomly generated nonzero octets.  The length of PS
         will be at least eight octets.

      b. Concatenate PS, the message M, and other padding to form an
         encoded message EM of length k octets as

            EM = 0x00 || 0x02 || PS || 0x00 || M.

As you can see there are three overhead bytes and a minimum of 8 bytes of random padding.

Without the padding RSA encryption would be deterministic and not secure.

Originally the RSA encryption scheme has mostly been used with PKCS#1 v1.5 defined padding. No other schemes were all that popular at the time. So it is most likely that PKCS#1 v1.5 is implicitly used when no padding scheme is indicated.

Officially the name should be RSAES-PKCS1-V1_5-ENCRYPT of course, but nobody uses the function names directly.

Note that there are other modes of padding such as OAEP (defined in the same RFC), which is more secure. For new protocols PKCS#1 padding should not be used anymore. If you're stuck with an old protocol that requires PKCS#1 unpadding, you should make sure that padding / decryption oracles do not apply.


Compressing EC private keys For reasonable security, EC private keys are typically 256-bits. Shorter EC private keys are not sufficiently secure. However, shorter symmetric keys (128-bits, for example) are comparably secure.

I have a case where I need to regenerate an EC private key (that can be constructed by a special method) with as little stored information as possible. Fewer than 128-bits is not possible without compromising security against an exhaustive search.

I'm curious if I can use the following method:

Generate a random 128-bit value. This is the value I would store to recreate the private key.
Use a 256-bit hash, say SHA256, of the random value as the private key. (I have a method to do this that doesn't bias any keys over any others.)
The corresponding public key would be made public.

Thus, I can regenerate the private key from the 128-bit value. It seems to me that the private key and 128-bit value should be just as secure as using a random 256-bit value for the private key and storing that. Exhaustive search is clearly impractical, and the properties of the EC key shouldn't be capable of being walked backwards either from the public key or through the hash. In principle, the EC search space is halved, but it doesn't seem like there would be any practical way to take advantage of this.

Is there anything I'm missing? Is there any reason this wouldn't be just as secure as storing the full 256-bit key? Assume the public key and the algorithm are known to potential adversaries. The adversary's goal is to get the private key. It seems to me that this is obviously as secure as the underlying algorithms, but I know enough not to trust myself.

What you suggest is valid. Here is a way to show it:

In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules:

a key pair generator, which produces a pseudo-random key pair;
a signature generator, which uses the private key to produce a signature over some piece of data;
a signature verifier, which verifies a signature over some piece of data, using the public key.

It is acceptable that the key pair generator is a deterministic algorithm, provided that it is "cryptographically strong" and works over a "long enough" secret seed. "Long enough" means: a string of length at least $t$ bits if a security level of $2^t$ must be achieved.

What you suggest is simply storing the PRNG seed instead of storing the output of the key pair generator. You run the PRNG again each time you want to use the private key. Since the PRNG is deterministic, this yields the exact same signatures that you would have obtained if you had stored the private key, so, from the outside, this is indistinguishable from the "normal" setup. Hence the security.

The concept is applicable to any asymmetric algorithm, not just EC-based algorithms. You could do so with, e.g., RSA, using the PRNG to regenerates the primes $p$ and $q$. However, for RSA, the cost would be high (generating a private key is considerably more expensive than actually computing a signature) and the generation process is susceptible to partial leakage through timing attacks, so this would be a bit delicate. For algorithms such as DSA, Diffie-Hellman or ElGamal, or their EC variants, a private key is just a random value modulo a given $q$ (the group order), so that's fast.

The only tricky point is to show that "one SHA-256 invocation" is a suitable, cryptographically strong PRNG, when you only want 256 bits of pseudo-alea. In the random oracle model, no problem. In a practical world of standard compliance and administrative acceptance, you might want to use an Approved PRNG, in particular HMAC_DRBG (that's the one NIST considers to be "the strongest").

Note: it is not strictly necessary to have an unbiased selection of the private key. For (EC)DSA, there is a private key $x$, and, for each signature, a new random $k$ modulo $q$ must be generated. It is crucial that $k$ is negligibly biased; but for $x$, you can be a bit more lenient. For instance, for a curve where the subgroup order $q$ has size 256 bits or more, it suffices to generate a single 256-bit integer, and reduce it modulo $q$. Some values may have a twice higher chance of being selected than others, or, if the size of $q$ is greater than 256 bits, some values have probability zero of being selected; but this is not an issue for $x$. For $k$, this would be a very serious problem.


After Google's collision attack, is RSA-SHA1 signature still safe? Google succeeded to get a collision in SHA-1 last year in an attack called shattered. Does this fact make certificates based RSA-SHA1 Signature risky for  creating fraud certificates?

If RSA-SHA1 signature is still safe, why is that (because the attacker doesn't have the private key)?

The answer is "not safe".

But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice.

Google found one collision based on some existing, publicly known collision
attacks on SHA-1. Sees the introduction of Google's paper for a complete list of prior work.

First, let me briefly explain how RSA-SHA1 signature works. The explanation below is adapted from a W3C's page introducing RSA-SHA1.

The message $m$ is compressed via SHA-1 into a fixed-length string $h=\mathsf{SHA1}(m)$.
The RSA signature scheme (with padding via PKCS#1) creates a signature on $h$ rather than $m$. $\sigma=\mathsf{RSASignPKCS\#1}_\mathsf{sk}(h)$.

If SHA-1 is fully broken, we expect that we can find $m_1$ and $m_2$ with the same hash value under possible resource constriant: $\mathsf{SHA1}(m_1)=\mathsf{SHA1}(m_2)$.

In this case, they have the same $h$. A RSA-SHA1 signature for $m_1$ is also a RSA-SHA1 signature for $m_2$.

Now I give an example of why it fails. (corrected example, thanks to @peter-green)

I am the website owner of randomwebsite.com.
I want to have VeriSign sign a certificate for cvs.com.

So, I use the collision attack to generate two certificates.

A certificate for randomwebsite.com.
A certificate for cvs.com.

These two certificates have the same hash.

I have a CA to sign the certificate for randomwebsite.com.

Now, if you have randomwebsite.com's certificate signed by CA via RSA-SHA1, which has a signature for that hash. This signature can also be used in the certificate of cvs.com.

You can apply the signature to the fake cvs.com certificate. Different from the real cvs.com certificate, for this one, you have the private key associated with the public key in the certificate.

A more detailed discussion can be found in another post.

A lesson from the SHA-1 story:

Always use the MOST advanced cryptography. We know SHA-1 has some problems and there is SHA-256, SHA-512 and others to replace it. There is no reason to sit in front of a tiger.

Some comments to this post are of great help.
Thanks to Joshua, Squeamish Ossifrage, and Peter Green.


Should I be worried about XTS tampering when encrypting backups using VeraCrypt? From Wikipedia:

XTS mode is susceptible to data manipulation and tampering, and applications must employ measures to detect modifications of data if manipulation and tampering is a concern: "...since there are no authentication tags then any ciphertext (original or modified by attacker) will be decrypted as some plaintext and there is no built-in mechanism to detect alterations. The best that can be done is to ensure that any alteration of the ciphertext will completely randomize the plaintext, and rely on the application that uses this transform to include sufficient redundancy in its plaintext to detect and discard such random plaintexts."

I am researching secure ways of backing up data on a regular basis (using deduplication or versioning).
The backup would be stored in low security location (meaning an attacker could have access to the data over long amounts of time and over multiple backup cycles).
Should I be worried about XTS tampering when encrypting backups using VeraCrypt?

With XTS mode encryption data can be "tampered with" with the caveat that any changes to the data are random and unpredictable to an attacker. Since encryption acts as a pseudo-random function for any secure encryption you end up with a secure scheme:
Note that for each block there is a unique 128-bit block id according to XTS mode. This ID needs not be random.
XTS mode takes ENC(block XOR block_id) XOR block_id

If XTS was only ENC(block XOR block_id) an attacker can control the value block XOR block_id used to encrypt. This can be potentially useful if the attacker wants to convert it to ECB mode encryption allowing them to run other attacks; but only works in a chosen-plaintext case. This assumes the attacker knows the block id.
If XTS was only ENC(block) XOR block_id an attacker can XOR the block ID manually from the ciphertext to reveal ECB-mode encryption. This assumes the attacker knows the block id. This works in a ciphertext-only attack.
If the attacker can perform #2 they can extend that to ENC(block XOR block_id) XOR block_id. This yields an attack where they combine attacks #1 and #2.

... Or can they?
If an attacker tries the composite attack they'll be restricted by their knowledge of the block id. But in XTS mode the block id is kept secret by encrypting another key, and using that to create the block id. If the attacker knew the block ids used, they could use the outlined composite attack.

If the scheme was ENC(block) XOR block_id the attacker could find the block ids used via the same cryptanalysis that breaks ECB mode, if they knew the pattern between block ids; effectively yielding an obfuscated ECB mode encryption in any case there the block ids are predictable (eg. each block id is the previous id + 1).

If the scheme was ENC(block XOR block_id) the attacker would be unable to recover the block ids, since they would be unable to determine from the ciphertext which ids are likely to be correct.

In the actual XTS mode, since it combines both of those simplified cases the attacker is SOL. Plus, you may have noticed neither of those cases allow an attacker to intelligently modify the plaintext from the ciphertext.

Those attacks can reveal patterns in the information but neither allows (intelligent) data tampering.

CBC mode allows tampering because each block is XORd with the ciphertext of the previous block (the block id is known simply by looking at the ciphertext).

The attacker can modify the ciphertext of the previous block to change the data in a specified block.
The previous block, after tampering, becomes meaningless; but the block the attacker wanted to change is intelligently modified.

In CTR mode tampering is possible because the plaintext/ciphertext isn't passed through the encryption function, at all; it's simply XORd with a random stream (the random stream is generated by the encryption function).

In a secure block cipher, any change to the ciphertext yields random and meaningless plaintext once passed through the encryption function. Therefore, any attempt at tampering would yield that result.
In short,
XTS mode does allow tampering in a certain sense, but the attacker cannot know or predict what the data will become. They can only say "F**k you, your data is meaningless!"


4 x E = D in Simplified AES how it's possible? Can anyone explain how it's possible through hexadecimal or Binary 4 x E= D


How to encrypt many files with AES-GCM, without running the key derivation function each time? Linked question: AES encrypting multiple files

With a password, I have 100k files to encrypt. (Maybe 100k files today; or maybe 50k today, 10k tomorrow, and 40k files the next week).

Up to now, I did this (pseudo-code):
for each file:
    plaintext = file.read()
    nonce = getrandom(bytes=16)
    key = KDF_PBKDF2(password, salt=nonce, count=1000000)  # very slow for each file!
    ciphertext, tag = AES_GCM_cipher(key, nonce=nonce).encrypt(plaintext)
    write to disk:   nonce | ciphertext | tag

and to decrypt the encrypted file
nonce, ciphertext, tag = file.read()
key = KDF_PBKDF2(password, salt=nonce, count=1000000)    # very slow for each file!
plaintext = AES_GCM_cipher(key, nonce=nonce).decrypt(ciphertext)

Obviously, this is not optimal, since I run the KDF function for each file, and this is slow!

I thought about this solution:
# do this ONLY ONCE for each encryption session:
salt = getrandom(bytes=16)
key = KDF_PBKDF2(password, salt=salt, count=1000000)   # run only once

for each file:
    plaintext = file.read()
    nonce = getrandom(bytes=16)
    ciphertext, tag = AES_GCM_cipher(key, nonce=nonce).encrypt(plaintext)
    write to disk:   salt | nonce | ciphertext | tag

but this has the drawback of having to prepend 16 more bytes (salt) at the beginning of each encrypted file. Is it a common practice?
And above all it has the following drawback when decrypting:
for each encrypted file:
    salt, nonce, ciphertext, tag = file.read()           # since salt may be different for each file
                                                         # we have to run:
    key = KDF_PBKDF2(password, salt=salt, count=1000000) # very slow for each file!
    ...

Since salt is on the beginning of each encrypted file, this means we have to run the KDF function ... for each encrypted file that we want to decrypt! This will be very slow.
We could put them in cache cache[salt] = key, such that if we find the same salt again, we already have the key, but I'm not sure if this is an elegant solution.

Question: which scheme to use to encrypt 100k files (in one pass, or in multiple sessions) with a password with AES-GCM?

One serious about password-based cryptography must not walk away from KDF_PBKDF2, but run to Argon2 (or scrypt if it's more readily available)! Bitcoin mining has (in 2020) shown that dedicated ASICs performing SHA-256 at high rate (220 TH/s) and efficiency (15 pJ/H) can become commercially available for few thousand US dollars. This makes it untenable to rely on PBKDF2-HMAC run on standard hardware for stretching of user-chosen passwords in high-security applications.
The method proposed has one characteristic: salt is common to several files if, and for wide random salt only if, they have been encrypted together. This is both a possibly unwanted information leak, and a way to solve the drawback mentioned: the password-stretching code used in decryption can maintain a RAM cache of (salt, key) pairs.
I'd consider replacing AES-GCM with AES-GCM-SIV, for peace of mind in case of stuttering of the RNG, but keeping in mind that two passes are needed over the data.
As much as I advocate trimming the last byte when it counts (e.g. when the data lies on a barcode or goes thru a slow or/and battery-depleting communication medium), I won't recommend saving on salt and nonce size in file encryption like we're in the 1980s.


Recommended skills for a job in cryptology First let me apologize if this is an ill posed question. Let me also note that I do not in any way seek a comprehensive answer, simply your thoughts on what makes for a valuable asset to a company like the NSA. I am a Maths student in the US, and I realize that a problem-solving mind is at minimum required for said question.

Some other responses I would find helpful include coursework, relevant programming languages, as well as helpful books. I am currently reading Schneier's (sic?) Applied Cryptography.

It seems we have aligned interests. I'm also a university student (although I am a math/comp sci double major) looking to pursue a career in cryptography. To that end, I have been self-studying it for a while now. So, take what I say with a grain of salt. As a forewarning, this post focuses specifically on what topics cryptographers often encounter and less about what, as a person, makes you useful as an employee to a crypto-agency.

From what I can best tell, the requisite knowledge of computer science is entirely dependent on what you want to do with cryptography exactly. If you are looking to work in an applied area, then you had best had a strong grasp of the basics of computer science. If you are implementing algorithms, then you will likely need to know the basics of modern-day computer architecture.

The reasons for this are many-fold. First, an understanding of computer architecture will allow you to optimize code like no other. For instance, a knowledge of things like instruction-level parallelism and pipelining is incredibly important because taking proper advantage of both can seriously speed code up. Second, you may need to know some basics about architecture in order to ensure security of your scheme. For instance, if you are working with smart cards, you will need to be able to design, or at least verify the security of, tamper-resistant circuitry.

Further, you will need a strong knowledge of C, which sits so close to the hardware that it isn't too far a step away anyways. From what I can tell, the vast majority of "serious" crypto code is written in C, even if it has a language wrapper around it (e.g. PyCrypto). Other languages, especially interpreted ones, simply do not allow the same performance as C, and we do like performant implementations. Another selling point of C is that, in crypto, you are most often working with raw bytes and bits, which is exactly where C shines. It's the de facto language for low-level work.

To that end, I would really recommend you pick up a minor in computer science if you are going to work with applied cryptography at all. Relevant courses include introductory programming, operating systems, assembly language, architecture, and complexity theory. There are lots of computer science resources on the web, though, so don't feel too discourage if a minor is simply not possible! An excellent C resource is Learn C the Hard Way. If you want to know more about operating systems (especially important if the code you write will be run on a real-life computer...) then Operating Systems Design and Implementation is an excellent resource. Unfortunately, I don't know of a good reference on computer architecture because of the extreme fast-paced movement in the field; I recommend trying to understand some of the optimizations current crypto algorithms implement.

Of course, to get very far in crypto, you will have to have a strong understanding of mathematics. The Handbook of Applied Cryptography, an excellent reference for crypto in general (with the entire book free online, by the way, on the linked site), has an entire chapter devoted solely to the mathematical background necessary, and then another entire chapter just for number theoretic problems. Since you are a math student, this is probably where you shine.

The HAC lists probability theory, information theory, complexity theory, number theory, and abstract algebra as being introductory background material, and the rabbit hole just goes deeper and deeper. In that list, I don't think there is any particular area that is neglected; all of them are used frequently in different areas of crypto. I can give specific examples if you would like.

You will also need the tools of theoretical computer science. (Sometimes, you will even see cryptography as a field under theoretical computer science, though I feel this definition is rather restrictive.)

Of course, complexity theory is already on the list, and it is indeed the premier star of the show as far as TCS topics in cryptography go. But you might also need to know a few models of computation, e.g. Boolean circuits, Turing machines, random access machines, and the like, because sometimes they're important to a particular problem. (For instance, Craig Gentry used Boolean circuits as the computational model in his fully homomorphic encryption scheme presented in his thesis.) You might consider these models of computation a part of computational complexity theory, though.

Information theory is also on the list of topics in the HAC, and you might find it sometimes included in theoretical computer science lists. Honestly, the line between theoretical computer science and math is often blurred.

For good references in theoretical computer science, I would first recommend a good text on complexity theory; the one I studied was Computational Complexity by Papadimitriou. The wonderful folks over at cstheory.se recommend two other works on complexity theory, but I can offer no evaluation of either. They also have a post devoted to some good books for crypto, which I just now spotted! There are some on the list there I haven't seen. The full post is, in general, worth checking out, but I thought I would link you to crypto-specific areas.

Of course, there are areas of cryptography that are, shall we say, less often "applied" to the real world than others. An example of such is the idea of a zero-knowledge proof, namely proving you know something without revealing what that something is. These things are applied sometimes, and their applications are fantastic, but they haven't been --- as far as I can tell --- widely adopted as, say, generic "guarantee confidentiality and integrity" areas of crypto (e.g. things like AES+HMAC). At least, not in the public eye. If you are not convinced, take a look at the front page of this StackExchange.

For a good reference on "theoretical" crypto topics, I would highly recommend Foundations of Cryptography by Goldreich. It's a two-volume work and covers the real theoretical material lurking in the background. The second book is more applied than the first. Further, Katz and Lindell's Introduction to Modern Cryptography is also quite good, although I haven't studied it extensively.

Of course, there are also generic crypto references, which is probably what you're most after here. Applied Cryptography and other books by Schneier (et al?) are good. The HAC, which I linked to above, is an excellent tome, touching on tons of topics in applied crypto with a heavy dose of theory too. The post I linked to above (on cstheory.se) has a few recommendations too. For a good history of the subject matter, I would highly recommend (if you want brevity) The Code Book, which is a really nice overview of the history of crypto. Of course, if that interests you, there is always the tome on the subject, Kahn's The Codebreakers. You can also see Thomas Pornin's excellent answer on a question similar to yours on security.se.

In short, this post is a high-level overview of some possible self-study options in crypto. Since I am only a university student, I can't tell you what employers do and don't want you know (especially not the NSA), nor can I tell you what topics are the most important in current-day research. I also make no claims that this post is complete and doesn't make glaring omissions. But I think it has been fairly accurate, at least to the extent that my knowledge and experience permit.


NTRU key size (confused) I'm evaluating the performance of NTRU; and I got confused. the key size is said to be smaller than RSA but larger than ECC.

Using both the reference implementation when I choose APR2011_439 setting from BC I've thought that 439 would represent the key size in bits. But when I store the public key in byte array its size if 604 bytes (PKCS1Encoding encoding). I'm very consufed. With APR2011_439 I can encrypt blocks of max 54 bytes in size so that would indeed be the key size. But why does the key stored in a byte array take a huge ammount of 604 bytes? It is the same with reference implementation.
Please explain I'm very short on time.

I've thourgh that 439 would represent the key size in bits.

No, NTRU doesn't measure things like that.  Instead, it's the number of elements in a ring.  In addition, with the current parameter sets, each ring element is a value between 0 and 2047 (11 bits), and the public key consists of one ring, and so it takes up $11 \times 439 = 4829$ bits, which compresses to 604 bytes.


What is a related key? We talk of related keys and related key attacks, but what is a 'related key'? So in three related parts:-

How can one key be related to another key?
Is there a metric describing the degree of relationship?
Is there a link between the nature of  keys' relationships and any specific cryptographic functions?

Related keys are keys with any mathematical relationship that leads to exploitability in the cipher. This can be a simple relationship, such as having many bits in common. This was the case with RC4 when used in WEP, where each packet is encrypted with a key composed of 104 bits of unchanging key material and 24 bits for an IV, leading to the FMS attack. The relationship might be more subtle, with keys sharing a complex differential relationship, as with the related key boomerang attacks in 256-bit AES.

A trivial example of related keys would be two keys which cause a collision in the cipher's key schedule, resulting in distinct keys having a relationship that allow them to resolve to the same round keys. Full collisions in the key schedule result in equivalent keys, such as with TEA where certain flipped bits in the key cause collisions. Related key attacks often (but not always) are caused by a weakness in the key schedule. A good cipher should not suffer from related key attacks, and all keys should be equally good.

It may be tempting to think that related key attacks don't really matter. After all, any good protocol will have each and every new key completely distinct from each previous key. However, the problem of related key attacks comes up if the cipher primitive is later used in other constructions, such as for a hash function. This was the case with TEA which was abused by Microsoft in the Xbox as a hash. This is an issue because many hash constructions such as Davies–Meyer use each (attacker-controlled) message block as a key. Related keys in the underlying block cipher could then manifest as collisions.

The most severe related key attacks are ones where keys can be related by chance or due to the way they are used in the protocol. It's more common that the relationships are so complex as to be very unlikely to ever arrive by chance and typically need an attacker to influence the choice of keys. As mentioned above, this is typically an issue when a block cipher is used to construct a hash function.


ECDSA, EdDSA and ed25519 relationship / compatibility I'm trying to understand the relationship between those three signature schemes (ECDSA, EdDSA, and ed25519) and mainly to what degree they are mutually compatible in the sense of key-pair derivation, signing, and signature verification. But I was not able to find any conclusive information. I mean, for example, can you verify ed25519 signatures with EdDSA and/or vice versa?
I found the best info here from which I got the suspicion that there might be some compatibility between those schemes, but I could not find any source to prove or disprove it.
Could somebody shed some light on this?

Ed25519 is a specific instance of the EdDSA family of signature schemes.  Ed25519 is specified in RFC 8032 and widely used.  The only other instance of EdDSA that anyone cares about is Ed448, which is slower, not widely used, and also specified in RFC 8032.  Keys and signatures in one instance of EdDSA are not meaningful in another instance of EdDSA: Ed25519 and Ed448 are different signature schemes.

The ECDSA family of signature schemes is not related to EdDSA, except in that the mathematics behind it also involves elliptic curves.  Any particular instance of ECDSA, such as ECDSA over the curve secp256k1 with SHA-256 (as Bitcoin uses), is incompatible with any other instance of it, such as ECDSA over the curve nistp521 with SHA-512.

On a practical level, what a user might need to know is that Ed25519 keys are not compatible in any meaningful sense with keys in any instance of ECDSA.  So, e.g., in the ssh protocol, an ssh-ed25519 key is not compatible with an ecdsa-sha2-nistp521 key, which is why they are marked with different types.  Similarly, an ssh-ed448 key, for Ed448, is incompatible, which is why it is also marked with a different type.

On a technical level, what a protocol designer should know is that the ECDSA family of signature schemes is an archaic slow design that encourages security-destroying implementation errors, while the EdDSA family of signature schemes is a modern design that avoids those errors.


Does a padding oracle have the encryption key? Where in real life do I see such an oracle? So after some searching, I kinda know the attack procedure of altering bit by bit. But I'm still confused how this is possible. If I understand it correctly, the attacker never has the key, or tries to iterate keys. So since the oracle can check the padding, I guess itself has the encryption key?

What is a real life oracle example I can see? I know this should be well patched nowadays, but what were affected before patching? I read that some kinds of web servers were impacted most, but what part of the server has this kind of oracle?

There are many examples of real padding-oracle attacks in practice. SSL/TLS is arguably the most famous example. However, they appear everywhere. In a paper by Practical Padding Oracle Attacks by Rizzo and Duong they find a number of interesting examples. But, they are really all over the place.


Hash + Salt v. Hash + Encryption I was wondering if using a salt with a hash is more effective than hashing and encrypting your hash.

Yes. They provide different things.

The reason you hash a password is so you compare it later on without ever exposing the plaintext. A salt is used to make a large collection of hashes harder to bruteforce.

Encrypting a hash does nothing to make the hash harder to bruteforce. If you're compromised to the point your hashes are leaked, there is a good chance the attacker will also be able to figure out the encryption method and the key.


Keys-space for a restricted substitution cipher How can one calculate the key-space for a restricted substitution cipher? A restricted substitution cipher is one where no letter is assigned to itself. For an alphabet with 26  letters how many keys are there for a restricted substitution cipher? What is the correct way to approach this question? I have been adviced to look into cycle notations, Markov chains and the structure of the symmetric group and its conjugacy classes.

It is called derangement, see Wikipedia.
Also, in Mathematics Stack Exchange 1, 2

Number of derangements of n elements $=\sum\limits_{k = 0}^{n}(-1)^k\frac{n!}{k!}$

When n = 26 the result is 148362637348470135821287825 $\approx 2^{87} $


Private evaluation public quick verification VDF Does anyone know of any VDF, that can be calculated by someone holding some private key in t sequential steps and is quickly verifiable in exponentially reduced step by anyone using some public key and the proof that does not leak the key ? Like opposite of RSA timelock question. A link to some paper would help. can someone tag vdf, posw and blockchain in it? I don't yet have privileges.

A Survey of two verifiable delay functions authored by Dan Boneh, Benedikt Bunz and Ben Fisch is the best resource for understanding the most promising implementations of VDFs. It is a succinct review of two recent beautiful Verifiable Delay Functions, one due to Pietrzak and the other due to Wesolowski.
There are currently three candidate constructions that satisfy the VDF requirements. Each one has its own potential downsides. The first was outlined in the original VDF paper by Boneh, et al. and uses injective rational maps. However, evaluating this VDF requires a somewhat large amount of parallel processing, leading the authors to refer to it as a “weak VDF.” Later, Pietrzak and Wesolowski independently arrived at extremely similar constructions based on repeated squaring in groups of unknown order.
The security of Pietrzak’s scheme relies on the the security of the low order assumption: it is computationally infeasible for an adversary to find an element of low order in the group being used by the VDF. The Wesolowski scheme assumes the existence of groups that satisfy something called the adaptive root assumption, which is not well studied in the mathematical literature.
Recently, Starkware, the Cryptography Engineering firm led by Eli Ben Sasson has come up with a VDF service known as Veedo, deployed on Ethereum TestNet and MainNet. Please find the details in the following post.


Can Java Decrypt a 4-byte MIC? I am using AES/CCM/NoPadding in Java, and it produces a 8-byte MAC when encrypting data. However, the data I receive, produced by a Bluetooth module, produces a 4-byte MIC.

Both the Bluetooth module and my Java/android app, using AES/CCM, produce the exact same output, but have the differences of the MIC and MAC.

Is there a solution to this when trying to decrypt?

You say they produce 'the exact same output' but are different; I assume you mean the same ciphertext but different MAC aka MIC which is also output. Note Sun/Oracle Java, or more exactly the set of cryptoproviders in Sun/Oracle Java, does not (yet?) support CCM at all, and AIUI neither does OpenJDK. However the optional third-party provider from BouncyCastle does. Android Java on the other hand uses spongycastle which I understand to be a clone of BouncyCastle, but I don't know which version(s).

BouncyCastle 1.50 up provider implementation of AES CCM accepts via Cipher.init(key,param) parameter type javax.crypto.spec.GCMParameterSpec which exists only in Java 7 up, to specify the MAC aka tag size (in bits) as well as the IV aka nonce. Yes, GCMParameterSpec for a CCM cipher. If what you have in Android is equivalent to BC >=1.50 on Java >=7 try that.

Otherwise I think your only choice is to implement CTR + CBCMAC yourself, which wouldn't be all that hard.


What security differences are there between E(p',"well-known-plaintext") vs. hash(p') where p'=KDF(p) I am using a KDF to derive a key, p' from a password p. I would like to know if the password is correct before using the derived key.

Bruce Schneier's PasswordSafe format V3 has

  H(P') is SHA-256(P'), and is used to verify that the user has the correct passphrase.

I understand that bcrypt uses the derived key with Blowfish to encrypt "OrpheanBeholderScryDoubt" 64 times to create a password hash. (edit: I am not concerned specifically about Blowfish, but about any block cipher used in this manner. Bcrypt is just an example.)

Question:

Is there any difference in the security of these two approaches to verifying a password?

Context:

I want to be able to authenticate a user before giving him access to his account.  Most of the account metadata are also encrypted with p' to protect them from disclosure to third parties.

Edit: Further research

The SHA-2 functions are based on the Merkle–Damgård construction, which is a method of creating a hash from a block cipher. Merkle–Damgård is popular because it provably preserves specific security properties of the underlying block cipher. It does have well-known weaknesses, with some known "strengthening" strategies (used in SHA-2). The main focus of the SHA-3 competition was to find a different construction without these weaknesses.

I have not been able to find any similar security proofs of the construction of bcrypt, but I also have not been able to find any attacks against it. No one seems to be using bcrypt for any purpose other than hashing/verifying passwords.

For the purpose of a password vault, as used by the PasswordSafe V3 format, the verification of the derived key is not strictly necessary. In the V1 and V2 formats was necessary because the data had no MAC.  Of course, current best practice suggests that all encryption be authenticated. Colin Percival (author of scrypt) suggests verifying the MAC before passing attacker-controlled data to ANY complicated piece of code, such as an encryption or compression function, even when such protection does not provide any cryptographic security benefit.

It is important to make sure that password based key derivation takes place before passphrase correctness is checked. Otherwise, possible attacker can choose if they attack against passphrase correctness check or pbkdf function.
(Appears ok on the both functions.)

PasswordSafe
In case of very high entropy key, it theoretically could be possible that for instance SHA-256(P') would be easier to break than the key. However, for any typical passwords, expected amount of entropy is (possibly) between 10 and 80 bits, and thus the passwords are likely weaker than the hash. (Thus appears ok.)

bcrypt
I don't like decision to use blowfish encryption in crypt. This is because cryptographic key should usually be used only for very small (preferably one) purpose. The use in blowfish algorithm "consumes" allowed key uses. Maybe blowfish is the weakest link?

Overall, it seems that both choices should appear good enough for common practice, but I think the PasswordSafe's choice of SHA-256 appears even more conservative and secure. However, using SHA-256 appears extraneous as well.


The number of keys generated in TLS 1.2? In section 6.3.  Key Calculation in the standard documentation here, I see the following:

  The master secret is expanded into a sequence of secure bytes, which
  is then split to a client write MAC key, a server write MAC key, a
  client write encryption key, and a server write encryption key.

  To generate the key material, compute

  key_block = PRF(SecurityParameters.master_secret,
                  "key expansion",
                  SecurityParameters.server_random +
                  SecurityParameters.client_random);

  until enough output has been generated.  Then, the key_block is
  partitioned as follows:

  client_write_MAC_key[SecurityParameters.mac_key_length]
  server_write_MAC_key[SecurityParameters.mac_key_length]
  client_write_key[SecurityParameters.enc_key_length]
  server_write_key[SecurityParameters.enc_key_length]
  client_write_IV[SecurityParameters.fixed_iv_length]
  server_write_IV[SecurityParameters.fixed_iv_length]

Correct me if I am wrong please, does this mean:

$ms$, $kc_{mac}$, $ks_{mac}$, $kc$, $ks$ = $kdf (ms, nonce_s, nonce_c)$ ??

My questions:

Does that means the kdf generates "actually" 6 keys, but in fact they are 4 keys?
Does that means, the Finished messages are encrypted with the MAC keys and the data are encrypted with another key?
Is the client_write key different from the server_write key? shouldn't they generate a share secret? shouldn't the application data encrypted with share symmetric key? why does the standard make two keys?

1) Does that means the kdf generates "actually" 6 keys, but in fact they are 4 keys?

The KDF generates 6 values; of the 6, 4 of them can be considered "keys" (in the sense that they'll be used to key some cryptographical primitive) and 2 are not (an IV is typically not considered a "key", as exposing it does not yield a security weakness).

Also, some TLS transforms do not use all of the 6 values; the protocol handles that by making the length of the values they don't use to be 0 (so the same general structure applies).  I mention this because you may run into this situation later on...

  3) IS the client_write key different from the server_write key?

Yes, the client_write key is different from the server_write key.  The client_write key is used to encrypt the traffic that is sent by the client to the server, while the server_write key is used to encrypt the traffic that is sent by the server to the client.

As for why they use two different keys for the different directions, well, the original SSL protocol had different keys in the two directions because it used RC4 as the encryption transform, which would have serious problems if you used the same key in the two directions.  When we get to TLS 1.2, they maintained the same structure, in part because they still support RC4, in part because it also helps some transforms (e.g. GCM, which you could use the same key in both directions if you were careful with nonces, but it's easier not to have to worry about that), in part because using different keys for different purposes is just good practice, and in part because there was no real reason to change.

  shouldn't they generate a share secret?

Actually, the shared secret (assuming you're using a DH-based transform) is computed much earlier, as the premaster secret.  That's one of the inputs into the KDF, hence all the keys generated by TLS depend on it.

To answer your further questions:

  Which key is the key used in the Finished MAC ?

The master secret; that's not any of the 6 traffic values (which are used to protect traffic between the two stations), but an intermediate value that is generated from the premaster secret, and in turn is used to generate the 6 traffic keys.

And, yes, it is a value that is shared between the client and the server (absent a man-in-the-middle attack).

  But the standards talk about 6 keys, each party has its own key?

Again, only 4 of those values are "keys"; in any case, they are used to protect records that are exchanged between the client and the server; they too are also common between the two sides, with the understandard that the 'client->server' traffic will be protected by 3 of those values, and the 'server->client' traffic will be protected by the other 3.  All these keys are symmetric, so for the system to work, both sides need to know their values.

If you really want to learn about TLS 1.2 from the source, you might try looking at rfc5246.  This is not a description of TLS 1.2; it is the official definition, and hence cannot be wrong.


Functional signatures vs homomorphic signatures I found that homomorphic signatures allows an agency to carry out arbitrary computation $f$ on the signed data $m$ and accordingly gain a signature for the computation result $f(m)$ with respect to $f$. Another related notion is functional signatures, in which DO hands out a secondary key $sk$ to allow a specified agency to sign messages $m'$ which satisfy that $m' = f(m)$.
Could you please let me know: What are the differences between these two schemes? Because to me they appear to be the same.

The difference is that in homomorphic signatures anyone can compute on the signatures, whereas in functional signatures only the party holding the functional secret key $sk_f$ can compute $f$ on signatures (signed by master secret key corresponding to $sk_f$)


On composition of encryption schemes If we composed (as in function composition) multiple CPA-secure encryption schemes would the result also be CPA-secure?

Yes, if (and this is important) the keys for $E$ and $S$ are selected independently.

Consider that we had two encryption methods $E$, $S$ for which their composition $E(S(x))$ is not CPA secure; that is, we have some distinguisher $D$ that had some advantage in distinguishing that from a random function.  Then, we can build a distinguisher for $E$ (by selecting a random key for $S$, then then use the distinguisher $D$, and when it made a query, we'd take the plaintext it selected, encrypt it with $S$ with our random key, and then gave that ciphertext to the object we're distinguishing (either $E$ or the random function).

Similar logic can be used to show that we can use the distinguisher to distinguish the inner function (by selecting a random key for the outer function).

Hence, if $E$ and $S$ are indistinguishable, so is their composition (in the CPA model).  In fact, we can make a stronger statement; if either are indistinguishable, so is the composition.

On the other hand, if the keys aren't independent, then all bets are off.  Not only do these simulation arguments don't work (as the simulator is unable to select the appropriate key), but the possible insecurity of the system can be seen by considering the case where $E$ and $S$ are inverses of each other.


Side-channel attacks against ECDH for Weierstrass normal form curves I hear a lot about why Montgomery curves are used in ECC, and one reason is that the same algorithm can be used to do both point addition and doubling (this is not true for the Weierstrass normal form).

What are the most prominent unsafe features of curves, and ways one can screw up an ECDH implementation? Are there "more" ways to screw up with the WNF as opposed to the Montgomery form?

Can you point me to an overview of the problems associated with curves in WNF?

The problem doesn't lie with curves in Weierstrass form necessarily, but with naive implementations of elliptic curve arithmetic on such curves.

Basically, if you implement an ECC scheme (ECDH, ECDSA or whatever) on a smart card using a curve in Weierstrass form in the most straightforward way possible (by writing a simple double-and-add loop for exponentiation using textbook formulas for addition and doubling), then anyone can basically take the smart card, perform power analysis while the scheme is running, and directly read off your secret exponent from the power trace because additions and doubling produce quite different patterns on the trace.

See e.g. J.-S. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems", CHES 1999, for some of the basic attacks and countermeasures.

Using appropriate countermeasures, you can certainly implement elliptic curve cryptography on Weierstrass curves in a way that is largely secure against side-channels. The argument of proponents of other curve forms (such as Montgomery curves if you want ECDH, or curves with unified arithmetic like Edwards curves for signatures and other applications) is that, as you say, implementations are easier to get right with those other forms (and as a side benefit, they tend to have better performance characteristics as well). See also this related answer by Thomas Pornin.

For example, the Montgomery ladder, which is the standard way in which you would implement exponentiation on a Montgomery curve, is safe against simple power analysis without having to add in any other countermeasure. Of course, if you want to protect against stronger physical attackers, you may still need to add other countermeasures to your implementation (against DPA, fault attacks, etc.), but the basics are covered, so the situation is really a bit better than with Weierstrass form, where the most standard exponentiation algorithm is leaky and countermeasures tend to be costly.

Side note: the idea that on Montgomery curves "the same algorithm can be used to do both point addition and doubling" isn't entirely correct. Typically, people use Montgomery curves for the very efficient x-only differential-addition and doubling operation that can be used to do efficient, SPA-secure exponentiation up to sign (the Montgomery ladder). But you can't really do point addition at all (certainly not x-only point addition, since it's not well-defined, and if you're going to use two components, you might as well use a better suited curve form).

It's twisted Edwards curves (among others) that admit addition formulas that can also be used for doubling. Now it turns out that any Montgomery curve is birationally equivalent to a twisted Edwards curve and vice versa (you can use any such curve in one form or the other depending on the application) so the distinction might sound a bit academic, but all of these curves can also be put in Weierstrass form as well, after all, so the difference certainly matters as far as implementations are concerned.


Encryption method that is purposely vulnerable to cracking parts at a time? Is there a method of encryption where your key is made up of $n \cdot s$ bits, but also such that an attacker would know when they've successfully cracked each $s$-bit part?

For example, the full key could be $\texttt{1011 0101 1010}$, for $(n=3, s=4)$and you would be able to know if you successfully guessed that the first four digits are $\texttt{1011}$?

Note the entire key could be discovered in $n \cdot 2^s$ time if you individually cracked each of the $n$ parts.

Think of it by analogy like cracking a combination lock by sound, where you would know when you successfully discovered the first number, then the second number, and finally the third number?

Encrypt a short known plaintext ($s$ bits) using truncated keys (to $s$, $2s$, $3s$, etc. bits) and publish them alongside the ciphertext. Then an attacker can break them in order of increasing keylength, until they recover the full key.

There is a quite similar vulnerability when performing a chosen-ciphertext (online) attack against short polynomial MACs. For example consider GCM with a short 32-bit authentication tag (hence you should never use short tags). The attacker submits messages to an oracle and learns if they're accepted or not. After a successful forgery (chance $2^{-32}$) the attacker learns 32-bits of the MAC key. After several successful forgeries they can recover the full MAC key. The decryption key can then be recovered using standard oracle attacks against unauthenticated CTR mode.


Why are MACs not included when defining Protocols? I see often in literature related to cryptographic protocols that MACs (Message Authentication Codes) are not included in protocol definitions.

For example:

A -> S: {TA, B}KAS
S -> A: {TS, KAB, B}KAS
S -> B: {T'S, KAB, A}KBS

Shouldn't it be defined as follows ? (Encrypt-then-MAC + using second key for MACs)

A -> S: {TA, B}KAS, [{TA, B}KAS]KAS'
S -> A: {TS, KAB, B}KAS, [{TS, KAB, B}KAS]KAS'
S -> B: {T'S, KAB, A}KBS, [{T'S, KAB, A}KBS]KBS'

Isn't integrity a concern, or do protocol analysts generally assume that cipher-text cannot be modified at this level of protocol abstraction? Do you exclude ciphertext-only attacks?

It depends on the protocol. In general IND-CPA secure ciphers are assumed. That would mean that confidentiality is taken care of by the cipher.

If integrity and/or authenticity are also required then it should be made explicit in the protocol. In that case it is however perfectly possible to use one key, e.g. by using an authenticated cipher such as GCM.

If ciphertext only attacks are excluded depends on the context.


Proper way of encrypting large files with AES-256-GCM I would like to encrypt and decrypt files with AES-256-GCM. I need a solution that works with Java, PHP and JavaScript. In practice, users can upload, download files via web browser and/or desktop app and there are files that will be generated by the server itself. (I'm currently using openSSL, but I'm thinking of switching to Sodium). I have a working solution already that works fine using relatively small files (<100MB).
However, I am concerned about memory usage for large files (like videos, disk images).
I found a couple of implementations where file chunks are used. (The resources I found were not specifically security-related sites.)
The concept is:

Read 1MB from the original file
Generate an IV
Encrypt the chunk
Save the IV, ciphertext, and tag to the output file
Repeat until the end of the file

The IV is always 12 byte and the tag is always 16 byte so it is not very difficult to implement it.
The solution works, but the real question is, is this solution good from a security standpoint or should something else be used?

No, the way that it is described, the solution is insecure.
The chunks themselves are of course secure. That is: as long as you verify the authentication tag and if the IV is indeed unique, i.e. a nonce as required by GCM.
However, an adversary can simply switch around the chunks in the file, including the IV and authentication tag. That way the file can be rearranged. Similarly, whole chunks can be removed without issue. If you use the same key for multiple files, you can replace one file with another, or even move chunks between files.
The way around this is to verify that all the authentication tags are in the correct order, e.g. by using HMAC or even by using them as Additional Authenticated Data (AD or AAD) in a separate call to GCM. Then add the final authentication tag to the start or end of the ciphertext of the chunks.
As GCM is insecure for large amounts of data, I'd use a separate data key for each file. You can generate one using a key based key derivation function (KBKDF such as HKDF) from the master key and a 256 bit random salt (the salt needs to be included with the ciphertext, of course). Then you can use a zero based 12 byte statically sized counter as nonce.
That will still leave the issue of being able to switch files. That could be avoided by including the file path into the calculation of the keys and saving it in the file, but beware that this will break any file that is renamed. This is a pretty tricky issue that will require domain specific solution. Similarly, changes to files are as tricky to handle. Some kind of separate register / third party may be required.

Note that in principle GCM uses CTR mode and can be made an online capable cipher. Such a cipher directly converts plaintext to ciphertext and vice versa. That way you can have, say, 1 GiB chunks while using a buffer size of 1 MiB or less (or even no application specific buffer at all).
Problem is that many implementations of GCM do away with this property. Some do allow incremental "update" calls, but even then the decryption specifically may not be fully online. An example of this is Java where you have calls to update methods, but since the authentication tag is considered part of the ciphertext the online property during decryption is lost (i.e. it has to buffer as many bytes as the authentication tag, because it cannot distinguish between the two until all the bytes are updated).


Why would someone prove security in the real-ideal model instead of Universal Composibility framework? I am somewhat confused in the reasons why one would use the real-ideal model instead of the universal composibility framework.

The UC framework seems to me, to provide a much stronger definition of security. Is there some explanation to this?

Try to prove something non-trivial using the universal composability framework and you will quickly understand why few people use it.

EDIT: Snide remarks aside, it is pretty widely acknowledge that universal composability is really hard to use in papers. It's even hard to typeset - I've seen proofs with UC functionalities that don't fit on a single page! A colleague of mine has said that proving non-trivial things using UC is like writing a web server in assembly language.

Aside from the practical difficulty of writing proofs with it, there's a more fundamental difference between UC and the real-ideal paradigm: the latter has an intuitive philosophical appeal that comports with the way people think about security. The former doesn't have the same "interpretability" IMO.


randomness of encrypt In the paper "Efficient Encryption from Random Quasi-Cyclic Codes" of Gaborit et al. p.14, I read "Encrypt$(pk=(G,Q,s),\mu,\theta)$: uses randomness $\theta$ to generate $\epsilon \xleftarrow{\\\$}V,r=(r_1,r_2) \xleftarrow{\\\$}V^2$...". Does it mean exactly "uses randomness $\theta$"? Where Can I find a descryption of a PKE in this terms?

For an encryption scheme to satisfy the standard notion of security (IND-CPA), its encryption algorithm must be randomised. Therefore $\textsf{Encrypt}$ has access to random coins, denoted here by $\theta$. It is usually implicit in the syntax of $\textsf{Encrypt}$
$$c\leftarrow\textsf{Encrypt}(pk,m),$$ but it can be made explicit as
$$c=\textsf{Encrypt}(pk,m;\theta).$$
For example, the encryption algorithm in El Gamal (which is IND-CPA secure under the DDH assumption) with public key $pk=(G,g,h,q)$ and message $m\in G$ can be described as
$$(c_1=g^r,c_2=h^r\cdot m)=\mathsf{Encrypt}(pk,m;\theta),$$
where the random coin $\theta$ (interpreted as a string) is used to sample $r\in[1,q-1]$.


Measuring entropy of a uniform distribution source What is entropy? I do not understand it at all.  One article states:

When there is an equal chance for all items to appear, we have a
uniform distribution. In uniform distribution the entropy is high.

I'm confused. If entropy is high, we should consider that disorder is high too, but in a uniform distribution we don't have disorder because all items have the same chance to appear.
Is it possible for someone to explain entropy in cryptography and make this concept clear for me?

In cryptography and information theory, Shannon entropy $H(X)$ is a characteristic of a source $X$ of discrete symbols; e.g. a characteristic of a dice. It's usually expressed per symbol produced, and with unit the bit (per symbol). It tells the expected/average number of bits necessary to encode the value of a symbol, knowing the characteristics of the source. In particular, the entropy of a known¹ deterministic source (such as a Pseudo Random Number Generator with known¹ seed) is $0$.
Assuming the symbols can take values $x_i$, are produced independently at random (that is, earlier outcomes have no influence on later ones), and each symbol $x_i$ has fixed probability $p(x_i)\ge0$ with $1=\sum p(x_i)$, then
$$H(X)=\ \sum_{i\text{ with }p(x_i)\ne0}p_i\,\log_2\frac1{p(x_i)}$$
For example, a fair dice has entropy $H(X)=6\,\left(\frac16\log_26\right)=\log_26\approx2.585\ldots\,$bit/symbol. Another dice, biased towards generating 6 with probability $1/5$, and the 5 other sides having probability $4/25$, has $H(X)=\frac15\log_25\,+5\,\left(\frac4{25}\log_2\frac{25}4\right)\approx2.579\ldots\,$bit/symbol.
This illustrate the fact that for a given number $n$ of symbols, entropy per symbol is maximal at $\log_2 n\,$bit/symbol when all the symbols have the same probability, that is uniform distribution. The article mentioned in the question has it right!
Intuitive justification: when things have a high probability to be in a corner (uneven distribution), there is less disorder/entropy than when they are spread evenly all around. In the later case it takes more information to describe where each thing is.

¹ What happens if we remove known is a matter of perspective. Any PRNG implementable with finite resources has zero entropy, for we can define all it's output with a finite amount of data. On the other hand, for practical adversaries, a Cryptographically Secure PRNG that outputs integers symbols in $[0,n)$ is indistinguishable from a true RNG with entropy of $\log_2 n\,$bit per symbol and the same output domain.