What happens for factoring algorithms if P=NP? If someone ever demonstrates that P=NP, will it give us a polynomial factoring algorithm, or will it only tell us that such an algorithm exists, but we still have to find it?

Proving P=NP would not necessarily give you an algorithm, because there are many different methods to prove something (i.e. Direct proof, Proof by contradiction, etc.).

But it is shown that if you were to find a polynomial time algorithm to solve a NP-complete problem that you could modify that algorithm to solve all NP-problems, including the Integer factorization problem.


How do I encrypt a long message using ElGamal encryption correctly? According to ElGamal encryption, in order to encrypt a message I need to generate a shared secret s and after that I am to calculate c1 and c2 that are the final encrypted data. But what if my message is much longer than the bitness of the encryption system? I could split the message into many chunks and encrypt them separately.

Would it be correct to use the same shared secret for all these chunks?
Or I have to generate separate shared secrets for each chunk?

The first option would be preferable because it is much less expensive, but naively it looks less secure. Does this option have any vulnerability? Is there any research where I could read about it?

As I mentioned in my comment, how you are proposing to use El Gamal has little to do with how we use it (or any public key encryption system) in practice.  However, I can modify the question slightly in a way to make it relevant:

But what if have multiple messages I want to encrypt?

Would it be correct to use the same shared secret for all these messages?
Or I have to generate separate shared secrets for each message?

In your question, you were splitting up one message into several; however, someone could equally well want to encrypt several independent messages to the same public key.
Now, if we were to use the same shared secret, we'd give (for the messages $M_1, M_2, ,,., M_n$), we'd give the adversary the values $S \cdot M_1, S \cdot M_2, …, S \cdot M_n$).
Now, with encryption, we want to limit any information the attacker can obtain from the ciphertexts to what he already knows.  Now, this is an issue with reusing the same shared secret; for example, if the attacker already happens to know (or guess) $M_1$ (or in the split-up message case, he already knows a part of the original message), we'd like him not to be able to leverage that to learn anything else.  However, with knowledge of $M_1$, he could recover $S$; with that, he could recover the plaintexts of all the other messages (or in the split-case, the entire long message), and so he does learn far more than what he started with (which was knowledge of $M_1$).
Because of this (and other attacks that allow the adversary to recover $M_1 \cdot M_2^{-1}$, also more information than we'd like him to have), we really need an independent shared secret for each message.


Can you identify the public key used to encrypt something? If I encrypt a string with a public key, does the encrypted ciphertext reveal the public key I used to encrypt it? Basically, I don't want anyone to know who the ciphertext is addressed to.

I'm thinking about RSA, but also interested in DSA. The ciphertext is not known.

An RSA ciphertext won't reveal who it is encrypted to, but it might reveal some information about who it isn't.

We'll assume that everyone has an RSA key of the same length (e.g. 2048 bits).  Now, a public key consists of a large modulus N (and an exponent, that's not important for this discussion); a ciphertext consists of a value C between 0 and N-1.

Suppose Alice has a public key $N_{alice}$ and Bob has a different public key $N_{bob}$.  If we were to encrypt a message with Alice's public key, that generates a value $C < N_{alice}$.  Now, if $N_{bob} < N_{alice}$, then it is possible that $C \ge N_{bob}$; if that happens, someone listening in can immediately deduce that $C$ was not encrypted with Bob's public key.

Now, this isn't an inherent problem with RSA; if Alice and Bob cooperated, they could generate keys $N_{alice} \approx N_{bob}$ (say, agree in the first 200 bits); this would make it quite improbable that an attacker would be able to rule out a particular public key,  This doesn't reduce the security of RSA, but it is not generally done.

As for DSA, well, DSA doesn't encrypt messages.  If we look at DL-based encryption systems (El Gamal, IES), we see that the ciphertext doesn't reveal the public key (assuming that the various public keys use similar parameters; for example, the same group).


Security relevance of random factor in Paillier In the Paillier cryptosystem [1] the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$.

The additive-homomorphic property of the system shows that
$g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1r_2)^n = g^{m_1+m_2} r'^n\mod n^2  = m_1 + m_2 \mod n$

so the resulting $r'$, that would be needed to encrypt $m_1 + m_2$ to the identical result of the homomorphic addition, would be: $r_1 \cdot r_2 \mod n^2$

Supposed now one were to homomorphically sum up the encryptions of a couple of messages from a limited publicly known set of plaintexts $S=\{0, 1\}$. If one then were to proof the correct encryption of the sum by disclosing the encrypted sum, the plaintext sum and the resulting random factor $r'$ for the encrypted sum - would this provide any useful information about which summand encrypts which plaintext message?

Assuming "revealing r" would provide any information about the summands of a homomorphically added sum. Would it help to use primes as random factors for the encryption of the summands? I mean an attacker then would have to find an efficient way to factorize the resulting $r'$.

Is there a way to turn "revealing r" into an interactive version involving a challenge? Would this solve the problem that by passing on $r'$ the proof becomes transferable which may be an undesired property?

[1]
Pascal Paillier -
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Link

Easy solution is to use a large $r$. You are correct that if the $r$'s were small primes we would have a problem, ergo randomness is essential. However, if the $r$'s are generated randomly then their product doesn't help in guessing one. (Think about guessing $x,y$ random given $x+y$ in an abelian group).


Range query on array of encrypted data using homomorphic encryption Given an array or database entries of encrypted data is it possible given a min/mix value to get a range of encrypted entries? The min and max values would also be encrypted.

There is order-preserving encryption made by Boldyreva. That is given $a$ and $b$ with $a>b$ then $\operatorname{OPE}(a) > \operatorname{OPE}(b)$ where the OPE is the order preserving encryption.

OPE has already many implementations and OPE used by CryptDB to execute the order based queries to test their capabilities and benchmark on TPC-C queries.

Note that OPE leaks information about the plaintext. An adversary can guess approximately the position of the plaintext of a ciphertext lives in the plaintext space.


Inverse MixColumns Operation of AES I am aware that MixColumns is a mixing operation which operates on the columns of the state, combining the four bytes in each column. So we multiply our state with the special matrix. To multiply, we’re computing many dot products. And for each dot product, we’re multiplying bytes as Galois fields $\pmod 2$, then reducing the answers $\bmod$ the magic polynomial: $x^8+x^4+x^3+x^1+x^0$.

Thankfully, the entire task can be greatly sped up by using a few look-up tables. The multiplication matrix consists of Galois fields for $1,2,3$. So we can pre-compute the results of all 256 eight-bit Galois fields (the possible bytes in our state) multiplied by these values.

How will I implement the inverse MixColumns for decryption process?

MixColumns implements a matrix multiplication, so InvMixColumns is the multiplication by the inverse of that matrix. Thus, it boils down to computing the inverse of the matrix. It can be tedious to do by hand, but it involves only straightforward computations. Alternatively, look up the AES standard itself (FIPS 197): the inverse matrix is spelled out explicitly in section 5.3.3.

More generally, FIPS 197 is quite readable (as standards go) and if you want to know how AES works, it is recommended to read it through (and in particular section 4, that gives some details on the underlying mathematics).


Is there a way to provide proof of batch RSA security? Suppose we have two encrypted messages with two different public key issued from the one server. There is a client who wants to send these to messages to the server.

In the middle there is an adversary, who eavesdrops all the communications, so he already got the two encryption keys and the two encrypted messages.

According to batch RSA, the adversary can recover the encrypted messages without the need to use the private key to decrypt the messages. Can anyone explain how can we prove that batch RSA is secure in such a scenario?

RSA public key encryption should always be used together with a randomized padding scheme, such as OAEP or PKCS#1 v1.5. Only if you don't use such padding and encrypt the same message with a sufficiently high number of different public keys, an adversary might simply apply the Chinese Remainder Theorem to the cipher texts, and then calculate the E:th root of that value (E being the public exponent used by the RSA public keys).


What is the key length of shared secret by Curve 25519 ECDH Both parties uses Curve 25519 key pairs for ECDH key exchange. What is the key length of shared secret after ECDH?

In this paper you can find nearly everything about Curve25519. In the section "Specification" you find the answer:

  {Curve25519 secret keys} × {Curve25519 public keys} →
  {Curve25519 public keys}

this is the function, which is calculated for a key exchange. So the shared secret key has the same properties as the public keys:

  { $q: q \in ${ $0,1,...,2^{256 - 1}$}}

This matches, what Bernstein says in the introduction: The key length (for both public and private) are 32 byte long. And in that format they are stored. In other words every key is 256 bits long.

In this post you see an example for these keys.


Is there a way to generate a password from another but those 2 will have no relation? For example I have the password X and I want to encrypt 2 different things. Even if one of them was stolen due to a keylogger, other will be completely safe. I wonder how safe something like this would be if the master key is completely random, secure and unknown. Also with what algorithm, program would i be able to do this on Linux systems?

I think something like this is possible actually because of Electrum's key generation method. It uses one master private key to generate all the addresses and private keys.

Using the HKDF algorithm would work:

prk = HKDF-EXTRACT(salt, master_key)

Key1 = HKDF-EXPAND(prk, "info 1", digest_len)
Key2 = HKDF-EXPAND(prk, "info 2", digest_len)

This creates two keys that are generated from the master key, but given Key1, someone else wouldn't be able to generate Key2, as they don't know the master key.


LUKS multiple key slots - what's the intuition? LUKS volumes have the ability to allow multiple independently usable passwords, as explained here:
[https://code.google.com/p/cryptsetup/wiki/FrequentlyAskedQuestions]

The intuition behind basic encryption with a single key is pretty straightforward.

ciphertext = BIG_FUNCTION(plaintext, key)
plaintext = BIG_FUNCTION^(-1)(ciphertext, key)

Can anyone explain how a LUKS volume can permit independently usable passwords? I'm just looking for the intuition - not necessarily a detailed explanation of how LUKS in particular handles this.

Roughly your password is used to encrypt a MasterSecretKey. Then you use this MasterSecretKey with a symmetric algorithm to encrypt or decrypt your data (the disk sectors).
They eight key slots in LUKS are eight different encryptions of the same MasterSecretKey under eight different passwords.

See also this image:  (original web page: http://auto0.info/secret-messages-download-red-hat-fedora)
(original image http://nnc3.com/LM10/Magazine/Archive/2005/61/065-071_encrypt/images/fig3-partition-header.png is not more available)

Actually LUKS does not encrypt the MasterSecretKey with a password but with a key, generated with a PBKDF.

A similar approach is used by GPG when you send a message to a set of distinct recipients.

This is usally know as KEM/DEM paradigm: Key Encapsulation Method/Data Encapsulation Method and it is the standard method when you use public key to encrypt something.


Is there any encryption method (theoretical) that could process instructions on encrypted code? Is there anything such as an encrypted Turing machine? More precisely, is there any (encryption) system such that given:

a Turing machine: T
a public/private key pair

there exists a Turing machine T' (or something Turing machine like) where the tape, states and so on are encrypted using (this method together with the) the public key and such that if, both T and T' are let run for the same number of steps, the state and tape of T' decrypted with the private key equals the state and tape of T.

ie. is there some encryption where one can apply basic operations on the encrypted data?...

Yes.  It's called Fully Homomorphic Encryption.


Definitions of secrecy I found terms like "forward secrecy", "future secrecy", "backwards secrecy" and "perfect forward secrecy" and I would like to know their definitions and to understand the differences among them.
I found several confusing definitions online, especially mixing up the meanings of forward secrecy with perfect forward secrecy, or the meanings of forward with backwards secrecy.
Thank you.

In cryptography, forward secrecy = perfect forward secrecy, backward secrecy = future secrecy.

First, recall some background. The above terms are often discussed in the setting of secure channel establishment protocols, e.g., TLS, Signal, etc. In such a protocol, consider two parties, a client and a server, try to communicate with each other securely. The server (and the client if client-authentication is needed) is granted a certificate that shows its public key, and the server (and the client) itself knows the corresponding private key (a.k.a. the long-term secret). They essentially use the long-term secret and some randomness to compute and share a secret session key (only used within a session) and establish a secure communication channel based on the session key, e.g., using an authenticated encryption (with associated data) scheme.

Forward secrecy means if the long-term secret (together with the party's current session key and all other secret states) is corrupted (i.e., revealed), then the past sessions are still secure, i.e., the confidentiality of the previous messages exchanged between the client and the server is not compromised. I think people call this forward secrecy because they want the encrypted messages in a session to be secure even if "forward" long-term key corruption occurs. TLS is an example that achieves forward secrecy with Diffie-Hellman key exchange.

Then, as you may guess, backward secrecy guarantees the "opposite direction" of forward secrecy. In other words, this security guarantees that the encrypted messages in a session should remain secure even if "backward" long-term key corruption occurs. People more often call this future secrecy perhaps because they want to emphasize that even if at some point the long-term secret (together with the party's current session key and all other secret states) is corrupted the future messages can still be secure (if the previously corrupted party somehow becomes "clean" again). (I agree that the terms are a mess because "future secrecy" looks and sounds almost the same as "forward secrecy".) Signal is an example that achieves backward secrecy with the Double Ratchet Algorithm which can self-heal itself soon after corruption.


Attacks on MICKEY 2.0 Stream Cipher I would like to know if there are any known attacks, besides from side-channel attacks (differential fault attack, correlation power analysis, template attack), against MICKEY 2.0 or MICKEY-128 2.0.

I already did a deep research on the web using several scientific databases, but I did not found anything besides the above mentioned.

No, there do not seem to be any real attacks beyond those.

Note that MICKEY 2.0 is part of the eSTREAM portfolio and the one portfolio cipher that was very successfully attacked (pdf), F-FCSR, was removed (pdf) quickly thereafter. So you might expect MICKEY to be removed as well if a good enough attack is found.

The second review (pdf) of the portfolio from 2012 says:

  It has been noted, e.g. Gierlichs et al [29], that straightforward implementations of the MICKEY ciphers are likely to be susceptible to timing or power analysis attacks. Otherwise there have been no known cryptanalytic advances against MICKEY 2.0 or MICKEY-128 2.0.


Is XOR adequate for encrypting truly random data? It is well-known that the two-time pad is very insecure.  However, it seems unexploitable in the case where the plaintext is indistinguishable from random (ex. symmetric keys).

Is this property useful?

Note: I don't plan on using this in production.

By two-time pad I assume you mean using a one time pad key to encrypt two messages. Lets say $K$ is the key and $m_1, m_2$ are your messages. Then from the ciphertexts $c_1 = m_1 \oplus K$ and $c_2 = m_2 \oplus K$ an adversary could trivially learn information such as $x = c_1 \oplus c_2 = m_1 \oplus m_2$. Whether or not this information is "exploitable" may be application specific (in general it is very hard to say what "exploitable" should mean). However, the fact is that you are leaking information on your secret messages and you should be very careful.

Take the following example of how this could go very wrong: Say I want to send two random 128 bit strings $m_1$ and $m_2$ to a friend who should then use $x = m_1 \oplus m_2$ as an AES key. If I send $m_1$ and $m_2$ using regular OTP then there is no problem. Using the two-time pad, as described above, the AES key is revealed.


Is it possible to recover an RSA modulus from its signatures? Let's say that you have some small number of RSA signatures of known data: you know some pairs $(m_k, c_k)$ such that ${c_k}^e \equiv m_k \pmod n$.  If you know $e$, because probably it's one of $\{3, 17, 65537\}$, is it possible to recover $n$?

calculate
$$gcd(c_1^e - m_1 , c_2^e- m_2, \dots , c_k^e-m_k)$$

With a bit luck this should get $n$.
It will be an interesting exercise to calculate the probability of success based on the number of cleartect/ciphertext pairs.


TRNG vs PRNG - Entropy? How much more entropy gives a Hardware Random Number Generator or True Random Number Generator compared to a Pseudo Random Number Generator?

I know it depends on which TRNG is used, but I'm thinking in general. Does a TRNG generally provide more security than a PRNG?

Entropy as defined in information theory and cryptography is a difficult concept. One of the most common fallacies is that a piece of data has or "contains" entropy by itself. People who misunderstand this talk about bit streams having entropy, or measuring entropy of a piece of data. Or measuring entropy of a RNG.

To measure entropy you need a data source, plus a model. You compare the predictions given by the model (which are usually a-priori probabilities of certain results) with results from the data source (actual values received, and the probability of getting that result that the model provided before you looked) in order to assess the entropy generated by the data source with respect to the model*. What that means is the value you get for entropy varies depending on how you construct your model.

When considering security of a system, you can look for an "attack" model that tries to reduce the entropy of the system it measures by predicting its results. A successful attack model has a low measure of entropy against its target system.

Generally when looking at attacking cryptographic RNG systems, we look for the best possible model, and declare that the source being attacked has X entropy under that model. This sometimes gets conflated into saying a source (or password) has so many bits of entropy.

With that view, there is a sharp divide between good quality PRNGs and TRNGs. Namely, if your model of the PRNG is accurate and includes the correct seed then a PRNG has effectively zero entropy. But without the seed, and assuming a good quality PRNG, then we don't know of any practical models that can differentiate between a PRNG and a TRNG (also assuming the latter is properly whitened). That is, all known models fed with output from either a PRNG with unknown seed or TRNG will measure the same entropy (with statistical variation within expected bounds) Theoretical models can differentiate, because you could demonstrate a finite state by running e.g. $2^{256}$ iterations and seeing repetition.

This is partly self-defining. If a practical model was found that could separate a PRNG used for cryptography from a TRNG, and that demonstrated by showing a lower measure of entropy, then the PRNG would likely be abandoned for cryptographic use.

  Does a TRNG generally provide more security than a PRNG?

In a theoretical model where you could make enough observations to figure out some of the state of a PRNG, then a TRNG that was essentially the same PRNG plus regular re-seeding from an unpredictable source would have higher entropy against that model.

The caveat is having an unpredictable source. TRNG sources are measurements of physical processes which have been chosen to be very difficult to predict (or for thermal noise or quantum sources, where the best theories to date model them as inherently random). The assertions about the source being unpredictable could turn out wrong. Or a more likely problem is that either the source or measurement process could be tampered with or intercepted.

So a short answer, with caveats, could be "Yes, a typical TRNG design could be considered more secure than its own PRNG component, because successful attacks against it would involve more work."

However, that is not the same as saying "This PRNG supplies less entropy than this TRNG" - without a qualifying model, the statement is meaningless.

* It is sort of possible to estimate entropy contained in a piece of data, but this is not as well defined, and is usually based on some assumption such as comparison with a simple model of a TRNG, compressibility etc. It is unwise to use these kinds of estimates when dealing with more formal definitions of randomness.


Incorrect solution for Discrete Log Problem when using the Index Calculus algorithm The index calculus algorithm can be used for computing discrete logarithms.
The basic idea is that you search for a set of linear independent vectors.
When you solve the corresponding matrix, you find the solutions for the discrete log problem of all the prime factors in your factor base. These can be used to solve the original discrete log problem.

I decided to make an implementation of it just for fun.
However, when solving the corresponding matrix, I sometimes run into solutions for the factors that are incorrect.
Let me show an example. Assume we have generator $g = 5$ and $h=543$ with $p = 2003$. Using the factor base $\mathcal{F} = \{2,3,5,7,11,13\}$, we want to find a solution for $$g^x \equiv h \mod(p)$$

Lets say we find the following relations which are $\mathcal{F}$-smooth:
\begin{align*}
5^{790} &= 3^2 \cdot 11^2 \\
5^{729} &= 2^5 \cdot 5 \cdot 11 \\
5^{1162} &= 3^3 \cdot 5 \cdot 7 \\
5^{919} &= 2^2 \cdot 5 \cdot 7^2 \\
5^{150} &= 2 \cdot 3^2 \cdot 7 \\
5^{953} &= 2 \cdot 5 \cdot 7 \cdot 13
\end{align*}

This leaves us with the following matrix:
$M = $
\begin{pmatrix}
0 & 2 & 0 & 0 & 2 & 0 & 790\\
5 & 0 & 1 & 0 & 1 & 0 & 729\\
0 & 3 & 1 & 1 & 0 & 0 & 1162\\
2 & 0 & 1 & 2 & 0 & 0 & 919\\
1 & 2 & 0 & 1 & 0 & 0 & 150\\
1 & 0 & 1 & 1 & 0 & 1 & 953
\end{pmatrix}

Using Gauss-Jordan Eliminiation, we get the following solutions:
\begin{align}
\log_5(2) &= -93 \equiv 1909 \mod(2002)\\
\log_5(3) &= 60 \\
\log_5(5) &= 859 \\
\log_5(7) &= 123 \\
\log_5(11) &= 335 \\
\log_5(13) &= 64
\end{align}
We can check the only the $\log_5(7)$ is correct.
My question is: how is it possible that the solutions for the factors in the factor base are (mostly) incorrect, although the relations we found are linear independent?

Did it a quick sanity check, and indeed your relations hold in $\mathbb{F}_p$. I cannot judge where you went wrong of course, but my guess is that you are dividing at points where you can't. The Gaussian elimination is done $\bmod{2002}$, hence dividing with any positive integer which has $\gcd$ unequal to 1 with 2002 is off-limits. Below I show how you can get some solutions from your system of equations.

Note that you can trivially cancel out 5's on the right side of your equation, to get the system of equations
\begin{align*}
5^{790} &= 3^2\cdot11^2\\
5^{728} &= 2^5\cdot 11\\
5^{1161} &= 3^3\cdot7\\
5^{918} &= 2^2\cdot 7^2\\
5^{150} &= 2\cdot 3^2\cdot7\\
5^{952} &= 2\cdot7\cdot13\\
\end{align*}
This does not affect the solutions of course. Instead we get the matrix
$$\begin{pmatrix}
0 & 2 & 0 & 2 & 0 & 790\\
5 & 0 & 0 & 1 & 0 & 728\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
1 & 2 & 1 & 0 & 0 & 150\\
1 & 0 & 1 & 0 & 1 & 952
\end{pmatrix}$$
Using Gaussian elimination (for the full computation check below) we obtain the relations
\begin{align*}
2^{20} &= 5^{714} \\
3^4 &= 5^{1384} \\
3^{60} &= 5^{740} \\
7^{20} &= 5^{458} \\
11^4 &= 5^{196} \\
13^2 &= 5^{986}
\end{align*}
Of course $3^4=5^{1384}\implies3^{60}=5^{740}$, hence we get solutions
\begin{align*}
2^{20} &= 5^{714} \\
3^4 &= 5^{1384} \\
7^{20} &= 5^{458} \\
11^4 &= 5^{196} \\
13^2 &= 5^{986}
\end{align*}
Now note that $801\equiv5^{-1}\bmod{2002}$, hence $$2^{20} = 5^{714}\implies (2^{20})^{801} = (5^{714})^{801}\implies 2^4=5^{1344}.$$
Similarly $7^4=5^{492}$, and we have
\begin{align*}
2^4 &= 5^{1344} \\
3^4 &= 5^{1384} \\
7^4 &= 5^{492} \\
11^4 &= 5^{196} \\
13^2 &= 5^{968}
\end{align*}
Now we get into some trouble, since $\gcd(2,2002)=2$, hence we cannot simply eliminate 2. However we can conclude that $\pm 13\equiv5^{493}\bmod{p}$. Simply trying both gives that $\log_5(-13)=493$. Moreover $\mathbb{F}_p^*$ is cyclic of order 2002, and since 2002 is not divisible by 4, it does not contain any element of order 4. So the only elements $x\in\mathbb{F}_p^*$ that satisfy $x^4=1$ are $\pm1$. Hence
\begin{align*}
\pm2 &= 5^{336} \\
\pm3 &= 5^{346} \\
\pm7 &= 5^{123} \\
\pm11 &= 5^{49} \\
-13 &= 5^{493}
\end{align*}
Simply trying the two options leads to the solutions
\begin{align*}
-2 &= 5^{336} \\
3 &= 5^{346} \\
7 &= 5^{123} \\
11 &= 5^{49} \\
-13 &= 5^{493}
\end{align*}

Gaussian elimination:

Multiply the bottom row by 2 (the 6th row, starting the count at 1), and then subtract the 4th row from the bottom row. This leaves
$$\begin{pmatrix}
0 & 2 & 0 & 2 & 0 & 790\\
5 & 0 & 0 & 1 & 0 & 728\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
1 & 2 & 1 & 0 & 0 & 150\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Multiplying the 5th column by 2, and subtracting the fourth gives
$$\begin{pmatrix}
0 & 2 & 0 & 2 & 0 & 790\\
5 & 0 & 0 & 1 & 0 & 728\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Multiplying the first row by 2 and subtracting the 5th leaves
$$\begin{pmatrix}
0 & 0 & 0 & 4 & 0 & 196\\
5 & 0 & 0 & 1 & 0 & 728\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Multiply the second row by 4 and subtract the first to get
$$\begin{pmatrix}
0 & 0 & 0 & 4 & 0 & 196\\
20 & 0 & 0 & 0 & 0 & 714\\
0 & 3 & 1 & 0 & 0 & 1161\\
2 & 0 & 2 & 0 & 0 & 918\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Multiply the 4th row by 10 and subtract the 2nd to get
$$\begin{pmatrix}
0 & 0 & 0 & 4 & 0 & 196\\
20 & 0 & 0 & 0 & 0 & 714\\
0 & 3 & 1 & 0 & 0 & 1161\\
0 & 0 & 20 & 0 & 0 & 458\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$
Finally multiply the 3rd by 20 and subtract the 4th to obtain
$$\begin{pmatrix}
0 & 0 & 0 & 4 & 0 & 196\\
20 & 0 & 0 & 0 & 0 & 714\\
0 & 60 & 0 & 0 & 0 & 740\\
0 & 0 & 20 & 0 & 0 & 458\\
0 & 4 & 0 & 0 & 0 & 1384\\
0 & 0 & 0 & 0 & 2 & 986
\end{pmatrix}$$


Recent attacks on RSA At Blackhat 2013 this week, there was a talk saying RSA is (essentially) doomed in the near future.

networkworld.com ~ “Black Hat: Elliptic curve cryptography coming as smarter algorithms threaten RSA”

What "two devastating attacks in the past 6 months" is Mr Ritter referring to, and how real is the threat to RSA?

Behold! The slides from the presentation, as pulled from the Black Hat 2013 iSEC Partners page. The presenters are not cryptographers — they're security researchers. You can find more information about the presentation at the Black Hat website, including a brief biography of the researchers in question.

It appears that the presentation focused on advancements in the discrete logarithm problem, particularly by Joux, and less on factoring itself; instead, the argument was that since advances in the discrete logarithm problem tend to lead to advances in factoring (and vice versa), and since Joux has been making some particularly good progress in that area, RSA is thus in imminent danger.

I'm ambivalent on the matter.

To answer your question directly, I'm not sure which two "devastating attacks" the article in question is talking about. The slides, as linked above, contain links to many different results (see page 26 and onward). However, if I had to guess, I would suspect they are talking about

Joux's A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic, published on Feb. 20, 2013, and
Barbulescu et al.'s A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, published on Jun. 18, 2013.

These two papers are cited in the slides on pages 26 and 28, respectively.


The affine transformation is defined as a degree 7 polynomial multiplication modulo $x^8 + 1$.

In the format of the question, the terms are the right hand column, top to bottom.
$A = x^7 + x^6 + x^5 + x^4 + 1$, and $B = x^7 + x^5 + x^2$.

The inverse can be determined through several methods. Since there are only 254 valid polynomials (omitting 0 and 1), you can just multiply them together until you get 1. Additionally, they happen to be cubes of eachother:

$$(x^7 + x^6 + x^5 + x^4 + 1)^3 ~~mod~~ x^8 + 1 = x^7 + x^5 + x^2$$
$$(x^7 + x^5 + x^2)^3 ~~mod~~ x^8 + 1 = x^7 + x^6 + x^5 + x^4 + 1 $$

This is because of the period of the affine transformation, which happens to be 4. The period is how many times you need to perform the transformation to arrive at the original input. Any affine transformation in $GF(2^8)$ will have a period of $2^0$ through $2^4$ in succeessive powers of 2, or {1,2,4,8,16}.

Therefore, since $A^4 = A^0$, $A^{4-1} = A^3 = A^{-1}$, and since $A^3 = B$, $B = A^{-1}$


Can we use Shamir secret sharing conversely? In Shamir secret sharing scheme, we have a secret and then the shares are generated based on the secret. The question is can we generate the shares before knowing the 'secret' (which is uniformly random). Specifically, suppose $n$ users choose random numbers $r_1,r_2,\dots, r_n$, can we reconstruct a secret (random number) using $t$ of them with Shamir's technique?

No, if $n$ users have independently chosen secret random numbers $r_i$, and for any given $t\in[1,n)$, we can't use Shamir secret sharing to construct a secret dependent on $t$ out of $n$ of the $r_i$, and independent of which $r_i$ are picked. The critical issue is that what Shamir secret sharing assigns to a user is dependent on what the others get.

More generally, I think there is no function taking $t\in[1,n)$ pairs $(i,r_i)$ with distinct $i$ and producing something independent of the picks but dependent on each $r_i$. I'm trying to think of a proof, but nothing has happened yet.


What is SHA-256 in Conjunctive Normal Form? What is the conjunctive normal form (CNF) representation of $\text{SHA-256}(m)=h$, where $m$ is of fixed (or bounded) size and $h$ is 256 bit?

There is none. Conjunctive normal form is for Boolean formulas, which have a single truth value. SHA-256 is not a Boolean formula (SHA-256(x) is not "true" or "false.") Furthermore, CNF is only applicable if you have a fixed number of variables; this is not true for SHA-256, which has variable-length input. At best you could have 256 different formulas, each for one bit of the output, and have $2^{64}+63$ different variables in each formula.

You've probably confused decision problems with function problems. Any algorithm that returns "true" or "false" can be represented, ultimately, as a gigantic Boolean formula. Anything not just returning "true" or "false" cannot, as a Boolean formula returns only "true" or "false." While there is a $2^{64}+63+256$-variable formula that evaluates to "is $x_1\ldots x_{256}$ the SHA-256 hash of the $x_{257}\ldots x_{320}$-bit number stored in $x_{321}\ldots x_{\text{last}}$," the formula is really just one of those things that exists in theory and not in practice.


Modulus for elliptic curve point multiplication I want to implement a point multiplication ($k \cdot P$) operation on FPGA. I have a BN curve $y^2=x^3+2$, and a scalar value $k$. The $x$ and $y$ coordinates of point $P$ are of 256 bits. In the double and add formulas, there are three main operations: addition, multiplication, and division. Each of these are mod operations (e.g, $a+b \mod m$). What should be the value of this $m$? Could it be the reduction polynomial (remember that I am working in a prime field) or some constant integer value?

It's the prime of the prime field.

(Note that, if you're also using the curve for pairings, you'll need arithmetic over both $\mathbb{F}_p$ and $\mathbb{F}_{p^{12}}$. The first can be viewed as arithmetic modulo $p$, but the second is slightly more complex, and can be viewed as arithmetic of polynomials over $\mathbb{F}_p$, modulo a reduction polynomial.)


test vectors for 3DES seem to in fact be testing DES - not 3DES NIST SP 800-20 Appendix A has what presumably are supposed to be test vectors for 3DES except almost all of the test vectors utilize 8-byte keys and not the 24-byte keys that 3DES is supposed to have. See, for example, table's A.2, A.3, A.4, A.8 and A.10. So what's the point? These test vectors don't seem like they're testing what they ought to be testing.

It is for the 1st version of 3DES which is only using the same key three times (3DES-EDE1)

Which is equivalent to DES (I think they did that so you could use 3DES to exchange with someone using DES).

There are 3 different versions (or ways of using DES). EDE3 is the strongest with 3 different keys being used.


Is a continuous stream of encrypted data embedded in garbage more or less secure than only encrypting the data? Consider a communication channel that needs to be secure (Encryption can not use full "volume" encryption, since future messages are not known). Would it be better to

only transmit encrypted messages and remain silent the rest of the time (therefore letting eavesdroppers know when a message is passed),
or sending encrypted pseudo-random data (or almost-meaningful garbage messages) during the remaining time - yielding a continuously encrypted stream which on the one hand hides the information of message transmission times, but otherwise adds the risk of a Known-plaintext attack should the garbage-generator (or the way separating actual message) be predicted.

Does the answer also depend on whether the messages shall be secure "forever" or if it is sufficient to maintain secrecy for a limited amount of time?

It depends on what your requirements are. In general, it is accepted that an observer knows when meaningful data is exchanged - even if he can't read it - because, well, we simply don't care. But in some cases this may be unacceptable, such as in p2p protocols where anonymity is very desirable and a fuzzy network can add a decent amount of secrecy.

On the other hand, continuously streaming is quite heavyweight, as it is in general not possible to keep streaming indefinitely (and intercepting all the garbage data and interpreting it as meaningless probably isn't free either, although that depends on your transmission protocol).

  or sending encrypted pseudo-random data

Huh? Why would you encrypt pseudorandom data? This is actually a bad idea - by doing that and encrypting your pseudorandom stream with the same key, you will have tainted all the garbage data with your key material - the same key used to encrypt your precious ciphertext - thereby giving the attacker orders of magnitude more stuff to work with. If the underlying pseudorandom data that you originally encrypted is broken, boom, you just gave your opponent lots of plaintext/ciphertext pairs, and your key (and therefore, your ciphertext) is now potentially compromised.

No, just send pseudorandom data that's independent of all other information you might rely on, so just grab a few hundred bits of entropy and run some cipher in CTR mode or something to produce a nice pseudorandom bitstream - this way, even if this part of your scheme is broken, your ciphertext remains safe (even if the attacker now knows its size and roughly when it was sent).

  but otherwise adds the risk of a Known-plaintext attack should the
  garbage-generator (or the way separating actual message) be predicted.

How so? If your cryptography is sound, and the garbage data does not leak any information about the plaintext or any key material (which it shouldn't, since it's just random bits), the two methods should provide equally optimal privacy. Even if an attacker somehow managed to distinguish the relevant ciphertext, he still wouldn't be able to decrypt it.

  Does the answer also depend on whether the messages shall be secure
  "forever" or if it is sufficient to maintain secrecy for a limited
  amount of time?

Again, it depends on your requirements. There is no "one size fits all" cryptography, and every application needs its own version of it, that's why there are so many different protocols and schemes around. You need to figure out yours and implement it.

So basically, define your use of the word "secure" in your first sentence. Secure against what, and how secure should it be (should it provide only privacy? privacy and anonymity? perhaps integrity too, what about authenticity? etc...)


Decryption that is easy for humans and hard/impossible for computers Is there any research into digital cyphers that are easy for humans to decrypt, but hard for computers?

One example is Captchas, though those are being increasingly broken by computers.  However, Captchas are not quite what I have in mind.  Captchas depend on human domain expertise, which could theoretically be captured algorithmically and then cracked pretty easily with computers.

What I am looking for are cyphers that humans can easily decrypt, but are provably computationally hard or impossible.  The encryption process has to also be performed algorithmically.

The scenario this encryption scheme would work in is the following:

The encrypted message is made available for offline processing.
Within a relatively short time the human can derive the message.
An algorithm will either find the message impossible to derive, or at least impossible in practice.

My opinion is that in order to design a cipher that is easier to decrypt by a human than by a competently programmed computer, the only working option is making the ciphertext or key unavailable to the computer due to some input limitation (like, the ciphertext or key is 3D-engraved in plexiglass, and the computer has no 3D vision); but that could be circumvented by an upgrade of the computer. With the relevant data available, no matter if we consider decryption with or without the key (the question is ambiguous about that), decryption is data processing, and properly programmed computers tend to vastly outperform humans at that.

Update: there are areas where the visual capabilities of the human brain (or possibly capabilities pertaining to other senses like audition) make humans somewhat competitive with computer programs; like finding a good move at the game of Go or Chess, an approximate solution to the Traveling Salesman Problem, or identifying some flaws in a pseudo random generator. I challenge that it allows constructing a cipher as asked, for two reasons:

For identification of flawed RNG, and arguably the TSP, there is evidence that humans perform significantly worse than computer programs primarily and competently designed for speed at the price of some error rate or non-optimality. Even for games, computer programs exist that beat the best humans with heavy hardware, and 99% of humans with a mere PC.
In tasks where humans are even mildly competitive with proper computer programs, humans tend to find only approximate solutions, and different humans will often find different solutions. It is hard to turn such capability into reliably deciphering a ciphertext, as necessary to answer the question.


Incorrect Test Vectors for AES' MixColumns? I'm looking for test vectors for AES' MixColums and I found this: https://en.wikipedia.org/wiki/Rijndael_mix_columns#Test_vectors_for_MixColumn.28.29.3B_not_for_InvMixColumn

Here it says that the operation on the column 1, 1, 1, 1 doesn't do anything and returns 1, 1, 1, 1.

I don't understand this. From MixColumns here's what we're doing:

$$
\begin{bmatrix}
\mathtt{02} & \mathtt{03} & \mathtt{01} & \mathtt{01} \\
\mathtt{01} & \mathtt{02} & \mathtt{03} & \mathtt{01} \\
\mathtt{01} & \mathtt{01} & \mathtt{02} & \mathtt{03} \\
\mathtt{03} & \mathtt{01} & \mathtt{01} & \mathtt{02} \\
\end{bmatrix}
\begin{bmatrix}
\mathtt{01} \\
\mathtt{01} \\
\mathtt{01} \\
\mathtt{01} \\
\end{bmatrix}
\cdot
=
\begin{bmatrix}
\mathtt{a_0} \\
\mathtt{a_1} \\
\mathtt{a_2} \\
\mathtt{a_3} \\
\end{bmatrix}
$$

And so, $a_0 = a_1 = a_2 = a_3$ will be calculated as:

$$
(\mathtt{02} \cdot \mathtt{01}) + (\mathtt{03} \cdot \mathtt{01}) + (\mathtt{01} \cdot \mathtt{01}) + (\mathtt{01} \cdot \mathtt{01})
$$

with:

$02 * 01$ is $X * 1$ which is $02$
$03 * 01$ is $(X+1) * 1$ which is $03$
$01 * 01 = 01$

So the total should be $03 + 02 + 01 + 01 = 07$.

No, $03 + 02 + 01 + 01 = 01$

The problem is that you are misinterpreting $+$, it's not addition modulo 256; instead, it's the addition operation in the field $GF(2^8)$, which can be computed by performing the exclusive-or on the inputs.

And, $03 \oplus 02 \oplus 01 \oplus 01 = 01$


Is PBKDF2-HMAC-SHA1 really broken? I just read through this article which demonstrates practical (and seemingly trivial) collisions in PBKDF2-HMAC-SHA1, and provides a few examples of collisions.

Am I missing something here? Is PBKDF2-HMAC-SHA1 really broken this badly and trivially? Or am I missing some wider context?

Password hashes need first pre-image resistance and should not cause many collisions among typical passwords (preserve the entropy). This collision "attack" violates neither requirement and causes no practical security issues.

While this issue can find trivial collisions, they're not between commonly chosen passwords. A SHA-1 hash (and thus the shorter of the colliding passwords) has 160 bits, the longer has at least 65 characters. There is no way two users will end up with such a colliding pair by accident.

Doing it deliberately doesn't cause any problems either. It only means that the legitimate user knows two valid passwords for their own account.

I'm sure that cryptographers have known about this issue for years, but didn't care since it's no real attack if PBKDF2 is used as intended. I mainly posted it for fun and because I'd prefer new password hashes coming out of the PHC competition to be collision resistant. Programmers expect these function to be collision resistant, so they might use it in an unusual way that, unlike normal password hashing, relies on collision resistance.

It's also fun to surprise the "MD5 is bad as a password hash because collisions" crowd a bit since it's just as easy to find collisions in the "proper choice". (MD5 is bad because it's fast. Its known cryptographic weaknesses don't apply to password hashing.)

We had a discussion about this on the password hashing competition mailing list, where I posted this:

  This results from PBKDF2 using the password as HMAC key instead of message.

  HMAC seems to be designed with a fixed length uniformly random key
  (i.e. it aims to be a PRF),
  so I consider using the password as key instead of message abuse.

  HMAC is a bit weird with variable size keys:

  If the key is shorter than the block size, pad it with zero bytes
  If the key is longer than the block size, hash it

  This is generally not a problem for the usual thread model of HMAC
  (assumes uniformly random keys with fixed size) and PBKDF2 (password
  hashing, only first pre-images matter). But it means that there are
  trivial collisions and even second pre-images (add a 0 byte at the
  end, if the original key was shorter than the block size, this won't
  have any effect).

  As an example with nice printable characters in both passwords:

  plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd
  and eBkXQTfuBqp'cTcar&g* have the same PBKDF2-HMAC-SHA1 hash (no
  matter the salt or the number of iterations).

  I found those with a CPU and unoptimized code. One of our GPU hashing
  friends could easily find a similar pair for PBKDF2-HMAC-SHA-256.


128 bit 3DES Key and AES Key: what's the difference? Apologies if this is really basic but I couldn't find the answer to this.

I have heard some Info Sec colleagues talking about creating an AES key in preference to a DES or 3DES key but I don't know the difference; I thought a key was just a random string of bits? Is there a difference? Can you use the same key with different algorithms? i.e. a 128 bit key with 3DES and also with AES?

Both an AES-128 key (as defined by FIPS 197), and a TDES Keying Option 2 key (as defined by FIPS SP-800-67) are 128-bit bitstrings. Similarly, both an AES-192 key and a TDES Keying Option 1 key are 192-bit bitstrings. The differences are:

In AES, all bits of a key matter to the result; in TDES, 1 bit out of 8 (the lower-order bit of each byte in the usual representation) either

is ignored, and can have any value;
is checked, and must be the complement of the exclusive-OR of the 7 others; that is, each byte is adjusted to odd parity; see this answer for details on the oddity (pun intended) of DES key bytes.

TDES has a complementation property, which  removes an extra bit of security for a given key size in many situations (including CPA attack); that further reduces a 128-bit TDES Keying Option 2 key to 111-bit strength, and a 192-bit TDES Keying Option 1 key to 167-bit strength.
The block size is 128-bit for AES, 64-bit for TDES; this means that AES and TDES are not interchangeable, even though they use the same key (analogy: truck and car are not interchangeable, even though both might run on gasoil). As rightly pointed in that other answer, that block size difference also makes a security difference in some applications.
AES is unbroken for any practical purpose, but there are attacks on TDES (at least, with Keying Option 2) using conceivable amounts of computing power and not-far-from-conceivable amounts of memory.
I'm leaving alone the non-issue of DES weak and semi-weak keys, which is immaterial in practice, and much more for TDES.

If one generates a TDES key with knowledge that 1 above will apply when it will be used, one can generate the key at random just as for an AES key (there might be different regulatory requirements). If one generates a TDES key with knowledge that 2 above will apply (or does not have such knowledge but want to err on the compatible side), one must adjust the low-order bit of each byte according to the 7 other bits.

One can use a TDES key for AES (AES-128 or AES-192 depending on TDES keying option); however, if the key was generated with low-order bit adjustment, that weakens AES-128 by $2^{16}$ w.r.t. brute force key search, which is (somewhat) undesirable and (very) unusual (AES-192 would be weakened by $2^{24}$, which likely is still strong enough except perhaps from a certification standpoint).

One can use an AES key for TDES (assuming matching key option) if

the TDES implementation does not check parity (case 1 above);
or the AES key is parity-adjusted to transform it into a TDES key.

In any case, it would be a bad idea to use the same key for both AES and TDES, for a successful key recovery attack on either cipher (e.g. by DPA) would then translate into an attack breaking the other.


Will X9.31 remain a secure & acceptable deterministic random generator beyond 2015? I am actually looking for available crypto libraries including a deterministic random generator for the purpose of a dedicated crypto key generator unit.
I have a simple question about the X9.31 based PRNG as proposed for instance in Botan library, since I noted that NIST SP800-131 document indicates that use of the X9.31 prng is disallowed from 2015:

Has a PRNG based on X9.31 (as Botan's one) some weaknesses that make that it is no more considered as sufficiently secure and so it is effectively preferable to use another (i.e. CS-PRNG) ?
or NIST recommendation is driven by other objectives (as to limit to CS-PRNG defined in NIST SP800-90A standard) ?

X9.31-based PRNGs as used in current practice (including in the Botan library) tend to be extensions of the generator of ANSI X9.31-1998 appendix A.2.4 (which designated purpose is as a submodule of a prime generator for RSA keys). This really is the PRNG of ANSI X9.17-1985 Appendix C (which designated purpose is generating DES keys), also described in modern form in section 5.3.1 of the HAC. This generator has a sound and time-tested structure; however I know no theoretical argument reducing security to that of the underlying block cipher. Update: and, as pointed by Gilles in another answer, it lacks backtracking resistance: past output can be deduced from the current state, which is a concern in some applications where the state is kept for extended period, rather than safely disposed of after use, and could get compromised.

This original generator, designated ANSI931_TDES2 in NIST test vectors, does show its age in the use of Triple-DES with two keys, which has limited 64-bit block size, 112-bit key entropy, theoretical vulnerability to meet-in-the-middle variants, and poor suitability for software implementation, with in particular risk of timing attacks on CPUs with caches, and other side-channel attacks. All this is reason enough for ANSI931_TDES2 to be abandoned with a deadline at the end of 2015, per NIST SP800-131A Table 3.

Four common extensions have been defined in NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-Key Triple DES and AES Algorithms (2005). ANSI931_TDES3 just widens the key to an effective key size of 168 bits. ANSI931_AES128, ANSI931_AES192, ANSI931_AES256 use AES, with the corresponding key size; and make all variable data 128-bit wide. As far as I can tell these generators are in an administrative state of limbo: neither explicitly deprecated, nor with recent re-approval. I sure would not want to use ANSI931_TDES3 for any new development.

It seems inconceivable to me that a practically useful cryptanalytic attack of ANSI931_AES256 (the variant claimed to be used in the Botan library) could emerge within a human lifetime, assuming an adversary knowing nothing about secret key and primary seed material chosen uniformly at random, trying to predict some of the output, knowing all other external data (other output and auxiliary seed material), and not in a position to conduct side-channel or fault injection attacks on the internal state of the generator (Update: including as left after the PRNG's intended use). I base this assessment on the lack of published attack on the original PRNG after 30 years of exposure, and the dramatic security boost given by the widening of key and state.

Note: After I dug ANSI X9.31-1998 from my chest of purchased standards, I intended to make this answer a detailed analysis of the birth, life and fall of the 3 generators in appendix A, and their descendants. This turned out to be inextricably difficult, because the algorithm in appendix A.2.1 as written is dead wrong in step 4e where the output is supposedly generated, and there's no test vectors as a lifebuoy; also I could not determine which of it or FIPS 186-1 Appendix 3.1 (nearly identical except for the defective step) predates the other.


Test vectors for PRESENT algorithm? I'm looking for Test Vectors to test my implementation of PRESENT. I would like to test a different input from the usual where the key and the plaintext are either 000..000 or FFF...FFF.

There are many sources presenting the test vectors.
But you can also extract it from sourcecode implementations as opencores.org et al offer them…

 Plaintext: 0000000000000000

 Key: 00000000000000000000 (80-bit)

 Round key 1: 0000000000000000
 Round key 2: c000000000000000
 Round key 3: 5000180000000001
 Round key 4: 60000a0003000001
 Round key 5: b0000c0001400062
 Round key 6: 900016000180002a
 Round key 7: 0001920002c00033
 Round key 8: a000a0003240005b
 Round key 9: d000d4001400064c
 Round key 10: 30017a001a800284
 Round key 11: e01926002f400355
 Round key 12: f00a1c0324c005ed
 Round key 13: 800d5e014380649e
 Round key 14: 4017b001abc02876
 Round key 15: 71926802f600357f
 Round key 16: 10a1ce324d005ec7
 Round key 17: 20d5e21439c649a8
 Round key 18: c17b041abc428730
 Round key 19: c926b82f60835781
 Round key 20: 6a1cd924d705ec19
 Round key 21: bd5e0d439b249aea
 Round key 22: 07b077abc1a8736e
 Round key 23: 426ba0f60ef5783e
 Round key 24: 41cda84d741ec1d5
 Round key 25: f5e0e839b509ae8f
 Round key 26: 2b075ebc1d0736ad
 Round key 27: 86ba2560ebd783ad
 Round key 28: 8cdab0d744ac1d77
 Round key 29: 1e0eb19b561ae89b
 Round key 30: d075c3c1d6336acd
 Round key 31: 8ba27a0eb8783ac9
 Round key 32: 6dab31744f41d700

 Round Output 1: ffffffff00000000
 Round Output 2: 80ff00ffff008000
 Round Output 3: 4036c837b7c88c09
 Round Output 4: 73c2cd26b6192359
 Round Output 5: 41d7be58531e4446
 Round Output 6: 182ef861ad62fd1c
 Round Output 7: 0ea0a5b67effc5a4
 Round Output 8: bba0b848a113e080
 Round Output 9: fa943423a9142338
 Round Output 10: 69f2e22d63684d54
 Round Output 11: 548a4b63c330a59d
 Round Output 12: d75f955fa228e4ca
 Round Output 13: 44255864103841f9
 Round Output 14: e2cc9004363f6c12
 Round Output 15: c36682c5cd375421
 Round Output 16: 597db55cc2a5d9b6
 Round Output 17: e67ce40e71b8b713
 Round Output 18: 751df6d6807b5b59
 Round Output 19: b948414e23332c93
 Round Output 20: 5b75890dcfb3d563
 Round Output 21: 5679203168278f5a
 Round Output 22: 17c377c413fa45a3
 Round Output 23: 262a2de73b5f3ecd
 Round Output 24: d3a053128b4d7bb3
 Round Output 25: 7db29209c28a20fa
 Round Output 26: 62050c9940f400b9
 Round Output 27: 65d50da21fbcc09f
 Round Output 28: 6a50663c540d862f
 Round Output 29: c79b8ff00a48df35
 Round Output 30: 4a38c5e00283fba1
 Round Output 31: 38d2f04c34635345

 Ciphertext: 5579c1387b228445


7zip : Why does encrypting the same file with AES-256 not give the same output? Using 7-zip 19.00, on Windows 10 1909, build 18363.592, I encrypted a text file with the contents "hello there" using AES-256 and the password "123". I did this two times, the exact same procedure, but as shown below, the output is different:

Why?

This is expected behavior since 7zip uses Cipher Block Chaining (CBC) mode for encryption. For which you need the Initialization Vector (IV) to be unique and unpredictable.
It was using 64-bit IV but fortunately, that was changed to 128;

Encryption strength for 7z archives was increased: the size of random initialization vector was increased from 64-bit to 128-bit,
and the pseudo-random number generator was improved.

If the encryption of the same file results in the same ciphertext then we will be thought that there is a problem with the IV generation. Hopefully, from here we see that there is not.
Note 1: 7zip uses $2^{19}$-times iterated SHA256 to derive the AES-256 key from passwords. This is not safe from massive parallelization. A password with high entropy like diceware is recommended.
Note 2: The first comment under question claims that CBC mode of operations has IND-CCA actually it can't, it has IND-CPA. See the seminal work of Rogaway on modes Evaluation of Some Blockcipher Modes of Operation


Blind signatures security I was reading up on blind signatures. I came across the following paragraph in this paper.

  Previous methods of proofs used to establish security arguments for
  signature schemes no longer work since, during the collusion between
  the signer, the attacker and the random oracle, we lose control over
  the value that the signer receives: it no longer comes from the random
  oracle, but from the attacker. As a consequence, the signer cannot be
  simulated without the secret key, otherwise the signature scheme would
  be universally forgeable

The authors go on to use the concept of witness indistinguishibilty to solve the above problem.

I am not able to understand what the author means by :

  the signer cannot be simulated without the secret key.

Can anyone explain why this is the case?

Without the secret key, the signer can only be simulated through creative use of the random oracle (which is the only thing meaningfully in control of the simulator). Traditional signature proofs involve the simulator responding to random oracle queries in a way that will necessarily make their signatures validate, which they can do because they have control over the random oracle's input and can program it to have the right value specifically on the query needed for a particular signature.

If they program the wrong value, the simulation will produce an invalid signature (proof fails), and if they program the right value on the wrong query, they're also out of luck since the right query needs to have an independently random output from the attacker's view, so the simulator is forced to use the wrong value on the right query.

However in a blind signature the simulator doesn't get to query the random oracle for signatures, it has to sign the attacker's challenge. In effect, the attacker gets to behave as the random oracle. For common signatures which are also proof-of-knowledge of the secret key (at least when the public key is fixed in advance), this necessarily forces the simulator to have knowledge of the secret key.


AES multiple devices to server communication I have multiple devices connecting to a server, whose communication needs to be encrypted. At the moment I have an AES library doing the job (possibly inadequately): I am using a database of keys on the server, that corresponds to the keys stored on the devices (one per device).

Each message from the device to the server is preceded by an unencrypted ID identifying that message as coming from that particular device and thereby showing the server which key to use to decrypt the rest of the message.

As this is sent unencrypted, I think this is somewhat insufficient to identify the device so I placed a device specific "secret" in the bit of the message that is encrypted which, if absent or incorrect will lead to the server discarding the message.

<device ID>"<device secret><device status>"

Where the "" mark the encrypted part. The device secret is the same every time and the device status is constantly changing.

My question is: Will the presence of this "secret" (presuming it is the same in every message coming from that device, and in the same location within the message) cause repeating patterns in the ciphertext making some form of attack possible? If this is the case, then how could this be avoided?

I can think of one way using a random message, sent from the server, that is then "mixed in" with the message before it is encrypted so the message is different every time, but this significantly increases the traffic. So I wanted to check to see if this was necessary or if there is a better way of doing this!

Will the presence of this "secret" (presuming it is the same in every message coming from that device, and in the same location within the message) cause repeating patterns in the ciphertext making some form of attack possible?

As long as the AES mode uses an IV and the IV is different for each message, there will be no patterns in the ciphertext.

However, there may be other attacks.

  As this is sent unencrypted, I think this is somewhat insufficient to identify the device so I placed a device specific "secret" in the bit of the message that is encrypted which, if absent or incorrect will lead to the server discarding the message.

A better way to do that would be to use authenticated encryption. Either AES in GCM mode or AES CTR + HMAC would work, for example. That will also prevent changes to messages, which may currently allow an attacker to change the device status in a message.

Even then, replay attacks may be possible. To prevent those you could verify the IV is never reused, for example by using a counter as the IV (in CTR or GCM modes) and storing the last value on both server and device, or by having the server send a random session number the device needs to include in its message.


Lehmer random number generator cipher - looking for differentials I'm looking for differentials in my kind of toy encryption scheme. I can't find any.
Let's consider linear congruential generator:
$X_{k+1} = a \cdot X_{k} \mod 2^{128}$
Such that $a$ is some number which for every 128-bit input $X_{k}$ from $0$ to $2^{128}-1$ will give us different output $X_{k+1}$ from $0$ to $2^{128}-1$. So we got bijection here (we can find many such odd $a$). Now let's say we will choose such 128-bit $a_{1},a_{2}, ..., a_{10}$ as a keys, randomly. We make $10$ rounds of encryption like that:

$a_{1} \cdot INPUT \mod 2^{128}$
Reverse $128$-bit block.
$a_{2} \cdot (2^{128}-INPUT) \mod 2^{128}$
$a_{3} \cdot INPUT \mod 2^{128}$
Reverse $128$-bit block.
$a_{4} \cdot (2^{128}-INPUT) \mod 2^{128}$

and so on...
Do you see any differentials here? Let's skip the encryption problems with zero-block - it can be solve easily, for example if we will use xoring before every round. Of course it is just keyed Lehmer random number generator with a modulus which is a power of two - and such generators have problems with low bits, but I can't use it to find differentials in that case.

Do you see any differentials here?

Yes; consider a differential where one side is the value $X$ and the other side is the value $2^{127}-X$.
Your cipher consists of three operations:

Multiplying the current value by an odd value $a_i$ modulo $2^{128}$

This operation preserves the differential with probability 1; one side would evaluate to $a_i \cdot X$ and the other side would evaluate to $a_i \cdot (2^{127} - X) = a_i \cdot 2^{127} - a_i \cdot X = 2^{127} - a_i \cdot X$

Negating the current value (which is done as a part of rounds 2-10)

This operation preserves the differential with probability 1; this happens because $-(2^{127} - X) = 2^{127} - (-X)$

Reversing the bits in the current value

This operation preserves the differential with probability 0.5; namely, if the lsbit of $X$ (equivalently, $2^{127} - X$) is a 1.  This happens because, when the lsbit is a 1, this relationship is equivalent to the relation that $X \oplus (2^{127}-X) = 2^{127}-2$.  This later relation is preserved when you reverse the bits, and hence the former one is as well.
This gives you a differential that holds with probability $2^{-10}$ through the ten rounds of the cipher.


Ciphers based on Keywords I am looking for different ciphers that use a key word (like "hello" or "awesome") to encrypt a given text. I know about the Keyword Cipher already; I'm looking for others.

Try looking at the Vigenere, or here is a complete list of keyword ciphers:
All the ciphers listed here are based on keys, but could be a little difficult to use. Some include making the keyword into a numerical sequence. By numbering each letter according to their place in the alphabet. If a letter appears twice, number them left to right.

i.e.
CAESAR =
314526


Uniformly distributed secure floating point numbers in [0,1) Is there any way to generate

cryptographically secure
uniformly distributed

floating point numbers in the interval [0,1)?

For example, in Javascript, there is Math.random(), which yields these (pseudo-random) numbers, yet not cryptographically secure.

There are several algorithms at https://stackoverflow.com/questions/686353/c-random-float-number-generation, yet at https://stackoverflow.com/questions/34575635/cryptographically-secure-float, the problem of denormal numbers was pointed out.
Inversion sampling as of Wikipedia requires a uniformly distributed [0,1) number to start, so this is seemingly not trivial to apply.

What is a good approach?

For most purposes, the following trivial method should be adequate:

Generate a random  $n$-bit integer (i.e. a uniformly distributed random integer between $0$ and $2^n-1$ inclusive).
Cast the random integer into a float and multiply it by $2^{-n}$ to scale it to the interval $[0,1)$.

There's some leeway in choosing the number of bits $n$, but a generally reasonable choice is the significand precision $n_p$ of your floating-point format (e.g. 53 bits for IEEE 754 double-precision floats).  In particular, this is the highest number of bits for which the distribution of the resulting floats will actually have the full $n$ bits of entropy — or, in other words, the highest number of bits for which step 2 above is fully reversible.  If $n > n_p$, the conversion to float will map some pairs of integers to the same floats, resulting in an output distribution with less than $n$ (but still more than $n_p$) bits of entropy.

Regardless of the value of $n$ chosen, the distribution of the floats generated using this method will be "approximately uniform", in the sense that, for any $0 \le a < b < 1$, the probability of the output falling in the subinterval $[a,b)$ will differ from $b - a$ by at most $\max(2^{-n}, 2^{-n_p})$.  For $n \le n_p$, it will also be uniform in the sense that each float value that can be generated by this method is generated with the same probability ($2^{-n}$).

However, the floats generated using this method will not be uniform in the sense that each possible float within $[0,1)$ would be equally likely to be generated.  In fact, this holds for any random float generation method that is approximately uniform in the sense described above, simply because the density of representable floating point values is itself not uniform — there are far more floats in the interval $[0,\frac12)$ than in $[\frac12, 1)$.  Thus, it's fundamentally impossible to generate random floats that would be uniformly distributed in both of these senses.

In any case, it's important to realize that a random float in $[0,1)$ is not the same thing as a uniformly distributed random real number in $[0,1)$: the latter distribution has infinite entropy, whereas the entropy of any actual distribution of floats representable on a computer is inevitably finite.  While it's sometimes (I would even say most of the time, at least outside crypto) fine to substitute one for the other, it's important to keep the difference in mind when analyzing the security of algorithms that, conceptually, assume access to uniformly distributed real numbers.


What can eve see when I go to https//paypal.com If I go to https://paypal.com/ and login, can Eve find the approximate size of the HTTPS request from my browser?  Can she see the approximate size of the responses from the paypal server to me? and also can she see that I am visiting paypal.com in particular? To what extent does SSL protect you?

Eve can see the size of the HTTPS request and response, as well as the domain and subdomain you connect to (via rDNS lookup or via SNI sniffing). TLS only protects the precise content of the data being transmitted, not where it is going. In particular, it works like this:

https://foo.example.com/some/page.html#some-fragment
| proto |    domain    |     path     |  fragment  |

proto - There are only two protocols in common use, HTTP and HTTPS.
domain - The domain is example.com and *.example.com, detectable with rDNS or SNI.
path - The path is completely encrypted and can only be read by the target server.
fragment - The fragment is visible only to the web browser and is not transmitted.

The attacker can see the protocol and domain, but not the path or the fragment. I wrote a more detailed answer about this on Information Security.


How are the lower levels calculated using upper levels in an optimized Merkel Hash Tree? I was reading about the TIK protocol for thwarting wormhole attacks on adhoc networks.
It uses a Merkel Hash Tree to store keys. But since the number of keys can be large, the tree is optimized by only storing the upper levels.

As far as I understand, the $a$ node is the result of the hash of its two children. But what I do not understand is that hashing is irreversible. If it is theoretically not feasible for an adversary to construct the child nodes if the parent node is known, how does storing the upper layers help at all?

What am I missing here?

The usual way to do this is by using a CSPRNG to generate the leaf values, such as AES in counter mode.  That way, once you have calculated the entire tree, you only need to store the upper layers, the secret AES key, and the initial counter value, and it is quite easy to recalculate very quickly any particular branch you need.

For example, let's say you generate a tree of depth 20 using AES in CTR mode to generate the values $v_0, v_1, v_2, ...v_n$ (in figure 1 on page 5 of the paper you linked), so there is a corresponding counter-value $c_i$ for each $v_i$, such that $v_i = E_K(c_i)$.  Let's also say you only store the AES key, the first counter value, and the top 9 layers of the hash tree (so you only need to keep 511 hashes, and can discard the remaining 1 million or so hashes in the tree).

To recalculate the path from any one particular leaf, $v_i$, back to the top-most node, all you need to do is re-generate the leaf value for $v_i$ using AES and the counter value $c_i$ (which is easy if you know the initial counter value and the index $i$), plus 2047 of its immediate neighboring values, and then use the hash function $H$ to re-generate the branch of the tree from those 2048 values up to one of the 256 stored values in layer 9 (which takes much less time to calculate than the initial set-up because you are only doing one 256th of the tree rather than the whole tree).


What is certainty in a real world zero knowledge proof? This question follows directly on from How do I explain zero knowledge proof to my 7 year old cousin?

Most of the simplistic answers there suggest that proof is obtained iteratively, slowly reducing the probability of Peggy simply randomly going through the cave. Or counting leaves over and over.  The Wikipedia page suggests the Peggy should demonstrate her magic skills 20 times. Later on there is mention of repeating the proof 128 times. That's a bit of a statistical difference.

In a real world situation of proving something like the existence of a correct 256 bit AES key, how many times would the proving have to be attempted for certainty?

There is obviously no definite answer to that. The general principle, however, is not at all a problem of cryptography: it is a question with a long history in probability and economics. It is referred to as Cournot's principle in this answer of Bjørn Kjos-Hanssen on cstheory.stackexchange.

As detailed by the document which I linked to, the question has long bothered people, especially when it comes to law. When can magistrates declare moral certainty? If there is a 99.99% chance that a guy is the killer, can we safely condemn him? The general consensus is what is known as Cournot's principle, which connects mathematical probabilities with the empirical "real world":

  rare events simply don't happen

Or, as put by Kolmogorov: if $P(E)$ is very small and we make a single trial, we can be practically certain that $E$ will not happen.

Of course, none of this really "answers the question". In reality, finding out which probability you will associate to certainty is essentially a matter of three things:

How many trials could a cheater have?
How strong is the incentive to cheat?
How disastrous would be the rare event?

If the attacker has a single trial, and a mistake would not be the end of the world, go for $1/{2^{20}}$ and you'll be fine. If your life depends on the outcome, or an attacker could repeat trials as often as he wants until he succeeds, you want to take a large margin, and you can go for $1/{2^{128}}$.

Note: items 1 and 3 in my list above are, in fact, closely related. Indeed, extremely rare events appear all the time: take a deck of cards, shuffle it, pick ten cards. What was the probability that you would get exactly those ten cards? It's obviously extremely low. Most things are just not so important, so the situation where an unlikely event happens is in fact very common, as there are virtually many "trials" of "unimportant events". This justifies restricting our attention, not to any event, but to "situations with potentially disastrous outcomes": there are very few such situations, hence we get less trials to get a disastrous event.

Note 2: if you want more "actual numbers" for which some famous guy randomly decided that they indicate that an event is unlikely, look at Borel's choice in page 17 of the same pdf I linked to before: he mentions $10^{-6}$ as "uncertainty on the human scale", $10^{-15}$ as "uncertainty on the terrestrial scale", and $10^{-50}$ as "uncertainty on the cosmic scale". Which is, again, an attempted answer at the following question: how many trials does a human / the earth / the universe gets at producing an event with an important outcome?


I've searched about this problem these two days, considering the paper cygnusv mentioned, and finally after reading the problem related to the pqc implementation, I guess that's the condition which is not formally mentioned in NTRU papers. And this condition
$$q > p(6d + 1)$$
must be true in order for the probability of unrecoverable messages to be less than $2^{-80}$.


Efficient hardware implementation of real-time asymmetric video encryption I want to encrypt video directly at the source where it is being captured, e.g. inside a video camera. This way I can transmit the encrypted stream over WiFi securely.

I could use AES on the chip inside the camera, but this would be open to an attack on the semiconductor package, where an actor could retrieve the AES encryption key and use it to decrypt the data.

Is there an asymmetric encryption algorithm like RSA (which is unfortunately not efficient to encrypt a video stream), that is efficient at encrypting a video stream and that can also be implemented in hardware (like on an ASIC chip)?

This would allow me to store only the public key inside the ASIC, thereby increasing security. After receiving the encrypted stream I would be able to use the private key to decrypt it.

Would you recommend the video stream being compressed before being encrypted?

Would you recommend the video stream being compressed before being
  encrypted?

This is an excellent question in itself. What compression does, it recognizes redundancies in the data and removes those. So it changes the length of the data as a function of its value. Now cryptography doesn't promise to hide the length of the transmitted data, because that would be an impossible goal to achieve. So an outside attacker, could now go ahead and deduce some information about the plaintext, through the encryption, simply by looking at the length and frequency of packet transmissions. This in fact has been a famous attack, called CRIME, and has lead to TLS abandoning compression at the security protocol level. So you have to evaluate yourself whether the trade-off of leakage versus size gains is worth it to you.

Of course, with video being nicely encode-able with lossy methods, you can get a constant bit-rate encoding, where each unit of time of video material is encoded to the same unit of bit-output. As indicated in the other answers and the comments, this should leak very little to no information.

Now for your actual question:
(Hybrid) McEliece

McEliece is an old code-based signature scheme. It encrypts data by running it (as a vector) through a matrix-vector multiplication and then adds a limited amount of noise to the result. The decryption is more involved and essentially works off of error correction codes being applied to remove these errors. So let's go through things to figure out why it would be a good pick:

It is insanely fast. As you read above, it's simply a binary matrix-vector multiplication and a binary vector addition with some carefully generated noise. As such it is essentially, naturally, a lagre bunch of AND and XOR gates along with the output of a HW RNG, which can be built to be quite fast somewhat easily.
It is post-quantum resistant. McEliece (well, variants of it) are currently considered for the NIST post-quantum competition and McEliece has stood the test of time against quantum algorithms for a few decades now.
It has a large public key. Given that you don't actually seem to want to transmit the public key, this shouldn't be a problem in your case and even then, you mostly transmit video data, an extra Megabyte for the public key won't end the world.
Decryption is somewhat complicated. But this doesn't seem to be much of an issue for you, as far as I can tell.
It is rather badly supported. That is, it is used very sparsely. Given that you roll your own ASIC, you seem to be able to set your own standard here, but make sure to run things through proper cryptographers and don't just take the word of a random internet potato!
It lacks a lot of standardisation. When you use it "raw", that is not for some hybrid encryption as would be usual these days, you need to look around a bit to find a padding scheme that makes McEliece IND-CCA2 secure, which is really a security notion you want, but again, consult a proper cryptographer on this!

Now for your actual problem: The slow speed of asymmetric cryptogaphy. Well, there the solution of hybrid encryption. That is you take your favourite encryption scheme (such as McEliece), encrypt a lot of random bytes with it, prepend the ciphertext to the message and use the hash of the bytes as the key for authenticated symmetric encryption. This has the advantage that you can now keep the key for a (short) period of time in volatile registers and use the fast symmetric crypto to do the bulk of the work. Of course you can also pair hybrid encryption with slow asymmetric crypto such as RSA and just continuesly run the RSA encryption in a loop, generating a new session key once a second or so. The advantage of the hybrid encryption is that you need to spend less area on the asymmetric crypto (because you need less parallel instances / less area-time-trade-offs) and more on your actual logic and of course the fact, that you should have no problem finding pre-made IP for such symmetric encryption modules.


How to select corresponding ciphertext in anonymous Identity-based broadcast encryption? In identity-based broadcast encryption, suppose the broadcast ciphertext $(r_1,r_2,\dots,r_i,U,W,V)$ is sent to the receiver. It does not describe which user corresponds to which ciphertext part.
User $i$ should decrypt using the corresponding $r_i$ value. How do the users know about that?

In some cases, they use some function
$f(x)=k-\prod_{i=1}^{t} (x-v_{i})$ to get $k$ by replacing $v_{i}^{'}$ in place of $x$.

In real implementation, how to define such kind of function for unknown $x$ for $n$ receivers.

Example paper: Anonymous Multi-Receiver Identity-Based Authenticated Encryption with CCA Security (PDF) by Fan et al.

User $i$ should decrypt using the corresponding $r_i$ value. How do the users know about that?

From my understanding, a sender $S$ computes a polynomial $f(x)=\sum_{i\in\{0,...,t\}}c_ix^i$ which evaluates to $k$ if the the value of $x$ corresponds to the "share" of any of the designated user $ID_1,...,ID_t$ --- a share of a user $i$ as computed by $S$ is $v_i:=H_1(e(rQ_i,d_S))$, where $r=H_2(M,k)$. A receiver $i$, once it sees the polynomial, evaluates it on his share $v_i'=H_1(e(V,d_i))$ and if $v_i=v_i'$ it gets the gets back the key $k=f(v_i')$ (i.e., correctness). So, there is no correspondence between the users and the values of $c_i$s.

  In real implementation, how to define such kind of function for unknown $x$ for $n$ receivers.

As done in the paper, one just sends the coefficients of the function $f(x)$.

P.S. I hope I am not missing something.


Linear Cryptanalysis What is the principle of linear cryptanalysis, as applied to a block cipher ? For instance, this page gives the rough outline of differential cryptanalysis.

There is a reasonably clear description in section 2 of Pascal Junod's thesis.

A linear approximation, which allows guessing 1 key bit

Linear cryptanalysis begins by finding a linear equation which holds with probability distinct from $1/2$. We are talking about linearity in $\mathbb{Z}_2$, i.e. we XOR bits together. The question is a XOR of some specific bits of the plaintext, the ciphertext and the key (I am talking about linear cryptanalysis of a block cipher, as it was originally designed, about DES by Matsui in 1993). The XOR of several bits is either 0 or 1, and, assuming that the block cipher is "perfect", it should give 0 with probability $1/2$ and 1 with probability $1/2$.

Now let's assume that a given equation will yield 1 with probability slightly higher than $1/2$: for a given key, if you do the XOR with many plaintexts and corresponding ciphertexts, you will get 1 a little more often that you will get 0. This is the bias which linear cryptanalysis will exploit.

The first basic step is that by gathering many plaintext/ciphertext pairs, where the encryption used the key we want to attack (this is a "known plaintext attack"). For each of them, the equation is a XOR between a few bits of the plaintext, a few bits of the ciphertext, and a few bits of the key. For each pair, we know the plaintext and ciphertext, so the equation tells us what is the value of the XOR of the few key bits. The equation is "right" a bit more often than "wrong", so, with enough pairs, a majority emerges and gives us a definite answer. This yields 1 indirect key bit.

Guessing many more key bits

1 key bit is not much (although it divides by two the cost of exhaustive search), so Matsui enhanced the attack in the following way. Let's consider the linear cryptanalysis over the first 15 rounds of DES (DES has 16 rounds). That cryptanalysis has a corresponding linear equation. A quirk of DES (at that point it becomes useful to have a look at some schematics about DES) is that we can "mostly" see the output of the 15th round. For linear cryptanalysis, we are interested in some specific bits of the plaintext and of the "ciphertext", the ciphertext being here the output of the 15th round. We have the output of the 16th round; from it, we can compute the value of the bits we are interested in, from the output of the 15th round, provided that we correctly guessed a dozen specific key bits. That's because the 16th round modifies the output of the 15th round using the key, but not all key bits are involved in the computation of each bit for this round. Only 12 key bits in total have any influence on our "back-computation" where we try to compute the bits-for-the-equation in the 15th round.

Now comes the really smart part. Matsui runs 4096 linear cryptanalyses in parallel. That is, given the plaintext/ciphertext pairs (for the full 16 rounds of DES), Matsui tries each of the $2^{12} = 4096$ possible values for the 12 key bits, each of them allowing him to recompute the output of the 15th round, and apply the 1-bit linear cryptanalysis. Now, for the one instance where he guessed correctly, the 1-bit linear cryptanalysis "works" and a clear majority emerges; but for the others, the incorrect guess on the key bits means that we work with wrong values (for the 15th-round bits), so the equation does not work and no clear majority emerges. So the attack not only yields one indirect key bit (from the equation) but also twelve additional key bits: the twelve bits which make the 15-round linear approximation work. 13 key bits, now that's good: it divides cost of exhaustive key search by 8192.

Matsui got even further by doing the "guess some key bits" for two rounds, the first and the last, using a linear approximation of 14 rounds (rounds 2 to 15). This yields 22 direct key bits (and one indirect). DES has 56 key bits, so the remaining $2^{33}$ are easily obtained by exhaustive key search (only 8 billions of possibilities).

Limitations

The real problem with linear cryptanalysis is that it needs many known plaintext/ciphertext pairs, enough for a clear majority to emerge when applying the linear approximation (the equation is only slightly more often right than wrong). Matsui computed the number of needed pairs to be $2^{43}$, although Junod found out that with a few tweaks, $2^{39}$ are enough. Each plaintext is 8 bytes, so we are talking about 4 terabytes. There are not many attack situations where the attacker can correctly guess 4 terabytes of plaintext, and still needs to obtain the key...

(Linear cryptanalysis of DES is how I first entered the realm of cryptography; my task was to reimplement Matsui's method on DES reduced to 8 rounds. The approximation on 6 rounds is much better than on 14 rounds, so it requires only a million or so plaintext/ciphertext pairs. It took less than a minute on the machines of that era, 50 MHz Sparc systems. The part about guessing some key bits and doing many 1-bit cryptanalyses simultaneously is what took me the most time to understand. It was very educational.)


hill cipher encryption way 1x3 plaintext matrix Can someone help me with a Hill cipher?

When do I have to use:

1x3 plain text matrix (p1, p2, p3) * 3x3 key matrix
3x3 key matrix * 3x1 plain text matrix

Or they are both correct?

I tried to search the internet, but found nothing useful.

Both representations are essentially equivalent.  If

$$
\begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix}
= \begin{bmatrix} k_{11} & k_{12} & k_{13} \\ k_{21} & k_{22} & k_{23} \\ k_{31} & k_{32} & k_{33} \end{bmatrix}
\cdot \begin{bmatrix} p_1 \\ p_2 \\ p_3 \end{bmatrix},
$$

then, equivalently

$$
\begin{bmatrix} p_1 & p_2 & p_3 \end{bmatrix}
\cdot \begin{bmatrix} k_{11} & k_{21} & k_{31} \\ k_{12} & k_{22} & k_{32} \\ k_{13} & k_{23} & k_{33}
\end{bmatrix}
= \begin{bmatrix} c_1 & c_2 & c_3 \end{bmatrix}.
$$

This is a special case of the general rule that

$$ c = K p \iff p^\top K^\top = c^\top, $$

where $M^\top$ denotes the transpose of the matrix $M$.


Are the RFC3526 MODP groups Schnorr groups? I was wondering if a group like the 1536-bit MODP Group from RFC 3526 was a
Schnorr group?

A Schnorr group must apparently have:

$p$ and $q$ being primes
$p = q\cdot r+1$
$1 < h < p$
$h^r\not\equiv 1\pmod p$

And then $g = h^r\bmod p$ is the generator.

In RFC3526's 1536-bit MODP, there's a prime:
$$2^{1536}-2^{1472}-1+2^{64}\cdot\lfloor2^{1406}\cdot\text{pi}+741804\rfloor$$
(not too sure what $\text{pi}$ is here)
and the generator is $g=2$.

My question is if such a group is a Schnorr group or not?

If it's a Schnorr group, what are the values or $p$, $q$, $r$ and $h$?

References:
RFC3526 MODP Diffie-Hellman groups for IKE
en.wikipedia.org/wiki/Schnorr_group

Yes, it meets the formal definition of a Schnorr group; however it was constructed somewhat differently.  Normally, when we generate a Schnorr group, we pick a prime $q$, and then search for an $r$ so that $qr+1$ is also prime; with the RFC3526 group, they picked $p$ and $q$ simultaneously.  In addition, when it came to selecting the generator, they did not select the value $h$ and compute $g$ from that.  Instead, they selected $p$ such that $g=2$ generated a prime subgroup.

As for the values you asked about:

$$p = 2^{1536} - 2^{1472} - 1 + 2^{64} * \lfloor 2^{1406} \pi + 741804 \rfloor$$

(and yes, $pi = \pi$ is everyone's favorite transcendental number)

$$q = (p-1)/2$$

$$r = 2$$

$$h = 2^{(p+1)/4} \bmod p$$

We have this rather odd looking $h$ because that makes $h^r \equiv 2$.  Since Schnorr groups had no restriction on what $h$ is (other than $h^r \not\equiv 1$), this satisfies the definition.


Security implications of not concatenating a 1 to the IV when using GCM When using GCM, The padding string $0^{31}||1$ is appended to the IV. I know that this is done to avoid the repetition of $E_K(0^n)$ which is used as key for the GHash. But what would be the security implications if the IV could be $0^n$, what concrete attacks would be possible then?

If the counter mode started at $\text{Nonce}\mathbin\|0^{32}$ instead of at $\text{Nonce}\mathbin\|0^{31}\mathbin\|1$ then one could submit an encryption query for $(0^{96},0^{128})$, i.e. the 128-bit all-zero plaintext along with the all-zero nonce. The first block of the ciphertext would then be computed as $E_K(0^{128})\oplus 0^{128}=E_K(0^{128})$ which is just the global GHash key $H$ and the blinding value for the $0^{96}$ nonce.

If you have both of these values, and the latter one is leaked through a similar strategy for each nonce value, you can do arbitrary modifications of the ciphertext, which directly propagate into the plaintext through counter-mode's homomorphic property, and fully recompute the authentication tag yourself and submit that to your decryption oracle, which will accept the tag and return a valid decryption 100% of the time which completely breaks all security notions that try to ensure some form of integrity (e.g. CCA-security, INT-PTXT, INT-CTXT, AE, ...).

And even if you specifically disallow $0^{96}$ as a nonce, you still get the blinding value which allows you to recover $H$ at least for single-block messages given that the tag is $((c_1\cdot H)\oplus (\operatorname{len}(A)\mathbin\|\operatorname{len}(C)))\cdot H\oplus E_K(\text{Nonce}\|0^{32})=c_1\cdot H^2\oplus (\operatorname{len}(A)\mathbin\|\operatorname{len}(C))\cdot H\oplus E_K(\text{Nonce}\|0^{32})=\tau$ which is a quadratic equation in one unknown over a field which is solvable using the standard equation and a square-root computing method.


What is the use of encoding a hash output? In many applications, the MD5 algorithm is used which produces a 128-bit output which is represented as a sequence of 32 hexadecimal digits.
This output is further encoded using a base62 or base64 scheme.

I wanted to understand what is the need for further encoding the hash value.
Why could we not use the same hash value and store it in our databases?

Is it done to reduce space consumption?

Based on my understanding, the MD5 hash output is 16 bytes. When we encode it using the base64 scheme and produce 8 char long string, it will be 8 bytes.

What is the need for further encoding the hash value?

Representing the hash as a string of characters, without increasing the size too much. This is known as Binary-to-text encoding. It is commonly used for cryptographic data (hashes, ciphertexts..), because that can contain arbitrary sequences of bits (or arbitrary sequences of arbitrary bytes), and some data communication, storage or display means can only handle characters in some alphabet.This is not to be confused with encoding characters into bytes, as needed to hash or encipher text.

I will make the explanations and examples with the MD5 hash of a 26-ASCII-character message given in example in RFC 1321 appendix A.5:

  MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b

The hash is not c3fcd3d76192e4007dfb496cca67e13b. It really is a 128-bit sequence (or bitstring) which representation with 0 (resp. 1) for a bit clear (resp. set) is:

11000011111111001101001111010111011000011001001011100100000000000111110111111011010010010110110011001010011001111110000100111011

The 32-character sequence c3fcd3d76192e4007dfb496cca67e13b is a representation of the hash per lowercase big-endian hexadecimal. That was obtained from a representation of that hash as 16 bytes (or equivalently 16 octets) per this code C code (from the RFC):

/* Prints a message digest in hexadecimal.
 */
static void MDPrint (digest)
unsigned char digest[16];
{
  unsigned int i;
  for (i = 0; i < 16; i++)
    printf ("%02x", digest[i]);
}

Note: In the above, unsigned char is a byte representing an integer in range [0…255] that encodes 8 bits of the hash. Conversion to characters is in the printf function, with "%02x" specifying at least 2 lowercase hexadecimal characters.
Note: Each group of 4 bytes is the little-endian representation of a computer word, but that's a consideration internal to MD5.

Beside the aforementioned representations as 16 bytes, and 32 lowercase (big-endian) hexadecimal characters, there are other common representations, including

C3FCD3D76192E4007DFB496CCA67E13B : 32-characters, uppercase (big-endian) hexadecimal
w/zT12GS5AB9+0lsymfhOw== : 24 characters, Base64 per RFC 4648
w_zT12GS5AB9-0lsymfhOw== : 24 characters, Base64 with Filename Safe Alphabet
w/zT12GS5AB9+0lsymfhOw : 22 characters, Base64 with pad suppressed

If is possible to convert from a text (equivalently, character) encoding back to the hash. The same hexadecimal decoding method can handle uppercase and lowercase. The same Base64 decoding method can handle common alphabets and make pad optional.

There are other, more seldom-used, sometime more compact Binary-to-text encodings. See this for why Base64 is most popular.

  When we encode (a 16-byte MD5 hash) using the base64 scheme and produce 8 char long string, it will be 8 bytes.

No. Each Base64 character encodes 6 bits (except the last non-pad character which can encode 2, 4 or 6 bits; and final pad characters, if any). Therefore, per Base64 encoding, a 128-bit hash requires at least ⌈128/6⌉ = 22 characters, plus pad if any.

Depending on computer language and options, each character may in turn use several bytes. For example, each character in a C string is represented by 1 byte, in a Java String 2 bytes. Also, there is size overhead for each object, which may not be negligible.In a Python string, starting with version 3.3 or so of Python, each character in the above encodings by default uses 1 byte. In previous versions it used 2 or 4, depending on Python environment; refer to PEP 393.


Using password-based encryption as a hashing scheme Classic scheme:

Given password and hashing algorithm
Generate salt
Calculate hash=hashing(password, salt)
Separately storing hash & salt

Checking password validity: comparing stored hash with calculated test_hash=hashing(test_password, salt). If hash=test_hash - password is ok, otherwise test failed.

Proposed scheme:

Given password, cipher algorithm and predefined dictionary (e.g. set of digits {0,1,2,3,4,5,6,7,8,9})
Generate salt
Generate random test_phrase from our dictionary (e.g. only random digits, like test_phrase=32759823767865236451236647894678923897)
Calculate hash=cipher(test_phrase) with key=keygen(password,salt)
Storing hash and salt (no need to store test_phrase)

Checking password validity:

calculating test_phrase=decipher(hash) for a test_key=keygen(test_password,salt)
check if test_phrase consists only symbols/bytes of predefined dictionary (e.g. decrypted phrase are only digits, say if decrypted phrase is smth like: askjdfhasjkdfhasjkdhe-0123=jkasfhasjdfh - that means test failed, since some symbols are not digits)

Question

What do you think about pros/cons for this proposed hashing scheme?

Essentially, instead of checking against a (salted) hash of a password, you suggest using the hash (since you can choose hashing = keygen) as a key to encrypt a kind of test value. The main question is whether this adds or reduces security.

If you store the hash/key directly, the chance of a randomly chosen password hashing to the same value is $2^{-n}$, where $n$ is the length of the hash in bits.
If you use the key to encrypt a string from the dictionary in your example (10 out of 256), the chance that a random key (from a password guess) decrypts the stored value to a valid $k$-bit string is $(10/256)^{k/8} = 25.6^{-k/8} \approx 1.5^{-k}$.

To have equivalent security you need to store a longer verification string. For example, to match the security of a 256-bit hash value, you'd need to encrypt a 439-bit value.

In addition, the whole process would allow an attacker to discard wrong guesses slightly faster than the verification process takes, since most encryption algorithms encrypt in blocks and if the first block is a mismatch, the whole thing must be.

That's without considering the inherent insecurity in using a complex scheme that relies on multiple primitives for its security.

You could get back to an equal length-to-security ratio by encrypting a known string (like a string of zeros) instead. The downside of complexity would remain, without a clear upside to compensate. It could be more resistant to a weak hash, but that might be difficult to prove.


What is the significance of i^Q mod P = 1 and are there any special properties to be aware of? I'm studying UProve, and one of the fundamental components of this technology is based upon the relationship between

  i^Q mod P = 1

Lacking a specific name I can call this mathematical relationship, where can I learn more about this equation?

I've heard that not only will the equation equal one, but there are instances it may equal P.

PS - I'm not sure how to tag this so your feedback is welcome, or let me know if this is better on the math.SE

A special case of the relation you've found is called Fermat's little theorem.
In a more "mathy" way this looks like:

$i^Q\equiv 1 \pmod p$

which will always hold for $Q=p-1$ and for any $Q|p-1$.

The use of this theorem is limited in cryptography, however the problem of determining $Q$, if only $i$ and $p$ are known, this problem is called "discrete logarithm problem" (assuming there isn't a "1" on the right side but rather some random number).

If $p=r*s$ and you're given $Q$ then this is called the RSA-problem (the problem if finding the Q-th root modulo p), again assuming the right side isn't 1 but rather some random number.