AES Mix Column Transformation Section 3.4.3 "The MixColumns Step"(page 39) of "The Design of Rijndael", it states

  The columns of the state are considered as polynomials over
  $\operatorname{GF}(2^8)$ and multiplied modulo $x^4 + 1$ with a fixed polynomial $c(x)$.

  The polynomial $c(x)$ is given by
  $c(x) = \mathtt{03} \cdot x^3 + \mathtt{01} \cdot x^2 + \mathtt{01} \cdot x + \mathtt{02}$

  Let $b(x) \equiv c(x) \cdot a(x) \pmod{x^4 + 1}$. Then

How this polynomial multiplication modulo $x^4+1$ is converted to Matrix Multiplication?

The columns of the state are considered as polynomials over $\operatorname{GF}(2^8)$

Bytes are values in $\operatorname{GF}(2^8)$. Thus a column composed as the 4 bytes $a_0,a_1,a_2,a_3$ represent the polynomial  $a_0 x^0 + a_1 x^1 + a_2 x^2 + a_3 x^3$ (notice the ordering with respect to the power!).

Now we have:

\begin{array}{cccccccccccccccc}
(a_3 x^3 &+& a_2 x^2 &+& a_1 x^1 &+& a_0 x^0) &\cdot&\\
& & (\texttt{03}x^3 &+& \texttt{01}x^2 &+& \texttt{01}x^1 &+& \texttt{02}x^0) = \\
\texttt{03}a_3 x^6&+& \texttt{01}a_3 x^5 &+& \texttt{01}a_3 x^4 &+& \texttt{02}a_3 x^3 &+& \\
& & \texttt{03}a_2 x^5&+& \texttt{01}a_2 x^4 &+& \texttt{01}a_2 x^3 &+& \texttt{02}a_2 x^2 &+& \\
& & & & \texttt{03}a_1 x^4&+& \texttt{01}a_1 x^3 &+& \texttt{01}a_1 x^2 &+& \texttt{02}a_1 x^1 &+& \\
& & & & & & \texttt{03}a_0 x^3&+& \texttt{01}a_0 x^2 &+& \texttt{01}a_0 x^1 &+& \texttt{02}a_0 x^0)
\end{array}

If we apply $\mod (x^4 + 1)\ $ we have:
\begin{array}{cccccccccccccccc}
(a_3 x^3 &+& a_2 x^2 &+& a_1 x^1 &+& a_0 x^0) &\cdot&\\
& & (\texttt{03}x^3 &+& \texttt{01}x^2 &+& \texttt{01}x^1 &+& \texttt{02}x^0) = \\
\texttt{02}a_3 x^3 &+& \texttt{03}a_3 x^2 &+& \texttt{01}a_3 x^1 &+& \texttt{01}a_3 x^0 &+& \\
\texttt{01}a_2 x^3 &+& \texttt{02}a_2 x^2 &+& \texttt{03}a_2 x^1 &+& \texttt{01}a_2 x^0 &+& \\
\texttt{01}a_1 x^3 &+& \texttt{01}a_1 x^2 &+& \texttt{02}a_1 x^1 &+& \texttt{03}a_1 x^0 &+& \\
\texttt{03}a_0 x^3 &+& \texttt{01}a_0 x^2 &+& \texttt{01}a_0 x^1 &+& \texttt{02}a_0 x^0 &= \\
b_3 x^3 &+& b_2 x^2 &+& b_1 x^1 &+& b_0 x^0
\end{array}

Thus by reading the colunns:

\begin{array}{cccccccccccccccc}
b_3 = \texttt{02}a_3 + \texttt{01}a_2 + \texttt{01}a_1 + \texttt{03}a_0\\
b_2 = \texttt{03}a_3 + \texttt{02}a_2 + \texttt{01}a_1 + \texttt{01}a_0\\
b_1 = \texttt{01}a_3 + \texttt{03}a_2 + \texttt{02}a_1 + \texttt{01}a_0\\
b_0 = \texttt{01}a_3 + \texttt{01}a_2 + \texttt{03}a_1 + \texttt{02}a_0\\
\end{array}

by reordering over $b$:

\begin{array}{cccccccccccccccc}
b_0 = \texttt{01}a_3 + \texttt{01}a_2 + \texttt{03}a_1 + \texttt{02}a_0\\
b_1 = \texttt{01}a_3 + \texttt{03}a_2 + \texttt{02}a_1 + \texttt{01}a_0\\
b_2 = \texttt{03}a_3 + \texttt{02}a_2 + \texttt{01}a_1 + \texttt{01}a_0\\
b_3 = \texttt{02}a_3 + \texttt{01}a_2 + \texttt{01}a_1 + \texttt{03}a_0\\
\end{array}

by reordering over $a$:

\begin{array}{cccccccccccccccc}
b_0 = \texttt{02}a_0 +  \texttt{03}a_1 + \texttt{01}a_2 + \texttt{01}a_3\\
b_1 = \texttt{01}a_0 +  \texttt{02}a_1 + \texttt{03}a_2 + \texttt{01}a_3\\
b_2 = \texttt{01}a_0 +  \texttt{01}a_1 + \texttt{02}a_2 + \texttt{03}a_3\\
b_3 = \texttt{03}a_0 +  \texttt{01}a_1 + \texttt{01}a_2 + \texttt{02}a_3\\
\end{array}

Which is exactly the matrix multiplication:

\begin{array}{cccccccccccccccc}
\begin{bmatrix}
b_0\\
b_1\\
b_2\\
b_3
\end{bmatrix}
=
\begin{bmatrix}
\texttt{02} & \texttt{03} & \texttt{01}& \texttt{01}\\
\texttt{01} & \texttt{02} & \texttt{03}& \texttt{01}\\
\texttt{01} & \texttt{01} & \texttt{02}& \texttt{03}\\
\texttt{03} & \texttt{01} & \texttt{01}& \texttt{02}
\end{bmatrix}
\times
\begin{bmatrix}
a_0\\
a_1\\
a_2\\
a_3
\end{bmatrix}
\end{array}


Comparing Difference Distribution Tables I have been studying the Diff. Cryptanalysis and finding it hard to do a problem. The problem is

I have calculated the tables programmatically and found that the second table has a max value of 6 where as the first has a max value of 4.What can i infer from the tables?
PS:I started reading this recently and need help in atleast the direction to think


Zero-knowledge proof system which is not proof of knowledge? I have learned that a zero-knowledge (ZK) proof system can be constructed by making use of the three-color problem. In this particular case, the proof system also happens to be proof of knowledge (POK), i.e. any prover necessarily needs to know a witness in order to convince the verifier.

Are there ZK proof systems which are not POK?

There are certainly ZK proof systems which are not known to be POK, and for which no knowledge extractor is known. For example, take the Goldreich-Kahan 4-round ZK proof system. However, do we know of a non-trivial proof system that is provably not a proof of knowledge? Not that I know of.


Creating a message authentication scheme I have such situation. I have a device like dongle. But it has certain limitations. For example, it can only have implemented encryption and decryption functionality.

The availability of ciphers which it can use it can use is also limited. Current option is 3DES.

Now, I need to create a message authentication scheme (which gives both integrity and authenticity) from this situation.
I know ideally HMAC, CBC-MAC, should be used, but we don't have that situation.

I am interested would such option be considered a somewhat secure MAC:

I want to authenticate message M
I apply hash on message M say SHA1, e.g. M' = SHA1(M). This I do from my PC which is more powerful than my dongle, HASP.
I feed the device-HASP, with M' (there is an issue here, please see below), it encrypts it with a key, e.g.,

TAG = 3DES_ECB_ENCRYPT(M', KEY)

The 3rd step is done because to avoid sending lot of data to the device.

My TAG is the authentication tag, which I will send together with message M.
This is the scheme basically:

My problems and questions are:

You know 3DES block size is 8 bytes, how can I feed it with output of SHA1 (in a secure way) which is 20 bytes? Or what workaround exists for it?
How secure is my MAC?

I know this is not the most secure, but like I said we have some limitations, and are ok with it if it is not catastrophic mac scheme.
e.g. our current MAC was just DEC ECB encryption, of XORED plain text.
So now instead of XOR ing plain text blocks between each other we use SHA1.
Old scheme is described here.

PS. Similar approach is mentioned here: https://cseweb.ucsd.edu/~mihir/cse207/w-mac.pdf, but there whole plain text is given to encryption function, here I can't do that - I can't give 200 bytes of data say to the dongle, that is why I want to hash it first, and give smaller amount of data to the device

Doing this would not be secure.

If you truncate the SHA-1 to 64 bits before encryption, then anyone can find a collision in about $2^{32}$ tries (taking minutes on a desktop CPU), and by finding the encryption of one message hash also learn the other. Even a second preimage attack may be feasible.
If you use ECB mode to encrypt a longer hash, then the attacker can attack it "piece by piece", finding one hash value that collides with several block-aligned parts of earlier hashes. This is more difficult than finding a 64-bit collision, but much easier than finding a full collision.

The best you could hope for would be somewhere between 60- and 70-bit security (collision search on full SHA-1), but that would require better encryption/MAC on the hash, and would be more complex than simply implementing HMAC or CBC-MAC.

If the dongle can do (semi-)arbitrary things with 3DES and the PC can do arbitrary things, then I would recommend:

Using a longer hash, e.g. SHA-256, on the PC: $h = H(m)$
Using a block cipher-based MAC on the device on the hash: $t = M(k, h)$.

That gives you the weaker of:

the collision resistance of the hash (128 bits for SHA-256) and
the security of the MAC.

The block cipher based MAC could be e.g. CBC-MAC. That is simple enough and with SHA-256 you would only need to process four blocks on the device itself.


Why does CBC decryption with a wrong IV still give readable results? While developing some code that uses the .NET AesManaged algorithm, I made some mistakes but was surprised at the results.

My encryption was correct.  I was generating a random IV block and writing it to the file (without encrypting the IV).  Then I was encrypting the plaintext and writing it.

The decryption was wrong though... instead of reading the first block from the file an using it as an IV, it was just using a random IV and decrypting everything.  The first block came out gibberish but the 2nd (and subsequent) ones were decrypted properly!  Why would this be?

And even weirder... when I tried to fix it by encrypting the IV in the encryption code (instead of writing the IV unchanged) the decryption result was the same!  (gibberish then correctly decrypted blocks).

Although I eventually fixed my code, how do these results make sense?

This is what ciphertext block chaining is about - each plaintext block is XORed ("chained") with the previous ciphertext block before encrypting (and after decrypting).

The initialization vector then takes the place of the ciphertext block before the first block (since there is none).

So, mistaking the initialization vector as a ciphertext block does nothing wrong for decryption (other than that you'll get an additional garbage block of plaintext).

You did observe (part of) the malleability property of CBC: One can change the start of the ciphertext (including the IV), even prepend/remove blocks, and the result is still a valid ciphertext, and the plaintext block after the changed one will be changed in a predictable way.

This is used for some attacks on protocols using CBC, when they allow a chosen-ciphertext attack - search for the padding oracle attack, for example.
For this reason, you always (not only for CBC) should use authentication together with your encryption, for example in form of a MAC around your ciphertext (including the IV).


How would you find the Blinding factor R in RSA blind signature algorithm? How would you find the Blinding factor $R$ in RSA blind signature algorithm when having – for example – $p=11$, $q=3$, message $m=6$, and public key $pk=7$?

The answer doesn’t have to use the numbers in the example. I’m just trying to understand how to find the blinding factor $R$ having any numbers.

You don't “find” the blinding factor. It is picked randomly before starting the computation. The whole point of blinding is to use a random value in the computation and to perform the computation in such a way that this random value affects intermediate values but not the final result.


Cipher Block Chaining (CBC) encryption in SSL Is cipher block chaining (CBC) mode used in SSL encryption? If block reordering is already protected by SSL and TCP sequence numbers, what added advantage does CBC provide?

The sequence number is used to disallow re-ordering of the messages / records themselves, not the blocks inside them. The block cipher / mode of operation is used to keep the data within the messages confidential; the chaining happens over one message, not over all messages - at least not for newer the newer TLS protocols.

Re-ordering of blocks within the messages can be performed if CBC mode is used. However, the plaintext message that is encrypted has been protected with an authentication tag using HMAC, which means that the altered plaintext message will fail verification afterwards.

ECB mode is always insecure if the blocks can have any, interdependent data. The reason for this is that identical plaintext blocks will always result in identical ciphertext blocks, which leaks information. It is similar to using the same IV for CBC mode, but for each and every block. Block ciphers in ECB mode are not CPA secure.

Note that the newer TLS 1.3 protocol disallows CBC mode altogether. There have been many issues with the authenticate-then-encrypt and CBC mode in TLS, requiring protocol specific alterations to CBC padding mode for instance. Nowadays either an authenticated stream or stream cipher mode should be preferred. Most of these modes - such as GCM - use counter (CTR) mode instead of CBC.

CBC is mainly used for legacy applications. It has wide support in crypto libraries, which makes it a logical choice for applications that do not require anything better. Most cryptographers here will however try to avoid CBC mode as it requires a random IV and padding or ciphertext stealing. It only provides real benefits over insecure modes such as ECB.

SSL is an old name. Nowadays TLS should be preferred as SSL may refer to the old protocols which are now commonly disabled in clients / servers. There was some talk about reintroducing the SSL name for TLS 1.3 but fortunately - in my strongly voiced opinion - that didn't happen.


How exactly works the quantum communication done by China? This video and this article announced that spacial quantum communication were finally done using satellites.

As a recap, when two particles are entangled, if a measurement is done to one of them, the appositive value results in the other particle. Nevertheless, traditionally is believed no practical communication is possible to do using this approach because the data is random.

The video says that the way the dealt with the problem is that some information is send trough the quantum channel but extra information is sent also using conventional information which is complemented with the quantum information to get the complete message.

How exactly it works?
What the extra information sent in conventional channel is about?
Is this extra information smaller than the original message?
If not smaller what's the point of using the quantum channel and not just sending all the message in the conventional channel?

Finally they say that it offers unhackeable security. Is that statement valid in any way?

I watched the video with the sound off, but the giveaway are the lasers. It's simply(!) the extension of quantum bit transmission to orbiting satellites, rather than via fibre optics.  All the same principles apply, although it's hard to keep a physical lock on the satellite.  Clearly this becomes impossible when the satellite disappears beneath the horizon.

There is a rule of thumb that says general media + tech = 0.  The general press are hopeless in trying to convey a technological story.  What the Chinese will have done is to transmit entangled photons to the satellite.  They may have then send another set of entangled photons back to the earth station.  This allows transmission of data via statistic analysis, and the BB84 protocol is a common technique for this. The Chinese may not have got as far as this protocol.  It would be sufficient to prove entanglement between the earth station and the satellite. This would be the real advancement in this item.

This answer details how a quantum network works.  In summary, keys are generated via quantum RNGs and transmitted via photons.  Transmission is akin to a one time pad (OTP), but a bit cleverer as there is a great deal of noise within the transmission.  That's why the key exchange is unbreakable.  Those keys are then used for conventional encryption over conventional wiring.  With a  satellite, that conventional encrypted transmission could be achieved via lasers, just minus the glass fibrery bit.

  If not smaller what's the point of using the quantum channel and not just sending all the message in the conventional channel?

That's a good question.  Currently the key exchange is done via OTPs.  It's low baud, so a conventional channel is used in an office setting for the Gigabit throughput.  ID Quantique only manage about 10 KBits /s currently.  It is conceivable that when this technology is miniaturised to portable size, military battlefield communication could all be performed via pure BB84, without bothering with the conventional encryption. And it would all be unbreakable, whilst currently the conventional encryption might be broken one day.

But it might be jamable and susceptible to MITM attacks.  Another almost coincident laser directed at the satellite receiver could swamp it.  This is speculation at this stage, but someone's working on it, I'm sure.


Permutation for which an inverse is a hard problem Is it possible to construct (even if we don't know how) a permutation for which an inverse must exist but is difficult to find (brute force required)? The one way permutation contains no hidden information (keys) or state - it's public.

Or can it be proven that such a construct is not possible?

In case I'm not specific enough in what I'm asking, such a construct would allow for a sponge construction with no hidden state because no inverse permutation for it can be found.

It is obviously possible; one simple example is the function $f(x) = g^x - 1 \bmod p$, where $p$ is a large prime, and $g$ generates the entire group $\mathbb{Z}_p^*$; this is permutation over the range $[0, p-1)$, and is difficult to invert if the discrete log problem is hard.

What may be more difficult is to design an efficient hard-to-invert permutation; most efficient permutations are designed as a composition of trivially invertible permutations (and hence the result can be easily inverted).


What is the "single-letter characterization of the secrecy capacity"? I'm reading a paper [1] in which secrecy capacity are being discussed under the following terms:

  A single-letter characterization of the secrecy capacity that holds for the general case remains unknown until now (if it exists at all). Only a multi-letter description of the secrecy capacity has been established so far.

What do the terms marked in bold mean, either in plain English or expressed in terms of entropy/mutual information/etc ?

[1]: Secure Communication under Channel Uncertainty and Adversarial Attacks - Rafael F. Schaefer, Holger Boche, and H. Vincent Poor

Secrecy capacity is defined as the maximum bit rate that can be sent securely through a channel. Single-letter means that the corresponding capacity expression does not depend on the block length $n$.

For example in a degraded wiretap channel, we have the following single-letter characterization of the capacity $C$:

$$C = I(X;Y) - I(X;Z)$$

But in more complex models like the compound wiretap channel, it's hard to find an expression that doesn't depends on $n$:

$$C = \lim_{n\to\infty} \frac{1}{n} \max_{U} ( \min_{s\in S}I(U,Y_s^n) - \max_{s\in S}I(U,Z_s^n))$$

Single-letter characterization is a desirable property, since it is simpler to express and compute.

Adapted from a mail explanation from R. F. Schaefer


Why was it easier to decode messages that you had several copies of? During WW1 the German ambassador in Washington, von Bernstorff, blamed their numerous transmissions of the same messages as the cause for the successful decoding done by the British. I don't see the reasoning unless the same messages were sent in different codes, but why would the Germans do that? Bernstorff said:

  There is absolutely no cipher which they (the British) cannot
  decipher, provided they have before them a sufficient amount of
  telegrams. And this result, particularly in the case of the United
  States, was probably due to the fact that circumstances were such as
  to force us to make use of an extraordinarily large number of ciphered
  messages, and we often sent our reports and telegrams in double or
  triple form, in the hope that in some way they should reach Germany.
  Consequently, the British must have had an enormous amount of material
  in the way of cipher dispatches of ours, and in this way it was
  possible for them to break down our various ciphers.

Dooley says that simple substitution or transposition were used by both sides from 1914 to mid-1916--for radio, telegraph, and phone messages. Radio became more important in the summer of 1916, and then cryptanalysis became the name of the game for determining order of battle.[1]  Crystal set radio often required messages to be sent repeatedly due to signal attenuation, interference, operator error, etc.  But this is probably not what he was referring to.

Von Bernstorff was likely referring to the debacle of the Zimmermann telegram, where the same message was sent using two different encryption systems from Berlin to Mexico City.  It was a British intelligence coup.  Both cipher systems were weak, but the older one was almost completely broken.

The Germans did that because their embassy in Mexico City did not have their government's more modern cipher book.  Their people in Washington, D.C., fatefully relayed the Zimmermann telegram using an older cipher system.

Unsurprisingly, we have evidence that Von Bernstorff did employ one cipher which probably worked against the British, and that was the null cipher.
David Kahn says how Bernstorff used null ciphers in press cables to get past British collection.[2]

[1]  Dooley, John, F. (2016) Codes, Ciphers, and Spies: Tales of Military Intelligence in World War I (p. 49). New York, NY: Springer.

[2]  Kahn, David (1967) The Codebreakers (pp. 521 and 1063). New York, NY: The Macmillan Company.


Paillier encryption: Many private keys for a public key Assume $N$ is a public key for paillier encryption, generated by a third party.

Question: Given $N$ can each client generate its own private key, such that its public key is $N$? So all parties separately generate their private key, but their public key is the same.

No, that doesn't work.

If one party chooses primes $p,q$ and sets $n = pq$, then other parties would also have to know $p$ and $q$, because it is the only way to get the same $n$.

But you just left out a part of the public key, which is $g$. This results in a different question:
If you have a trusted party set up $n$ and assign different $g$ values to each party, would that work? No it would not, because in the decryption process you need to calculate $c^{\lambda}$. And knowing $\lambda$ would allow the factorization of $n$. So basically every party would be able to decrypt the messages to every party, as if they were just using one public key.


Depth of the SHA-256 collision search knowing partial input and final hashes So I have a partial input data (string) PART1+UNKNOWN+PART2, length of UNKNOWN is self-describing.
I have a bunch of valid hashes (about 8 or so) that are compatible.
My question is then: will bruteforce search for full collision given the data at hand be as long?

Yes, but please note that the question/answers you are pointing to are about partial collisions on the output, not partial input. Finding a full hash collision is not computationally feasible for hash functions that are considered secure, such as SHA-256.


what does the leading byte represent for the initial point G? Per SEC 2, the base point $G$ for secp192r1 is as follows:

G = 04 188DA80E B03090F6 7CBF20EB 43A18800 F4FF0AFD 82FF1012
07192B95 FFC8DA78 631011ED 6B24CDD5 73F977A1 1E794811

According to this JavaScript ECDH Key Exchange Demo, when you click the secp192r1 button, the $(x, y)$ coordinates for $G$ are as follows:

x = 602046282375688656758213480587526111916698976636884684818
y = 174050332293622031404857552280219410364023488927386650641

$x$ is equal to what you'd get if you converted 188DA80E B03090F6 7CBF20EB 43A18800 F4FF0AFD 82FF1012 from hex to decimal. Same thing for 07192B95 FFC8DA78 631011ED 6B24CDD5 73F977A1 1E794811.

But what does the 04 at the beginning mean?

But what does the 04 at the beginning mean?

It means 'this elliptic curve point is specified in uncompressed format', that is, the $x$ and $y$ coordinates are given explicitly.

The other alternatives are :

02, which means 'this is a compressed point, where we give the $x$ coordinate explicitly; of the two possible $y$ coordinates that are compatible with that $x$ coordinate, select the one with the 0 lsbit.
03, which is the same, except you select the $y$ coordinate with a 1 lsbit.

The compressed formats are about half as long (saving space), but requires more computation (a modular square root) to use if you perform an operation that requires the $y$ coordinate.


What is the use of segments in Cipher Feedback Mode (CFB) In NIST SP800-38A: Recommendation for Block Cipher Modes of Operation
CFB can be used with a parameter s - the size of a data segment in bits - which determines the amount of key stream material that is produced per block.

API's often also have parameters to at least generate a segment 8 of bits or a segment of the same size as an entire block - which is the maximum for s. Usually s is of course limited to multiples of 8 as the input/output is specified in bytes.

Usually OFB can also be parametrized this way, but it doesn't seem that the use of a parameter s (with a different value from the block size) is a recognized mode of operation in the standard.

What is the use of parameter s? Does it just have to do with error propagation?

Actually, s is in CFB mode to handle transmission channels for the encrypted data that can add or drop individual bytes.

In the olden times (say, the 70's), it was common to transmit data over serial channels, for example, RS-232.  These channels were not perfect, and one common error we see is that if the transmitter sent 7 bytes, the receiver might get only 6 (or possibly 8); this would happen only on occasion, but it was a definite possibility.

Now, consider what would happen if we sent CBC-encrypted data over such a channel.  The first time we drop a byte, what would happen is that the block boundaries that the encryptor and the decryptor assume would not line up; what the encryptor thought was the first byte of the next block, the decryptor would assume is the last byte of the previous block.  The decryptor would get gibberish, and (this is the important point) there is no mechanism for them to ever resync.

That is what s in CFB mode is for; if we set s=8, then after a drop (or add) error, the decryptor will get the next 8 bytes (8 assuming DES; this is the 70's after all) as gibberish, but then it will start to decrypt correctly (assuming, of course, that the transmission channel doesn't give us any more errors).

Now, times have changed; we don't deal with such channels that much any more.  In addition, we are considerably more sensitive to what an active attacker could do; if we did need to deal with such a channel, we're more likely to break up the plaintext stream into a series of records, encrypt (and MAC) each record separately, and insert a noncryptographical resyncing protocol (e.g. byte-stuffing in end-of-record markers) on top of it.  That way, an error may cause us not to receive a record or two, but nothing more (and the attacker could not introduce any bogus data).

As for the s parameter in OFB mode, that is universally recognized as a bad idea; using an s < n vastly increases the probability of OFB falling into a short loop, with no benefit in compensation.


Simply using password as a third "private key" for PAKE I'm reading through the development of PAKE protocols, starting with EKE and SPEKE, their potential pitfalls, and what motivates their protocol choices. And I've been wondering, what is wrong with the following (very simple) modification to classic DH to make that PAKE:

Let Alice and Bob have a shared secret s = hash(password). Alice and Bob pick private keys a, b. Starting with DH, Alice and Bob compute their public keys as

$A = g^{as}\mod p$

$B = g^{bs}\mod p$

After they exchange public keys, they can calculate their shared key as
$K = g^{abs}\mod p$

What is wrong with this simple scheme? I'm guessing it somehow allows an offline dictionary attack on s. I know s has no low entropy, but I'm still not seeing how.

Here's the problem with this scheme: suppose $A$ is the honest client, and $B$ is a dishonest server (who doesn't know $s$).  Then, $A$ tries to log in, he selects $a$ and transmits

$$A = g^{as} \bmod p$$

Then, $B$ just picks a random value $b$, and transmits

$$B = g^b \bmod p$$

Then, $A$ will compute a 'shared secret' $$S = B^a \bmod p$$ (which would be $g^{abs} \bmod p$ had $B$ executed the protocol honestly, instead, we have $S = g^{ab} \bmod p$).  Then, $A$ sends a message $M_S$ keyed by that shared secret (whether it be a key confirmation message or an initial encrypted data exchange, it doesn't really matter).

$B$ has no further interactions with $A$.

Then, here is what $B$ can do; he can pick an entry in his dictionary $password'$ and compute $s' = hash(password')$.  He can then compute $S' = A^{s'^{-1}b} \bmod p$; if he happened to pick the correct password, then $s = s'$, and so $S' = A^{s^{-1}b} = g^{as \cdot s^{-1}b} = g^{ab} = S$, and so he can use that shared secret to verify the message.

If he didn't happen to pick the correct password, he can go back and select another entry in his dictionary, and repeat the off-line computation until he finds the right entry.

Bottom-line: with your protocol, an active attacker can do a full dictionary search as the result of a single exchange.


The Salsa20 core preserves diagonal shifts? What do we mean by

  the Salsa core preserves diagonal shifts

The input of the Salsa20 core is a 4x4 array of 32-bit words. If you move all the inputs diagonally (wrapping), the output will be the same as the original output, except that it's moved by the same offset.

$P^\prime_{i,j}=P_{i+k,j+k}$ implies $C^\prime_{i,j}=C_{i+k,j+k}$ (indices reduced modulo 4)

This symmetry follows directly from Salsa20 applying the same operations to all columns and all rows.

The full Salsa20 uses four fixed input words, which ensures that no matter how you choose the remaining inputs, you can never find two different inputs which could be transformed into each other using such a diagonal shift.


Has AES-128 been fully broken? Has AES-128 been broken over the full 10 rounds? If so, by what means? By a commercial entity? By a supercomputer?

If not, why is AES-256 used to replace AES-128 so frequently?

AES is a block cipher and is supposed to be a pseudorandom permutation. It can achieve IND-CPA or IND-CCA or authenticated encryption by using the appropriate mode of operation together with AES. Let see what can be achieved or not.

Has AES been fully (10-rounds) broken? by what means? (commercial? supercomputer?)

Direct brute-forcing

The total BitCoin miners reached $\approx 2^{92}$ double SHA-256 calculations in a year. So you need on average

$2^{35}$ multiple power of this monstrous computing power to break AES-128
or wait for $2^{35}$ years.

The Summit in Oak Ridge can reach $2^{71}$ SHA-1 in a year so no threat there.

In short, there is no threat from here.

Best Known Cryptographic Attacks
The key of AES-128 can be recovered with a computational complexity of $2^{126.1}$ shown in Biclique Cryptanalysis of the Full AES by Bogdanov et. al, using the biclique attack, achieved in 2016. Note this is not the related-key-recovery attack from the same authors and that such attacks are not practical since we are generating the keys randomly. The attack requires $2^{88}$ data complexity and $2^8$ memory complexity.

In short, theoretically, one can say it is broken since the attack requires less than the brute force. However, the attack time and data complexity are not practical, either. From the paper; As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.
The other theoretical attacks on AES-128 are based on the Biclique Cryptanalysis;

Biclique Cryptanalysis of the Full AES, Bogdanov et al.
Better than Brute-Force - Optimized Hardware Architecture for Efficient Biclique Attacks on AES-128, Bogdanov et al.
Sieve-in-the-Middle: Improved MITM Attacks,  Canteaut et al.
A Framework for Automated Independent-Biclique Cryptanalysis, Abed et al.
Bicliques with Minimal Data and Time Complexity for AES, Bogdanov et al.
Improving the Biclique Cryptanalysis of AES Tao et al.

\begin{array}{|c|c|c|c|c|r|}\hline
\text{data} & \text{w/o SIM} & \text{Mem. Bytes} & \text{with SIM} & \text{Mem. Bytes} & \text{reference} \\ \hline
2^{88}& 2^{126.21}& 2^{14.32}& - & - &  \text{Bogdanov et al. 2011}\\ \hline
2^{4}& 2^{126.89}& 2^{14.32}& - & - &  \text{Bogdanov et al. 2012}\\ \hline
- & - & - & 2^{126.01} & 2^{64} &  \text{Canteaut et al. 2013}\\ \hline
2^{72}& 2^{126.72}& 2^{14.32}& - & - &  \text{ Abed et al. 2014}\\ \hline
2 & 2^{126.67} & 2^{14.32} & 2^{126.59} & 2^{64} &  \text{Bogdanov et al. 2015}\\ \hline
2^{64} & 2^{126.16} & 2^{14.32} & 2^{126.01} & 2^{64} &  \text{" "}\\ \hline
2^{56} & 2^{126.13} & 2^{22.07} & 2^{125.99} & 2^{64} &  \text{Tao et al. 2016}\\ \hline
2^{72} & 2^{126.01} & 2^{26.14} & 2^{125.87} & 2^{64} &  \text{Tao et al. 2016}\\ \hline
\end{array}
Where SIM is Sieve-In-the-Middle technique

Multi-Target attack
If you had plaintext-ciphertext pairs with different encryption keys then with a multi-target attack you can find some keys faster. The expected cost of finding a key from $t$ targets is $2^{128}/t$. If you have a billion targets that you will be able to find the first key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This applies not only to AES but all block ciphers.

Post-Quantum Crypto
Due to Grover et. al's seminal work we know that the security of any block-cipher is halved in key size and it is shown to be asymptotically optimal.
Thus, AES-128 will have 64, and AES-256 will have 128-bit security if someone can build the QC. If you consider your assets valuable, the reasonable choice is to double the key size.
One can also use Grover's algorithm in parallel like in classical parallelization. One, however, will get $\sqrt{K}$ speed gain with $K$ copies.

why has 256 bit key based encryption is used so much to replace it?

Therefore, to mitigate the attacks that exist now or in a possible future, you need to double the key size. In AES, this makes AES-256. If you consider the overhead of using the AES with 256-bit key, in which we need 14 rounds, in CPU this makes around 40% percentage overhead. So, as stated in comments by Prof. Lindell, in marketing AES-256 sounds better, and becomes the standard.
The 256-bit marketing also may come from the US/NATO military regulations which use several distinct security levels (e.g. confidential =128, secret =192, top-secret =256). The 17 years old document from June 2003 states top-secret must be used 192 or 256 bits keys;

The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use

In a side note, according to leaked documents by Snowden, NSA looking for tau statics to break AES. After this revelation, consistent and strong encryption is required from governments. After 5 years, nothing has been related to tau statics and AES appeared in academics area.
Current Nist Recommendation NIST as of March 2019 disallows less than 112-bit security for block cipher in SP 800-131A Rev. 2:

The use of keys that provide less than 112 bits of security strength for key
agreement is now disallowed.

Validation of the 40% overhead of AES-256 with AES-NI
The below numbers are from a laptop with a i7-6700HQ CPU to validate the performance overhead with AES-NI.
$openssl speed -evp aes-128-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-128-ctr     509191.01k  1592361.66k  3090684.67k  4237894.66k  4708169.05k  4763506.01k

$openssl speed -evp aes-256-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-256-ctr     439608.45k  1479537.77k  2478394.14k  3129161.54k  3255877.41k  3396628.62k


Working Precision and Time-constant Arithmetic with ECC? I am interested in Elliptic Curve Cryptography and found algorithms for constant-time multiplication.
Within these algorithms arithmetic operations must be performed (like addition and multiplication).

I have two questions about these 'internal' arithmetic operations:

these 'internal' operations must be performed in constant-time, too, right? Then I guess the precision of all intermediate variables must be the same.
But what precision is necessary here (e.g. if I multiply two 256 bit numbers, I need 512 bits for the result, I guess).
What are good algorithms for performing these 'internal' arithmetic operations in constant time?

You can have additions and multiplications take constant time on a hardware level; however, the multiply units generally take 4 cycles due to the array multiplier design for a 32-bit width, at 64-bit on Intel, it's 6 cycles.  The division will always be iterative, which is the problem.

Here's an example of a routine that I have for adding two 256 numbers in constant time on my i7 (note, these times will be different for different cores):

add256:
        xorl      %r9d, %r9d         # 1 cycle
        movq      (%rsi), %rax       # 1 cycle
        addq      %rax, (%rdi)       # 1 cycle
        movq      8(%rsi), %rdx      # 1 cycle
        adcq      %rdx, 8(%rdi)      # 1 cycle
        movq      16(%rsi), %rcx     # 1 cycle
        adcq      %rcx, 16(%rdi)     # 1 cycle
        movq      24(%rsi), %r8      # 1 cycle
        adcq      %r8, 24(%rdi)      # 1 cycle
        setb      %r9b               # 1 cycle
        ret                          # 1 cycle

You are not going to get true constant time unless you are in assembly.  I believe that the best way to get constant time would be to just figure out the maximum it time it takes to do a calculation, and then pad intermediate cycles with junk because the ADD and MUL will take different times.

The thing that will hurt you the most is the division that is iterative, as that takes an arbitrary amount of cycles.


In The Ristretto Group, do all points sampled with Elligator have the same order? Assume the Hash-to-ristretto255 function Elligator as laid out here. Assume a random hash that is then mapped to a point in the Ristretto group - is this point then of prime order (is it even in the same order order as the basepoint?).
If not, is it guaranteed that the Discrete Logarithm is still hard for the sampled point?

From the main page;

Ristretto is a technique for constructing prime order elliptic curve groups with non-malleable encodings. It extends Mike Hamburg's Decaf approach to cofactor elimination to support cofactor-8 curves such as Curve25519.

The cofactor can cause some problems in some protocols, MQV, HMQV, MVQ and HMVQ
The main idea is the coset definition, only Edwards here;
Edward Curve ( twisted Edward Curve if $a\neq 1$ and untwisted Edward Curve if $a=1$)
$$\mathcal{E}_{a,d} := \{(x, y) \in \mathbb{P}^2 (\mathbb{F}) : a \cdot x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2\}$$
has a cofactor of 4. A complete ( if $d$ and $ad$ are nonsquare in $\mathbb{F}$) Edward curve $\mathcal{E}_{a,d}$ has a $4$-torsion group ( elements of order $4$) and it turns out that it has exactly has 4 elements. Then the below coset is defined w.r.t. $P=(x,y)$
$$\mathcal{E}[4] + P = \{(x, y); (y/ \sqrt a, −x \sqrt a); (−x, −y); (−y/ \sqrt a, x \sqrt a)\}$$
Now, this coset eliminates the co-factor problem. Similar definitions for Jacobi with isogenies are given. Also for the compatibility of the Montgomery curves.

In The Ristretto Group, do all points sampled with Elligator have the same order?

This coset operation makes sure that the order (number of elements) of the coset curve is prime. Since the order of the group is prime then by the Lagrange theorem all elements have prime order ( order of elements must divide the order of the group).
In short, now, the hash-to-group with Elligator maps the hash into elements where each has prime order, except the identity.

Does any basepoint create a weakness?
The answer is no!. Consider that an attacker chooses the base $G$ deliberately that they can solve it easily. There is a simple approach for them to solve for any basis $G'$;

Solve DLog $G'$ to base $G$ to obtain $G' = [k]G$.
Now given $[x]G'$ solve it in the base $G$ to obtain $r$ such that $[x]G'=[r]G$
To get the $x$ just compute $x = r\cdot k^{-1} \pmod n$ where $n$ is the group order.


ECDSA public key recovery is discovered by whom? I'm looking for the history of the method (ECDSA public key recovery from signature). Where did this implementation first appear in (is it bitcoin?) and who discovered this method?

Update: in a footnote of his paper Generic Groups, Collision Resistance, and ECDSA (online since 2002-02-27), then published in Designs, Codes and Cryptography (2005), Daniel R. L. Brown wrote that

In ECDSA, the public key can be recovered from the message and the signature.

Then, acting as editor of the SEC 1 standard, he put there how such ECDSA public key recovery can be made. In this version v1.99 of 2009-05-21 with changes since v1.5 visible, that section appears as a late addition.
Thus it seems possible that Daniel R. L. Brown of Certicom came up with ECDSA public key recovery circa 2002. At least he knew about its feasibility. That vastly predates Bitcoin.


Embedded device needs PRNG, has AES & EEPROM TL;DR - the device is just a microcontroller and essentially does whole-disk encryption. At initialization time, I need a PRNG to create the key material.

I have a software AES ECB encrypt operation (among other things - I also have CTR mode, but it isn't tooled for this use, and I have AES CMAC).

Some quick googling suggests that if I had a 16 byte PRNG key, then I could simply keep a 16 byte counter value and count from 0 for each block, run that through ECB and use that as the PRNG output.

I don't mind performing a read of /dev/urandom at manufacturing time and writing that into the controller's EEPROM.

Is it really just that simple?

Is there any reasonable alternative to pre-seeding the PRNG key (I'm guessing not)?

No it's not that simple because you'll be selling kit that has  predetermined secret information within it.  Why should I use Orthrus when you know the PRNG seed?  How can I trust you when your user name starts with the letters NSA?  Seriously though, I don't think that your Mega32 is a secure  chip (cryptographically) so someone might be able to read back the seed using their own software.  There might also be side channel attacks.  (It might be worth while posting another question specifically regarding use of a Mega32 for secure computation.  There are people here who are very knowledgeable about that).

That aside, you have huge computational power on that chip and a shed load of I/O ports including a comparator on port D. And you have AES functionality.  Include a hardware random entropy source.  They're fairly easy and there are circuits widely available. Try to avoid using a reverse biased transistor as they're unstable long term, but if you only switch them on at card initialisation, you'll be fine.

Build one or two transistor or diode circuits, feed them though your comparator and you'll get thousands of bits of entropy in a few seconds.  Worth the wait for the undoubted benefits.  Pass a secure hash function over it like SHA-1, and you have your perfect seed material.  (I personally prefer Pearson hashes in memory rich environments).  You can generate 16 bytes of pure entropy in no time.  Ask another question about the specifics of this later.

The important part of what I've said is marketing.  You can market a hardware entropy source on the grounds of "quantum security" , "no one knows the seed", "unique randomness" etc.  Sounds a lot better than "I hid something inside the chip that I hope no one finds. Ever". The value of security through obscurity is debatable, but either way cannot trump quantum physics.


Is the following PAKE protocol UC secure? Consider the following (simplification of a) PAKE protocol: Alice and Bob start with a pre-agreed password pw. To establish a new session key $k$, first Alice samples a random nonce $r$ and sends it to Bob. Bob samples a nonce $r'$ and sends it to Alice. The session key is $k = \mathcal{O}(pw,r,r')$, where $\mathcal{O}$ is a random oracle.
It seems that the simulator can easily extract the input of corrupted Alice (or Bob) by simulating the random oracle and proceed with the simulation without much problems. However, this can't be a secure PAKE protocol (right?) because it would allow for offline dictionary attacks: once eavesdropping on both nonces ($r$ and $r'$) the adversary can just query the oracle on all possible passwords on the dictionary (that is poly size) and the session key will be among the oracle answers. This will be a problem once the session key is used for anything.
So my question is, is the protocol above UC secure wrt to the $\mathcal{F}_{\mathsf{pwKE}}$ functionality of this paper (my guess is probably not for the reason above), and if not, where does the simulation actually fails?

You're right that it's not UC-secure, for exactly the reason you say. It allows offline dictionary attacks. Here's how that problem manifests in the UC model:
Consider this particular environment:

Environment chooses honest party's password $pw$ uniformly from some known  polynomial-size dictionary $\mathcal D$ (without loss of generality $\mathcal{D} = \{1, \ldots, m\}$.
Environment initiates the protocol and waits for honest party to report an output $K^*$
Environment requests from the adversary a sequence $k_1, \ldots, k_m$. The adversary wins the game if $k_{pw} = K^*$.

It is easy for an adversary to win this game in the real world interaction with probability one. The adversary sets $k_i = \mathcal{O}(i,r,r')$.
It is also not hard to see that no adversary can win this game in the ideal world interaction with probability better than $1/m + 1/2^\ell$ (where $\ell$ is the output length of $\mathcal{O}$). Observe the following:

The only way to get the honest party to report output in the ideal world is for the simulator to initiate an online password guess.
Since the honest $pw$ is uniform in $\mathcal{D}$, the probability of this guess being correct is $1/m$.
Assuming the online guess is incorrect, the functionality delivers a totally uniform/independent value $K^*$ to the honest party. In particular, $K^*$ is independent of whatever $k_{pw}$ value that the adversary sends to the environment. So it can match only with probability $1/2^\ell$.

I think the essence of your question relates to the fact that extraction has to happen at the time of the protocol execution (that's what makes it an online password guess).
In this protocol, as soon as the parties have exchanged $r$ and $r'$, the real-world honest party will output a key, so the simulator will need to send a password guess to make the same thing happen in the ideal world.
But what if the adversary hasn't even queried $\mathcal{O}$ yet -- what will the simulator do?
This protocol fails to limit the adversary to one password guess (every time it queries $\mathcal{O}(pw',r,r')$ the simulator would have to know whether $pw'$ is correct, in order to produce a consistent response), and it fails to limit that password guess to the period of time that the protocol is running.


Zero Knowledge for Low Entropy Witness For any PPT prover ($p$) and verifier ($v$), imagine I have a low entropy witness, say smaller than $2^8$.  Now, let us say I have a dlog statement in the form of  $y = g^w$. Theory says I could use a sigma protocol such that $p$ can prove to $v$ that it knows $w$. I could also make use of the fiat shamir transform to make it non-interactive.

This is not the case when the entropy of the witness is low as in this example. In both cases I could simply enumerate the $256$ possible witness  and use the response and commitment to check to which one it might correspond i.e:

For a commitment:

$t = g^v$

A challenge $c$ and a response:

$r = t + c \times x$

It is obvious to see that if I have $r, \space c$ and $t$ I can recover $x$. The same happens if we were to use Pedersen commitments instead.

I assume this is a common problem for all dlog based ZKPoK, but I am not sure, nor I do not know what should I use instead.

The one liner in this case is: How can I prove Knowledge when the witness entropy is that low?

$\newcommand{\NP}{\mathsf{NP}}\newcommand{\lang}{\mathcal{L}}\newcommand{\rel}{\mathcal{R}}\newcommand{\bin}{\{0,1\}}$
Let $\lang\subseteq\bin^*$ be any $\NP$ language with a corresponding $\NP$ relation $\rel$.
Now assume that every statement in $\lang$ has a short witness, i.e. a witness of constant (as in your question) or at most logarithmic length. I.e. it holds that
$$
  \forall\,x \in \lang\ \exists\,w\in\bin^{\log(|x|) }. (x,w)\in\rel
$$

By definition of an $\NP$ language, it is possible to check whether $(x,w)\in\rel$ in polynomial time for any pair $(x,w)$. Say it takes at most time $p(|x|)$ to decide. It thus follows that¹ we can give a polynomial time algorithm for deciding $\lang$ as follows:
\begin{align}
&\underline{\mathcal{A}(x)\hspace{6em}}\\
&\text{for } w\in\bin^{\log(|x|)}\\
&\quad \text{if } (x,w)\in\rel \\
&\quad\quad \text{return } 1\\
&\text{return } 0
\end{align}

It is easy to see that this algorithm is deterministic, always decides correctly and runs in time at most $$2^{log(|x|)}\cdot p(|x|) = |x|\cdot p(|x|)$$ and therefore in polynomial time. We can thus conclude that any such language is in fact in $\mathsf{P}$.

And for any language there exists a trivial proof system, that consists of just sending nothing. The verifier can simply verify the statement themselves. Note that this proof system is trivially sound (as the prover cannot influence the verifier's decision at all), as well as trivially zero knowledge, since the simulator just needs to "simulate" the empty interaction.

Now you specifically asked about proofs of knowledge. It is easy to see that this is in fact also formally fulfilled here, as the algorithm $\mathcal{A}$ needs to be modified only slightly to extract $w$ from $x$ alone.

\begin{align}
&\underline{\mathsf{Ext}(x)\hspace{6em}}\\
&\text{for } w\in\bin^{\log(|x|)}\\
&\quad \text{if } (x,w)\in\rel \\
&\quad\quad \text{return } w\\
&\text{return } \bot
\end{align}

¹As you in fact observed correctly.


Is there a password hash function with a human component? Sort of Related: Is there a cryptographic hash function that can be performed with pencil and paper?

One problem with hashing passwords is that the attacker has more of everything it seems. More speed, more memory, more time, newer algorithms, etc. It's a constant race to keep up. We have the advantage of having to try less passwords, but even that is only somewhat enough.

What if we threw a human into the mix? Currently, solving 1000 captchas, for example, is \$2. If we had a task as complex as a captcha incorporated into a hash function, and the attacker needed a billion guesses, that would be \$2,000,000 to crack one password.

Of course, incorporating captcha into a hash function I'm pretty sure would be impossible. But there are other tasks that humans seem better that are purely computational. For example, see foldit.

The idea is that when the user enters their password, at a certain step in the hash function, there would be a problem that a human can solve much more efficiently, and the human does it (it can, for example, be presented as a game). It would probably be for the more security conscious, depending how "fun" the hash function is to compute.

Is there such a thing? Is there a hash function such that one of the steps is much more efficient for a human to compute, while still being cryptographically secure?

Note: As for why captchas probably wouldn't work is this, there are only two approaches I can imagine, neither of which works:

The algorithm produces an image for the human to solve (based on the input and other parts of the algorithm). The human solves it, and the algorithm factors that into the hash. The problem is that, unless it used some direct method, to generate a captcha it would need to generate a random word, and then create a distorted image of that word. An attacker can simply edit out the "create a distorted image" step from the algorithm, and no human is necessary. (Perhaps cryptographic obfuscation could be used to prevent removing the distortion part of the algorithm, but that technology is practical yet.)
Same as above, but to generate the captcha, and has a huge base of images. Keep in mind that it simply needs to be a captcha, the algorithm doesn't need to know what word goes with each captcha (that's what the humans for). The problem is that A) you would need an infeasible number of images to make it secure and B) whoever is generating all these captchas may make them in such a way that they know what how to solve them.

Also, computers are somewhat good at solving captchas.

Okay, here's what I think we need:

There must be a very large number of problems (on the same order as the number of passwords/inputs).
A computer must be able to efficiently generate a random problem without knowing the solution.
A human must be able to solve the problem a couple of orders of magnitude better than a computer.

It should be hard for the computer to guess the answer as well. This means the space of possible solutions needs to be large.

There should be a unique solution.

The computer should be able to check if something is a solution

Bonus: Being fun

With these, what we do is:

Use the password/input to seed a random number generator
Generate a random problem
Have the human give the solution
Now process that into the final hash

Steps #1 and/or #4 will involve computer hashing algorithms. (It doesn't need to exactly follow the above steps; I'm just trying to reduce it to a simpler problem.)

Answer: No.

Reason: Useless.

Explanation:

Not necessarily perfectly reproducible as crowds of people may give different output. So you will end up introducing some degree of tolerance.
Once introducing that degree of tolerance, pattern recognition algorithms will be able to automate that and possibly even achieve a higher accuracy than the humans.
NSA will hire many cheap labour agents and manage to get them work for you and cause your hashes to be insecure. NSA is rich, they can hire many of such cheap labour. How can you ensure that the many humans that are solving hashes for you are actually honest people that are not NSA agents?

My opinion: you are trying to solve an existing problem (so the problem actually exists). It's just that your proposed solution is not going to solve the problem. Instead, I even think it will worsen the situation. You seem to be over estimating the uniqueness humans have. Humans are not that unpredictable. Some human-only problems are considered solved by pattern recognitions algorithms. I also think that humans are more predictable than PRNGs. So why not incorporate a seeded PRNG into your hashing function instead? Such seeded PRNGs are less predictable than humans aver all.


How is an X.509 public key used for TLS? Wikipedia's TLS article says:

  The client responds with a ClientKeyExchange message, which may contain a PreMasterSecret, public key, or nothing. (Again, this depends on the selected cipher.) This PreMasterSecret is encrypted using the public key of the server certificate.

The parenthetical remark is interesting. It implies that if there is no premaster secret (which I believe is the case for a DHE key exchange), then the server's public key is not used. However, the server needs to prove that it has the corresponding private key. So where does that proof happen in the protocol if RSA key exchange is not being  used?

When a (EC)DHE (non-anon) cipher suite is used, the server's public key is used to verify the signature of the ServerDHPublic. Diffie-Hellman is an anonymous key-exchange protocol. A signature is used to make sure that the client is talking with who he thinks to talk and no MITM attack has took place.


How to perform the modular reduce of Rijndael's finite field I am trying to understand how to calculate the modular reduction of Rijndael's finite field.

The example on this page says that {53} • {CA} = {01}, because (11111101111110 mod 100011011) = {3F7E mod 11B} = {01} = 1.

I am able to get to the point where I have 3F7E mod 11B, but cant seem to figure out how the reduction works.

      11111101111110 (mod) 100011011
     ^100011011
       1110000011110
      ^100011011
        110110101110
       ^100011011
         10101110110
        ^100011011
          0100011010
          ^100011011 <-- here, right shifted two places?
            00000001

From this example, why does it right shift two places at one point?

I also found an example that 0x1b*0xaa equals 0x8c. Trying to solve this myself I get to the point: 0xE0E mod 0x11B

 111000001110
^100011011
  11011010110
 ^100011011
   1010111010
  ^100011011
    010001100
   ^100011011
     10010111

This makes it 0x97


Should a company ever implement a (recent) published cryptographic protocol I understand that you should never, EVER, EVER implement your own unpublished cryptographic protocols. This topic has been well discussed in many places, e.g. here.

However, once a protocol has been published, peer-reviewed and been around for a few years, what are the general guidelines about implementing this protocol for yourself?

The general advice I've heard is don't. (e.g. SEJPM's comment to this question). Instead, use a pre-existing open source implementation that has been well reviewed such as SSL. But this has a few problems:

There may be restrictions on the use of such implementations.
Sometimes no implementation exists. The protocol may be only have been implemented 1-2 years ago, and no-one has got round to implementing it yet.
An implementation you find may also be faulty. Of particular concern, it is possible the authors may be aware of the fault (such as a backdoor).

And it seems that companies do implement crypto protocols without publishing the implementation, such as the product "Sharemind".

So, should a company ever implement a published protocol for a commercial product? And if so, what guidelines should they follow?

So, should a company ever implement a published protocol for a commercial product?

Yes, if it's something that really adds value for your users. No if it's about saving 4 signature bytes and 112 CPU cycles.

  And if so, what guidelines should they follow?

Publish the source code, at least for the crypto part, so it can be peer reviewed.
Hire experts in the field as consultants to review the implementation.

Both of the above points will help make a strong case for adoption to clients who may have conservative attitudes to security.


What is a smart card? In many cryptographic protocols, some information is transmitted within smart cards. So, what is a smart card? Is it a physical card? What are they used for in cryptographic protocols?

A Smart Card is small portable physical device, typically flat and in the format of a traditional credit card (sometime much smaller: an example is the SIM card in a mobile phone), embedding:

An Integrated Circuit with memory providing permanent data retention; that's using EEPROM, Flash, or FRAM in most of today's Smart Cards.
Temporary coupling means with a reader device allowing to power that IC, and communicate with it; that may for example be contacts, often according to the ISO/IEC 7816-3 standard; or a few turns of conductive material in the card, forming an inductive loop operated at 13.56 MHz, often according to the ISO/IEC 14443 standard.
Inhibiting means restricting read or/and write access to that memory according to some policy. This can go from a few logic gates, to microprocessor(s) with cryptographic accelerators for 3DES, AES, RSA, and ECDSA.

Wired logic Smart Cards

The first commercially successful Smart Card was a pre-paid phone card, used for over two decades in public phone booths in France, replacing coins (which made phone booths too much an attractive target). It had 256 bits of memory, implemented in EPROM technology with 21V programing voltage, plus one physical fuse. The contacts allowed to reset an 8-bit address counter, increment it, read the selected bit, and program the selected bit. Its memory access policy was: any bit can be read; any bit can be programmed (from 0 to 1) when the fuse is not blown; only the last 160 bits can be programmed when the fuse is blown (this is implemented by a logic function of the fuse's state and the three hight bits of the address counter); erasing (from 1 to 0, by exposing the bare IC to ultraviolet light) erases all bits, and normally occurs only in a late manufacturing stage of the IC. The first 96 bits contained issuing information, written before the fuse was blown. Some of the last 160 bits (as defined by issuing information) each represented a certain prepaid value, when still erased. Programming one of these bits reduced the remaining value in the Smart Card. Erasing did not help an adversary, for the issuing information could not be restored after erasure. That information was also protected by a checksum (a 7-bit field containing the binary expression of the number of 0 bits in like 88 other bits of that information; this corruption detection system is such that altering any number of bits in the same direction makes the information invalid).

Fraud by simulation (which was possible due to the lack of cryptographic protocol and secret key in that early Smart Card, and did occur) never was a seriously damaging issue, although about two billions of that Smart Card have been made. That was the kind preferred by Roland Moreno, often credited for the invention of the Smart Card circa 1974 (full disclosure: we have been close friends from 1983 till his death in 2012).

Microprocessor Smart Cards

Many contemporary Smart Cards have a built-in microprocessor, usually on the same die as the long-term memory, implementing the access control policy, in the form of a program rather than wired logic. The access control policy can thus be almost arbitrarily complex (including contained in the memory itself, and alterable as part of the access control policy). That processor can be anything from a 1 MIPS 8-bit CPU, to a much faster 32-bit RISC core. There can be dedicated co-processors for cryptographic algorithms: DES/3DES, AES, RSA (and other cryptography based on exponentiation in $\mathbb{Z}_{n}$), ECDSA (and other cryptography based on elliptic curves), complete with sophisticated protection against side-channel attacks; hardware TRNG+PRNG with testability features; shield against intrusion; detectors of abnormal operating conditions (shield breach, light, temperature, supply voltage glitches..); bus encryption; parity or SECDED on memory; perhaps two CPUs, with hardware checking they obtain equivalent results, for added protection against fault injection attacks; and more.

For a tour (absolutely recommended) of a high-end Smart Card IC, see e.g. that Security Target (alternate link), starting with the block diagram on page 20.

Access control policy implemented in Smart Cards

As an illustration of a common feature, the Smart Card's permanent data memory can contain a Personal Identification Number and a counter of consecutive PIN presentation errors. The usual PIN access control policy will block PIN presentation if the counter of consecutive PIN errors reaches 3; increment the counter at each PIN presentation, then if the PIN is correct reset the counter and enable some function until power off: reading from or writing to some section of the memory; or/and using some information in the memory as the secret key of a cryptographic MAC allowing the Smart Card to be part of a challenge/response protocol. Such PIN policy makes the Smart Card safe against misuse in case of loss of the Smart Card without the PIN, with high confidence (0.03% risk for a 4-digit PIN).

Smart Cards are also useful a containers for an individual's or server's credentials in a Public-Key Infrastructure, in the form of a private key, generated within the Smart Card, or injected into it. The policy will typically include no function allowing the private key to leave the Smart Card, restricting the use of that key to, say, RSA signature of (the hash of) a message supplied to the Smart Card. That prevents compromise of the confidentiality of the key (but not misuse), should the Smart Card be connected to a compromised device/PC.

A lot of work goes into the access control policy of a modern Smart Card; see for example this (highly technical) two parts specification aimed at e-government applications; or (that's relatively simple) what pertains to the card in the European Regulation specifying the Digital Tachograph for trucks, in Annex 1B, appendix 2, and appendix 11 for the RSA + 3DES cryptography.

Comments on what ought to be added welcome!


Why do 1st and 3rd key have to be the same in 2 key 3DES? From this answer:

  However, that wasn't the only situation they had in mind; they also
  considered the case where someone implemented 2 key 3DES in hardware
  (which the first and last subkeys were constrained to be the same)

Why are the first and last keys constrained to be the same?

In two key 3DES two keys are equal so that key size is only 112 bits, compared to the 168 bits of full 3DES. The advantage is a smaller key size without a correspondingly large loss in security: both two and three key 3DES can be attacked in about $2^{112}$ time.

With the encrypt-decrypt-encrypt construction it clearly must be the first and last key that are equal, since having two adjacent keys equal would make the decryption and encryption cancel out. Even with EEE it would have been weak to have equal keys adjacent: it would effectively be a cascade of two 56-bit strength ciphers (DES and double-DES), which a standard meet-in-the-middle attack breaks in roughly $2^{56}$ time.

So having the first and last keys equal is the only option that makes sense.


Can I use a differential that can be traced through the whole cipher with 100% probability? I'm trying to attack a very simple cipher using differential cryptanalysis as a way of becoming familiar with this method. The cipher is so simple that I've found a differential which I can trace through all the rounds of the cipher with 100% probability (it is not 0 of course).

I've read/watched a few tutorials and if I've understood them correctly recovering the last subkey works as follows:

Find $\Delta_X$ which you can trace with high probability.
Choose two plaintexts such $X_1$ and $X_2$ that $X_1 \oplus X_2 = \Delta_X$
Encrypt them, getting $Y_1$ and $Y_2$.
Try to brute force last round's key. For each key: Decrypt the last round for both ciphertexts, getting $Z_1$ and $Z_2$. If $\Delta_Z=Z_1 \oplus Z_2$ is the same as you predicted form $\Delta_X$ the key can be correct. It gets one point.
Repeat it for different plaintext pairs.
The key that has the highest score is probably the correct one.

Maybe I've misunderstood something about DC, if so, the remainder of this question is probably nonsense. That's why I've described what I think differential cryptanalysis is.

But if it's correct:

Key doesn't influence the differential (it holds with 100% prob.) so whatever key I try while decrypting the last round, the differential on it's input is always as expected. Thus I can't eliminate any keys.

This seems suspicious to me - if a differential holds with 100% prob. the cipher is weak, right? Can a cipher be so weak that some attack doesn't work on it? It seems quite strange...

Usually differential cryptanalysis relies on something called the "wrong key randomization hypothesis", which is the assumption that decryption of the last round with the wrong key results in a random difference at the beginning of the last round, while decryption with the correct key will result in the expected difference with the probability of the differential (which hopefully is sufficiently high or low as to be distinguishable from a random difference).  However, if there is a probability one differential going through the entire cipher then by definition that means that decryption with any key will lead to the same difference.

You might try linear cryptanalysis instead.  A probability 1 linear characteristic through the entire cipher will give you 1 bit of the key with just a single known plaintext (Edit to add: poncho adds a good clarification - the probability 1 linear characteristic must involve at least one key bit to be useful for Matsui's algorithm one).  If for some reason there is no linear characteristic through the entire cipher, then you could try differential-linear cryptanalysis using that probability 1 differential through most of the cipher and a short linear characteristic at the end.


Why does PBKDF2 xor the iterations of the hash function together? The definition of PBKDF2 states that I obtain a derived key (1) by calling a pseudorandom function a bunch of times recursively:

  $U_1 = PRF(password, salt)$
  $U_2 = PRF(password, U_1)$
  …
  $U_n = PRF(password, U_n-1)$

The standard then defines the actual key material K as

  $K = F(password, salt, n)$

where F is $U_1 \oplus U_2 \oplus \cdots U_n$

I don't understand what the purpose of XORing the blocks together is. Assuming that PRF is a cryptographically strong function, how does XORing the blocks help? Why is $U_n$ not strong enough key material by itself?

The standard mentions that the blocks are XORd together “to reduce concerns about the recursion degenerating into a small set of values” but I guess I don't understand how that can happen since the password is being fed back into the function at each iteration.

If the recursion can degenerate into a small set of values, doesn't that mean there is a short cycle in the hash function? Isn't that a bad thing for cryptographic hash functions?

(1) Assume for simplicity that the key is the same length as the hash function output.

The XOR is indeed meant as a protection against hypothetical short cycles. For a given password $P$, the sequence of $U_i$ should make a "rho" structure: at some point in the sequence, a cycle is entered. For a $n$-bit hash function and random password, on average, there will be a single "big" cycle of size about $2^{n/2}$ and for almost all possible salt values, that cycle will be entered after following a "queue" of average length $2^{n/2}$. However, there can exist passwords for which the central cycle is smaller than that, and there can also be some extra small cycles. Finding a password which yields a small central cycle, or hitting a salt value which leads to an alternate small cycle, is overwhelmingly difficult, and no known example of that is known. Yet the PBKDF2 designers thought that the XOR was a cheap way to cope with such a risk: in effect, this means that the $U_i$ will depend on the queue as well as on the cycle itself.

There is a potentially important point here: when you apply the PRF, i.e. jump from $U_i$ to $U_{i+1}$, the space "shrinks": not all $n$-bit values are possible as output of the PRF. The further you go, the more the space shrinks, until you reach the "central cycle". This implies that if $F$ used only $U_c$ (the last $U$ value), then the space of the generated $n$-bit key blocks would be less than $2^n$; in other words, you would use a hash function with a $n$-bit output and you would not get your $n$ bits worth of security. The XOR aims at counteracting this effect.

Nevertheless, the PBKDF2 structure has never been, to my knowledge, proven in any way, so I would recommend using it only with a hash function which outputs $2n$ bits, if $n$-bit security is to be achieved. E.g., for 128-bit security (a sensible level), use SHA-256. Thus, the big central cycle size will be, by itself, sufficient, regardless of whether the extra XOR is really beneficial or not.


Anti-spamming hash-based proof-of-work? I'm planning to implement a public mailbox for receiving feedback, and I'd like to use hash-based proof-of-work to frustrate spammers.

First, we want to use 320-bit capacity Gimli permutation as the underlaying primitive for the sponge-based hash function, because

I don't want to make it hard for server to re-evaluate KDF each time there's a message,
it's not available on commodity hardware, which means someone will have to pay for silicon to have it accelerated,
less parameters to tune (capacity/rate and preimage length).

Second, for each message, there will be a time-based challenge (server will allow a small window for error) prepended to each message to be hashed and sent to deter pre-computation attacks.

However, there's a few things I'm not confident about. Namely:

Whats the advantages and disadvantages of using plain hash and KDFs when used in POW?
Besides replay, pre-computation, what are the other attacks that must be considered in designing a secure proof-of-work system?

I agree with e-sushi that PoW does work, however, the primitives used by HashCash are too friendly for adversaries. As the OP pointed out we need contextually bound challenge and response that cannot be reused or precomputed.

We cannot prevent the work from being delegated; but we can make the PoW much more expensive than an ASIC friendly hash function. The argon2 KDF family is well suited for this, specifically argon2d which was designed for PoW; whereas argon2i was designed for secret passwords.

The memory and cpu parameters may be tuned individually such that no real users are too inconvenienced and the server is not overwhelmed when under load.

Instead of requiring the PoW be computed 100% of the time, you might only require it while the server is under load. This may not apply to your use case.

  Whats the advantages and disadvantages of using plain hash and KDFs when used in POW?

Advantages:

Increase adversary costs

Disadvantages:

Inconvenience users (less than a captcha)
More code running on the user's client, inconveniencing users who opt to disable JavaScript
Drain the power of user's mobile devices
Adds additional computational costs, increasing power consumption for minimal benefit

  Besides replay, pre-computation, what are the other attacks that must be considered in designing a secure proof-of-work system?

Remote delegation to unsuspecting users (like recently cryptominers on government sites)
Deniable of service. The adversary may produce fake solutions without trying. The server still performs the computational costs.

Alternatives:

Enable the user to send money as a micropayment. This scale will require a high performance ledger, or better many ledgers. On the other hand, an adversary may have enough money to burn, possibly stolen.


Crypto lib that use files instead of passphrase I would like to program an application to allow people to encrypt files without using a password or pass-phrase but an arbitrary long file.

I'm searching for a library that allows me to safely create a front-end.

Example: user 1 on PC1 encrypt the picture selfie.png (size 2 MB) using the key-file ketfile.foo (size 2 MB), then send  this file to user2 on PC2 that use keyfile.foo to decrypt selfie.png.
Of course I assume that the keyfile.foo was "securely" sent.

This idea come from the Vernam Cipher "Unbreakable" cipher.

Note: I won't recommend a specific library for these, because this would be off-topic and the risk would be there that this gets outdated sooner than later (especially as soon as CAESAR finishes).

This is a very standard solution to the authentication problem although usually one does do both (e.g. passphrase and keyfile).

On the conceptual level any library exposing some sort of KBKDF or PBKDF and a decent encryption mechanism is sufficient.

What you do is simple and clear: You look at your chunk of data and extract derivation paramters from it (they are associated data), then you ask the user for the file name and completely parse it into your PBKDF / KBKDF of choice. From this you derive an encryption key and a nonce / IV and you're good to go to apply authenticated encryption on your data

You should use a password based key derivation function (PBKDF such as Argon2, scrypt or bcrypt) if you suspect the file to be low entropy (less than $2^{128}$ plausible possibilities) and use a key based key derivation function (KBKDF such as HKDF or KDF2) in all the other cases. For the actual encryption AES-EAX is your mode of choice for files that get larger than 60GB and AES-GCM for anything smaller.


byte length and offset for k3d3/ed25519 byte[] variables? I've discovered for myself that java's BigInteger is very slow, so I'm trying to weakly optimize this java implementation of ed25519 which I will fork and post if successful by substituting BigInteger with jscience's LargeInteger.

I'm almost done converting all of the BigIntegers to LargeIntegers, but I still need an equivalent to BigInteger's and, and I need to know how long some byte[] variables should be and their offsets to use valueOf with byte[]s.

I could keep some of the existing code and merely convert BigIntegers to LargeIntegers, but I'd prefer to fully replace BigInteger.

"length - the maximum number of bytes to read." sounds like I should use .length of the byte[] to be converted.  Is that correct?  If not, what should be used?

"offset - the offset at which to start reading the bytes." sounds like I should use 0.  Is that correct?  If not, what should be used?

I'm 100% new to binary and cryptography.

Almost every Java .valueOf(byte[] s, int offset, int length) has the same meaning:

s is the array to read from.
offset is the location in the array to start reading from (inclusive).
length is the number of bytes to try and read - "try" because the array may not be long enough to have that many bytes from offset.

Remembering that Java arrays are zero-indexed, .valueOf(z, offset, length) will read from every byte from s[offset] to s[offset+length-1]. However, if offset+length > s.length, then every byte from s[offset] to s[s.length] will be read.

As an example, if we have byte[] s = new byte[] {10, 20, 30, 15, 4}, then:

LargeInteger.valueOf(s, 0, 5) will use all five bytes.
LargeInteger.valueOf(s, 1, 3) will use bytes {20, 30, 15}.
LargeInteger.valueOf(s, 3, 7) will use bytes {15, 4}.

In Ed25519, the length and offset you use will depend on what part of the byte[] you need to access. For example, initially you take a seed k and hash it to get h = H(k), which you then split into a LHS and RHS. You could convert the LHS and RHS independently into LargeIntegers with LargeInteger.valueOf(h, 0, b/8) for the LHS, and LargeInteger.valueOf(h, b/8, b/4-b/8) for the RHS.

So the end answer is, in most cases yes, you will use offset = 0 and length = s.length. And it looks like you can directly replace BigInteger.valueOf() with LargeInteger.valueOf().


Hard discrete logarithm problem I want to give an introductory talk on Diffie-Helman key exchange. Along the way, I will mention that there exist groups, like $(\mathbb Z/p\mathbb Z)^\times$ for which it is believed that the discrete logarithm problem (DLP) is hard. Trying to anticipate a question from the audience, suppose someone asks:

  Are there groups for which the DLP is surely known to be hard?

What is a good way to answer such a question, and in the case of no asnwer, how do I convince the audience that the Diffie-Helman key exchange is still worth the hustle?
I understand this is not good question to ask here, so I bring my honest apologies.

I think this is a very good question, and an interesting one. Not sure if my answer will go in the direction you meant.

Generally when first discussing the DLP for groups, you'd want to find an attack which uses only the most basic properties of a group. That is, you think of having a black box into which you can feed any two group elements, and it will compute the group operation on them. You see the result, but have no idea how it was computed.

Now suppose we have such a black box group, and assume that it is cyclic of prime order $r$. Then this paper proves that you need on average at least $O(\sqrt{r})$ calls to the black box to solve the DLP. For those groups we are sure that the DLP is hard, for some definition of "sure" and "hard".

This may be somewhat counterintuitive. Note that for a prime $p$, $\mathbb{Z}/p\mathbb{Z}$ with addition is a prime order group for which the DLP is trivial. Also for every black box group $G$ such that $|G|=p$ there exist an isomorphism $\phi:G\cong \mathbb{Z}/p\mathbb{Z}$. The problem is that we cannot reduce the problem from the black box group $G$ to $\mathbb{Z}/p\mathbb{Z}$, since we cannot compute the isomorphism $\phi$ efficiently.


is the XOR of PRG outputs a PRG? I am going through the course http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html, as it has a good lecture notes. I found exercise 2 solution a puzzling statement: it says that $G^\prime (x_1 , x_2 ) := G(x_1 ) ⊕ G(x_2)$ is a PRG, though I'm not sure why it is always the case. I get the intuition that xoring pseudorandom string with another pseudorandom string is also pseudorandom, though the formal proof is unclear to me.

Is it also true to PRG with any stretch $l$?

This follows essentially from the security of the one-time pad: if you have some arbitrary distribution $D$ over a group $G$, and the uniform distribution $U$ over the same group $G$.  If $D$ and $U$ are independent, then sampling $x\gets D$, $y\gets U$ and computing $z=x\cdot y$, the resulting $z$ is distributed uniformly over $G$.

So, in fact, $G'$ doesn't even have to be $G(x_1)\oplus G(x_2)$; something like $B(x_1)\oplus G(x_2)$ for some arbitrary stretching function $B$ which doesn't necessarily have to be a PRG would be also fine.


What is the probability of a SHA-512 hash containing both digits (0-9) and alphabets (a-f) all the time? Quite curious to know if ever a SHA-512 hash will contain only digits or only alphabets. Thanks in advance.

A cryptographic hash outputs a string of bits.

Whether or not it appears as digits/alphabet letters is a matter of how the output is encoded and presented to the user.

You could easily ensure that nothing but digits/alphabet letters in what is presented to a user by performing base conversion on the output, from a base-2 system (binary) using the symbols $0$, $1$ to a base-$n$ system using arbitrary symbols.

For example, If you encode the output in the hexadecimal number base, a user will see only hexadecimal values (0-9 + A-F).

If you wanted to operate under the assumption of a given number base, you would do some math to quantify the probability of a given subset of symbols occurring in the output - but you have to pick a specific encoding first before you can do so, as the choice of encoding will drastically chance the probability.

For example, consider an encoding that uses (0-9 + A-Z + !) - The probability of sha512 outputting a string with only the symbols (0-9 + A-Z) is relatively high. While in the opposite case, if the encoding only uses (! + ?), the probability is non-existent.


Perfect secrecy of a crypto system Suppose we have the following crypto system: $P = C = K =
\{0, 1, . . . , n − 1\}$, $E_k(x) = (x + k) \bmod n$ and $D_k(y) = (y − k) \bmod n$. Prove that the crytosystem has perfect secrecy. Perfect secrecy means that the ciphertext does not leak any information about the plaintext (i.e., $P(X = x) = P(X = x \mid Y = y)$).

What you are describing is One-Time-Pad encryption, and yes it does have perfect secrecy.

Note that for any ciphertext $y$ there is exactly one key $k'$ for each possible plaintext $x'$ so that $E_k(x') = y$. So if you choose the key uniformly at random the ciphertext gives no information on the plaintext, because any plaintext is equally likely.


Find an example of a lattice such that LLL algorithm can't find the shortest vector of the lattice, satisfying I want to find an example of a basis of a lattice of dimension $n$ such that LLL algorithm can't find the shortest vector of the lattice, and such that the shortest  vector of this lattice, say $b=c_1b_1+\cdots+c_nb_n$, has small $c_i$, i.e., $c_i \in \{-r,\ldots,r\}$ with small $r$.

Note that $b_i \in \mathbb{Z}^n$ and $c_i \in \mathbb{Z}$.

Such example must satisfy $\log_2(2(r+1)) \cdot n \leq 15$, say $n=5$ and $r=4$.

The idea here is to have a treatable value for $2^{\log_2(2(r+1)) \cdot n}$.

I can't find any lattice satisfying this.

Thanks in advance.

Bruteforce appears to work well enough. The following Sage script finds an instance quickly:

from sage.libs.fplll.fplll import FP_LLL
from sage.libs.fplll.fplll import gen_uniform

n = 5 # dimension
q = 16 # size of matrix entries

while True:
    M = gen_uniform(n, n, q)
    L = M.LLL(delta=0.999)
    S = FP_LLL(L).shortest_vector(algorithm='proved')
    if min([ row.norm() for row in L]) != S.norm():
        break

print M
print L
print min([ row.norm() for row in L])
print S
print S.norm()

As a concrete example, the lattice (column vectors)
$$L =
\begin{pmatrix}
16252&  5541& 48769&  2593& 22395\\
 2404& 46418&  5335& 59631& 29390\\
41816& 27475& 56363& 50417& 62371\\
27419& 53783&  1412& 42344& 55983\\
62503& 52719& 22160&  3940& 64256\\
\end{pmatrix}
$$
can be reduced with LLL ($\delta = 0.999$) to
$$B=
\begin{pmatrix}
  1855&  31849 & -6182&  -5480&  16007\\
 23160& -24484 &  2259& -11807&  10586\\
 29450&   -465 &  8167&   2997& -19059\\
 10069&  -8429 & 24671& -21117& -18320\\
  4328& -17879 & 30280&  29190&  24708\\
\end{pmatrix}
$$
Yet, none of those vectors is the shortest. The shortest vector is $$(-19381, -7964, 16504, -24114, 739),$$ which can be written as $2L_0 - L_1 - L_2 + 2L_3 - L_4$, where $L_i$ is the $i$th row of $L$. So we have $n = 5$ and $r = 2$.


is it possible to generate IV for a given block with AES GCM So, I have a java CipherInputStream encrypted using AES/GCM/NoPadding (Bouncy Castle). I can decrypt the stream just fine with the IV (12 bytes) and the AES key.

Is there any way I can decrypt the stream if I start reading it from some random byte?

Can I generate a correct new IV knowing the original one, byte im starting to read from and total stream length?

Note: This answer is entirely theoretical and may not be implemented in your favorite software library.

  Is there any way I can decrypt the stream if I start reading it from
  some random byte?

Yes and no.
Yes, you can jump to some random byte in a AES-GCM cipher text and decrypt it, by just applying the underlying CTR decryption, i.e. by incrementing the counter appropriately.

No, you really shouldn't do that, because this way you can't verify the tag, because this requires parsing and processing of the entire cipher text (including the IV). And if you can't verify the tag, the cipher text can be altered trivially without you even knowing it.

Yes and no, you can just verify the tag, as it's a function of the ciphertext and that quite fast and afterwards, if the tag is valid, decrypt only the bytes that interest you. The pure verification is as couple of times faster than the full verification and decryption and hence you indeed would save some computational ressources.


Perfect Deniability of a MAC Overview
One feature that is often underlooked of the One-Time Pad is its perfect deniability.  i.e. If Alice sends a message to Bob that is seen by Eve then if Eve later goes to Alice with the ciphertext and tries to force Alice to disclose her key Alice can "make up" a key and Eve can't prove that the key Alice provided was the real key or not.
One downside of the OTP is its malleability.  So a common suggestion is to append a MAC so Bob can see if the message was tampered or not.
I am curious if it was possible to construct a MAC such that if Eve tries to retrieve the key from Alice, Alice can "make up" a key for the MAC and Eve can't prove that that was the real key.  i.e. Given a plaintext and MAC Alice can construct a real looking "fake" key in polynomial time.  For example HMAC will not satisfy this property because otherwise it would be prone to preimage attacks.
Is this a good definition for perfect deniability of a MAC?
Applications

Realistically none since the OTP is impractical.
If Alice and Bob are on an anonymous network (example TOR) then Eve cannot prove who sent the message, but Bob can confirm it was sent from Alice and if it was tampered with
If Alice posted this in a public place (like a forum, blockchain or public bulletin board) nobody can prove Alice posted it (assuming she posted it anonymously) but Bob can confirm it was sent from Alice and if it was tampered with
Can you think of other applications?

A Carter-Wegman -style MAC gives you easy deniability when you use a one-time pad to encrypt the universal hash. You can compute a hash for your fake message and choose the key accordingly, just like you do with the one-time pad that you use to encrypt the message contents.

This is actually available widely to programmers: NaCl has crypto_onetimeauth which uses Poly1305 (a polynomial evaluation MAC) with the latter half of the single use key used as a one-time pad. To get the same MAC value for another message you can just compute the MAC, then modify the pad part to match your target.

Not all uses of Poly1305 give you perfect deniability, however. The ones where the key or pad comes from AES (Poly1305-AES) or another cipher (e.g. crypto_secretbox) likely do not because you cannot freely choose the value of it without affecting message decryption or the authentication of other messages.


Getting a key size of DSA/Elgamal certificate I've tried to get a public key size of DSA/Elgamal PGP certificate. Using the Cleopatra I find out that there is actually two public keys - one with DSA with key size 1024 bits and the other Elgamal with 2048 bits.
Now my question is which of this key sizes is the actual key size for this certificate and more importantly, why?

It's extremely likely that 1024 is the master key size as authentication and signing are usually the main purposes of PGP. The key used for encryption is generally valid for a shorter time and is therefore a subkey of the master key. So both 1024 and 2048 bit public keys are included in the PGP certificate.

Note that the key size for encoding the key will be larger and the key strength (compared to e.g. an AES key) will be much less.

Both 1024 and 2048 bit keys are rather small for common purposes. It is highly advisable to upgrade to larger, RSA based keys. For more information about key sizes and their strengths, please take a look at https://keylength.com.


Understanding Lindell's proof of (semi-honest) oblivous transfer In Lindell's tutorial "How to simulate it" [2016/046], section 4.3, he gives a semi-honest protocol for oblivious transfer, based on enhanced trapdoor permutations and a corresponding hard-core predicate. I don't understand some details in the proof and hope somebody can explain it to me.
He gives the following definition: $B$ is a hard-core predicate of a trapdoor permutation $f_\alpha$ if:

for every non-uniform PPT adversary $A$ there exists a negligible function $\mu(n)$ such that for all $n$:
$$
\Pr[A(1^n, \alpha, r) = B(\alpha, f_\alpha^{-1}(S(\alpha; r)))] \leq \frac{1}{2} + \mu(n),
$$

where $\alpha$ is an index in the collection of functions $\{f_
\alpha\}$ and $S$ samples (almost uniformly) in the range/domain of $f_\alpha$.
Protocol 4.2 computes OT-functionality $((b_0,b_1), \sigma) \mapsto (\lambda, b_\sigma)$ as follows:

$P_1$ sends index $\alpha$ of a trapdoor function $f_\alpha$, where $P_1$ knows the trapdoor but $P_2$ does not.
$P_2$ samples random $x_\sigma$ and $y_{1-\sigma}$, computes $y_\sigma=f_\alpha(x_\sigma)$, and sends $(y_0, y_1)$.
$P_1$ uses the trapdoor to compute $x_0$ and $x_1$, then sends $B(\alpha, x_0) \oplus b_0$ and $B(\alpha, x_1) \oplus b_1$.
$P_2$ computes $B(\alpha, x_\sigma)$ and can therefore output $b_\sigma$.

Part of the proof of security (Theorem 4.3) constructs a simulator $S_2$ for corrupt party $P_2$ (the recipient), by showing that if you can distinguish the output of $S_2$ from that of $P_2$, you can use that to construct an algorithm $A$ that breaks the assumption that $B$ is a hard-core predicate, summarized as follows:

Algorithm $A$ [...] receives $(1^n, \alpha, r)$ for input. $A$'s aim is to guess $B(\alpha, S(\alpha; r))$.

However, there is no guessing because you can simply compute $B(\alpha, S(\alpha; r))$, right?
The final equation of the proof computes $\Pr[A(1^n, \alpha, r) = B(\alpha, x)]$, but it is unclear to me here what $x$ is in this expression (the preceding paragraph only mentions how to sample $x_\sigma$).
Given the definition of the hard-core predicate, I would have expected to see $f_\alpha^{-1}$ in this part of the proof.

The answer is that it's me and not you. There was a typo in the proof and indeed $x$ referred to here is $f^{-1}_\alpha(S(\alpha,r))$. I have made the change in the proof and updated the ePrint paper. Thank you for pointing out the typo.


Key derivation from a random seed The main problem is to use a block cipher to generate a random key.

I would like to generate 256-bits key which can be as random as possible. I generate it in the following way:

Pick a plaintext $p_0$ of 64 bits and a 256-bit key $k_0$. ( can be given from keyboard as seed)
Implement a cipher which goes from 64-bits to 64-bits.
Encrypt $p_0$ with this cipher using $k_0$ to get $c_0$. (Assuming that the cipher is a pseudo-random permutation then $c_0$ is pretty random)
Set $p_0 = c_0$ and repeat the process say for 1000 times.
At the end use the last 4 encrypted messages of the loop to fill the key $k_0$ and take this as the new key.

Is this method random enough? Maybe there is a problem as I'm using all time to encrypt $k_0$? Which is the best implementation to get a really random key?

What you are describing is called output feedback mode, a mode of operation for block ciphers to create a stream cipher. You are discarding the first 996 output blocks and are using the following four ones.

In general, your algorithm (as any algorithm) can't produce randomness, just stretch existing randomness in a way which might look more random.

If there are $N$ possible values for $p_0$ and $M$ possible values for $k_0$, we get at most $N·M$ possible different values for the final key – no algorithm can do better, arguably.

If the key $k_0$ is fixed (or known to the attacker), she can just as well as you calculate the whole series and get the result from $p_0$ (or even, if she had only one block of the output, calculate $p_0$ and the other blocks of the output).

The moral: don't try to invent your own scheme.

For deriving a key from another, already high entropy key (e.g. to use different keys for different uses), use a key derivation function. Those are often based on a MAC or a hash function, use the key and a "personalizer" as input, and create another key.

For deriving a key from a password (i.e. a low-entropy key which a human can memorize), we want a slow key derivation function. These take a password and a salt (different for each use, but doesn't need to be secret), do a lot of work(configurably much), and produce a key. Examples are PBKDF2, bcrypt and scrypt.


Why is Diffie-Hellman Insecure If Order of the Generator Has Only Small Prime Factors? In this post from security SE, Tom Leek mentioned that, for Diffie-Hellman to be secure order of the group $g$ should have a prime factor at least $2k$ bits long, where $k$ is the security parameter.

Why is it so? Order of $g$ has to be large, otherwise, the discrete log would be easy. But I couldn't see any other reason why the order of $g$ should have a large prime factor. And why should it be at least $2k$ bits long (instead of $k$ bits long)?

It also says the private keys $a$ and $b$ should also be $2\text{k}$ bits long. They should be large, otherwise, the discrete log would be easy. But why should they be $2\text{k}$ bits long, instead of $\text{k}$ bits long?

But I couldn't see any other reason why the order of g should have a large prime factor.

Let $p$ be the Diffie-Hellman modulus. The order $q$ of the subgroup generated by $g$ must have at least one large prime factor to prevent the use of Pohlig–Hellman algorithm. The complexity of this algorithm $$\mathcal O\left(\sum_i {e_i(\log n+\sqrt p_i)}\right)$$ where $e_i$ is the power of the prime factor $p_i$. In short, the larger one of the $p_i$s the higher complexity.

  Why should it be at least 2k bits long (instead of k bits long)?

The $\text{k}$-bit is the required for the target security. The generic attacks on Discrete logarithm problem have $\mathcal{O}(2^\text{k/2})$ complexity thus you need to start at least from $2\text{k}$.

Note: The safe primes $p = 2q+1$  guarantees that the order of $g$ is $q$ or $2q$.

  It also says the private keys a and b should also be 2k bits long.

No, the $2\text{k}$-bit for the choice of $a$ and $b$ is not necessary. As you can see from this answer;

  The standard Decisional Diffie-Hellman assumption holds for the case that $g^{x_a}$ and $g^{x_b}$ are uniformly distributed in the group (which should be a prime-order subgroup).

There is also a linked article (Short Exponent Diffie-Hellman Problems) for this issue in the comments of this the answer.


What are the inputs of the AES key wrap algorithm? I have trouble understanding inputs for AES key wrap algorithm as it is explained in section 2.2.1 of RFC3394.

Context:

I have a data encryption key (DEK) for AES-128 with CTR, which is used to encrypt a database file on a mobile device. DEK is device specific and has limited lifetime (1 year) as key rollover is applied. DEK is generated with help of salt and secret values generated on the server when authenticated user provides some random value (constant as long as mobile application is installed).
I have a key-encryption key (KEK, AES-128), that is derived from user's passphrase and is used to encrypt the DEK (encrypted DEK is stored in plaintext).
DEK and KEK never leave the device.

Above scheme helps me keep DEK unchanged in case user changes her passphrase and allows users working with the application in offline mode (correct passphrase recreates KEK which decrypts DEK which next allows working with database).

My question is how should I apply AES key wrap? The RFC states:

  The inputs to the key wrapping process are the KEK and the plaintext
     to be wrapped.  The plaintext consists of n 64-bit blocks, containing
     the key data being wrapped.

What are plaintext and KEK here? My DEK is plaintext and my KEK is the KEK? Or it should be passphrase (plaintext) and my DEK as KEK? I'm pretty confused and would appreciate any guidance here. Thanks!

The DEK is indeed the "plaintext" and the KEK, derived from the user's pass phrase in your case, is the KEK.

A passphrase is not a key and should never be directly used as a key; you should use a password based key derivation function (such as PBKDF2) to derive a key from a passphrase.