Why is it better to add and double points on an elliptic curve using projective space? I have been given a textbook which defines the addition of two points on an elliptic curve and the doubling of a point on an elliptic curve. This textbook explains elliptic curves in projective space where $z=1$ and it expresses the points on the curve as affine points of the form $[x,y,1]$ but it never really explains why we want to do this.

I have looked over many solutions of which only explain the addition of two points $P$ and $Q$ as the following:

We find the line between the points, find the point of intersection on the curve and finally reflect it over the x axis.

The textbook I have been given says that for adding two points P and Q we use the group operation $P\bigoplus Q=O*(P*Q)$ where $O$ is a "point at infinity" $[0,1,0].$ We first find the slope of the line between the points and then we plug it in to the following equations:

$x^3=m^2-x_1-x_2$

$y^3=-m(x_3-x_1)-y_1$

and the point should be denoted as $[x,y,1]$.

This textbook has confused me beyond belief.

To my understanding, a projective plane essentially is a plane that is parallel to another plane that lies flat on the x,y axis. This plane is perpendicular to the z axis (points satisfy $z=1$), it contains affine points of the original plane and the point at infinity $O$. If one were to construct a 3 dimensional line crossing the origin it would eventually pass through the coordinates $[x_z,y_z,z]$, so the point $(1,2)$ would be found on the projective curve as $[1,2,1]$.

Is there any specific reason why we want to express points of the elliptic curve in projective space? Does it make adding two points or doubling a point easier?How might I explain to someone why I chose to represent it using projective space if they were to ask me why not just use the algorithm shown in the picture?

Is there any specific reason why we want to express points of the elliptic curve in projective space? Does it make adding two points or doubling a point easier?

Because it is a lot more efficient.

If you take a look at the operations involved in performing an elliptic curve operation on a prime curve, they are:

Modular addition and subtraction
Modular multiplication
Modular inversion, that is, given $a$, find $b$ such that $a \cdot b \equiv 1 \pmod p$

It turns out that modular addition and subtraction is fast, modular multiplication is somewhat slower, and modular inverse is dreadfully slow.

And, if we do everything using affine coordinates, it turns out that we need to do a modular inversion for every point addition or doubling.

In contrast, if we do things using projective coordinates, it turns out that we don't need to compute any inverses at all (we do increase the number of modular additions and multiplications we need, however the time involved there is much less than doing a single modular inversion, and so it is a win).

Now, at the end, we'll need to convert back to affine coordinates; that involves a single modular inversion; however when we do a point multiplication, that means that we replaced several hundred modular inversions with just one - a definite win.


Can you explain what the AES paper means by "sharing active S-boxes"? I am reading the "Biclique cryptanalysis of the full AES" paper. What do they mean by "sharing active S-boxes"? How can this concept can be advantageous to make a bicycle? If there is someone who reads this paper, please explain it to me.

We talk about cryptanalytic tools here. A differential trail  describes how a certain difference evolutes throughout the cipher, which helps to find out a key in a standard differential cryptanalysis. Each trail activates certain non-linear operations (S-boxes), which contribute to its probability (a difference goes through a nonlinear operation probabilistically).

The biclique key search method works with a pair of such trails in a small part of the cipher. For the method to work, these trails must activate non-interleaving groups of S-boxes, otherwise more sophisticated conditions come into play.


How to determine secp256r1 or secp256k1 is used on the web sites I'm pretty new at Cryptography (and at Cryptanalysis), but I went to the website Elliptic to try to discover the elliptic curve they use, and I found they use ECDP 256. So, by SEC2 I discovered they do use either secp256r1 or secp256k1. How can I know which one they do use? I do also need to find the base point they are using. Where can I find that? Thanks.

If you look at the all information on the site that provides you can find the answer very fast.

X9.62 ECDSA Signature with SHA-256

X9.62 : Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Standard (ECDSA)"
So, it is the NIST curve and NIST uses the $r$ versions like secp256r1.

A must-read question on our site

Should we trust the NIST-recommended ECC parameters?


Duration for attacking Two-Key Triple-DES Encryption using all RAM ever built? I am considering attacks on Two-Key Triple-DES Encryption assuming $2^{32}$ known plaintext/ciphertext pairs (that's a mere 32GiB of ciphertext) by the method devised by Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption (in proceedings of Eurocrypt 1990), or another published method not requiring significantly more DES computations.
As a synthetic information for decision makers, I am looking for an independent estimate of how much time this is expected to require, assuming all the RAM ever built by mankind to that day (of April 2012) was put to full use.
Note: I'm purposely not asking when the attack could become feasible using all the RAM ever built by mankind, because estimates on the amount of RAM mankind will build, and when, are less falsifiable.
Update: I am not considering cost; neither of RAM, power, logic including DES engines (as long as the number of DES operations remains within $2^{90}$). I am willing to assume that the amount of RAM used, and its effective speed, are the only factors to account for in determining the expected duration of the attack. This is similar to the hypothesis made by the authors of the linked paper, that their attack is limited by the amount (or cost) of RAM used, with all other factors of secondary importance.
Update: sadly, nobody dared answer the question and the bounty period is over. Thus here is a first order answer to criticize.

The original article rightfully neglects the cost of DES computations (there are less than $2^{90}$) and everything except memory accesses to its Table 1 and Table 2. I go one step further: considering that Table 1 is initialized only once and then read-only, it could be in ROM, and I neglect all except the accesses to Table 2. The attack requires an expected $2^{88}$ random writes and as many random reads to Table 2, organized as $2^{25}\cdot 24$-bit words.

The cheap PC that I bought today (of May 2012) came with 4 GByte of DDR3 DRAM, as a single 64-bit-wide DIMM with 16 DRAM chips each $2^{28}\cdot 8$-bit, costing about \$1 per chip in volume. Bigger chips exists: my brand new 32-GByte server uses 64 chips each $2^{29}\cdot 8$-bit, and these are becoming increasingly common (though price per bit is still higher than for the mainstream $2^{28}\cdot 8$-bit chips).

Two mainstream $2^{28}\cdot 8$-bit chips hold one instance of Table 2, and one 124-bit word can be accessed as 8 consecutive 8-bit locations in each of the two chips simultaneously (consecutive accesses are like 15 times faster than random accesses). One $2^{29}\cdot 8$-bit chip would be slightly slower.

Assuming DDR3-1066 with 7-cycles latency (resp. DDR3-1333 with 9-cycles latency), 8 consecutive access require at least $(7\cdot 2+7)/1066\approx 0.020$ µs (resp. $(9\cdot 2+7)/1333\approx 0.019$ µs). This is a decimal order of magnitude less than considered in the original article. For each instance of Table 2, that is 0.5 GByte, we can perform at most $365\cdot 86400\cdot 10^6/0.019/2\approx 2^{49.6}$ read+write accesses per year to Table 2 using mainstream DRAM. Thus with $n$ GByte of mainstream DRAM, and unless I err somewhere, the expected duration is $2^{37.4}/n$ years.

Based on press releases of a serious reference, there are less than $2^{31}$ PCs around, and assuming that my cheap PC is representative, that's $2^{33}$ GByte. Another way to look at that is that each 0.25-GByte chip cost about \$$1$; and the DRAM revenues in 2011 is less than \$$2^{35}$, thus enough for $2^{33}$ GByte (but notice that most of the revenue is from chips that are not optimized for cost per bit). I'll guesstimate all the RAM ever built is equivalent to at most $2^{35}$ GByte of mainstream DRAM for the purpose of the attack.

Thus at the end of the day, my answer is: the attack in the original article, updated to use all the RAM chips ever built by mankind to mid 2012 at the maximum of their potential, has an expected duration of at least 5 years; or equivalently has odds at best 20% to succeed in one year.

Update: as noted by the authors of the original article, "the execution time is not particularly sensitive to the number of plaintext/ciphertext pairs $n$ (provided that $n$ is not too small) because as $n$ increases, the number of
operations required for the attack ($2^{120-\log_2 n}$) decreases, but memory requirements increase, and the number of machines that can be built with a fixed amount of money decreases". By the same argument, our required amount of RAM is not much changed if we get more known plaintext/ciphertext pairs.


Why is factoring $p-1$ easy when $p$ is a safe prime? A paper states:

  [...] $(p,g,y)$ is a correct ElGamal public key if $g^x=y\pmod p$. To verify this the order of $g$, and thus the factorization of $p-1$, is needed. This is easy for safe primes (i.e., primes $p$ for
  which $\frac{p-1}2$ is prime), but may be hard otherwise [...]

Why is it easy to factorize a safe prime's predecessor?

If $p=2q+1$ is a safe prime (that is, $q$ is a prime as well), then $p-1=2q$ has exactly two prime factors: $2$ and $q=(p-1)/2$.


What's the difference between threshold signatures and multisignatures? I was wondering what's the difference between threshold signatures and multisignatures. In what respects do they differ? For example, is n-out-of-n threshold signature, just a multisignature?

Threshold signatures do not enforce accountability meaning a t-out-of-n threshold signature does not tell the verifier which $t$ of the $n$ signers created the signature. Multisignatures enforce accountability as the verifier learns which t signers created the signature. There does not need to be a threshold for multi-signatures.

But n-out-of-n threshold signature should give same properties as an n-multisignature.

As an example, consider BLS signatures. You can have a 3-of-5 threshold signature without learning which 3 signers created it but if you had a multisignature from 3 signers, you need to know which 3 signers created the signature (so you add their public keys). In fact a threshold signature by any 3 signers will have the same value but a multi-signature will have different values depending on which 3 signers were involved. You could create a multi-sig from 2 signers as well.


Usage of 3DES for single block I have a device, HASP, which has functionality to encrypt 8 byte data using 3DES in ECB mode, with three different keys, I am interested how secure is this?
I know it might not be most secure, but how much? Attacker may query HASP to encrypt something, and try to bruteforce keys from this?

Idea is I thought if I need CBC in my application, I will query the HASP as many times as needed and perform chaining of blocks on PC side.

Or is it better to tell HASP producers to implement encryption of single block however in CBC mode?

If double key DES is used then it is not very secure (63-80 bit security). If tree separate DES keys are used then you'd still have about 112 bits of security.

That's still not that much, but it would probably not be commercially viable to retrieve the keys of a sentinel using brute force as hacking the application itself is probably a lot more cost effective.

How secure the mode of operation is depends strongly on how the device is used. I'd strongly advice against using the device for anything other than (software protection and) licensing.

These kind of devices often use deprecated encryption that are just barely able to perform the task they've been designed for. When you are encrypting multiple blocks you may already go outside this framework.

That said, in principle the block cipher protects the key whatever mode is used. You'd still not be able to retrieve the key whichever mode you are using - outside brute force and attacking other locations that contain the key or key derivation information of course.


Yubico's take on U2F key wrapping I've been reading up on Yubico's implementation of U2F. What I understand so far is that two things are calculated. So upon registration first you calculate a private key by

$PrivateKey = HMAC(AppID+nonce,DeviceKey)$

This is then used to simulate the encrypted private key which is sent to the server in the U2F spec:

$KeyHandle = nonce, HMAC(AppID,PrivateKey)$

with "normal" U2F, you send the encrypted private key and a public key to the server. When a user authenticates, he is sent his encrypted private key and a challenge, which is some value encrypted with the public key. If the user can decrypt the challenge by decrypting the private key and decrypting the challenge he has proven he is in fact who he claims to be.

Now this is where it gets fuzzy for me.

The keyhandle is just a nonce and HMAC concatenated, how is this
turned into a private key?
How is the public key  derived as the private key is just a hash in
this case?

The $KeyHandle$ is not the public key, it's a value used to identify the public key that's been registered.  Essentially, it's an identifier of a specific pairing of that device with that server, with its own unique private/public key pair.

From the page you linked to, the $KeyHandle$ is not a sum but both values, the nonce and the MAC of the AppID and the generated private key.  When it's registered, it sends the $KeyHandle$ and public key to the server.

When authenticating, the server sends that $KeyHandle$ back, so the device simply uses the nonce to regenerate the private key, verifies it with the MAC, then uses that to prove it knows the private key corresponding to the public key sent during registration.

The hash is just a large number.   ECDSA is used in UAF. When using modular exponentiation systems, the public key is often of the form $g^x mod$  $N$ where x is the private key, EC is similar in form.


Two parties SPDZ Protocol Input sharing Assume we have two computing parties for SPDZ protocol. The two parties are also the input parties. How can they share the MACs on their input shares assuming one party is the master who owns the MAC key and one is the client who do not have the key ?

The MAC key is not pre-owned by someone but generated in the offline phase. Each party $P_i$ chooses a random value $\Delta_i$ and the sum $\Delta = \sum \Delta_i$ is the MAC key. To ensure $\Delta_i$ is consistently used in all shares, ciphertexts of $\Delta_i$ are exchanged and zero-knowledge proofs are used to prove they are correct.

See for example the protocol in Fig 4 in the Overdrive paper.


Can we prove $(a,b,c,d)$ is of form $(g,g^x,g^y,g^{xy})$ without knowing $\phi (N)$? assume $N=pq$ where $p$ and $q$ are two large prime numbers and all computations are modulo $N$.

given $\phi(N)$, one can prove that the tuple $(a,b,c,d)$ is of the form $(g, g^x,g^y, g^{xy})$, i.e. it is a Diffe-Helman tuple.

Question: Can we prove that the $(a,b,c,d)$ is a Diffe-Helman tuple without knowing $\phi(N)$?

Edit- Application:

Assume someone is given $(g,g^{2^3},g^{2^5}) \bmod N$. He wants to compute $g^{2^{8}}$ and prove that he has done the job correctly, but he does not know $\phi(N)$.

From the paper you linked in the comment:

Each of these $k$ proofs take four rounds and they can all be done in parallel. These proofs are based on a classic zero-knowledge proof that a tuple $( g, A, B, C)$ is a Diffie-Hellman tuple. [13]

That classic proof works as like this (ommitting the moduli, all calculations within the group structure):

The tuple $(g,A,B,C)$ is given
The prover additionally knows $x$, s.t. $B = g^x$ and $C = A^x$. This is the same as a DH tuple, where the prover just knows one of the exponents. If we define $y$ as solution to $B = g^y$, then the tuple has the standard form $(g,g^x,g^y,g^{xy})$.
In the ZK proof, the prover first chooses $r$ randomly, and then sends $(m_1,m_2) = (g^r,A^r)$ to the verifier.
The verifier chooses a bit $b$
The prover sends $r' = r + bx$
The verifier checks if $g^{r'} = m_1 B^b$ and $A^{r'} = m_2C^b$

Can we prove that the $(a,b,c,d)$ is a Diffe-Helman tuple without knowing $ϕ(N)$?

As you can see above, the zero knowledge proof does not require knowing $\phi(N)$, it doesn't require anything else than the normal group operation. So yes, that's possible.

Edit- Application:
Assume someone is given $(g,g^{2^3},g^{2^5})\mod N$. He wants to compute $g^{2^8}$ and prove that he has done the job correctly, but he does not know $ϕ(N)$.

Well, that does not work. Computing $g^{2^8}$ from the given values is an instance of the computational Diffie-Hellman problem. However, if it's possible to calculate that, then the DDH problem can't be hard either. And that means, it doesn't really make sense to create a ZK proof in the first place. If you want to prove that, I think this would contradict the strong RSA assumption.
Ah, as a final note: Knowing $\Phi(N)$ is equivalent to knowing the fatorization of $N$. However, that does not necessarily imply, that this knowledge allows the calculation of DLOGs (unless the modulus is constructed in a special way, e.g. $\phi(N)$ just has small factors). But what is gained is the ability to calculate discrete roots - in RSA the exponentiation by $d$ is just the calculation of the $e$th root.


Diffie hellman: fixed modulus a risk? In DH, are algorithms with fixed modulus p (large safe prime) to be avoided?

What if it was changed every x minutes?

There's a standard argument that NFS finite field discrete log computations can be factored into a precomputation for a particular group ($p$) and then a cheap computation to break each target $g^x$ and recover $x$.*  See, e.g., https://weakdh.org for an application of this in practice to justify scrambling in 2015 to eradicate 512-bit ‘export-grade’—i.e., breakable by the NSA in 1995—DH groups.

The reasoning then goes that if every application uses a different $p$, it eliminates the batch advantage of doing a precomputation in the first place: the bad people in Ft. Meade, MD, would have to repeat the costly precomputation for every application.  However, this precomputation is infeasible to do even once for sufficiently large groups: there's no evidence that humanity has the resources to do it for a well-chosen 2048-bit group in the foreseeable future.

But let's say you wanted to use bespoke DH groups for vanity's sake.  This poses several problems:

It's costly to find them—you can get a sense of how slow it is in the privacy of your own living room with the openssl dhparam command.
The parties in an application have to agree on a DH group, and validating the group according to standard security criteria is costly—and has been a source of vulnerabilities in practice.  Sometimes bogus DH parameters get hard-coded in software in the wild.
We have known since 1993 of theoretical ways to put back doors in DH groups, and more recently that they might even be practical for reasonable group sizes like 2048 bits (summary).

Just use the smaller-faster-safer-simpler X25519 and forget about finite-field Diffie–Hellman groups, or if you must use FFDH, use the RFC 3526 groups chosen semi-rigidly by the RFC 2412 process.

* This is the case for multiplicative groups of integers modulo a large prime $p$—that is, finite-field discrete logs in prime fields.  The story for binary fields is much worse, so nobody uses binary fields for this.  In contrast, no such precomputation is known for elliptic curve discrete log computations—there's factor of $\sqrt{n}$ cost advantage to attacking a batch of $n$ targets simultaneously over attacking each of them individually, but it doesn't break down into a target-independent precomputation followed by a low per-target costs.


Is it acceptable to write the nonce to the encrypted file during AES-256 GCM? I've used AES-128 in CTR mode in the past and using the same key but different IVs for each file, I wrote the IV to the first 16 bytes. Is it safe to do so with the nonces used in AES-256 GCM? I'm using the word nonce here because that's what is declared in the Sodium library.

Are the uses for IVs and nonces exactly the same?

Also, is there any use in providing additional authenticated data? Should I keep it NULL?

The IV of encryption schemes can be made public without damaging the security of the encryption, so there shouldn't be any issues with prepending it to the encrypted file.

The difference between IVs and Nonces was already explained by @SEJPM in the comments. Note that in the case of GCM, you do need to make sure that you do not re-use the IV with the same encryption key, as AES-GCM works (I'm simplifying here) by using the IV as a counter and encrypting successive counter values to generate a key stream, which is then XOR'd onto the plaintext to encrypt it (like the regular CTR-Mode). This means that if you re-use the IV and key, you will generate the same keystream again and allow more efficient attacks on the encryption (think key-reuse for one-time-pads, with the added bonus that you can also create forged messages that will pass the authenticity check of GCM, as @SEJPM points out in the comments).

You only need to add Additional Authenticated Data (AAD) if you have additional data you want to verify. An example would be to add the filename of the encrypted file as AAD if you want to be sure that the file cannot be renamed and still be decrypted. But this is highly situational, and you definitely don't need to use it.


Quadratic Sieve: what's the next step after it fails? Factoring some 20-45 digit values n with a (simple) quadratic sieve, the quadratic sieve may end up with pairs of x and y s.t. $x^2 \equiv y^2 \pmod n$, but neither x+y nor x-y has a nontrivial gcd with n for any of the pairs.
The contini pdf (www.crypto-world.com/documents/contini_siqs.pdf) is an excellent resource for this and related questions.

To factor these numbers, I've been trying a couple of things:

2) Add more tb-smooth squares' factorizations to the matrix in order to increase the dimension of the nullspace.

What is the best way to handle this?

explanation:
For every Linearly Independent vector in the matrix's nullspace, there's a ½ chance of finding a good pair.  If the nullspace has dimension around 10, that's a very high chance of success.

Update: Post above heavily edited to make it informative.  Having too few vectors could potentially happen (e.g. if fewer than recommended smooth squares are found), but the problem I was having came from my own error.

In the QS algorithm, every linear combination adding up to a zero vector modulo $2$ has a chance of $1/2$ to give you a nontrivial factor.

Your suggestion 2) is the way to go, because adding additional numbers provides you with a lot more different linear combinations to get that zero-vector ($\phi(b)+1$ is just the minimal number required to find at least one set of linear dependent vectors).


Is there a symmetric-key algorithm which we can use for creating a signature? I know that in the asymmetric-key algorithm the RSA signature exists but what about the symmetrical ones?

Symmetric analogue of signatures.
The symmetric analogue of a signature is variously called a message authentication code, MAC, or authenticator.  The same key is used to create and verify authentication tags on messages.

Consequently, unlike signatures, third parties can't meaningfully verify MACs: if Alice sends a message with a MAC to Bob, Bob can't use the MAC to persuade Charlie that Alice sent the message because Bob could have created the MAC too.

Typical examples include HMAC-SHA256, keyed BLAKE2, KMAC128, AES-GMAC (which requires a distinct nonce for each message), and Poly1305 (which alone can be used only for one message per key).  Authenticators are often combined with ciphers to make authenticated ciphers like crypto_secretbox_xsalsa20poly1305 or AES-GCM, which simultaneously prevent eavesdropping and forgery.

Signatures built out of hashes.
You can also make a public-key signature scheme out of a collision-resistant hash function $H$, like SHA-256.

In the traditional one-time signature scheme of Lamport, you randomly generate a collection of 512 bit strings $x_{0,0}, x_{0,1}, \dots, x_{0,255}; x_{1,0}, x_{1,1}, \dots, x_{1,255}$, and publish $y_{b,i} = H(x_{b,i})$ as your public key.  To sign the message $m$, let $b_i$ be the $i^{\mathit{th}}$ bit of $H(m)$; the signature is $x_{b_0,0}, x_{b_1,1}, \dots, x_{b_{255},255}$—that is, you reveal $x_{0,i}$ if the $i^{\mathit{th}}$ bit of $H(m)$ was zero, and $x_{1,i}$ if the $i^{\mathit{th}}$ bit was one.  Anyone can verify this using your public key by checking whether $y_{b_i,i} = H(x_{b_i,i})$, but only you knew the preimages $x_{b_i,i}$ in advance.

Modern variants like SPHINCS extend this idea to many messages, and eliminate the need for collision resistance of $H$ in order to go faster.

There's no symmetric keys here but sometimes hashes are considered to fall into symmetric-key cryptography, since, e.g., the function $k \mapsto \operatorname{AES}_k(0)$ is supposed to be an irreversible hash.


Using error-correcting codes for the bootstrapping procedure of Fully Homomorphic Schemes In the context of Fully Homomorphic Schemes, we use a technique called "bootstrapping" to refresh the ciphertext, by evaluating homomorphically the decryption circuit with an encrypted version of the private key.

I was wondering if it was possible to consider this approach, of reducing the error size, by using an error-control code instead (eventually designed for our FHE scheme).

I am not concerned about the efficiency of such a scheme right now, but would it be feasible to design a scheme such that we can apply an "error-reducing code" reducing errors instead of correcting all of them. I don't think there have been researches to this idea so far so it is maybe completely unthinkable but I wanted to discuss it with other people..

I think not, because the two types of error correction are doing fundamentally different things.

Conventional error correction schemes, for instance Reed-Solomon codes, expect the value to be near some codeword.  To correct an erroneous value, they change it to the nearest codeword.  You can picture it as a space where some points in the space correspond to correct values, and each of those points is encircled by a region of incorrect values that belong to that point.  The assumption of error correction is that value started at a correct point and drifted a little, but stayed in the point's own region.

With LWE, you are mixing the correct value with a ton of error, and secretly you know some way to unmix it later (bootstrapping).  You can't use less error and still have security.  In terms of the point analogy above, the incorrect values have to be all over the space.  They can't stay close to their correct value in any obvious way.  Otherwise anybody could see what the correct value is - it's the nearest correct point.  I doubt that you can use any conventional error correction without having obvious regions of some kind.

Error correction doesn't do much for the bootstrapping either, I think, because once you unmix the value, you can just throw away the error part.


Definition of diffusion matrix I've been studying this article and since I'm not studying cryptography in English and it is not my native language, I don't understand some of the terminology. More precisely: what are diffusion matrices as mentioned on page 3 right at the beginning of chapter 2? Do they have something to do with diffusion defined in Shannon's theory?

Yes, it is related. Claude Shannon in his famous article A Mathematical Theory of Cryptography defines the Confusion and Diffusion. Wikipedia's Confusion and diffusion page  defines diffusion as;

  Diffusion means that if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if we change one bit of the ciphertext, then approximately one half of the plaintext bits should change. Since a bit can have only two states, when they are all re-evaluated and changed from one seemingly random position to another, half of the bits will have changed state.

A diffusion matrix transforms columns and it similar to the MixColumns  operation of AES. It is optionally followed by a ShiftRows (like in AES) to provide further mixing where ShiftRows permutes the rows*.

If there is no diffusion matrix applied to AES ( or similar SPN based block cipher, and also no ShiftRows), then only a single bit change in the input will only affect the corresponding byte. Therefore, diffusion is necessary but not sufficient.

* FOAM: Searching for Hardware-Optimal SPN Structures and
Components with a Fair Comparison


Where are the ChaCha20 test vectors/examples? I see in the Salsa20 specification there are test examples throughout the document to help an implementer make sure every function works as designed. Consequently the whole algorithm would work perfectly if all the tests pass. Without these test vectors it would be very difficult to know whether the code was working as designed or was giving incorrect outputs. Test-driven development should be the gold standard for developing a cryptographic library.

So it came as a surprise to me when reading the improved ChaCha20 specification that there are no test examples to validate against. I have even had a look on the ChaCha web page but found nothing.

Even though ChaCha20 has better diffusion and is supposedly more secure, I would consider myself actually safer using the Salsa20 algorithm as I have reference test vectors for the code/library to validate against and I would know for sure that it was implemented correctly. Using ChaCha20 would be a risky move in comparison. How do all the other implementers of ChaCha20 e.g. OpenSSH know their implementation is correct? How are other people able to trust that their implementation is correct?

I would like to know where the ChaCha20 test examples are which show the correct outputs from the ChaCha quarter-round and ChaCha matrix? Why aren't they in the specification document?


Questions about hash functions Let $H$ be a secure hash function (e.g. SHA256), is it possibile to find $H(M1)$ given $H(M1||M2)$ if the length of $M1$ and/or $M2$ is exact the block size of the hash (that is, 64 bytes for SHA family hashes)?

I think this is formalized as non mallability of hash functions. However, you do not find it as a requirement e.g. in the SHA-3 competition and I think that practical hash functions are not analyzed in this direction. For non-mallability you might want to take a look at
http://eprint.iacr.org/2009/065


where does the prime number taken in DH algorithm in IPSEC I am studying & configuring IPSEC ikev1 and in between i am analysing the wireshark captures. I am using the linux kernel for TCP/IP stack and user-space i took ipsec-tools.

In the first two packet exchanges initiator is offering the proposals & responder will respond to the supported proposal.

Next two packet exchanges(packet 3[initiator] & 4[responder]) will perform DH key exchange.Here how the responder will came to know that which prime number the initiator uses & how it will be exchanged.

It's in the SA payload of the initial packets.

It's attribute type 4 within the SA payload; in Main Mode of IKE (which is what you're looking at) the initiator will propose a list of groups, and the responder will pick one and send it back its selection in packet 2.

Now, what they exchange is a short integer value; both sides are expected to know the translation between the short values (current standard values are between 1 and 30) and the actual DH (or ECDH) group.  See this page for pointers to the definitions of the current standard groups.


Does this block cipher mode allow for decryption? Is there's a way for someone (with the key) to decrypt a message encrypted with the cipher mode shown?

$$ P_0 = IV $$
$$ C_i = P_{i-1} \oplus E_K(P_i) \oplus P_i $$

Ok, I will assume that:

The block you have labeled as "Encryption" is some sort of block cipher
You run this mode to transform the IV and the plaintext into a ciphertext
You are asking whether someone with the IV, the ciphertext and the block cipher key can recover the original plaintext.

Well, the quick answer is that they can't.  This is true in two senses:

It is difficult to find a message that would encrypt to the given ciphertext.  To recover (say) the first plaintext block, they would need to find a $P_1$ that solves the equation:

$C_1 \oplus IV = E_K( P_1 ) \oplus P_1$

However, for conventional block ciphers, there's no easy way to solve for such a $P_1$.  Now, if the receiver knew the last plaintext block, he could decrypt all the rest.  However, that isn't a standard assumption.
There might be multiple plaintext messages that encrypt into the same value.  This is because, while $E_K( P_i )$ is a bijection (this is a standard assumption of block ciphers), there's no reason to suppose that $E_K( P_i ) \oplus P_i $ is (and, in fact, with high probability, it isn't).

To give a simple example of this last point, why don't see assume that we have a 1 byte block cipher with:

$E_k( 0x00 ) = 0x71$

$E_k( 0x17 ) = 0x66$

Then, if $IV = 0x19$, then:

The encryption of the single byte message $0x00$ will be the single byte $0x19 \oplus E_k( 0x00 ) \oplus 0x00 = 0x19 \oplus 0x71 \oplus 0x00 = 0x68$

The encryption of the single byte message $0x17$ will be the single byte $0x19 \oplus E_k( 0x17 ) \oplus 0x17 = 0x19 \oplus 0x66 \oplus 0x17 = 0x68$

Hence, in this case, if we get an encrypted message $0x68$, we have no idea if the original plaintext was $0x00$ or $0x17$


Review of AES encryption concept for an open source project i'm working on an opensource project, A generator for static (html/js), password protected photo galleries. The generator AES 256 encrypts many images with the same key in PyCrypto, and decrypt them with CryptoJS. That's what my prototype does so far:

General

AES 256 mode=CBC, padding=Pkcs7
Encrypt many images with the same salted password
an unique iv for every image
store the unencrypted salt and the unencrypted iv with every encrypted image
store the plain sha1 of the unencrypted image with the encrypted image

Password

salt = 16 random bytes from Random()
aes_key = PBKDF2(dkLen=32, count=1000, salt=salt) of the user selected password
The user can select the password. ATM the only requirement is: min 8 chars.

IV

iv = 16 random bytes from Random()

Do you think this procedure is ok for my use case?
If so, can someone review my python code to encrypt the images? (I'll provide the code on github if general procedure  is ok)

Thank you very much for help and have a nice day,
Boerni

You're pretty much on the right track, I've got a few comments/suggestions though:

  store the plain sha1 of the unencrypted image with the encrypted image

I'm assuming the sha1 hash is to ensure the integrity of the data being encrypted?  If that's the case, you should have a read through this answer.

Assuming you're limited to non-authenticated modes (I don't see GCM, EAX or otherwise) as options in CryptoJS, then you'd probably do best to encrypt-then-MAC:

InitialKey = PBKDF2(dkLen=32, count=100000, salt=salt, password=password) — where dkLen is the native block size of the underlying hash algorithm, in this case, sha256 = 32 bytes.  Note: 1000 rounds of PBKDF2 is considered weak in 2013, if you must use PBKDF2 (as opposed to something stronger like Scrypt), then aim for as many rounds as is tolerable by the user
SecondaryKey = PBKDF2(dkLen=64, count=1, salt=salt, password=InitialKey) — Note; just one round here.  If you're wondering about this two-step PBKDF2 process, check out this excellent answer by D.W.
AES_key = SecondaryKey:0-32
HMAC_key = SecondaryKey:32-64
HMAC = HMAC_SHA256((cipherText || iv || salt), HMAC_key) — where || denotes concatenation
cipherText = cipherText || HMAC

I'd be inclined to use CTR mode (and no padding) instead of CBC, but that's just a preference - CBC is perfectly fine.  Also, as @owlstead pointed out, you need to consider the implications of a user updating their password, and having to decrypt/re-encrypt all of their images, but that's beyond the scope of my answer.


find $x$, given $\{c_ix = k_i + y_i\}_{i=[1,n]} $ Given

$$c_1x = k_1 + y_1 $$
$$c_2x = k_2 + y_2 $$
$$\vdots $$
$$c_nx = k_n + y_n $$

where the values of $\{c_1 \ldots c_n \}$ and $\{ k_1 \ldots k_n \}$ are known, and $x, \{y_1 \ldots y_n \}$ are unknown. $y_i$ is chosen uniformly at random.

We are working in a field of $GF(p)$, so all $c_i, k_i, x, y_i ∈ \mathbb{Z}_p^*$. $p$ is some prime.

From here, how can we recover the value of $x$ ?

(suppose $c_i = c_j$ OR  $\ k_i = k_j$ for some $i,j$ that we know )

There is no way to recover $x$ in this scenario; there is not even a way to say "this value of $x$ is more likely than that value"

One demonstration is that if we attempt to test a particular value $x'$; we can compute the necessary values:

$$y_i = c_i x - k_i$$

However, if all the values $y_i$ are randomly distributed, and given that we have no further restriction of what the values $y_i$ might be, this distribution is no less probable than any other distribution; hence these relations give us no information about $x$.

Since those relations are the only thing we know about $x$, that means we have no criteria to say which values are more or less probable.

This holds true for any sets of values $c_i, k_i$, and specifically if we have $c_i = c_j$ or $k_i = k_j$.


one-way deterministic hash for low entropy input? My problem is the following:
we have a low entropy data called ID. (personal id number of 10 decimal digits plus a sum, and it contains a date)
We want to create a data (H) which is the same for the same id, but id can neither be computed nor brute-forced by trying all combinations.
It should be proven that even we are not able to reconstruct ID from H using neither computation nor brute force

My solution: use
k:= an RSA1024 key residing in a slow hardware token, unextractable
the reason is to improve entropy

H:=SHA512SUM(RSA(k,SHA512SUM(ID)))
We limit third parties to 1 operation per minute.

Please comment on whether this solution is sound enough, or are there better solution for the problem.
What measures can we use to express the soundness of the solution?

I don't think this problem is solvable as specified.

With a small message space, and deterministic hashing (or encryption), a generic attack involves exhaustively searching all likely messages to find one that corresponds to the known hash / ciphertext.

If all of the digits of the ID numbers were random, an exhaustive search would require about $10^{10} \approx 2^{33}$ iterations, and it might be feasible to use key stretching and/or rate-limited hardware to slow down the hashing enough to make such a search unfeasible.

Unfortunately, you say that some of the digits encode a date.  If these ID numbers are anything like the local government IDs around here, I'm assuming something like 6 digits encoding a birthdate (in DDMMYY format, or similar) plus a four-digit sequence number.  This reduces the necessary search space significantly:

Just the date format reduces the search space a lot: since there are only 356 valid dates in a year (or 366 for leap years), the actual number of valid IDs is only about $10^{8.4} \approx 2^{28}$.
If an attacker is targeting a specific person, they'll likely know the target's age to at least within a decade or so.  This cuts the search space further down by a factor of (at least) 10.
In the worst case, the attacker already knows the target's age and birth date, and only needs to determine the last four digits of the ID.  Thus, they only need to search $10^4 \approx 2^{13}$ ID numbers!
To make things even worse, the last four digits might not be random either.  If they're instead assigned sequentially, lower numbers will be much more common, and so a sequential exhaustive search is likely to find the correct ID much sooner than one would expect if they were randomized.

Basically, in the worst-case scenario described above (which, really, isn't that far-fetched at all), no amount of key stretching will help: if your organization wants to be able to legitimately process more than one ID per minute, then a determined attacker with access to the same resources (which is a reasonable assumption, if internal attacks are a concern) and knowledge of the date part of the ID will be able to de-hash the ID in less than one week (= 10,080 minutes).  If you need to be able to process one ID per second, the attacker only needs up to three hours.  That holds regardless of the hashing or encryption method you're using, or the tools you use to implement it.


Change in probability of collision when removing digits from MD5 hexadecimal hash values I am aware that MD5 has a known collision vulnerability and should not be relied upon when uniqueness is required, but in the environment I am working on I only have access to MD5 hash function. Background detail below, but in general how much and how bad is the change in the probability of hash collision if I removed a few digits from the hexadecimal representation of MD5 hash values?

Background: I am working on migrating data between two systems. The target system has a built-in database column of length 30 characters that has unique/primary key resolution mechanism, meaning as long as I put a matching value in that column the system will map it to existing record if exists and create new record otherwise. Unfortunately the primary key from source system has length of between 50 to 100 characters so my best bet is to generate a shorter hash value from it. I only have access to MD5 hash function but the hexadecimal hash value is 32 digits long so I have to drop two of the digits. There is virtually zero probability of anyone wanting to use collision attack on the data so my concern is pretty much on the distant possibility of Heaven-assisted coincidence that two primary keys might generate the same hash value.

N.B. Possibly related to "Should I use the first or last bits from a SHA-256 hash?", but that question is about SHA-256 while this one is about MD5.

First things first: there is nothing magical in hexadecimal. The output of MD5 is, nominally, a sequence of 128 bits, or, if you prefer, 16 bytes (each being able to get any value between 0 and 255). Hexadecimal is just a trick to represent a single byte as two characters in a limited range (digits, and letters from 'a' to 'f'). If you can have 30 characters then you can probably use more than the hexadecimal digits. For instance, with Base64 encoding, you can unambiguously represent any MD5 output (16 bytes) into 24 characters chosen in a list consisting of digits, uppercase letters, lowercase letters, '+', '/' and '=' (the '=' sign appears only at the end, and your 24 characters will always end with a pair of '=' signs, which you can altogether omit; hence, make that 22 characters).

To answer your initial question, assuming that MD5 behaves "randomly" (which is kind of true as long as nobody is actively trying to produce collisions), then keeping $n$ hexadecimal characters means keeping $4n$ MD5 output bits, and collisions are expected to appear around $2^{2n}$ keys. With $n = 30$, that's $2^{60}$, also known as "approximately a billion billions", which is still kind of huge. Still, you'd better use a shorter encoding such as Base64, which avoids the issue altogether.


MICKEY 2.0: Mutual irregular clocking, register states I'm trying to understand how MICKEY 2.0 works in detail.

In [1], page 6, it says:

  ... the state of the generator does not repeat within the generation of a single keystream sequence ...

What consequences does this have? As the internal state generates the output, I think that two identical inputs within the same keystream sequence therefore have different outputs. Or are there any other reasons for this?

Further, on page 6 it says:

  The influence of R on the clocking of S also prevents S from
  becoming stuck in a short cycle

As I read, a short cycle in this context is a sequence of continuously recurring states. Because the state of S depends on the output of R (whose states do not repeat), also the state of S does not repeat within the generation of a single keystream sequence. Is that right?

What exactly is meant by the mutual irregular clocking? I think that this refers to the dependence between register R and register S (see Fig. 3, page 6). The output of each of them depends on the state of the other one. As they are not clocking in regular time intervals, the term irregular clocking is used.

[1] http://www.ecrypt.eu.org/stream/p3ciphers/mickey/mickey_p3.pdf

In any keystream generator, if the state repeats, so does the keystream; which, under some standards assumptions, can be detected, and leads to a serious break (e.g. if the beginning of the plaintext is known for length a little above $k+\log_2k$ bits, where $k$ is the period of the keystream, then the period $k$ and the rest of the plaintext can be found). A necessary condition for security is thus that odds of the state repeating are negligibly low. This is insured (odds are zero) if the quoted property holds:

  ... the state of the generator does not repeat within the generation of a single keystream sequence ...

and that's why that property is desirable: it insures there is no class of weak keys leading to attack.

I'm not seeing assertion in the article, or simple proof, that “the state of S does not repeat within the generation of a single keystream sequence”. Rather, I see the reasonable assertion, without formal proof, that starting from a generator S based on iterating a lossless function, and using another unrelated generator R as an excitation to S by a combination with XOR keeping the iterated function lossless, it seems unlikely that the resulting generator S' ends up having a period shorter than R (that could occur only for a limited number of R having some sort of tight relation to S; perhaps that's even demonstrable). Rather, it is expected (in the absence of feedback of S to R, and if the function used in S is random enough) that S' has period a large multiple of the period of R, with the large factor commensurate to the square root of the number of possible states for S.


Using a mono-alphabetic substitution cipher with a different language per word How much harder is it to determine the secret key for a mono-alphabetic substitution cipher, if each word is translated into a different language before the cipher is applied?

If somehow computers could create their own language or set of languages such that there is a one-to-one correspondence between words and they are optimized such that the significant information obtained from the multi-language frequency table is minimized, would it result in something better?

This is a lossy algorithm. You will lose information during the translation and reverse-translation steps. Introducing loss into any algorithm obviously increases the difficulty in pulling the clean plaintext out, since it's potentially impossible to pull the clean plaintext out even with the key.

Even so, fairly normal cryptanalysis should apply here. You just need to use a multi-language frequency table. I assume that all languages involved will use a single alphabet? You would drop accents from languages that have them? This is no different than the common step of merging "I" and "J" in ciphers. If you rely on Romance languages, cognates would hurt you. If you go beyond Romance languages, then you're faced again with possibly lossy transliteration, particularly if you mix in Asian or Middle Eastern languages.

This is not dramatically different than the common technique of intentional misspellings. Take a look at Kryptos for a very advanced example that involves the kind of complications you have in mind.

I'd say that your idea makes analysis harder, but not fundamentally different.

When you make this a non-lossy translation, you're describing a homophonic cipher. A book cipher is an example. The idea is that you have different symbols representing the same letter or word. In your case, you're replacing the symbol "road" with either the symbol "rue" or the symbol "camino" or the symbol "lu" for example. You are then applying an alphabetic cipher to the result. This has been used for a several hundred years to prevent frequency analysis. Look at the Great Cipher for a sophisticated version of this approach. Note that as you've describe it, I strongly doubt you'd be able to devise a group of languages that resisted frequency analysis. You'd eventually have to start creating more random symbols (words) until this looked very unlike the original design in my estimation.


is it safe to leak some information about scrypt result? I am encrypting a file via AES-CBC and am using scrypt to extract a key from a user-provided password. The IV is public and is stored with the encrypted file.

Is it safe to generate my IV (public) and key (private) together using scrypt (e.g. set dklen=64 then use scrypt[0...31] for key and scrypt[32...63] for IV), or will I be leaking some kind of state information?

That should be fine, as long as you never reuse it for any other purpose.  (E.g., if you want to encrypt another file with the same password, generate a fresh salt.)

But there's a simpler approach: Use AES256-CTR with nonce 0 and forget about AES256-CBC altogether.  No more worry about unaligned message lengths or padding, how to choose initialization vectors, etc.

I encourage you to consider authentication too.  For example, instead of the unauthenticated AES256-CBC, you could use AES256-GCM, or AES256-CTR with HMAC-SHA256 in encrypt-then-MAC composition.  In fact, maybe you would be better off just using the scrypt(1) utility, which has a simple format.


Is it possible to generate backdoored DH parameters? I know it has been already asked and answered whether it's possible to generate weak DH parameters.

But "recentely" we experienced the Logjam attack, which makes use of the pre-computation capabilities of the GNFS to quickly break many discrete logarithm problem (DLP) instances.

Now I know that the main workload of the GNFS is to do the pre-computation for the given group (more than 99% of the required workload).

Now I've asked myself:
Is it possible to generate DH parameters that allow for speeding up the GNFS pre-computation given some (secret) knowledge?

A trapdoor in a discrete log group was first suggested in 1992 by Daniel M. Gordon[1] in response to the recently proposal by NIST for the Digital Signature Standard (among hundreds of other responses[2] including an objection to the now-infamous random generation of the per-signature secret).  Though the computational cost was too high for an academic researcher to demonstrate it at the time, Gordon did suggest alleviating the concerns by using what we would today call a semi-rigid procedure for choosing the primes.

Fast-forward to 2016, when Fried, Gaudry, Heninger, and Thomé dusted off Gordon's algorithm and applied it in practice[3] to spend:

12 core-hours choose a 1024-bit DSA prime $p$, with a 160-bit prime factor $q$ of $p - 1$, with an SNFS polynomial $f$ admitting…
a few hundred core years (spread across a few thousand cores for a couple of months on an academic cluster) of precomputation in order to enable…
a handful of core-days to compute each discrete log.

The paper [3] is worth reading for more technical details and historical background.  There are some caveats:

The experiment produced a group for DSA, a Schnorr group with a 160-bit prime subgroup, not a safe prime for DH to avoid Lim–Lee active small-subgroup attacks[4] which are not relevant in signature applications.  It's not immediately clear to me whether the technique would work to find a safe prime with a trapdoor: if nothing else, the arithmetic modulo a (say) 2047-bit $q$ would cost a dozen times what the arithmetic modulo a 160-bit $q$.

Counterpoint:  But there have been Schnorr groups inexplicably documented for use with DH, in RFC 5114.  The paper [3] reports systems in the wild using primes with an obvious SNFS polynomial, like $2^{1024} - 1093337$.  For years socat used a composite modulus[5].  And maybe a more careful reading of the costs than I have done would show that searching for a safe prime is not all that much costlier than a Schnorr group as demonstrated.
Obviously, a 1024-bit modulus is too small by today's standards: it has been considered plausible for some years now that well-funded governments or corporations could mount a GNFS discrete log computation in a group with a 1024-bit modulus.

Counterpoint: But it shouldn't be within the reach of an academic cluster!  If the trapdoor for this 1024-bit modulus is within the reach of an academic cluster today, is a trapdoor for a 2048-bit modulus within the reach of a major government or corporation?

So, while it is likely outside your budget to generate a 2048-bit safe prime with a hidden SNFS back door in the privacy of your own living room, you should definitely raise a lot of eyebrows at anyone suggesting to use DH primes other than the semi-rigid RFC 3526 ones.

Or just use elliptic curve DH, particularly X25519.


How is a generator found for a group, both in case of DH & ECDH? First step in DH & ECDH is to choose a random prime $p$. Then you choose a generator $g$ for the group $\mathbb Z_p^*$. How do you find a generator? Likewise in ECDH, you would need to find a generator which generates all the points in the elliptic curve? How is this done?

In the case of Diffie-Hellman Key Exchange (DHKE or DH) in the multiplicative group $\mathbb Z_p^*$, the recommendable practice is to pick a prime $p$ and generator $g$ from RFC 3526, which gives these parameters for bit size $k$ of $p$ in $\{1536,2048,3072,4096,6144,8192\}$. These $(p,g)$ obey the criterion below:

$p$ is a prime such that $q=(p-1)/2$ is prime, that is $p$ a safe prime. Since the order of an element $g$ of the group is a divisor of $p-1$, that order can only be $1$, $2$, $q$, or $2\,q$, which simplifies finding¹/checking the order of a candidate $g$:

If $g\bmod p=1$, then the order of $g$ is $1$.
If $g\bmod p=p-1$, then the order of $g$ is $2$.
If $g^q\bmod p=1$, then the order of $g$ is $q$, half the group order. Such $g$ are used in RFC 3526.
Otherwise (that is if $g^q\bmod p=p-1$ ), the order of $g$ is $2\,q$, that is $g$ is a generator of the whole group. There is no good reason to prefer such $g$, and they have the drawback that given $a=g^x\bmod p$, it's trivial to tell if $x$ is even or odd by checking if $a^q\bmod p$ is $1$ or not.

It is picked $g=2$, because

It's proven that any choice of $g$ of a given order does not make the discrete logarithm problem much easier.
That's the smallest positive $g$ usable, thus the natural choice.
It allows a sizable speedup in the modular exponentiation: most of the modular multiplications in square-and-multiply binary exponentiation can be avoided.

The low-order 64 bits of $p$ are set. This can be used to simplify Montgomery modular multiplication. Combined with (1) and $p>7$, that implies $p\bmod24=23$, and the order of $g=2$ is $q$. Notably, that goes against a check in OpenSSL.

The high-order 66 bits of $p$ are set, making $p$ near a power of two. This can be used to simplify modular reduction modulo $p$, by making it easy to find a most likely correct new digit/limb for the quotient in Euclidean division in base $2^b$ for $b\le32$ (and somewhat higher).

The next high-order bit of $p$ is clear, making $p$ not so close to a power of two that the Special Number Field Sieve applies.

The other bits make $p$ a nothing-up-my-sleeves number: for a $k$-bit modulus, it is used $p=2^k-2^{k-64}-1+2^{64}\,\left\lfloor2^{k-130}\pi+i\right\rfloor$ with the smallest $i$ such that $p\bmod3=2$ [which for a given $k$ determines $i\bmod 3$ ], $p$ is prime, $q=(p-1)/2$ is prime, and $2^q\bmod p=1$.

Of course, $k$ is chosen as a compromise between speed and security of DH. $k=2048$ is considered a minimum today. Message size grows as $k$. Execution time grows as $k^3$ in naive implementations of DH using textbook multiplication and secrets the size of $p$. While performance can be considerably improved by using better multiplication algorithms, and smaller secrets, DH in $\mathbb Z_p$ with secure-enough parameters is outperformed by a competent implementation of ECDH, see next section.
Note: An alternative practice, with no direct benefic in DH but common in signature because it allows a drastic reduction in signature size, is to use $(p,g)$ making the powers of $g$ modulo $p$ a Schnorr Group of order a prime $q$ of size much smaller than $p$, yet enough for security. We first choose prime $q$ with about twice as many bits as the desired security level, and $p=2\,q\,r+1$ for (even) $r$ making $p$ a prime of suitable size (e.g. 256-bit $q$, 3072-bit $p$). We pick some $h$ (e.g. $h=2$), compute $g\gets h^r\bmod p$, and check that does not happen to be $1$.

In the case of ECDH, that is DH in the group of points of an Elliptic Curve over some finite field $\mathbb F_{p^d}$ for prime $p$, the recommendable practice is to pick a standard curve and generator from some reference. A common one is SEC2, which includes the NIST curves of FIPS 186-4. Another is Curve25519. Yet another is RFC 5639, which gives the Brainpool curves.
Restricting to $d=1$ (that is curves on $\mathbb F_p$ for some large prime $p$, though not as large as needed for security of DH in the group $\mathbb Z_p^*$ ), practice is to use curves of prime order $q$, such that any point except the neutral $\infty$ has order $q$. It's proven that the choice of generator (aka base point) does not make the discrete logarithm problem much easier. How the generator is actually chosen varies. Sometime it's secret, lost, rediscovered, see this.
When we can't or didn't chose the curve to be of prime order, practice it to use a curve of known order of the form $h\,q$ where $q$ is prime and $h$ is as small as possible. This makes it easy to check the order of a point, and ascertain it's a multiple of $q$ (or exactly $q$, which is typical).
How a curve's order is found (aka point counting) is quite involved. That's one good reason why we have standard curves.

¹ A general method to find the order $i$ of an arbitrary $g$ in $\mathbb Z_p^*$ with $p$ prime is to test $i$ in increasing order among the divisors of $p-1$ (the order of such $\mathbb Z_p^*$ ), and stop at the first $i$ with $g^i\bmod p=1$. This generalizes to any group, and is applicable when we know the factorization of the group order.


Computational Complexity of SHA-3 (SHAKE128) Please, I got the question "what is the computational complexity of SHA-3 (SHAKE128)"?

What does that mean and how can I calculate that??

*I am using SHA-3 (SHAKE128) in my mechanism to hash fix input (100-bits).

Thanks in advance...

Strictly speaking, computational complexity is certainly not the right term. It is an asymptotic notion, describing the approximate behaviour of the cost for "large enough" inputs. SHAKE is an "extensible output function" (XOF) and its computational complexity is $O(m + n)$ where $m$ is the size of the input, and $n$ the size of the output. I.e., it's "linear". However, this does not apply to your case, where the input size is fixed (100 bits) and I suspect that your output size is also fixed. The "complexity" is when the input size "tends towards infinity", and 100 will never go toward infinity; it's fixed.

Therefore, we have to assume that reviewer of that journal uses the expression "computational complexity" in a loose, technically incorrect sense, to express the notion of "cost". In simple words: if somebody implemented your proposed protocol on some specific hardware (e.g. a PC), and ran it, to what extent would your specific choice of SHAKE would impact overall performance metrics of the system?

To take an example: consider SSL/TLS. That protocol starts with a complicated process call the "handshake", through which a client and server agree on a common shared secret, used thereafter to encrypt data. The bulk of the cost is in the data encryption, which does not use a hash function (if a proper ciphersuite was negotiated). Hash functions are involved in the handshake, but in conjunction with asymmetric cryptographic stuff which is, in practice, a lot more expensive. In the TLS protocol, you can therefore say that the choice of the hash function in the handshake has negligible impact on the performance metrics of bandwidth, CPU usage and latency, as long as you do not use a stupidly slow hash function. On the other hand, for embedded system with strong constraints on, for instance, ROM size, the choice of hash function matters because if you already have an implementation of a hash function somewhere in the system software, then reusing that implementation yields smaller code than including a new one.

My bet is that the reviewer wants something similar to the above analysis.(*)

(*) It's a lie. My real bet is that the reviewer is an unpaid student who did not know what to write in his review, and has only little idea what he is talking about.


Why this function isn't preimage resistant? Prove that the function
$$
G(z) = \mathcal{H}(z) \, || \, \text{LSB}(z)
$$
(where $\mathcal{H}$ is a collision resistant hash function, $||$ is concatenation and $\text{LBS}$ is the least significant bit of $z$) is not preimage resistant.
Obviously, if $z = 0^n$ then from the output $G(z)$, one can extract $z$ from the last bit. That also can be said about the case $z = 1^n$.
But is this enough to prove $G$ is not preimage resistant?

Pre-image resistance: given a hash $h$ it should be hard to find any
message $m$ such that $h=hash(m)$. This concept is related to that of
the one-way function. Functions that lack this property are vulnerable
to pre-image attacks.

Let $O$ be an oracle that provides pre-images for $G$ that is given $y$ it produces a pre-image $z$ such that $G(z) = y$. Now expand this to $$y = H(z)||LSB(z).$$ Therefore, given the oracle $O$ one can find the pre-images of $H$ by asking $x||0$ and $x||1$ to the oracle and test the result. As a result, if $G$ is not pre-image resistant then $H$ is not. too. This implies that $H$ is pre-image resistant then $G$.
In the details; the $O$ will produce $x_0$ and $x_1$ such that $G(x_0) = H(x_0)||0 = x||0$ and $G(x_1) = H(x_1)||1 = x||1$. As we can see that this may also produce collisions for $H$.

$G$ fails only two-bit resistance by leaking the LSB. If a hash function is failing its pre-image resistance by leaking LSB, then it has some serious problems. Consider that, one provides you the LSB of the pre-image for SHA256, can you find the pre-image easily?
To see the loss bits of resistance; let $H(z):\{0,1\}^* \to \{0,1\}^n$ be a collision resistant hash function. Then is has $\mathcal{O}(2^n)$ pre-image and secondary pre-images resistances, and $\mathcal{O}(2^{n/2})$
If $G(z):\{0,1\}^* \to \{0,1\}^{n+1}$ with $G(z) = H(z) \mathbin\|\text{LSB}(z)$ then it has $\mathcal{O}(2^{n-1})$ pre-image and secondary pre-images resistances instead of $\mathcal{O}(2^{n+1})$


How is the TLS 1.2 sequence number generated? In the other ciphers supported by TLS 1.2, namely stream cipher and CBC block cipher mode, the sequence number is implicitly in the MAC (RFC5246, 6.2.3.1):

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

How many bytes is seq_num? How is the sequence number generated? There seems to be no explicit information about this in the RFC document.

How many bytes is seq_num?

To quote the RFC (section 6.1; item 'sequence number')

 Sequence numbers are of type uint64

That is, they are 8 bytes long

  How is the sequence number generated?

From the same section:

 A sequence number is incremented after each
 record: specifically, the first record transmitted under a
 particular connection state MUST use sequence number 0.

That is, the sequence number for the first record is 0, the sequence number for the second record is 1, the sequence number for the hundredth record is 99.


Second pre-image resistance vs Collision resistance From Wikipedia:

  Second pre-image resistance

  Given an input $m_1$ it should be difficult to find another input $m_2$ such
  that $m_1$ ≠ $m_2$ and $\operatorname{hash}(m_1) = \operatorname{hash}(m_2)$. Functions that lack this
  property are vulnerable to second-preimage attacks.

  Collision resistance

  It should be difficult to find two different messages $m_1$ and $m_2$ such
  that $\operatorname{hash}(m_1) = \operatorname{hash}(m_2)$. Such a pair is called a cryptographic hash
  collision.

Could someone explain the difference between these two please? They very much appear to be identical to me, as in both definitions $m_1 \neq m_2$ and $\operatorname{hash}(m_1) = \operatorname{hash}(m_2)$.

The difference is in the choice of $m_1$.

In the first case (second preimage resistance), the attacker is handed a fixed $m_1$ to which he has to find a different $m_2$ with equal hash. In particular, he can't choose $m_1$.
In the second case (collision resistance), the attacker can freely choose both messages $m_1$ and $m_2$, with the only requirement that they are different (and hash to the same value).

(From this, it is also obvious that collision resistance implies second preimage resistance: An attacker can just choose an arbitrary $m_1$ and compute a second preimage $m_2$ to obtain a collision.)


Why does Rijndael with a 256-bit block require the bottom two rows to be shifted one more space than usual? From Wikipedia:

  For a 256-bit block, the first row is unchanged and the shifting for the second, third and fourth row is 1 byte, 3 bytes and 4 bytes respectively.

Why the change? Is there any difference than in using 0, 1, 2, 3 like the other keysizes?

That variation directly implements Rinjdael's ShiftRow as specified (section 4.2.2) in the proposal to NIST, defining Shitftrows for 128, 192 and 256-bit block size (Nb=4, 6 and 8).

Loosely speaking, the offsets improve the mixing (diffusion) properties of consecutive rounds of the cipher. More precisely the authors state their motivation (section 7.4) as:

  The ShiftRow offsets

  The choice from all possible combinations has been made based on the following criteria:

  The four offsets are different and C0 = 0;
  Resistance against attacks using truncated differentials [Kn95];
  Resistance against the Square attack [DaKnRi97];
  Simplicity

  For certain combinations, attacks using truncated differentials can
  tackle more rounds (typically only one) than for other combinations.
  For certain combinations the Square attack can tackle more rounds than
  others. From the combinations that are best with respect to criteria 2
  and 3, the simplest ones have been chosen.


What information does $g^x$ reveal about $x$? Let $p$ be a large prime number. Let $G$ be a subgroup of $\mathbb{Z}_p^*$ with order $q$ - again a large prime. Let $g$ be a generator of $G$.

Consider the following standard protocol for generating a random element $x \in \mathbb{Z}_P$:

Player 1 generates a random number $x_1 \in \mathbb{Z}_p$ and outputs $g^{x_1}$ as a binding commitment.
Player 2 generates a random number $x_2 \in \mathbb{Z}_p$ and outputs $g^{x_2}$ as a binding commitment.
The two players reveal $x_1, x_2$, and after checking consistency with the commitments, the output of the whole process is defined as $x = x_1 +x_2 \ (\mathrm{mod}\ p)$.

Suppose now that Player 2 would like to manipulate $x$. Her strategy is the following: She sees $g^{x_1}$. She generates $n$ random number $a_1, ...,a_n$. She computes $g^{x_1+a_1}, ..., g^{x_1+a_n}$, see which one she likes best, and sets $x_2$ accordingly: $x_2 = a_i$ for some $1 \leq i \leq n$. Finally, she outputs a commitment $g^{x_2}$.

This scheme is not considered secure, since Player 2 can obviously affects the distribution of $g^{x_1+x_2}$ and therefore the distribution of $x$.

  My question is, can Player 2 really manipulate $x$ to her benefit?

One way to formalise this question would be: Let $A \subset \mathbb{Z}_P^*$. If Player 2 is honest, we have
$$
\mathbb{P}[x \in A] = \frac{|A|}{p-1}.
$$
Can Player 2 increase this probability using the above strategy?

(Naturally, $A$ can be defined by "the set of all numbers $x$ in $\mathbb{Z}_p$ such that $g^x$ has a '1' in the last digit" and then Player 2 can easily make this probability equal 1, so this formalisation is not very good. Suggestions?)

You state

  One way to formalise this question would be: Let $A \subset \mathbb{Z}_P^*$. If Player 2 is honest, we have
  $$
\mathbb{P}[x \in A] = \frac{|A|}{p-1}.
$$
  Can Player 2 increase this probability using the above strategy?

  (Naturally, $A$ can be defined by "the set of all numbers $x$ in $\mathbb{Z}_p$ such that $g^x$ has a '1' in the last digit" and then Player 2 can easily make this probability equal 1, so this formalisation is not very good. Suggestions?)

One way to address this issue, let's call it the encoding of $A$ issue is to hide the obvious properties of $A.$ Thus the players can interact with a randomized encoding of $A.$ Specifically, for your case, we can define $A$ as the set of all numbers $x$ in the integers modulo $n$ such that $H(x)$ has a certain bit pattern $(a_1,a_2,\cdots, a_t)$ in its leading $t$ bits, where $H$ is a secure hash function.

So the game can be played on the hashed image of the relevant quantities.


Should I salt an AES password at each encryption? I saw a sample code where the same password is salted with a different value (using PBKDF2) for each encryption. That means that the salt must be stored for each encrypted message.

I don't understand why they do that since AES is used here in CBC mode with a random IV at each encryption, so a same plaintext will not produce the same ciphertext.

My understanding is to use a unique key for all the encryptions made with a same password. That key is produced by salting the password and I store the salt somewhere in cleartext. I though it was enough to do that because salting the password ensures the same password does not generate the same key. So the combination of the salted password and the unique IV are enough.

So my question is: is it a better behaviour to re-salt a password at each encryption?

No, it should not be necessary to derive a unique key for each message, although it certainly shouldn't do any harm, either.  CBC mode is provably secure (in the IND-CPA sense, or even IND-CCA2 if combined with a MAC) even if the same key is used for multiple messages, as long as the underlying block cipher is secure (a PRP) and the IVs are distinct and unpredictable.

One potential problem with using a deliberately slow KDF like PBKDF2 to derive a new key for each message is that this needlessly consumes resources, and thus reduces the legitimate user's performance advantage over an attacker (who only needs to run PBKDF2 once to test each password).  Even if one wanted to have a unique key for each message, it would be better to first derive a single intermediate key from the password with PBKDF2, and then use a faster KDF (like HKDF, or even PBKDF2 with an iteration count of 1) to derive the per-message keys from the intermediate key.  Of course, this is less of a concern if messages are typically long and few rather than short and many.


What are alternatives to Proof of Work for consensus of a blockchain that doesn't contain anything of value? For example, a distributed blockchain that would keep track of the weather. Anyone could add a weather reading, and several of these would be stored in each block, just like transactions in a cryptocurrency. There is no reward for mining these blocks, so speed of mining wouldn't be a huge concern for inflation, all that would matter is that all the nodes agree.
It seems to me that Proof of Work would work for this, but it would be lots of effort for nodes to get nothing in return, also the benefit of slowing mining isn't really important. Proof of Stake seems to be the next most popular consensus mechanism, but I can't see how that could possible work in this situation, where you have nothing of value to risk.
What other methods of consensus could work for this?

a blockchain that doesn't contain anything of value

Do you mean a blockchain with no associated token? If the data really has no value, no one will be interested in storing it on a blockchain.
If there is a limited amount of writers (i.e. up to ~100 nodes), it is possible to create a consortium network and deploy a blockchain using a Byzantine Fault-Tolerant (BFT) consensus (e.g. Proof of Authority). These blockchains do not require a token/cryptocurrency for the consensus. This is typically referenced to as a permissioned blockchain (as opposed to a permissionless/public blockchain such as Bitcoin or Ethereum).
Permissioned blockchains have different very different tradeoffs compared to permissionless blockchains. The blockchain is controlled entirely by permissioned nodes which are the only ones allowed to perform writes (in a public permissioned blockchain anyone is able to read). This model generally support a much higher throughput (more transactions per second) compared to permissionless consensus. Since nodes are authenticated in BFT protocols, the consensus model is designed to resists against malicious nodes up to a certain threshold (e.g. 1/3 of malicious nodes).
As a side-node, the flowchart in Fig. 1 from Do you need a Blockchain? can help to determine if a Blockchain is the appropriate solution for a problem.


Why should we consider the output of the AES s-box as a “sensitive value” in relation to side channel attacks? In general,  we consider the output of s-box in AES as a “sensitive value” in order to perform a side channel attack. I would be very grateful if you could explain to me the reason of that consideration. Why should we consider the output of the AES s-box as a “sensitive value” in relation to side channel attacks?

I would like to complete poncho's answer by mentioning a point that has not been discussed here.

On top of being an internal state which directly depends on plaintexts (resp. ciphertexts) and the key if you attack the first round (resp. the last one), making hypothesis on S-box output (resp. input) allows to exploit the non-linearity of this operation. Indeed, due to this property, passing the hypotheses through the S-box operation ensures a good distinguishability between the correct and incorrect key guesses.

For example, let's say you are performing a correlation power analysis (CPA) by considering the Hamming weight as leakage model. Then if you choose to focus on the round key addition (which also constitutes an internal state which directly depends on plaintexts (resp. ciphertexts) and the key), then all your key hypotheses which have a small Hamming distance with the good key will also result in a high correlation coefficient. The S-box non-linearity offers the  advantage to reduce the peak for all the wrong assumptions.


Finding the basis of the transpose of a q-ary lattice Given $q$ and a matrix $A \in \mathbb{Z}_q^{n \times m}$, the $q$-ary lattice is defined as
$$\Lambda(A)=\{x \in \mathbb{Z}^m:Ax=0 \bmod q\} $$
An instance of a q-ary lattice and its short basis is computed in Generating short basis for hard random lattices. Once the short basis $T_A$ for $\Lambda(A)$ is given, computing the short vector $s$ in $\Lambda
(A)$ is given in SamplePre algorithm.

Is it possible to find a short basis for $\Lambda(A^T)$, if we are given a short basis of $ \Lambda(A)$?

Basically I want to find the short vector $s^\prime$ such that $A^Ts^\prime=0 \bmod q$.

If $n<m$ then for almost all matrices $A$ the columns of $A^T$ will be linearly independent and in that case $\Lambda(A^T)$ is the lattice generated by the basis  $qI$ (which is the shortest possible basis for this lattice).


NIZK proof for Order-preserving encryption Suppose a cipher c=Enc(K,m), where Enc() is the order-preserving encryption scheme. Can NIZK be used to prove that c does indeed encrypt m? The Schnorr NIZK is based on discrete logarithms equality. I don't know if it can be used for order-preserving encryption.

Thank you!

You cannot prove that a ciphertext (produced by an order-preserving encryption scheme) encrypts a particularly plaintext in zero-knowledge, because verification of such a proof would necessarily leak the plaintext.

Perhaps you want to instead prove that the ciphertext is well-formed (i.e., produced by the scheme)? This is possible in the context of site's definition of [OPE][1], namely, a method of encrypting data so that it's possible to make efficient inequality comparisons on the encrypted items without decrypting them, since El Gamal conforms to this definition (see [plaintext equality tests][2]), and NIZK proof systems can be used to prove various properties about El Gamal ciphertexts.

EDIT. The comments note that:

I assumed (possibly incorrectly) that the message was not to be revealed, and
The site's definition of OPE is incomplete.

I've proposed an edit to the site's definition of OPE. This answer only applies to the original definition.


Designing a hash function from first principles rather than depending on heuristics Is there a general method to design a cryptographic hash function (with desired properties) from first principles? That is, is there a general process for constructing such functions? I get the impression that Merkle–Damgård construction simplifies the process by allowing collision-resistant compression functions to be used, but are there any general ways of finding "good" compression functions other than by using trial-and-error?
In the entries to the most recent NIST challenge, it seemed to me as if the teams were using very different approaches based on different heuristics, and then essentially testing their functions against many inputs, tweaking parameters, and after that iterating until all evidence pointed to their functions as being secure.

To what extent is this an accurate summary of their approaches? I would really appreciate a reference to a thesis or other publication on this subject.

You should design your hash on the bit level.

Regardless how you design your hash, at the end of the day you have a $m$ booleans functions for each output bit from an arbitrary $n$ bits of input.

Some properties of boolean functions

All your output bits will be some boolean function of your input bits.

All boolean functions can be turned into the so called algebraic normal form (ANF), which means your input bits are combined using AND and XOR operators only.

XOR operator is just addition modulo 2. AND operation is just multiplication modulo 2. And these operations are usually denoted with multiplication and addition respectively. In modulo 2 arithmetic addition and subtraction are the same operation, so don't be surprised when I use + when talking about differences.

The modulo 2 arithmetic forms a field, which means all your usual algebraic identities you know are true.

So now the operation of your cipher is just a system of $m$ equations for $n$ bits of input.

Due to nature of modulo 2, a lots of things cancel. Powers cancel: $0^n = 0$, $1^n = 1$. Even coefficients cancel: $x + x = 2x = 0$.

This means the equations for the output is simpler: The only possible coefficient is 1 (or 0 which means a missing term). And all of them is on the first power.

Nonlinearity

If you try to make a cryptographic hash function that only uses XOR and shifting, the equations will be linear even after infinitely many rounds, now the analyst is just a single Gauss elimination away from solving it and now they have the ability to create arbitrary preimages.

In order to avoid that, you need to make your equations non-linear by using the AND operator. Hashes do all sorts of shifting and XOR-ing but this non-linear step is what makes them secure.

But having non-linear terms are not enough. You must make sure the attacker cannot effectively cancel out the non-linear terms out of your equations by fixing some inputs to 1 or 0. Also you need to make sure the terms will not cancel if the attackers takes the difference of two equations. If you have the formula $xy + x + y$ for one and another formula $xy + y + z$ for another bit. Adding these two will give $x + z$ which is now linear and allows the attacker to solve it to get the relationship between two out bits.
Every independent linear equation an attacker can create will reduce the security of your hash with 1 bit. One way to mitigate this is making sure all the functions for the output bits contain different terms. In the previous example if we replace the $xy$ to $xz$ to the second formula. Adding together will not yield linear equation then. But if the attacker fixes the $x$ to a constant value then it becomes a linear equation. This is probably the most challenging part of designing your hash.

Balance

Another thing to consider is balance. You want your hash behave like the so called random oracle. This is important if you want your hash useful as a cryptographically secure random number generator for example. You should make sure all your bits in the resulting hash have 50% chance to be 1. The XOR operator have a very good property that makes it possible: in $a + b$, if either term have 50% chance to be 1, the entire expression will have 50% chance to be 1. To prove this let's consider $A$ and $B$ the probability that $a$ and $b$ are 1 respectively. The probability that $a + b$ is 1 is: $A(1-B) + B(1-A)$. That is either $A$ is 1 and B is 0, or $A$ is 0 and $B$ is 1. If we expand this we have: $A + B - 2AB$. Substituting 0.5 for $A$ gives: $0.5 + B - B = 0.5$. So as long as you can ensure there is at least one term in the final equations that has 50% chance to be 1 independent from other terms, then that will ensure your function is balanced. The simplest way to achieve this, is making sure at least one first order input bit term appears in the functions of all output bits and it will anchor the 50% chance.

Strict avalanche criterion

The next thing to consider is the strict avalanche criterion (SAC).  This means if you change any bit (or more generally any bit pattern) in the input, all bits in the output must have 50% chance to change. Failing to do so can give information to the attacker about the input, and makes your hash vulnerable to differential cryptanalysis. Let $H(x)$ the original hash, let $H(x + \alpha)$ the hash of the changed input. In $H(x) + H(x + \alpha)$ the changed bits will be set. You must make sure this function is balanced too so any bit has 50% chance to be set. Let's se what it means. Let x be the bit we changed. Let $xy + xz + yz$ the expression we test. Let $\bar x$ be the flipped $x$. So the test expression will be: $(xy + xz + yz) + (\bar xy + \bar xz + yz) = xy + xz + \bar xy + \bar xz = (x + \bar x)y + (x + \bar x)z = y + z$. Basically terms that doesn't cointain $x$ will be removed, and $x$ will will be removed from terms that contain $x$. This implies that in order to reach SAC it's a necessary condition that  every output bit depends on every input bit. If there is an output bit that doesn't depend on some input bit, your hash will fail to demonstrate SAC if that bit is flipped.

So now how can you make sure that $H(x) + H(x + \alpha)$ is balanced? There is a class of boolean functions that ensure that. They are the so called bent functions. The simplest bent function is just $xy$ where $x$ and $y$ are independent bits. These bent functions can be combined together by adding them up, so $ab + cd + ef + gh$ will be a bent function too ($a$-$h$ are independent bits). There are other more complex construction too (but I didn't find good examples). So if you want to have SAC, use bent functions. But bent functions come with a drawback: they can't be balanced. There will be a $2^{-n/2}$ bias releative to the 50%.
But this bias approaches zero as the number of bits reaches infinite.

My summary is no way exhaustive.

As the time passes and more and more attacks are discovered so new hash designs need to satisfy more and more conditions, balance, SAC and nonlinearity is a good starting point but probably not enough (I don't know all attacks).


Using ePassport with Active/Chip Authentication to sign documents I'm a complete newby, so please pardon my ignorance when it comes to basic cryptography aspects.

My question is whether a biometric passport with Active/Chip Authentication (AA or CA) can be used to generate digital signatures for docs (or rather their hashes). If so, is there any API available to do that?

Thank you in advance for your feedback!

Active Authentication (AA henceforth) relies on RSA or ECDSA and allows you to sign data. However, as our is not meant to sign data you should not use it for that purpose.

First of all,  the only PKI that verifies the public key is that used for passive authentication of the passport - so you probably have to set up a separate PKI for it to be useful. Passive authentication simply embeds the public key in a "data group" which is then authenticated by a signature set by a country's signing certificate. However, the public key used is not in a certificate itself.

Second, the signing is used for passport authentication only and therefore does not require user confirmation / commitment such as  entering a PIN. Hence any reader with access to the contents of the passport is allowed access to the signing procedure, so having a signature does not prove user consent in any way.

The old AA algorithm uses the ISO/IEC 9796-2 signature scheme 1 giving message recovery. I've never been able to find out why (and I was directly involved), probably it was copied from some banking standard. Newer ones may use PSS as well. If 9796 is used then you might not be able to find too many parties that are able to verify the generated signature. AA is performed using the INTERNAL AUTHENTICATE command and is performed over RND.IFD which is specified for 8 bytes only, severely limiting input data.

If the passport still uses AA then you might also have a problem with the size of the keys. If you want to sign something for non-repudiation then you may want to have an RSA key size of 3072 bits or above. There aren't many smart cards that have the hardware for such large key sizes (at least not if you want to fit the other tens of pages of protocol spec in there as well).

In principle AA may use ECDSA, but it makes more sense for the country to use CA if that's the case. Finally, there may also be passports that use PACE-CAM, where the CA internal authentication is embedded in the initial authentication procedure.

For Chip Authentication (CA) the signature generation was considered a threat to the privacy of the user. A country could for instance use it to sign time and coordinates to create tracking.  That's why CA is based on Diffie-Hellman key agreement rather than a signature generation function. Unfortunately, that also makes it unavailable for signature generation.

Conclusion: it is next to impossible to use AA and CA for digital signatures  used for non-repudiation; AA was not designed to support such use case and CA was deliberately designed to avoid the use case. AA could be used to sign 8 bytes without user consent, but that's about it.

Besides the technological barriers, I'd certainly consider using AA or CA for anything other than (national) border control morally wrong. It should not be used even with consent, as any advantage that is gained can also be used to pressure people into using a passport for what it is not designed to do.


One-Time-Pad with multiple keys? Would it be more secure if we used multiple keys in a One-Time-Pad encryption?

An OTP already provides provable confidentiality in the case that the key is as large as the plaintext, and that the key itself is completely random in an information theoretic sense. Provable security in this case means that even a computationally-unbounded attacker would be absolutely incapable of decrypting the ciphertext if they are not given the key. You can't get more secure than that. Adding another key to an already unbreakable cipher does not make it "more" unbreakable.

Do note that an OTP does not protect the integrity of the plaintext in any way, regardless of how many keys are used on top of each other. An attacker can flip any bit in the ciphertext and know that the corresponding bit in the plaintext will also be flipped. To avoid this, a message authentication code, or MAC, is required. A MAC needs a key of its own, so any extra key material can be used for integrity.


Does a break in a collision resistance property of a hash function by definition implies an attack at the first pre-image attack? Is there a formal security proof in the shape of reduction that states that if an attacker manages to break the collision resistance property of a cryptographic hash function (a random oracle) he will break the pre-image attack as well? To rephrase it: is first pre-image resistance as hard as collision resistance s.t if you break collision resistance you break first pre-image attack?

This relation obviously doesn't hold.

If you define "break" as faster than what's expected of an ideal hash function

Define TrivialCollisionHash = GoodHash(input.Skip(1 bit)). Finding pre-images for this is just as hard as for GoodHash, i.e. $2^n$. Finding a collision is trivial, just flip the first bit.

If you define "break" as faster than a certain computation bound

Use an ideal hash function. It has collision resistance of $2^{n/2}$ and first pre-image resistance of $2^n$. So an attacker with a computational bound between $2^{n/2}$ and $2^n$ can find collisions but not pre-images. For example an attacker who can perform $2^{160}$ oracle queries on a 256 bit hash function will most likely find a collision, but he probably won't find a pre-image.


Timing attack and good coding practices How would timing attack occur on a particular code but not in another code (because of good coding practice)? Could anyone give an example? I am having trouble figuring out how timing attacks would occur based on the way the code is written.

TL;DR at the bottom.

The general ideas of timing attacks are the following:

Secret data has influence on timing of software
Attacker measures timing
Attacker computes influence$^{-1}$ to obtain secret data

A Basic weakness: if( secret )

The base of an exploitable code sensitive to a timing attack looks like this:

if(secret)
{
  do_A();
}
else
{
  do_B();
}

The idea is that the time to compute A is different to the time to compute B. Thus knowing this difference, you can compute back the secret.

Let us have a look at the following code which is closer to a real world code.
This is the core operation in RSA decryption: $a^d \bmod n$ with secret key $d$:

typedef unsigned long long uint64;
typedef uint32_t uint32;

/* This really wants to be done with long integers */
uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      if((exp[i] >> j) & 1)
        r = ((uint64)a*r) % mod;
    }
  }
  return r;
}

In this code you can see that you have a if section which depend on the secret (exp[i] >> j) & 1. If the value of the secret is 1 then you will execute r = ((uint64)a*r) % mod. If the value of the secret is 0 you will execute nothing. Thus you have a difference in the time of the execution depending on the secret.

Let us improve this code a bit:

typedef unsigned long long uint64;
typedef uint32_t uint32;

/* This really wants to be done with long integers */
uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1, t;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      if((exp[i] >> j) & 1)
        r = ((uint64)a*r) % mod;
      else
        t = ((uint64)a*r) % mod;
    }
  }
  return r;
}

In this code you can think that because we do the same thing on both branch of the if statement that depend on the secret (exp[i] >> j) & 1:

1 assignment.
1 multiplication
1 modulo operation

The time to execute either branch will be the same, Right ?

Well... No. Because... t is a dead variable and the compiler will certainly notice it and will optimize the code. "This variable is useless, get rid of it!". The compiled code will therefore be the same as the one from before where you had your timing vulnerability.

But even if we force the compiler to not optimize the code, it is still not constant time :

modern CPUs have branch prediction.
and instruction cache.

Therefore we need to get rid of this branching weakness.

Removing the branches

How do we remove the branching of something like this:

if (s)
  r = do_A()
else
  r = do_B()

We replace it by something like this:

r = s * do_A() + (1 - s) * do_B()

Because we want fast code, we can expand s to all-one/all-zero mask and use XOR instead of addition, AND instead of multiplication.

So moving back to our Square-and-multiply:

uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1,t;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      t = ((uint64)a*r) % mod;
      cmov(&r, &t, (exp[i] >> j) & 1);
    }
  }
  return r;
}

where cmov (as conditionnal move) is an assembler instruction of same name (which doesn't use any prediction) or is defined as the following:

/* decision bit b has to be either 0 or 1 */
void cmov(uint32 *r, const uint32 *a, uint32 b)
{
  uint32 t;
  b = -b; /* Now b is either 0 or 0xffffffff */
  t = (*r ^ *a) & b;
  *r ^= t;
}

Another weakness: table[secret]

The idea is the following, the cache of your processor contains your table. And because everything in the cache is accessible within the same timeframe your secret is safe.

address  | content
------------------
0x0001   |    8
0x0002   |    7
0x0003   |    6
0x0004   |    5
0x0005   |    4
0x0006   |    3
0x0007   |    2
0x0008   |    1

That is true... if you only have this code running. However you always have other code running at the same time on your CPU, therefore some parts of your table will be as following:

address  | content
------------------
0x0001   |    8
0x0002   |   XXX
0x0003   |   XXX
0x0004   |    5
0x0005   |   XXX
0x0006   |    3
0x0007   |    2
0x0008   |    1

And we assume that the attacker has control over which part of the cache is corrupted. Therefore if secret is 0x0001 then you will have an immediate response from the cache. However, if the secret is 0x0002, the cache is invalid. Therefore the CPU will have to reload the value from the stack / memory. This takes a longer time, because we have a timing difference... We have a possible timing attack.

The counter measures are quite complex and I won't elaborate on them.

References

A big part of this answer is from this slides: Timing Attacks and Countermeasures by Peter Schwabe at the Crypto Summer School 2016 - Croatia.

Some interesting readings:

Osvik, Shamir, Tromer, 2006:
Cache Attacks and Countermeasures: the Case of AES.
http://eprint.iacr.org/2005/271/

AlFardan, Paterson, 2013: Lucky Thirteen: Breaking the TLS and DTLS Record Protocols.
http://www.isg.rhul.ac.uk/tls/Lucky13.html

Yarom, Falkner, 2014: FLUSH + RELOAD: a High Resolution, Low Noise, L3 Cache Side-Channel Attack.
http://eprint.iacr.org/2013/448/

Benger, van de Pol, Smart, Yarom, 2014: “Ooh Aah... Just a Little Bit”: A small amount of side channel can go a long way.
http://eprint.iacr.org/2014/161/

Bernstein, 2005: Cache-timing attacks on AES.
http://cr.yp.to/papers.html#cachetiming

Brickell, 2011: Technologies to Improve Platform Security.
http://www.chesworkshop.org/ches2011/presentations/Invited%201/CHES2011_Invited_1.pdf

Bernstein, Schwabe, 2013: A word of warning.
https://cryptojedi.org/peter/data/chesrump-20130822.pdf
https://cryptojedi.org/peter/data/cacheline.tar.bz2

Yarom, Genkin, Heninger, 2016: CacheBleed: A Timing Attack on OpenSSL Constant Time RSA
https://ssrg.nicta.com.au/projects/TS/cachebleed/

Hamburg, 2009: Accelerating AES with Vector Permute Instructions.
http://mikehamburg.com/papers/vector_aes/vector_aes.pdf

Biham, 1997: “A Fast New DES Implementation in Software.”
http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1997/CS/CS0891

TL;DR

If you read this and skipped the whole answer, then it means that you definitively don't want to write crypto code.

If you did read the whole answer, then you probably understood why it is a bad idea to write crypto code by yourself given how many ways you can screw up.


If I can crack the AES, how do I crack the wifi I am a student major in math.
My teacher said that AES (Advanced Encryption Standard) has many applications.
For example, the WPA2 in wifi.
Then he taught the theory of the AES and never says how to apply it.

So, my question is,
if I can crack the AES,
how do I crack the wifi and steal others' data (just for learning purpose).

Please give me the concrete steps.
If it is too complicate to explain at here,
you can give me the reference which I should read.

Edit: the point of my question is not "how to crack AES".
My question is "how to crack wifi if I can crack AES".
I can choose the key by myself in a private newwork.
Then I don't need to crack the AES.
The thing I want to do is crack and learn how to crack the wifi.

If you "crack the AES", a very hypothetical assumption, then you could simply parse the WiFi packets and decrypt the messages that are being send.

Cracking AES is however considered impossible. AES-256 is even considered secure against attacks that involve (somewhat less hypothetical but still unavailable) quantum computers.

Note that even RC4, which was one of the reasons that WEP was cracked, is considered pretty secure when used correctly. Generally you are better off attacking the protocol or protocol implementations.

If you really want to attack AES itself then side channel attacks are probably your best option.