Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1? I am from a web development background (I don't know an awful lot about cryptography or how the algorithms themselves work), so I am asking this question in simple terms.

Consider a hash of the word 'test' using SHA1:

a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

If I were to use SHA512 instead and then simply take the first 40 characters of the output:

ee26b0dd4af7e749aa1a8ee3c10ae9923f618980772e473f8819a5d4940e0db27ac185f8a0e1d5f84f88bc887fd67b143732c304cc5fa9ad8e6f57f50028a8ff

ee26b0dd4af7e749aa1a8ee3c10ae9923f618980

Questions

Are there any security implications for hashing and storing sensitive data like this?
Is it more or less secure than using the full SHA1 hash?
Is there an increased risk of hash collision when using the truncated version?

This is sparked by a debate over somebody doing this, where their reason was that it would be better to use the SHA512 version because it is a more secure algorithm, and by truncating it a potential hacker wouldn't know which algorithm was used in the first place.

My understanding was that SHA1 would always produce a unique value, whereas there is a chance that the first 40 characters of a SHA512 output could appear many times.

As a general rule, you should not use SHA1; instead, go with one of the hash functions from the SHA-2 family.

As far as truncating a hash goes, that's fine. It's explicitly endorsed by the NIST, and there are hash functions in the SHA-2 family that are simple truncated variants of their full brethren: SHA-256/224, SHA-512/224, SHA-512/256, and SHA-512/384, where SHA-$x$/$y$ denotes a full-length SHA-$x$ truncated to $y$ bits. (Technically the starting algorithm constant is different for the truncated versions, as pointed out by Henno Brandsma, but this is somewhat orthogonal to the point I'm trying to make.)

  Are there any security implications for hashing and storing sensitive data like this?

As far as determining the sensitive material from the digest itself, you're safe. All secure modern-day cryptographic hashes have what is called preimage resistance, which essentially means that it is computationally infeasible to "reverse" the hash, if you will. So, your sensitive data's confidentiality won't be compromised by storing the digest. (Note: See Gordon Davisson's comment below about this; there are possible security implications in some scenarios.)

Now, the real question is: why are you wanting to store the hash in the first place? Hopefully you are not using it to detect if the data is maliciously modified; that generally is the purview of a MAC, such as HMAC or CBC-MAC.

  Is it more or less secure than using the full SHA1 hash?

Much more secure, actually, if you care about collision resistance. There is an attack on SHA1 that finds collisions in 260 time, whereas truncating SHA-512 to 160 bits requires 280 time to find collisions (see the birthday attack). So, truncating one of the SHA-2 functions to 160 bits is around 220 times stronger when it comes to collision resistance. (Plus, finding collisions is now within the realm of possibility for SHA1. So, if you are reading this, and you are building a new system, you should choose SHA-2 or SHA-3.)

  Is there an increased risk of hash collision when using the truncated version?

Increased risk over SHA1? No. Increased risk over using the full SHA-512 output? Yes.

Truncating the output of a hash function always decreases its (theoretical) collision-resistance. In practice, it usually doesn't matter too much; for instance, 280 time is still pretty big. Still, if you used the full output of SHA-256, the same birthday attack would take 2128 time, which is totally out of reach.

  by truncating it a potential hacker wouldn't know which algorithm was used in the first place

Always assume the attacker knows everything about your algorithm/cryptosystem except for the secret keys. This is known as Kerckhoffs's principle. Why this is important is well-covered, so you should follow it.

  My understanding was that SHA1 would always produce a unique value, whereas there is a chance that the first 40 characters of a SHA512 output could appear many times.

SHA1 doesn't produce unique values. There are infinitely-many possible inputs to SHA1 (it takes a bitstring of any length), yet there are only 160 bits of output. By the pigeonhole principle, there have to be infinitely-many values that map to the same 160 bits of output. In February 2017, a SHA-1 collision was published. However, there have not been any published SHA-256 collisions to date, despite that the pigeonhole principle guarantees they exist.

I should note, if you are going to use the full output of SHA1, SHA-256, or SHA-512, you should be aware of length extension attacks.


Help in understanding exactly how lattices used as one way functions for hashing I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers and videos in an attempt to build my understanding of the subject, but due to the intensely technical manner in which information on the subject is presented, I have not been able to answer many questions in my mind. Due to the structure of my long distance course I have no access to professors or extensive libraries so my question is one which merely seeks to increase my understanding, please bear with me.

Thus far I have understood that:

Lattices are a collection of regularly ordered points in euclidean space (its terms like this which have caused me to be searching for answers for days)
A lattice may be defined through n vectors called a basis where n = the dimension (for now I am working in dimension 2), and any other basis can be found by applying positive or negative multiples of each vector in the basis to another vector in the basis
Defining a lattice L1 as a set of points allows one to multiply the whole set by some co-efficient which will essentially transform it into a new lattice L2
The determinant of the vectors of the basis essentially tells us the volume (area in 2 dimensions) of the parallelpiped which will be repeated to form the lattice, the lattice points being the vertices.

Having said this, I am now stuck in understanding how I move all of this to cryptography. I am on a question which asks me to compute the output for 3 inputs to a function:

  We will see that q-ary lattices give provably collision-resistent hashing. We choose integers q; a and b. Our hash function (presented by Mikl´os Ajtai in a breakthrough paper in 1996) is a 2-variable function: h(x, y) = ax + by mod q.
  (a) For q = 5; a = 14; b = 13; compute h(17, 8), h(21, 16) and h((17, 8) - (21, 16))

Having found the answers…

h(17, 8) = 14*17 + 13*8 = 342 mod 5 = 2;
h(21, 16) = 14*21 + 13*16 = 502 mod 5 = 2;
h((17, 8)-(21, 16)) -> (h(-4, -8) = 14*-4 + 13*-8 = 160 mod 5 = 0

I believe this means that with the first two points the lattice has been moved by some multiple of 5 plus two, which has displaced it by two and thus formed a new lattice. While in the last case, the lattice has been moved by a multiple of its determinant and thus is the same lattice.

However, I just cannot understand the link to hashing. In an application would the points be the cleartext and the answer modulo 5 the output of the hash function? If so would'nt there be too many collisions as we have already seen two examples of which give the answer 2? How exactly is this linked to the shortest vector problem or short integer solution if they are not the same thing? Are q-ary lattices aonly an attempt to store the basic pattern needed to reproduce the lattice? and if so wouldn't the lattice itself be the cleartext and the basic pattern (given by the basis and the determinant) the answer from the hash function? How exactly would you encrypt a message using a lattice?

I just wish I could find some text which explained this in English rather than symbols… like this http://www.wisdom.weizmann.ac.il/~odedg/COL/cfh.pdf . I really hope I have not repeated any questions through my lack of understanding. Thanks in advance.

I'm also afraid you couldn't understand this as D.W., but let us start.
I sometimes cannot understand your questions. Please restate them, if possible.

The definition of the Ajtai hash functions

Let $n$, $m$, and $q$ be positive integers.
Let $R = \mathbb{Z}_q$ be the quotient ring of integers modulo $q$.
Let us define a function, which maps a vector in $D^m \subset R^m$ to $R^n$ and is indexed by a matrix $\boldsymbol{A}  \in R^{n \times m}$ as follows:

$f_\boldsymbol{A}(\vec{x}) = \boldsymbol{A} \vec{x} \bmod{q} = \sum_{i=1}^{m} x_i \vec{a}_i \bmod{q}$.

The Ajtai hash functions is defined as a family of the above hash functions;

$\mathcal{F}_{n,m,q,D} = \{f_{\boldsymbol{A}}:D^m \to R^n \mid \boldsymbol{A} \in R^{n \times m}\}$.

You can obtain your function by setting $n=1$, $m=2$, $q=5$, and $D = R$;
then set $\vec{a}_1 = 14 \ (= 4)$ and $\vec{a}_2 = 13 \ (= 3)$.

For example, you can set $n = 256$, $q = 4097$, $m = 4096$, and $D = \{0,1\}$.
The input of the function is a bit string of length $4096$
 and the output of the function on such parameters is $256$-dimensional vectors whose coefficients are in $\mathbb{Z}_q$.

Is it shrinking?

Good parameters makes the above functions shrinking.
Correctly speaking, if the size of domain is larger than the size of range, that is, $|D|^m > |R|^n$, the function is (obviously) shrinking.

A possible choice of parameters is $D = \{0,1\}$ and $m > n \log_2(q)$, which often appears in the context.
Another possible choice is $D = \{-1,1\}$ or $D = \{-1,0,1\}$.

Is it hard to find a collision? What is the relation between a collision and a short vector?

  How exactly is this linked to the shortest vector problem or short integer solution if they are not the same thing?

If $D = R$, it is too easy to find the collision is function by the power of the linear algebra. You can use Gauss's elimination if $R$ is a field.
But, if $D \subset R$ and the size of $D$ is small, it becomes hard.
Roughly speaking, the number of collisions depends on the ration $|D|^m/|R|^n$.

In 1996, Ajtai shows that, for good parameters, if there exists an inverter of his hash functions, then there exists an algorithm finding a short vector from any $n$-dimensional lattice.
Goldreich, Goldwasser, and Halevi pointed out in the note you refer that, if there exists an algorithm finding a collision of the Ajtai hash functions, then there exists an algorithm finding a short vector from any $n$-dimensional lattice.
The reductions are based on the fact that the sum of short vectors is (relatively) short.

How should we interpret the above in lattice words?

You would skip this part.

We define a lattice related to a matrix $\boldsymbol{A}\in R^{n \times m}$ as

$\Lambda = \Lambda_q^{\perp}(\boldsymbol{A}) = \{\vec{e} \in \mathbb{Z}^m \mid \boldsymbol{A} \vec{e} \equiv \vec{0} \bmod{q}\}$.

This $\Lambda$ is an $m$-dimensional lattice.
(You can check this is a lattice by verifying that for any two vectors $\vec{e}, \vec{e}' \in \Lambda$, the sum of them lies in $\Lambda$ again.
 You can check this is $m$-dimensional by verifying that any $q \vec{u}_i$ is in $\Lambda$, where $\vec{u}_i$ is a unit vector).

This lattice defines a map from $\mathbb{Z}^m$ to a quotient group $\mathbb{Z}^m/\Lambda$, which is isomorphic to $R^n$.
The map is a hash function.

Conversely, a collision $\vec{e} \neq \vec{e}'$ for $f_{\boldsymbol{A}}$ implies a short non-zero vector $\vec{e}-\vec{e}'$ in $\Lambda_q^{\perp}(\boldsymbol{A})$.


Is it possible to work out the hash using length extension attack but with different hashes type? For example, I have:

Unknown: A secret variable, lets call it secret, that is unknown to me
Known: The length of secret, (lets say 128 bytes)
Known: The hash of secret, in hash1 (lets say hash1 is sha512, this is an important part of the question since hash1 isn't hash2)

My objective here is to get hash2(secret || data_that_I_know), but hash2 being different than hash1, (lets say hash2 is sha1).

With my current understanding of the length extension attack I believe I can obtain the digest of hash1(secret || data_that_I_know), but, is it possible to get the digest from another hash type (like sha256, md5 etc.)?

This is not possible in general, or for the specific case of SHA1 and SHA512. Length extension works because MD-hashes iterate the same function, so knowing the output you also know the intermediate state for some related longer inputs.

Now there are some cases with "different" hashes where it could be possible. That its when the hashes are related. Like SHA512 -> SHA512/500 or another such truncated hash that uses the same IV and compression function.

In that case you can use the normal length extension attack and just truncate the final output.


What is cryptographic agility? I keep seeing the term "Cryptographic Agility" referenced. What does it mean?

For instance:

https://msdn.microsoft.com/en-us/library/windows/desktop/bb204775(v=vs.85).aspx

  One of the key value propositions of CNG is cryptographic agility, sometimes called cryptographic agnosticism.

http://research.microsoft.com/apps/pubs/default.aspx?id=121045

https://media.blackhat.com/bh-us-10/whitepapers/Sullivan/BlackHat-USA-2010-Sullivan-Cryptographic-Agility-wp.pdf

The second source suggests that it means multiple encryption algorithms can use the same key. Is this true?

Cryptographic agility is the capacity for an IT system to easily evolve and adopt alternatives to the cryptographic primitives it was originally designed to use.

An example (and building block) for cryptographic agility is the X.509 certificate format, which is defined with various signature algorithms, hash algorithms, and key sizes, in a manner allowing in principle future growth.

Another is crypto provider APIs, such as Java's com.sun.crypto.provider.

A huge drawback of cryptographic agile systems is their complexity, leading to implementation and usage errors, incompatibilities and hasty workarounds for these, all conspiring to create security issues; examples abound. Also, the supposed agility often fails as soon as it is needed.

As an example of the later that recently hit me, consider code using Java's com.sun.crypto.provider made some time ago, invoking a cipher with

  Cipher cipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA-1AndMGF1Padding");

and having made the string parameterizable. Now, because SHA-1 collision resistance is broken, some authority says that it must be replaced with SHA-256 everywhere including in that application (notwithstanding the fact that SHA-1 remains perfectly safe in that application, as far as we know). So, we change the parameterizable string to "RSA/ECB/OAEPWithSHA-256AndMGF1Padding" and are flying, right? Er, no. It turns out that MGF1 stands for a mask generating function that uses a hash, which remains SHA-1 by default, and there is no such thing as "RSA/ECB/OAEPWithSHA-256AndMGF1WithSHA-256Padding", or hope that it will be added soon to com.sun.crypto.provider (see this answer for details); so you have to change the code anyway, plus add a lot of new messy non-standard things all around to have the hash parameterizable as a single string, as the IT system requires.

And there are other more subtle issues, including this (potential) security one: by using SHA-256, all things being equal, we reduce the message capacity for a single RSA block, and it is likely hard to rule out that com.sun.crypto.provider, or some other, will happily and transparently add a second block oblivious to us; thus we might end up with two RSA blocks, and that could well create a vulnerability that did not previously exist.

Proponents of cryptographic agility could understandably object to this line of thought that if com.sun.crypto.provider was more crypto-agile, the argument would fall apart.


Defining Symmetric vs Asymmetric cryptosystems I'm writing a project on the advantages and disadvantages of symmetric vs asymmetric cryptosystems. At the moment I am trying to define both systems using mathematical notation. Under the heading "Basic Cryptosystems" I have this:

  We can define the cryptogram functionally as
  \begin{equation}
\mathit{C=f(M,K)}
\end{equation}
  It will also be helpful to think of the cryptogram as a family of transformations with one parameter like this
  \begin{equation}
\mathit{C=T_{k}M}
\end{equation}
  The transformation $T_{k}$ applied to the message $M$ produces cryptogram $C$. The operation of the transformation $T$ will depend on which cryptosystem is being used. The index $k$ corresponds to the particular key being used.
  Assume there are a finite number of keys, each with associated probability $P(T_{k})$. There will then be some discrete statistical process which chooses a transformation from the set $T_{1}, T_{2}, ..., T_{n}$. These transformations have associated probabilities $P(T_{1}), P(T_{2}), ..., P(T_{n})$ respectively.
  We should also assume a finite number of possible messages $M_{1}, M_{2}, ..., M_{m}$ with associated a priori probabilities $P(M_{1}), P(M_{2}), ..., P(M_{m})$.
  Once $C$ is received, it can be deciphered with $k$ in order to reveal $M$. This is achieved with a unique inverse transformation $T^{-1}_{k}$ such that $T_{k}T^{-1}_{k}=I$, the identity transformation. So
  \begin{equation}
M=T^{-1}_{k}C
\end{equation}
  The inverse transformation must be unique for every $C$ which can be deciphered with key $k$ to reveal $M$.

My question is: does this definition apply to both symmetric and asymmetric systems? If not, how can I change it to account for asymmetric systems?

thanks

Your definition only covers symmetric encryption since the same "index" $k$ is used in $T_k$ and $T^{-1}_k$ (i.e., encryption and decryption use the same key)

If you want to give a generic definition that covers both types of encryption, you could say that the transformations are $T_k$ and $T^{-1}_{k'}$ and that in the case of symmetric encryption $k'=k$.


Purpose of repeating a 16-byte key for Salsa20 The core of the Salsa20 family of stream ciphers is a hash function that takes a 64-byte block, using it to generate a pseudorandom 64-byte output. The 64 bytes contain space for

a 32-byte key
a 16-byte constant
an 8-byte counter
an 8-byte nonce

These ciphers are intended to be used with 32 byte keys, but they can also be used with smaller keys. Using a 16 byte key involves changing the constant so there are no equivalent keys between the different sizes, and repeating the 16-byte key so it fits into 32 bytes (i.e. the input is $k \mathbin\| k$ for a 16-byte $k$ and just $k$ for a 32-byte $k$).

Why is this done? Why is the key not simply zero-padded? If cryptanalysis (but not exhaustive search) of the keystream can be made easier when a key without uniform distribution is used, the scheme is broken.

From section 4.1 of The Salsa20 family of stream ciphers:

  The diagonal constants are the same for every block, every nonce, and every 32-byte key. As an extra (non-recommended) option, Salsa20 can use a 16-byte key, repeated to form a 32-byte key; in this case the diagonal constants change to 0x61707865, 0x3120646e, 0x79622d36, 0x6b206574.

If we fix the second half of the key to all zeros we have at least 2 potential issues:

The zero-bits offer no additional diffusion effect, whereas repeating the key increases the diffusion effect.
Normally the adversary would know $1/2$ of the input and control $1/4$, but with $16$ more static known bytes, the adversary now knows $3/4$ of the input. This might give the adversary enough control to mount more attacks that may have not yet been analyzed; though likely only with a reduced round chacha.

Without doing the expensive analysis, I can only conjecture that the static zero bytes would only weaken chacha. I do not know by how much, but I do doubt it'll be enough to break the full 20-round chacha.


Can a commutative block cipher be indistinguishable from a random permutation, for fixed key? Define a commutative block cipher with keyspace the finite set $K$, and data space the finite set $S$, to be an application
$$\begin{align}
E:K\times S&\mapsto S\\
(k,x)&\mapsto E(k,x)\text{ also noted }E_k(x)\\
\text{such that }&\forall k\in K,\forall x\in S, \forall y\in S,\text{ if }E(k,x)=E(k,y)\text{ then }x=y\\
\text{and }&\forall k\in K,\forall k'\in K, \forall x\in S,E(k',E(k,x))=E(k,E(k',x))\\
\end{align}$$
Note: the first property states that the application $E_k$ from $S$ to $S$ is injective, implying that it is a permutation of $S$ given this is a finite set, and that's standard for a cipher; the second property is what makes the cipher commutative.

Question: what commutative block cipher do we have that is

conjectured computationally indistinguishable with effort polynomial in $\log(|K|)$ from a random permutation for unknown random fixed key $k$, assuming the attacker can obtain ciphertext for iteratively chosen plaintext;
efficiently computable, at least in the encryption direction (and preferably for decryption as well)?

If there was none: do we have some proof this can't be achieved?

In this answer, I explored a variant of the Pohlig-Hellman Exponentiation Cipher $(k,x)\mapsto E_k(x)=x^k\pmod p$ but stalled with something that remains distinguishable from a random permutation due to a multiplicative property similar to that of naked RSA: $\forall k\in K,\forall x\in S, \forall y\in S, E_k(x\cdot y\bmod p)=E_k(x)\cdot E_k(y)\bmod p$.

Update: the question as is was perfectly answered by poncho. Here is take two.

It can't be achieved under the assumptions you are making, because the attacker can distinguish it by selecting an arbitrary $k'$, and checking if $E(k')$ commutes with the permutation in question.  That is, to check a permutation $P$, we pick an arbitrary $x$, and check if:

$E(k', P(x)) = P(E(k',x))$

This equation always holds if $P = E(k)$ for some value $k$, and rarely holds if $P$ is a random permutation.


Perfect Indistinguishability in shift cipher I have the following question:

  Which of the following attackers can be used to demonstrate that the
  shift cipher for 3-character messages does not satisfy perfect
  indistinguishability?

  Output m0 = 'aaa' and m1 = 'bbb'. Given challenge ciphertext C, output
  0 if the first character of C is 'a'.

  Output m0 = 'abc' and m1 = 'bcd'. Given challenge ciphertext C, output
  1 if the three characters of C are all different.

  Output m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output
  1 if the three characters of C are all different.

  Output m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output
  0 if the first character of C is 'a'.

I assumed it was "Output m0 = 'aaa' and m1 = 'bbb'. Given challenge ciphertext C, output 0 if the first character of C is 'a'." since the shift cipher would be predictable (this is what I think) if the messages had the same characters in a row.

Can anyone explain why it should be :
Output m0 = 'aaa' and m1 = 'abc'. Given challenge ciphertext C, output 1 if the three characters of C are all different.

I'm assuming that, that attacker produce $m_0$ and $m_1$ and given one of their ciphertext as a challenge.

given $c$, the attacker cannot distinguish whether it is encryption of $m_1$ or $m_2$. Since, he doesn't know the key. He can guess only 1/2 probability. For this attacker, it has perfect indistinguishability.
given $c$, the attacker can distinguish that the plaintext has all characters different. Because the shift cipher's property, $$c = E_k(m_1) \text{ and } c=E_k(m_1) \Leftrightarrow  m_1 = m_2$$ and he output $m_0$ and $m_1$ with all different characters.
given $c$, the attacker can distinguish that the plaintext has all characters different. Because the shift cipher's property and and he was output $m_0$ as $aaa$ and $m_1$ as all different characters.
given $c$, the attacker can distinguish that because the attacker output $m_0$ and $m_1$, on advance he knows that first letter is always an $a$

As a result; 2,3, and 4 can be used to demonstrate that the shift cipher for 3-character messages does not satisfy perfect indistinguishability


How does the ring settings of enigma change wiring tables? EDIT: The model I'm trying to make is "Enigma 1". I learned initially about it from a book called "Code Book" and then looked at it in detail from its wikipedia page. The site wont allow me too add more links but google "enigma rotor details" and see the wikipedia page

There is a similarly worded question here but it doesn't answer mine.

I am trying to make an enigma simulator. I have finished doing everything except the ring settings. How do they affect the substitutions?

For example suppose the initial rotor settings are:

abcdefghijklmnopqrstuvwxyz
ekmflgdqvzntowyhxuspaibrcj

I think by applying the ring setting of B or 2, the settings should become:

abcdefghijklmnopqrstuvwxyz
kmflgdqvzntowyhxuspaibrcje

I think all I should have to do is add the ring positions to the rotor positions. But that doesn't seem to be the case.
I tried decrypting the first sample message from here that way but didn't succeed. I even tried to make the program run in a loop till it finds the intended answer so I could deduce the relation between ring settings and rotor positions, but it never found it.

But using the same settings on an online enigma simulator worked. Everything seems to be the same except that according to the online simulator, the rotor wirings on a ring setting of b or 2 should be:

abcdefghijklmnopqrstuvwxyz
kflngmherwaoupxziyvtqbjcsd

How on earth did it turn into that?

There's two missing pieces.  First, the ring setting changes the output letter, it doesn't rotate the whole exit pattern.  Second, the rotors are advanced before the letter is encrypted.

If your rotor (Enigma I Rotor I) is set up like this with the ring at A.

abcdefghijklmnopqrstuvwxyz
ekmflgdqvzntowyhxuspaibrcj

Then if you advance the ring to B all the outputs will be shifted up the alphabet by one.  A will become F instead of E.  B will become L instead of K.  And so on.

abcdefghijklmnopqrstuvwxyz
flngmherwaoupxziyvtqbjcsdk

This almost matches the simulator, but why is the simulator's output shifted over one?

abcdefghijklmnopqrstuvwxyz
kflngmherwaoupxziyvtqbjcsd

  Remember that, when depressing a key, the rotors advance before the electrical signal runs through the rotors. Therefore, to examine the current flow through the rightmost rotor in A position, the rotor must be set in the Z position before depressing the key (this also counts for the other rotors if they are due to step).

Source: Technical Details of the Enigma Machine

When you press A the rotor advances to B and encrypts the letter according to B.  Your simulator has to first advance the rotor and then encrypt the letter.


For large prime P, how often is (P-1) evenly divisible by 65537? When calculating prime numbers $p$ and $q$ for an RSA private key, one of the requirements is that $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, where $e$ is the RSA exponent (typically 65537).

I'm curious how often it happens in practice that a randomly generated prime number happens to not satisfy $\gcd(p-1,65537)=1$. Are the chances of this happening related to the size of the prime number?

If you generate a prime randomly, and then check, it happens with probability $1/65536$.

On the other hand, it is common practice to include the criteria $p \not\equiv 1 \pmod {65537}$ as part of the prime search; if you do that, the probability is 0.


Securing Data via secret key that must be revealed later This question is language and platform independent.

Assumptions:  I am a service provider and my service is storing data encrypted with a key that my customer knows - but I do not.

My customer (party A) wants me to retain this data to a specific time then release the data to another party (party B) who does not know the decryption key.

I should never be able to decrypt the data myself - even writing code to do so.

The initial customer is unavailable and unable to pass the decryption key on to party B.  It is my job as the service provider to provide a way for party B to decrypt the data.

Because party A cannot share the decryption key with party B ahead of time.

The catch is it must be impossible for me to know this decryption key and I must not be able to decrypt this data myself.  A computer program can do this - that is allowed - but there must be no way for me to manipulate the data stored and decrypt it.

It would be a simple matter to store the decryption key and pass it on at the proper time,  but I would then have access to decrypt the data and I do not want to even have that option.  So how do we keep the decryption key secret until time for the exchange and exchange it without revealing it to me?

Edit: ideally B should have to do nothing. B may not even be aware of the situation until it becomes necessary to decrypt the data.  This is the reason for the SP - but the SP cannot be able to decrypt.  SP is necessary to prevent B from accessing data prematurely and to facilitate decryption by B.  When it is time for B to decrypt A cannot be involved.

Purpose: protect data exchange from a to b where through dishonesty or coercion it is impossible for the SP to compromise the data and where a is no longer able to grant access to the decryption keys.   Impossible?

The root question is: is there a scheme by which SP can encrypt data and convey decryption info to B without being able to use the decryption key.

The solution can be complex.  SP doesn't have to know the link between the keys and the data or the links between data and recipient but when event occurs that releases the data then B must be able to decrypt.  It must be impossible to decrypt before event.

How can this be accomplished?

Thanks!

If I understand you correctly,
you want to set up a system such that

Alice stores encrypted data on Ted's servers
Some event occurs that tells Ted to do something.
Sometime before that event, Alice has disappeared and becomes unable to perform any other steps in the protocol.
Everyone wants Bob to recover the plaintext of Alice's data after the event.
Ted is never able to recover the original plaintext. (In other words, this is a "host-proof" protocol. See host-proof for many related questions and answers).
Bob is not able to recover the original plaintext before the event, only after Ted cooperates by doing ... something.
Bob doesn't need to actively communicate with Bob or Ted or even know Alice exists before the event.

It seems clear to me that Bob needs to know (or be able to find out) something that Ted doesn't know. If Ted hypothetically knows everything that Bob knows, then by the time Bob receives a message from Ted and has all the information needed to decrypt the data, Ted has long before that time already has all the information needed to decrypt the data, which means that hypothetical protocol fails to be host-proof.

It also seems clear that we must trust Ted to actually send something to Bob after the event.
If hypothetically both Alice and Ted refuse to communicate after the event, then Bob won't learn anything that he doesn't already know, and therefore either Bob has long before the event already had all the information he needs to recover the plaintext, or else he never is able to recover the plaintext -- both undesired.

Off the top of my head, one possible approach could be:

Ted and Trent: two trusted hosts

For each document, Alice generates a random symmetric key, encrypts the document with that symmetric key, and stores the resulting encrypted document on Ted's server or Trent's server or both.
For each encrypted document, Alice encrypts the (symmetric) key used to encrypt that document using a one-time pad. This splits the key into 2 pieces -- an encrypted symmetric key, and a piece of one-time pad that can later be used to decrypt it. (This is "trivial secret sharing". Any other secure form of secret splitting would also work. Other forms of secret splitting might work even better).
For each encrypted document, Alice stores one piece of the split key on Ted's servers and the other piece on Trent's servers, but never sends all the pieces of the split key to any one person.
After the event, both Ted and Trent send all data they got from Alice to Bob. (In principle, Ted and Trent could send all the encrypted documents to Bob ahead of time, and send either one part of the split key or the other -- but not both -- to Bob ahead of time).
Once Bob receives the encrypted version of a document and all the pieces of a split key for that document, Bob combines the split key to recover the original symmetric key, then uses that symmetric key to recover Alice's plaintext document.

Given the initial constraints, I don't see any way around trusting Ted not to reveal some information to Bob prematurely.
This protocol has the additional weakness of trusting Ted not to (ever) reveal information to Trent, and also vice-versa.


What does the encrypt function from Stanford JS Crypto Library do? The Stanford JS Crypto Library appears to be trusted by many people. Unfortunately there isn't a lot of documentation. Their encrypt function is documented as a "simple encryption function" (that's it). The default values in the source code look like it's AES-128? Are there any restrictions on input, like length, special characters, etc?

The SJCL demo page suggests that what it's doing is symmetric-key authenticated encryption using either the CCM or the OCB2 mode.  The cipher used appears to be AES, not that that matters much.  (Any other secure block cipher with similar block and key sizes would work just as well.)

Actually peeking into the code reveals that there's more to it than that.  For example, for the encryption key, it can apparently accept either a password string (which will be hashed using PBKDF2 to derive the actual key), an ECC ElGamal public key (used to generate and encapsulate a random symmetric encryption key) or, presumably, a raw AES key in the library's internal format.

In any case, besides the demo, the sparse auto-generated documentation, and the code itself, I have not been able to find any proper documentation or specification for this library.  While at a glance the design of the library seems sound enough, and while the author list includes Dan Boneh, who certainly seems a reputable and competent enough cryptographer, I still would not recommend using this library given its lack of documentation.

Simply put, even if the library itself worked perfectly and did exactly what it was supposed to, without proper documentation you simply have no way to tell (short of reviewing the whole source code yourself) whether you're using it correctly and securely or not.  Given that most crypto failures in practice arise from putting the right parts together in the wrong way, that's a glaring flaw in my book.


Who uses Dual_EC_DRBG? Recent news articles have suggested that the NSA may be involved in trying to influence the cryptography in public standards or commercially deployed software, to enable the NSA to decrypt the encrypted traffic.  For example, see this article in the New York Times.

The New York Times article specifically mentions a 2006 NIST standard, where two Microsoft engineers later discovered a serious problem in the scheme.  The New York Times article explains how the standard was written by the NSA, who pushed the scheme hard:

  Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.

  Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology, the United States’ encryption standards body, and later by the International Organization for Standardization, which has 163 countries as members.

  Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

After some sleuthing, I'm pretty certain this is a reference to the Dual_EC_DRBG pseudorandom number generator scheme described in NIST SP 800-90.  The weakness is that Dual_EC_DRBG appears to contain a backdoor, and anyone who knows the backdoor can totally break the PRNG.  The weakness was first described in a rump session talk at CRYPTO 2007 and was subsequently discussed by Bruce Schneier in Wired.

As a consequence, there are now good reasons to suspect that Dual_EC_DRBG contains a NSA backdoor, and the NSA might be able to spy on anyone who is using Dual_EC_DRBG.

My questions:

Who uses Dual_EC_DRBG?
Do any commercial products use Dual_EC_DRBG?
Does anyone use it?

Here is a list of products and companies who have had their EC DRBG algorithm validated by NIST.
http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html

The validation lists all modes that have been validated, so you can see which ones have gone to the effort of having their implementation of Dual_EC_DRBG validated.  Tim Dierks points out that, for Lancope's certification (NIST validation #288), Dual_EC_DRBG is the only listed mode of operation that was tested or validated.  It's hard to know why Lancope would have submitted their library for validation if they weren't using it.  So, it sounds like there exists at least one implementation in the wild that uses Dual_EC_DRBG.  (Thanks to Tim Dierks for this analysis.)


How to formally say that the integers modulo $p$ for a prime $p$ gives results that are "more random" than for a composite $n$? I'm doing a presentation on cryptography for non-experts. My main algorithm of the presentation is the Diffie Hellman key exchange. It uses modulo arithmetic for a prime $p$. During my presentation, I'd like to be able to explain why the modulo operation uses a prime instead of a composite number. I've seen documents that kind of 'hand wave' the explanation. The best explanation I've seen, albeit hand-wavey is from Quora:

But when data is not random then strange things happen. For example
consider numeric data that is always a multiple of 10.
If we use mod 4 we find:
$10 \bmod 4 = 2$
$20 \bmod 4 = 0$
$30 \bmod 4 = 2$
$40 \bmod 4 = 0$
$50 \bmod 4 = 2$
So from the $3$ possible values of the modulus $(0,1,2,3)$ only $0$ and $2$
will have collisions, that is bad.
If we use a prime number like $7$:
$10 \bmod 7 = 3$
$20 \bmod 7 = 6$
$30 \bmod 7 = 2$
$40 \bmod 7 = 4$
$50 \bmod 7 = 1$

My question is: Can we get more precise than this? Are there any mathematical theorems that can show why this pattern would emerge?

Can we get more precise than this?

Actually the "randomness" of the resulting values is not the blocking issue with composite moduli for DH.

What is much more severe is the fact that if you know the factorization of the modulus $n=pq$, then solving $g^x\bmod n$ is essentially the same as solving $g^x\bmod p$ and $g^x\bmod q$ both of which are substantially easier than solving the problem for $n$ itself (using eg GNFS). Afterwards you can cheaply recombine the solutions with CRT.

In particular note that using a 2048-bit safe prime for DH yields a secure (unauthenticated) key exchange (with effort needed of about $2^{112}$ to break it) whereas if you were to use eg balanced factors that would drop to solving two 1024-bit discrete log instances, both of which need about $2^{80}$ work (so $2^{81}$ in total). This is considered feasible if you have the right amount of funding (eg nation-state level). Obviously if you use unbalanced factors the run-time of attacks is dominated by the larger factor and at that point you may just do away with the smaller one and save yourself the computation time (for your normal exchanges).

If you don't know the factorization, things become harder, but so does uncertainity. You have to trust that whoever generated the composite modulus actually doesn't know the factors (and thus is able to much more easily break the security). Also it allows for parameter replacement attacks which in turn do allow such attacks. This is not a theoretical attack. And in fact with such a parameter replacement attack you could just sneak in a value that is a composite of 4x 512-bit primes, nobody could factor that (easily) but with about a week of pre-computation every discrete log instance with that modulus could be solved in a matter of seconds.

So TL;DR: By using composite moduli you only gain a lot of headaches and neither speed nor security.

If the above is too complex try the following:

We use primes for the modulus in Diffie-Hellman because it gives us no speed nor a security advantage not to use them. In fact quite the opposite, if we used composites, we could split the relevant hard problem of discrete logarithm along the factorization and solve both sub-problems in parallel. Even worse each of these instances is significantly easier to solve due to the large reduction due to the solving algorithm's complexity growing really fast with the problem size. If we don't know the factorization we'd have to trust the generator of the modulus not to exploit the above weakness against us and attackers may replace our parameters with theirs, giving them backdoor access to the data.


AES with different modulo operations? I don't get the modulo 10001 operation in MixColumns so much.

If I have to take the byte computations mod 100011011 anyway what leads me to a result of 4 byte length, why do I need the mod 10001 operation? Where is my mistake in thinking?

Can you maybe give me an example where I'ld need it?

I guess, you are referring to the mix columns operation from the point of view with polynomials over $GF(2^8)$.

A detailed explanation of this can be found at Wikipedia. It is a quite unusual structure, but it behaves just like you would consider any $GF$.

The columns are first considered as polynomial, or better: as coefficients for a polynomial of degree 3.
Then this polynomial is multiplied with a constant polynomial ($3x^3+x^2+x+2$)
Addition in this field is done with the XOR operation
Multiplication is quite complex, for details check out this.

As for your questions:
There are two different modulo operations. One is considered on the $GF(2^8)$, which is $100011011$. But this is just the finite field for the coefficients, and in the overall structure you actually deal with polynomials modulo $x^4+1$. I guess you have an error in your actual number there, because if you just write the hexademcimal representation of the coefficients, that would be the coefficients $1,0,0,1$ (with coefficients from 0 to 255), or $1|00|00|01$ written in hexadecimal.


Security of elliptic curves How can we say an elliptic curve is secure and can be used for cryptographic applications?

Mathematically speaking, we cannot. There is no proof that elliptic curves are actually "secure". But the same apply to about all other cryptographic algorithms, so we have to make do with the next best thing: since we cannot prove that any curve is "secure", we'll use curves that we do not know how to break (and not for lack of trying).

That last part is very important: we gain some level of trust in the robustness of a curve through that curve being exposed to the fierceness of many cryptographers for a long time. If a curve was thus specified and used and attacked for years, and none of them succeeded at even making a dent in it, then we begin to say that the curve is "probably strong"; or, similarly, that if that curve has weaknesses, then these weaknesses are not obvious. This is about the best we can achieve.

An important consequence is that only fully specified, standardised curves that have been analysed for years can claim to be "secure" in that sense. So, in practice, use one of the standard curves. Which means one of the three most common NIST curves (P-256, P-384 and P-521; see FIPS 186-4), or one of the two "newer" (but nifty) curves Curve25519 and Curve448 (see RFC 7748).

That being said, we can list a few basic criteria that "secure" curves must fulfill. Matching all these criteria does not guarantee security in any way, but if any of them is not matched, then cryptographers will laugh and mock it.

The curve order (number of points on the curve) must be a large enough prime integer, or a multiple of a large enough prime integer. "Large enough" means here that the equivalent of discrete logarithm for elliptic curve can be solved in time $O(2^n)$ for a prime of size $2n$ bits. Since we want at least "100-bit security", that prime integer should have at least 200 bits in length (cryptographers are suckers for powers of 2, so traditionally we aim for "128-bit security"). Implementation in many contexts is made easier if the curve order is prime, and not only a multiple of a big prime, so if a curve order is not exactly prime, it better have a good reason for that.
The curve should not be anomalous or singular or supersingular. These are special curves with additional mathematical property, which may thus lead to easier attacks. Note: for some specific contexts (pairing-based cryptography), we have to use special curves, and the possible weaknesses must be compensated for with, basically, use of bigger curves (hence slower).
The embedding degree of the curve must be large enough to discourage attacks that leverage the same mathematics as pairings (e.g. MOV attack). If the curve is defined in a finite field of size $q$, and the curve order is (a multiple of) the big prime $r$, then the embedding degree is the smallest integer $k \gt 1$ such that $r$ divides $q^k-1$ (this is the Balasubramanian-Koblitz theorem). The MOV and FR attack turn discrete logarithm on the curve (work factor $O(2^{r/2})$) into multiplicative discrete logarithm in a finite field of size $q^k$, where subexpoential algorithms are known.

In general, unless you use a special curve (e.g. supersingular) or deploy some extensive mathematical juggling aiming at generating a curve with a small embedding degree, a "random" curve will have an extremely high embedding degree ($k$ will have about the same size as $r$). One widespread ECC standard (ANSI X9.62) mandates that, when generating a curve (assuming you want to do that, but, as explained above, this is probably a bad idea), you should verify that $k$ is greater than $100$ (i.e. you check that $r$ does not divide $q^k-1$ for all $k$ from $2$ to $100$).
Since a curve is defined with an equation over a specific field and with a couple of extra parameters, there is room for inserting arbitrary values. Cryptographers don't like arbitrary values. If somewhat "magic" constants must appear, they prefer these values to be nothing up my sleeve numbers. We don't know how we could somehow "rig" a curve with special parameters, in a way which cannot be detected (e.g. with a low embedding degree), but in all generality we prefer it when such rigging cannot happen because values are not arbitrarily chosen.
Implementing elliptic curve securely is hard. For instance, the "new" curves Curve25519 and Curve448 are easier to implement securely for several reasons, the two main being:

These curves are derivative from Montgomery curves and thus admit an efficient point multiplication algorithm that is "naturally" constant-time (it won't leak secret values through varying execution time or memory access pattern).
Each of these curves is actually two curves, where any patterns of bits will be interpreted as a point on one of the curves or on the other. This avoids the need to perform point validation and make tricky decisions about the handling of invalid input data.

Thus, a "secure curve" must be such that it makes it easy, or at least not impossibly hard", to implement computations in a secure way. On that criterion, the NIST curves (P-256...) are "less secure" than Curve25519 and Curve448. Note, though, that even when a curve is easier to implement securely, that does not mean that it is easy in absolute terms. For about the same reason that you should not invent your own curves, you should not either make your own implementations. And if you use an implementation which was done with great care and was reviewed by many competent people, then the difference between curves in that respect is mostly nullified.

It shall be noted that while we want to avoid "special structure" in curves, one specific special structure is especially alluring in terms of performance: choosing a base field that promotes efficient computations. For instance, Curve25519 is defined in the field of integers modulo $q = 2^{255}-19$. This value being very close to a power of $2$, this makes computations much faster. This is the point where cryptographers tend to throw away caution for the sake of good benchmarks. We do not know how a special base field structure could be leveraged to break discrete logarithm faster; but we declared anathema on random parameters with no better justification, so it is kinda weird that we allow special fields and not arbitrary curve equation parameters. My gut feeling (which is thus scientifically unsubstantiated) is that if the standard curves ever get into cryptanalytic trouble, this will be due to special base field structure. But it won't prevent me from sleeping at night.

If any of the above seemed obscure, then go read this book.


OpenSSL AES 256-bit Key Management I am using C and OpenSSL to encrypt files. After experimenting with the OpenSSL command line utility, it makes you enter a passphrase that can be any length, but uses that to create a 256-bit key.

How many passwords or keys does aes use & how does it use them? If you can make your passphrase as long or as short as you want, what is the point of having a 256-bit encryption?

AES is a block cipher, a cryptographic primitive. It has no involvement with key derivation or anything of that nature. The three standard key sizes are 128 bit, 192 bit, and 256 bit. How you get those keys is beyond the purview of AES, which is concerned only with encryption. As I said, it is a cryptographic primitive, meaning it is meant to be used in a larger system (usually). In fact, "AES" itself can't encrypt more than one block of data; to do that, you need to use a block cipher mode of operation. I'd recommend, for non-authenticated schemes, either CTR or CBC, not ECB. But in general, you probably want one of the authenticated modes (AEAD), like GCM, OCB, EAX, or CCM.

So, the fact that OpenSSL lets you use a passphrase is entirely unrelated to AES. Typically, I would recommend against using passphrases for encryption, as they are notoriously low-entropy and vulnerable to simple guessing. OpenSSL does use a salt by default, which improves things, but the algorithm it uses is "somewhat" questionable. The default hash function used in it is MD5, and it only uses just a few rounds by default. So, if possible, I would very highly recommend you generate a real key instead of using a passphrase. And, like your question implies, if the adversary knows your file is encrypted with a passphrase, it makes using a larger key sort of moot.

Just remember that AES was designed as a block cipher, so the whole passphrase business is really separate from it. Anyway, if you are interested in the practical differences in AES-128, AES-192, and AES-256, there are several good questions on this site with good answers:

What are the practical difference between 256-bit, 192-bit, and 128-bit AES encryption?
What is the effect of the different AES key lengths?
Is AES-256 a post-quantum secure cipher or not?


Multisignature or Multi-password File I want to create a file that I could give to 3 trusted friends, and allow any two of them to decrypt it when together (or in sequence when not physically in the same place).  This is similar to a multi-signature crypto wallet, but I just want to do it with a file.

The use case is to create a document that would contain my sensitive passwords, bank accounts, life insurance etc... in the event of death or illness.  I would give it to three people in advance.

This is precisely the domain of secret sharing, of which there are various popular schemes like Shamir's secret-sharing scheme, and there are many widely available implementations of it in various forms which you can find with exactly those keywords.


Standards for finite-field discrete log cryptography The NIST and TLS standards for Diffie-Hellman key exchange over a finite field all work in a subgroup of ${\mathbb Z}_p^*$ having prime order $q$, where $p = 2q+1$. On the other hand, DSA has a larger cofactor, i.e., it works in a subgroup of ${\mathbb Z}_p^*$ having prime order $q$, where $p = rq+1$ and $r \gg 2$. The latter makes sense because it gives better efficiency while still giving the same security against known attacks.

So, why do the NIST/TLS standards not allow for cofactors greater than 2?

So, why do the NIST/TLS standards not allow for cofactors greater than 2?

Actually, NIST does allow larger cofactors - see table 1 in SP800-56A - they allow the subgroup (q) to be significantly smaller than the modulus (p).

As for TLS, previous versions of TLS (1.2 and earlier) did allow the server to specify the group (and made no requirements about the cofactor).  In TLS 1.3, they allow only a handful of specific groups to be used, all with a cofactor of 2.  Is there a specific reason they should have included a group with a larger cofactor?


Can a nested block cipher avoid the meet in the middle attack by using a secret initialization vector for the inner encryption? It seems to be believed that encrypting twice with a block cipher using an independent key each time is not as secure as you might expect because of the "meet in the middle" attack.

This is an attack with known plaintext.  The theory is that the attacker encrypts the plaintext with every possible key, and decrypts the known cipher text with every possible key and then looks for a match between decrypted cipher text and encrypted plaintext.  So brute force attacks takes only twice as long as for single encryption instead of $2^{\text{number of key bits}}$ times as long as you might expect.

However, as far as I can see, if the first encryption using $k_1$ used CBC with a truly random and secret IV, then no meet in the middle is possible because the attacker would have to encrypt for every key for every IV to find a match which for example in DES is harder than encrypting for every possible pair of keys.  In my hypothetical system, the IV can be simply double encrypted and prepended to the start of the ciphertext for the benefit of the intended recipient. It must not be used for anything else and if the second encryption wants to use CBC then it should use a separate random IV.

This seems so obvious that it must have been thought before, so what understanding am I missing?

Eli Biham examined this, along with a long series of other "internal chaining" modes in the paper "Cryptanalysis of Multiple Modes of Operation" in AsiaCrypt 1994.

His conclusion was that there were ways of attacking such modes that were strictly easier than the standard "external chaining" mode that is now commonly used; his paper is the chief reason that we stick to what we do use.

For example, in the case that you have CBC mode (with secret IV, as you suggested), followed by an independently keyed ECB mode, one way to attack this is to do a chosen ciphertext attack; ask for the decryption of the message (A B B) (where A and B are distinct blocks); if the plaintext message is (P1 P2 P3), then it turns out that $D_{k2}(A) \oplus D_{k2}(B) = P2 \oplus P3$; this makes brute forcing $k2$ straightforward (and once that is recovered, $k1$ can then be brute forced).

Other modes (I believe CBC mode followed by CBC mode would be one example) don't have such easy tricks; for them, you need to find an internal collision and exploit it.  One possible way to do it (for CBC mode followed by CBC mode) is as for the repeated decryptions of plaintexts of the form (A A A) (for various block-sizes values of A); if two different values A, B satisfy $A \oplus D_{k2}(A) = B \oplus D_{k2}(B)$, then the third word of the corresponding plaintexts will be the same.  Hence, if we ask for $2^{32}$ (assuming DES) such plaintexts, we can scan the plaintexts for collisions in the third word; once we find such collisions, we can do a brute force search to verify that the collision was caused at the $k2$ level, and if so, recover $k2$.

Now, it may be that these attacks are of mostly theoretical interest; they are often chosen ciphertext attacks, and chosen ciphertext attacks can be thwarted by a simple Message Authentication Code.  However, given that the standard modes don't have these theoretical weaknesses, people have found it safer just to stick with the now standard modes.


ECDSA signature verification checks From Wikipedia:

Check that $Q_a$ is not equal to the identity element $O$, and its
coordinates are otherwise valid.
Check that $Q_a$ lies on the curve.
Check that $n*Q_a = O$
Verify that $r$ and $s$ are integers in $[\![1;n-1]\!]$. If not, the signature
is invalid.

What is the mathematical reason for these checks and what can an attacker do if these checks are not carried out properly?

The original paper (Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA), International Journal of Information Security volume 1, 2001, pp. 36–63) is surprisingly quiet about the rationale for all of these.

  Check that $Q_a$ is not equal to the identity element $O$, and its coordinates are otherwise valid.

If $Q_a=O$, then the step $(x_1,y_1)=u_1\times G+u_2\times Q_a$ turns into $(x_1,y_1)=u_1\times G$ because the identity element multiplied with anything ends up being the identity element – the same as normal math ($0\cdot a=0$).

Let's start with the verification equation and roll it back with the assumption that $Q_a=O$. As a reminder, the signature is $(r, s)$. The signature is valid if and only if $r \equiv x_1 \pmod{n}$.

$(x_1, \_) = u_1\times G+u_2\times Q_a = u_1 \times G + O= u_1 \times G$, where $u_1 = zs^{-1} \mod{n}$.

An attacker trying to forge a signature for a new message has control over:

$z$ is a trimmed hash of the message. The attacker can compute this.
$(r, s)$ are signature parameters and thus provided by the attacker along with the message.

Because $Q_a$ is gone from the picture, the part that effectively binds the private key into the signature, a valid signature becomes trivial:

Compute $z$.
Pick any $s$ at random in the range $0 < s < n$.
Compute $u_1 = zs^{-1} \mod{n}$.
Compute $(r, y_1) = u_1\times G$.

Because the verifier skips verification that $Q_a \ne O$, this checks out.

(Note that this requires a way for the attacker to supply a public key $Q_a$. In many cases, the public key is pre-shared or otherwise hard-coded so this issue rarely arises in practice. Often, there may not even be a way for an attacker to force $Q_a=O$ if there's no accepted bit representation of $O$ depending on the implementation.)

  Check that $Q_a$ lies on the curve.
  Check that $n*Q_a = O$

If $Q_a$ is not on the curve or has an order that does not equal the expected $n$ for the curve, it may lie on another curve $E'$, chosen by the attacker; $E'$ would typically be a curve that has a small order and then use the Chinese remainder theorem to discover information about the private key in Diffie–Hellman settings.

This can be abused in the context of a certificate authority (CA) using ECDSA as a proof of possession of the private key for $Q_a$ when $Q_a$ is not validated (adapted from Adrian Antipa et al. Validation of Elliptic Curve Public Keys, section 4.3), though this is all in the context of ECMQV and thus a special case:

Select two values for $s$ and $u_2$ between $1$ and $n-1$ inclusive.
Compute $z$ and $u_1$ for ECDSA as normal; the message for $z$ may be chosen by the CA.
Compute $T_1=u_1\times G$ on curve $E$.
Compute $T_2=u_2\times Q_a$ on curve $E'$.
Compute $V=T_1+T_2$ using point addition as if both points were on curve $E$; the result will be on neither curve.
Set $r$ to the x-coordinate of $V$.
Compute $u_2'=rs^{-1}\mod{l}$, where $l$ is the order of a point with small, prime order on $E'$ that contains $Q_a$.
Repeat this procedure unless $u_2\equiv u_2'$
Output the signature $(r,s)$.

  Verify that $r$ and $s$ are integers in $[\![1;n-1]\!]$. If not, the signature is invalid.

The original paper by Johnson et al. notes on p. 48 that (a) this mitigates attacks related to ElGamal signatures without such checks, and (b) the check that $r>0$ in particular avoids an issue specifically relating to a base point $G=(0,\sqrt{b})$ (with $b$ from the short Weierstrass curve parameter for $E$: $y^2=x^3+ax+b$), though I am unaware of any elliptic curve standard specifying a base point with an x-coordinate of zero.

This also helps prevent malleability so that given an existing $(r, s)$ and existing message $m$, no new signature for the same $m$ can be made without possession of the private key. The group generated by the generator $G$ is a cyclic group of order $n$, which means that the cycle repeats after $n$ additions of $G$ to itself: $n\times G=O$, $(n+1)\times G=G$, …, therefore for every $(r, s)$, the tuple $(r + cn, r + cn)$ is also a valid signature for the same message for every integer $c>1$. Note that $(r, -s\mod{n})$ is already another valid signature that may need to be guarded against as well.


Is this a PRF? Fk(x) = G(k⊕x) where G is a PRG This is not homework, but a random thought.

Let $G(x)$ be a PRG.
We define the following function:
$$F_k(x) = G(k\oplus x)$$

My intuition is that it shouldn't be a PRF but I couldn't come with an example yet.

I tried to build a reduction from identifying G to identifying F but I'm not certain how you can simulate an oracle call when all you have is some string.

Given some PRG $G : \{0,1\}^n \to \{0,1\}^m$ with $m > n+1$, define $G' : \{0,1\}^{n+1} \to \{0,1\}^m$ like this:

$$
\begin{align}
G'(0\|x) & = G(x) \\
G'(1\|x) & = G(x)
\end{align}
$$

Lemma: If $G$ is a PRG, so is $G'$.

Proof: Let $s \in \{0,1\}^{n+1}$ be a randomly chosen seed, and let $s' \in \{0,1\}^{n}$ be its suffix (with the first bit of $s$ removed), which is also distributed uniformly at random. Since $G$ is a PRG, then $G(s')$ has a pseudorandom distribution. And since $G'(s) = G(s')$, so does $G'(s)$ have a pseudorandom distribution. So then, since $G'(s)$ is pseudorandom for random $s$, $G'$ is a PRG.

Theorem: $F_k(x) = G'(k \oplus x)$ is not a PRF.

Proof: Because of the definitions of $F$ and $G'$, we see that for all $k$ and $s$, $F_k(0\|s) = F_k(1\|s)$. Given oracle access to an $f$ that's either $F_k$ or a random function, we have the following distinguisher:

Pick an arbitrary $s$;
Query the oracle for $x_0 = f(0\|s)$;
Query the oracle for $x_1 = f(1\|s)$;
If $x_0 = x_1$, then output $1$, otherwise output $0$.

If $f$ is a random function, this outputs $1$ with probability $2^{-m}$.  But if $f$ is $F_k$, then it outputs $1$ with probability $1$.

So, there exists a choice of PRG for which your proposed construction is not a PRF.


Differences between methods of hardware random number generators I'm reading about various hardware random number generators which - among others - implement the following approaches:

Analog-to-digital converter noise
Johnson–Nyquist noise
Reverse biased semiconductor junction
Avalanche diode with optional atmospheric noise
Edit: Modular entropy multiplication

What are the practical pros and cons of these approaches? Is any of these methods "better", more reliable, or more resistant to physical attacks than the others?

The Electrical Engineering SE would be a good resource for questions about specific sources of noise. Which method is best is not a a question for which you will find a good answer to. The "quality" of any method depends on which models of electronic components are used. They have different properties that don't make direct comparison easy:

Power use: Two sources that produce the same amount of "randomness" per second can have drastically different power requirements.
Price: How much you have to pay matters. Just because something is more expensive doesn't mean it's better at producing randomness. Even if it was it might not make a difference because things are either sufficiently unpredictable or they are not. Cheap components may work well enough. They may work better. They may be worse.
Rate: How much randomness can you extract from a single? How much per unit of time and how much per unit of power?
Unpredictability and Leaks: How much noise is known only to the HWRNG versus how much noise can be read by an outsider. (This is the reason you should not rely on atmospheric noise. Yes it is unpredictable, but two people in the same area on this planet will read somewhat similar noise signals.) What about side channel risks and protection? It doesn't do much good extracting noise from a random process if the HWRNG leaks information based on how much power it draws while generating random numbers. Or if you can literally hear part of the noise signal coming form capacitors.
Life-time and Stability - The behavior of some components change as they age. Some components may wear out the longer you use them. Some may change even without use. If you calibrate a system for producing noise as it is now, you might end up with a more predictable HWRNG sometime in the future.
Production - Variations between components of the same type means you might not be able to buy commodity components and use them interchangeably. Even if two components came from the same manufacturer. One should test the components and design a HWRNG that isn't too sensitive to variation.
Tamper-ability - Physical access is devastating but remote attacks can be too. I'm sorry I don't have links, but one method used in remote attacks is, I think, referred to as "illuminating" a device. It's when you "shine" an electromagnetic signal at a device. It can turn into a fault injection attack (making unpredictable behavior predictable) or a side channel attack (causing secret information to be bounced back.)

From a cryptography perspective the source of "randomness" or "unpredictability" does not really matter. We just need a signal that has entropy (a term for how much unpredictability there is in a signal) and a means of estimating how much entropy a system has. No one should be using raw readings from signals as their binary output.

Real HWRNGs typically output "whitened" noise. The raw signals from a noise-producing system do not necessarily (almost certainly don't) look like samples from a uniform statistical distribution. The input signals need to be processed to extract randomness. They're not 100% random so the bandwidth of the signal coming out will be less than the bandwidth going in. That's where the entropy estimate comes in. You do not want to emit 100 bits of random output if your un-whitened noise signal is only as unpredictable as 10 coin flips. (We say the input has only 10 bits of entropy in this case.)

Informally speaking the randomness is typically extracted by something like a cryptographic hash function. The signal going in is digitized and fed to the hash function. When enough data is processed, say an estimated 256 bits worth of entropy, the hash function is evaluated and the result is used as a seed/key for a deterministic random number generator. As long as the entropy estimator does not over-estimate the amount of entropy then this hybrid-system is a sound construction.

From this crypto-perspective what matters is efficiency (power use, bits per second, unpredictability) and security (unpredictability, stability, lack of side channels, difficulty with tampering). How we can get that out of hardware is a different type of problem in the realm of physics and electrical engineering.


How does Truecrypt change password without the need for a complete re-encryption of volume From what I understand:

TrueCrypt takes the password as message
Add salt
calculates a digest
use digest for encryption

From what I understand. A good hash function

has Second pre-image resistance .i.e. It is difficult to find $m_2$ such that $m_1\neq m_2$ and $hash(m_1) = hash(m_2)$ .i.e. it is difficult to find a salt to produce the same digest

I observe that truecrypt can change my password in seconds (I assume the data is not reencrypted). How is this done while keeping the data on hard drive encrypted?

What Richie Frame describes above is correct. This is how most FDE solutions work.

A new random encryption key is created whenever new container is created or disk is encrypted. That encryption key (often called Master Key) is then protected by users' password. In case of Truecrypt, master key is stored in volume header (link) and volume header is encrypted with a key derived from a user password (another link).

Such scheme provides (at least) two major benefits:

Password changes are quick and do not require re-encryption
Multi-user setup is straightforward: just store master key encrypted with every user's password.

Major disadvantage is that if master key is compromised (e.g. by dumping memory while volume is mounted), adversary can maintain access to the data even if users change their passwords. To mitigate this some FDE solutions provide "re-encrypt" option which will create new key and re-encrypt all data.


Understanding the definition of polynomially CPA (IND-CPA) security I just started on encryption schemes and have some trouble in understanding the following definition of IND-CPA security:

$E$ is polynomially CPA (IND-CPA) secure, if for all adversaries $A$ and all polynomials $p$, we have: $Adv_a <= \frac{1}{p(\lambda)}$ for sufficiently large $\lambda$, i.e.: For all $A$ and all $p$, there exists an $N_p>0$ such that $Adv_a \leq \frac{1}{p(\lambda)}$ for all $\lambda > N_p$.

As far as I understand, in a simple IND-CPA game, an oracle sends a ciphertext to an adversary that is the encryption of one of two possible messages chosen by the adversary. An adversary now needs reply with what the actual message is.

What I don't understand is how I should interprate the polynomials $p$ and parameters $\lambda$. What do they consist of?

As explained on Wikipedia:

  The reciprocal-of-polynomial formulation is used for the same reason that computational boundedness is defined as polynomial running time: it has mathematical closure properties that make it tractable in the asymptotic setting. For example, if an attack succeeds in violating a security condition only with negligible probability, and the attack is repeated a polynomial number of times, the success probability of the overall attack still remains negligible.

Which is why you want it to work for all polynomial $p$ in your definition.

It is also important to notice that in this definition, it is implied that the adversary has a polynomially bounded computational power.

Which means basically that in the IND-CPA game, the adversary has the right to perform a polynomially bounded number of encryptions or other operations, before sending the two plaintexts to the challenger, which will choose one and return its encryption to the adversary, who must now guess to which plaintexts it corresponds.

Let me develop this with an example:
in the RSA-OAEP case, this forbids for instance the adversary to factor the public key using the GNFS since it has a complexity of :
$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\right]$$
for factoring the number $n$, but we're usually interested by the security parameter, which, in RSA-OAEP case, is the $\lambda=\log_2(n)$ , but this is not a problem, since its running time is super-polynomial but sub-exponential in the size $\lambda$ of the input $n$:
$$O\left(\exp\sqrt[3]{\frac{64}{9} \lambda (\log \lambda)^2}\right)$$ so it is still not a polynomial algorithm and thus cannot be considered when studying the IND-CPA security of RSA-OAEP.

However, if factorization were to be proven polynomial, then the adversary would win the IND-CPA game in the RSA-OAEP case thanks to it.

PS: As mentioned below, plain RSA is not IND-CPA since it is deterministic.


Sequence test for an image cipher I am reading a paper on security analysis of a cipher image using the paper at the following URL:

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8306512&tag=1

It indicates some test that a cipher image should pass for successful encryption. One of the simple test is to count the number of ones and number of zeros in the BINARY SEQUENCE of the image, and they should be equal, i.e 0.5 roughly of the total:

How is it possible to get a proper binary sequence representation of the image? Do I just convert each bit into its binary representation and form a binary sequence, do I have to do something else?

It's simple.  Lena is 512 x 512 pixels with a bit depth of 8.  So you simply export the raw image to a file that will be exactly 262,144 bytes long. It's critical that you export or save the image as a raw binary file, not one of those JPEGey things.  That won't work.

To determine the two chi values, you then consider the file as a series of consecutive individual bits, or as pairs of bits.  This will entail a load of bit shifting /masking operations in your favourite programming language.

A tip.  Install ent, and just run it twice against the encrypted Lena file.  Run one, use the -b option which will treat the file as a series of bits.  The output will produce a chi and p value.  Run again without the b option.  This will process the file as a series of 8 bit values.  If the encryption produces independent  (non correlated) bits, they can be lumped into four pair groups and treated as octets.  Assume the same 5% confidence value, and look at the returned chi value to see if it's acceptable. You'd expect  $219 \leq \chi^2 \leq 293$ for randomly distributed octets.

ent will also give you the Shannon entropy of the images for comparison with those in the paper.

Another tip.  Do not assume that a chi failure means the encryption fails.  Randomness is pesky and you have to try the test several times on repetitive images or keys.


More Knowledge Integer Factorization Say you have an integer that is produced by multiplying two random numbers

$$x_1 = a \cdot b_1 \bmod(p-1)$$ where $a$ and $b_1$ are relatively prime to $p-1$ and $p$ being a large prime.

Knowing $x_1$ leaves you with $p-1$ pairs of numbers for $a$ and $b_1$, so guessing the correct factorization is hard (right?).

Do you get any advantage in finding the correct pair if you get more $x_i$ where one of the factors is re-used? E.g.:
$$x_2 = a \cdot b_2 \bmod(p-1)$$

The question performs arithmetic in ${\mathbb Z_{p-1}}^*$, the integers reduced modulo $p-1$ that are coprime with this modulus. There are $\varphi(p-1)$ of these, where $\varphi$ is the Euler totient function. It is irrelevant that $p$ is prime, and the question has little to do with integer factorization.

For any $a\in{\mathbb Z_{p-1}}^*$, the application $\scr F_a:{\mathbb Z_{p-1}}^*\to{\mathbb Z_{p-1}}^*$, $b\to x=a\cdot b\bmod(p-1)$ is a permutation of ${\mathbb Z_{p-1}}^*$ (since $a$ has a multiplicative inverse). If follows that if $b$ is uniformly random on the set ${\mathbb Z_{p-1}}^*$, then $x$ is.

Therefore, no information is learned about $\scr F_a$, thus about $a$, from any number of $x_j$ disclosed without the corresponding $b_j$ (assumed independent and uniformly random on ${\mathbb Z_{p-1}}^*$), regardless of the size of parameters or computing power of adversary.


K Friedman - two texts explanation I read the $K$-Friedman test to determine the period of a Vigenère ciphertext, and I understand something like this:

$K$-Friedman test tries to find out what period of the cipher by calculating some values of $K(C,C^n)n$, where $C^n$ is the ciphertext with $n$ shifts to the left, thereby determining the most likely value of the cipher.

But deep down, what the Friedman Test does? Overlaps two texts and see coincident indexes? Can anybody explain this method better?

Just for simplicity lets assume that your short period "password" was just XORed with plaintext. So we have encryption procedure like:

for(int i = 0; i < plaintext_len; i++){
   ciphertext[i] = plaintext[i] ^ password[i % password_len];
}

When you shift your ciphertext by password_len and XOR it with original ciphertext, you'll cancel out your password and get XOR of original plaintext and shifted version of plaintext.

ciphertext[i] ^ ciphertext[i + password_len] =
plaintext[i] ^ password[i % password_len] ^ plaintext[i + password_len] + password[ (i + password_len) % password_len] =
plaintext[i] ^ plaintext[i + password_len]

Note that if you have a 0 char in the result, than the corresponding symbols in plaintexts are equal. The probability of such event for natural text is far from uniform and depends on plaintext language (for English it's 0,0644). If the period guess is wrong, the probability that a particular character in the result is 0 equals $1/m$ where $m$ is the number of symbols in your alphabet, for English it's about 0,03856.

So, you've got the rule how to decide on whether period guess is correct or wrong - just shift ciphertext, XOR it with original one, calculate the frequency of zeroes. If it's close to 0,0644 - your guess is likely to be correct, it it's close to 0,03856 - your guess is hardly correct.


Construct PRF with longer output from existing PRF Assume we have a secure PRF $F$ which takes a key of length $k$, a message of length $l$, and outputs an output of length $o$.
The task it to construct a secure PRF $G$ which takes the same input parameters, but outputs an output of length $2 \cdot o$, by using the first PRF.

My basic intuition would be to construct something like this:
$$G(k, m) = F(k, m) \| F(k, F(k,m))$$

But there is a dimension issue here, since the length of the output is not the same as the length of the message.

Could anyone give me a hint to push me in the right direction?

The $G$ that you have defined is not a PRF at all. I can distinguish it from random in just two queries. Since I have a feeling that this is homework (correct me if I'm wrong), I'll let you work out how it can be broken.


Randomization attack in voting protocols I'm looking into coercion-resistant voting schemes and one of the key elements of coercion-resistance is resistance to randomization attacks.

Juels et al. define a randomization attack as one where adversary coerces the voter to vote for a random candidate (as drawn from some distribution). Many other articles have since repeated this as a requirement for coercion-resistant voting schemes, so it seems to be important.

Since coercion-resistance is an extension of receipt-freeness, and receipt-freeness already guarantees that a voter can't be coerced to vote for a particular candidate, I'm having a lot of difficulty imagining a scenario where both of the following properties hold:

Adversary is unable to force a voter to vote for a particular candidate
Adversary is able to force a voter to vote for a random candidate

Can you provide an example of such a scenario?

Hirt and Sako present such a scenario here. Informal description:

A group of mutually distrusting authorities have encrypted candidates and shuffled their order. The voter expresses their choice by publicly pointing to an encrypted candidate. Outsiders can not tell who the encrypted candidate is, but the voter knows because each authority has secretly told the voter how they shuffled. Because the authorities use a designated verifier proof to convince the voter, only the voter is convinved. If the voter would attempt to pass the proof to the adversary, they would not be convinced, because the proof is constructed in such a way that the voter could have forged it.

The adversary is unable to force a voter to vote for a particular candidate, because the voter is unable to prove to the adversary, which choice (in the encrypted and shuffled list of candidates) corresponds to which real life candidate.
The adversary is able to force a voter to vote for a random candidate, because they can randomly pick a choice in the encrypted and shuffled list and verify that the voter indeed votes for the choice that they picked.


If a PRG is constructed by iterating a PRF, is it backtracking-resistant? Say we construct a pseudo-random generator from a pseudo-random function $f$ (using some constant key $k$ and some initial value $v_0$). We do this by feeding the output block of the PRF back into the PRF to produce a new block of pseudo-random bits. That is, $B_{i+1} = f_k(B_i)$. Is that backtracking-resistant?

I thought it would be backtracking resistant because if we compromise the internal state of the PRG at time $t+1$ (meaning the adversary gets $k$ and $B_{i+1}$), then we can't find any of the previous blocks $B_i$ (for $i < t+1$), since the PRF is hard to invert.
That is, $B_{i+1} = f_k(B_i)$, so we want to find $B_i$ by doing $B_i = f^{-1}_k(B_{i+1})$, but we can't invert it.

Am I missing something? Apparently it's not backtracking-resistant because the key isn't being changed, whereas other PRGs such as HMAC-DRBG are, because they update the key.

Is that backtracking-resistant?

No, as mentioned in the comments, if the PRF itself can be inverted when you know the key, the PRG is not backtracking resistant.

  I thought it would be backtracking resistant because if we compromise the internal state of the PRG at time $t+1$ (meaning the adversary gets $k$ and $B_{i+1}$), then we can't find any of the previous blocks $B_i$ (for $i < t+1$), since the PRF is hard to invert.

Being hard to invert when the key is known is not a required property of a PRF and many practical PRF constructions (like block ciphers) lack it.

  Apparently it's not backtracking-resistant because the key isn't being changed, whereas other PRGs such as HMAC-DRBG are, because they update the key.

Indeed. If you overwrite the key with data generated using the old key, there is no way to backtrack unless the PRF is invertible (to state and key) by those without the (old) key.


AES-128-CTR message integrity: Construction of HMAC (Note: This post is not about "rolling my own", but rather trying to deepen my understanding of the underlying structures.)

I'm having difficulties finding clear answers to some questions about the construction of HMACs:

Assuming we have one key for encryption and one key for message integrity checks, and we are using AES in counter mode.
As far as I understand, when creating the HMAC for a message, one should utilize all available information: The encrypted message, the key, the nonce and the counter.

In effect, does this mean that a separate HMAC must be created for every single message, i.e. all 16 bytes?
If this is true, how would the security of a scheme evaluated in which the HMAC would be calculated over arbitrary multiples of 16 bytes, for example only every 160 bytes?
And at last, going even further, what would be the weaknesses of using merely the encrypted message (and the key, for sure) for the HMAC calculation, thus leaving out the initialization vector?

Maybe someone can shed some light on this, I have seen people doing exactly this (for example one HMAC (no counter, no nonce) for a whole file), but I'm unsure about the correctness.

Thanks in advance!

In effect, does this mean that a separate HMAC must be created for every single message, i.e. all 16 bytes?

No, you can use HMAC over the whole message with all its blocks.

Of course, that means you can't localize corruption/tampering, so if you were sending a huge message you might want HMAC smaller parts (but longer than 16 bytes or you are transmitting more hash than message), so that you can retransmit only the incorrect part.

  And at last, going even further, what would be the weaknesses of using merely the encrypted message (and the key, for sure) for the HMAC calculation, thus leaving out the initialization vector?

If you received a message $n||E_{k,n}(m)||H_k(E_{k,n}(m))$, you would only be able to authenticate the ciphertext. If an attacker had tampered with the nonce $n$, AES CTR would happily decrypt your message but give you random data.


How to calculate the odds of finding "20" at least three times in a sha256 string? For example, what are the odds of this happening:

Can this even be calculated?

If we assume that the output of a SHA-256 hash is roughly random, this is ultimately just a combinatorics problem.  That is:

Given a random string of 64 hexadecimal digits, what is the probability that the sequence "20" appears 3 or more times.

We can think of this as having three set items, the three "20"s, and then 58 other hexadecimal characters distributed around them.  That gives us four spots to put the rest of the numbers:
$$ X_1\ |\ 20\ |\ X_2\ |\ 20\ |\ X_3\ |\ 20\ |\ X_4 $$
Where $X_n$ is a string of hexadecimal digits with size ranging 0 to 58, with $\sum_{i=1}^n len(X_i) = 58$ and "|" denoting concatenation.
After seeing kodlu's answers I figured I would include a more complete answer.
The above ultimately led me down the path of counting all possible 58-hexadecimal-digit strings and then counting the ways we can "insert" the 20's throughout it.  The number of random strings is $16^{58}$.  We can insert 20's at the beginning or after any of the digits, and there are 3 inserts required.  Since we want to allow repetitions (sections without any digits between the 20's) we want ${58 + 3 - 1 \choose 3} = {60 \choose 3}$ (see combinations with repetition).  Dividing that by the total number of SHA-256 hashes, we get:
$$ \frac{16^{58} \cdot {60 \choose 3}}{2^{256}} \approx 0.00203967 \approx ~0.204\% $$
Just to see if this made sense, I ran a quick test using bash to see how this panned out:
#!/bin/bash

function next() {
    head -c 32 /dev/urandom | xxd -p -c 64
}

total=100000

count=0
i=0
while [[ $i -lt $total ]]; do
    next | grep -q "20.*20.*20" && let count="$count+1"
    let i="$i+1"
done

echo "$count / $total"

I ran this a few times and got:
$$175 / 100000 = 0.175 \%$$
$$200 / 100000 = 0.200 \%$$
$$187 / 100000 = 0.187 \%$$
So this seems about right.

A couple notes on the properties of this.  As kodlu mentioned, since "20" is not symmetrical, we don't have to worry about things like "FFF" potentially counting as two instances of "FF" if that's what we were looking for.  However, if we don't want to count that as two, my approach should still work, even if we were using a symmetric target string like "FF" or "00".
Also, since we are looking for "at least" 3 occurrences of "20" in the string, we don't have care about whether any of $X_1, ..., X_4$ contain a 20, those are just extra.  In fact, this is exactly why this approach works.  That said, we may end up double counting in cases where our variant placements of 20s don't really change the ultimate string.  For example, if the 58-digit string is "202020202020..." there are many places we could insert our three "20's" without actually changing the resulting string.  Accounting for that could prove tricky, and I'm not sure how to do so at the moment, but given the extremely large number of cases we're looking at I'm inclined to think this is probably relatively small.  Although it's not hard to come up with other examples, so caution is good.  Regardless, this type of thing is exactly why I wanted to include a more empirical approach (i.e. brute-force counting with code).
On that note, I decided to run another, longer test (with 1,000,000 values) to see if it might be closer to my updated probability than my original one.  Or at least further confirm that we're in the right ballpark.  I got:
$$ 1797 / 1000000 = 0.001797 = 0.1797 \% $$
So, for what it's worth, it seems like the answer is at least "somewhere between 0.17% and 0.20%."


Proper encryption algorithm to use when encrypting data before backing it up to untrusted hosts? I'm writing a (non production/proof of concept) backup program that takes files from your computer, splits them into blocks, and then has other peers store those blocks to create an offsite backup.

Those peers could be other parties that you would not want to disclose the contents of your backup to.

These peers work in a peer to peer fashion, allowing them to get a copy of a block from anyone who has a copy. This means that a peer that is replicating a backup could connect to the machine that is being backed up and request a block from the middle of the file.

So, it seems like it would be good for the machine that is being backed up to locally encrypt, with a symmetric cipher, the data before it is sent off as a block to a peer.

Normally, I would think "use AES". But I'm vaguely aware that there are modes, like CBC. And I'm thinking that chained modes like that would make it very hard to efficiently open a file, seek to a position somewhere near the middle, read a piece of data, encrypt it, and come up with the same cipher text as if it started at the beginning of the file and encrypted all the blocks in order up to that position.

How do the people who do whole disk encryption do this? Is something similar to what they use available for Python (3.x if that matters)?

Why not gpg? The libraries are already written and open sourced, so you don't have to recreate the wheel.

Split the file into blocks, then add a control file adding whatever metadata you need to keep the files together and belonging to the correct person. Encrypt each block with the user's key, and put it on an untrusted host. He will then be the only person who can decrypt the files. Assuming the untrusted host doesn't delete the blocks.


What is the best way to forge a tag for a determined message? Assume a PPT adversary wants to forge a tag for a message. The adversary has oracle access to a verification function. The adversary knows that tags are generated by HMAC-SHA-256 with 128-bit key. I think the best way for the adversary is to randomly choose a key, calculate the HMAC of the message with the chosen key , and check the result with its oracle. Am I right? If so, what is the probability of his success if he tries $m$ different keys? I think it must be:
$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} $$
if I am right, can anyone simplify the sigma better than the following?
$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} < \frac{m}{2^{128}-m} $$

I think it must be:

$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} $$

This is not correct; this can be seen in the simple case where there are four possible keys and you get three guesses.  By the above logic, the probability of guessing the correct key would be $1/4 + 1/3 + 1/2 = 13/12 > 1$, which is absurd (as probability are never greater than 1).  The subtle error you make here is that you can add probabilities only when they are disjoint (and refer to the same event), and in the $m=2$ case (which is the easiest), you're adding a normal probability that the first key is correct ($1/2^{128}$) to the conditional probability that the second key is correct (assuming that the first key is not) ($1/(2^{128}-1)$.

Instead, the correct probability of guesses the correct value (given $m$ guesses), assuming that you will always make $m$ distinct guesses, is:

$$\Pr[forgery] = m / 2^{128}$$

In addition, to be precise, there are actually two ways that the attacker can win.  The first is that, in one of his $m$ guesses of the key, which is what you covered.

The other way he can win is if he selects an incorrect key, however the HMAC of that key just happens to be the right one (by shear chance).  If we assume that HMAC acts like a random oracle, and that we using an untruncated (256 bit) HMAC (I say this because it is quite common to truncate the HMAC output when transmitting it), then (assuming that all the guessed keys are incorrect, and that the adversary checks to see if two of his guesses just happen to be the same, and if so, selects a different key) the probability that we win this way is:

$$m/2^{256}$$

So, the probability that either one of these events occur (and so the attacker wins) is:

$$Pr[forgery] = 1 - (1 - m/2^{128})(1 - m/2^{256})$$

If you want to ignore this second case (which is, in fact, a quite low probability event), and say that it's $m/2^{128}$, well, that's reasonable...


Storing a Secure Boot image with AES-GCM instead of AES + RSA signature In Secure Boot (here defined as data is encrypted and authenticated), we can encrypt the data with AES-128 and authenticate it with a RSA signature, computed over the data's hash, afterwards.

On boot, the device first calculates the hash of the encrypted data, verifies it with the given signature, decrypts the data, and starts executing.
However, calculating the hash and verifying the signature is kind of expensive in case of time and resources, especially for embedded devices.

Proposal:
My idea is to replace AES and RSA signature with AES-GCM to speedup the overall boot time.
Using AES-GCM, we achieve the same security goals confidentiality and authenticity.
The used AES key is stored securely on the device in a HSM (Hardware Security Module).

Drawback:
I am aware of the fact that I loose the advantage of not having the private key on the device to generate a valid signature. In case of key compromise an attacker can read the data but cannot authenticate new data. Using AES-GCM a key compromise means that the attacker can not only read the stored data, but also authenticate it meaning he is able to execute his own data and fully take over the device.

Question:
So besides the discusses drawback, would you consider this a valid approach? Or is there any reason for not using AES-GCM that I overlook?

Edit: Added more details to the description.

Just to clarify this. I am not talking about updating the data to be executed. In the described situation the data is already on the device (how the data is put initially onto the device is not relevant here).

Yes, if you already have a shared symmetric key then this would be something to consider.

Note the following:

you do not need to store a private key in the embedded systems in your previous scheme;
the security of the key generating the signature is probably more important than the key providing confidentiality of the update (updates are often not encrypted - at least for many software packages out there);
related with the previous topic, keeping a private key secure at a central location is more secure than distributing the symmetric key (even if it is placed in a HSM);
the access to the HSM is paramount in this scheme, if the software contains all the data to use the key in a HSM, then one hacked embedded device is still enough to compromise the security - you probably need to encrypt / "sign" for each device with separate keys if you use just AES-GCM.

That's just out of the top of my head - there are very likely more points to consider.


Can AES be broken by factorization (using Quantum Period Finding)? I am trying to understand the paper "Breaking Symmetric Cryptosystems using Quantum Period Finding", and I reckoned the paper is roughly implying to break secret-key cryptographic system by finding the factors of the secret key. Is that correct?

Two things:

Firstly, the paper is not talking about factorization at all; instead, it is using the Quantum Computer as a "constant-that-doesn't-change-the-output" algorithm (that is, find an $s$ such that $f(x) = f(x \oplus s)$ for all $x$) to break certain message authentication algorithms (which may just happen to use AES).

The paper notes that, with these specific message authentication algorithms, if you are able to find such a constant, that also gives you enough information to break the message authentication code.

Secondly, this is not actually a practical break.  They run their attack in a "Quantum Oracle" model, where the attacker is given an Oracle where he can submit superpositioned queries, and get a superpositioned response.  Now, in practice, this superposition state is extremely delicate; it would take rather complicated Quantum Error Correction logic to maintain it (which is actually a bit more than what we can actually implement just now).  It would be quite impossible to send such a query over the internet and hope to get the correct response.

What the attacker would have to do is take this Oracle and build it in his Quantum Computer (which would implement this complication Quantum Error Correction logic), and use the attack that way.  Which leads to the question: if the attacker has access to the actual implementation with the secret keys (so that he can reconstruct it within his quantum computer), why doesn't he just look inside for the keys?


How to prove that a committed value is the square of other Given two Pedersen commitments $c_1=g^vh^{r_1}$ and $c_2=g^{(v^2)}h^{r_2}$, where the committed value in $c_2$ is the square of the committed value in $c_1$, is there a way to prove this relation in zero knowledge?

Yes there is - since any NP relation has a zero-knowledge proof of knowledge (assuming any OWF). Here, it's actually a standard and nice exercise, so I will give you a few hints (if you are stuck, I'll give you more hints):

Do you know how to prove knowledge of an opening to a Pedersen commitment? (hint: it's a straightforward generalization of the Schnorr proof of knowledge of a discrete logarithm)

Then if you know the above, the crucial trick is to rewrite $c_1=g^vh^{r_1}$ and $c_2=g^{(v^2)}h^{r_2}$ as $c_1=g^vh^{r_1}$ and $c_2=c_1^vh^{r_2-vr_1}$. Then, use the proof of knowledge of an opening to show knowledge of an opening of both commitments, to the same message ($v$), in different bases ($g$ and $c_1$).