CSR signature using elliptic curve We've been asked to generate a certificate signing request using elliptic curve and we can't use any third-party library as it's an embedded application with very limited resources).

We are used to generating CSR using RSA, but we can't find any documentation on how to do that with an elliptic curve; specifically, which data to use for the signing part. Studying OpenSSL-generated CSR it looks like there are multiple signatures generated, or a hash of some kind, but we don't know. And OpenSSL source code is quite difficult to read when you're not used to it.

Can anyone point us in the right direction?

It should be pretty much the same. If you can sign a CSR with RSA you can sign with ECC. The exact same data is signed, what changes is:

The signature algorithm should be the right OID (e.g. ecdsaWithSHA256)
The signature value must be the ECDSA signature encoded as specified in SEC (i.e. an ASN.1 sequence of the two integers in the signature)
The public key value must a SubjectPublicKeyInfo structure with values specified in RFC5480: the algorithm field is an AlgorithmIdentifier whose algorithm field is the OID id-ecPublicKey and whose parameters field is the OID of the curve used. Finally, the subjectPublicKey field in SubjectPublicKeyInfo is the public key encoded as specified by SEC section 2.3.3.


What does variable-base point/scalar multiplication mean in ECC? I am a bit confuse about the term, variable-base point/scalar multiplication, in Elliptic Curve Cryptography. What I have understood so far. It means that the base or point on EC is variable/unknown.

Am I right?

Yes, you are correct. There are various methods for scalar multiplication on elliptic curves.

Some of them are optimised for fixed base-point scalar multiplication, i.e., where you a-priori know that you will mostly/exclusively perform scalar multiplications with respect to a fixed base point on the curve. Thus, one can make (extensive) pre-computations (e.g., as done with the the fixed-base Comb multiplier). Think for instance of a scenario where you extensively issue ECDSA signatures, then you always do your scalar multiplication using to the same fixed base point.

Other methods are not optimised to some a-priori fixed point and thus are useful for variable base point scalar multiplication, which often arises in other cryptographic protocols where you do not know the point you will be using a-priori.

Clearly, there are many criteria to decide which multiplier you will use such as speed, side-channel resistance or memory footprint.


Reversability of Xor'd Values In Hash? This may be a dumb question so please forgive me if so, but is a hash function considered one-way even if you have half of an xor'd value?

For example say I have the values R and C, both are randomly generated and the same length as the output of the hashing function H, but while R is known C should not be given only R and h below:

h = H(C⊕R)

Is there any scenario in which you could determine C from h and R or which might reduce the difficulty of brute forcing C in this format to a level you would have to worry about?

Since both values are randomly generated, no, there are no scenarios in which you could determine C from h and R or where your ability to brute force C is made easier by having this information as opposed to just having h.


Why is the number of qubits used in Shor's factoring algorithm so high? When preparing the initial state of the algorithm to factor $n$ he computes $q = 2^l$ such that $n^2 \leq q < 2n^2$.

The first register then contains $l$ qubits. Why does this need to be so high. If we take $q=2^m$ such that $n \leq q < 2n$ we have $m$ qubits which is enoug to be able to represent all integers up to $n$.

Why does he take $l$ qubits is about half of that ($m$ qubits) would be enough?

There is a superposition of states initially, and there must be enough qubits in the circuit so that after the iterations the correct period of the function $f(x)=a^x\bmod N$ where $a$ is random and $N=pq$ can be found, i.e., the convergence should take place without wraparound effects, since we are working in a cyclic group and wraparound can introduce false alarms via accumulation.

Quoting Wikipedia:

  Shor's algorithm consists of two parts:

  A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
  A quantum algorithm to solve the order-finding problem.

  […]

  The quantum circuits used for this algorithm are custom designed for each choice of $N$ and each choice of the random $a$ used in $f(x) = a^x \bmod N.$ Given $N,$ find $Q = 2q$ such that $$N^{2}\leq Q<2N^{2},$$ which implies $Q/r>N.$ The input and output qubit registers need to hold superpositions of values from $0$ to $Q − 1$ and so have $q$ qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least $N$ different $x$ which produce the same $f(x),$ even as the period $r$ approaches $N/2.$


How are messages larger than 512 bits padded in SHA-256? In the NIST documentation for the Secure Hash Standard, it says to pad every message by appending the bit "1" to the end of the message, followed by k zero bits, where k is equal to the equation l (length of message in bits) + 1 + k = 448 mod 512. Then, it says to append a 64-bit block that is equal to the length expressed using a binary representation. The padded message should be a multiple of 512 bits. However, it does not seem to indicate how this would work for a message that is 512 bits or larger. My guess is that the equation above would be equal to the nearest multiple of 512 greater than the length minus 64. For example, for a message of 550 bits, k would be equal to 410. Am I right?

You're close; for a message of 550 bits, k=409; remember, k doesn't include the fixed 1 bit that you initially append.

In general, $k=512i + 447 - m$, where $m$ is the length of the message (in bits), and $i$ is the integer value that yields $0 \le k < 512$.  In your example, $m=550$, and $i=1$; this gives us $k=512\times 1 + 447 - 550$


Key exchange without an underlying semigroup I am wondering whether there is a general reformulation of perfect forward secrecy for 2 party key exchange in 2 messages using semigroups. I am looking for references, which would discuss such approach. I am trying to prove my probably misguided intuition, which tells me that every 2 party key exchange requires an underlying semigroup wrong, but so far I failed. The intuition is that if we want to work in 2 messages:

send message from A to B, B derives final key and sends a message from B to A and A derives the same final key we need a relationship like this.

We need a triple of operations (opAinit,opB,opAfin) such that opAinit : seed1 -> (shareA,msg1), opB : seed2 -> msg1 -> (msg2,key), opAfin : shareA -> msg2 -> key and the following to holdopAfin (fst (opAinit(seed1)),fst(opbres)) = opB (snd(opbres)), where opbres=opB(seed2,snd(opAinit(seed1)). Can this always be turned into an underlying semigroup? I am thinking that it should be possible to glue the different operations and domains/codomains into a semigroup action somehow.

Can this always be turned into an underlying semigroup? I am thinking that it should be possible to glue the different operations and domains/codomains into a semigroup action somehow.

It wouldn't appear so, as there's no reason to expect to be able to perform any operations other than the ones listed in the protocol; in particular, one wouldn't expect to be able to concatenate operations as would be expected in a semigroup.

For example, here's a simple way to turn a public key encryption method (e.g. RSA) into a key exchange method:

Alice generates a public/private key pair $pub_A, priv_A$, and also selects a random nonce $n_A$; she sends $pub_A$ and $n_A$ to Bob
Bob selects a random nonce $n_B$; he encrypts it with $pub_A$, and sends $Enc_{pub_A}(n_B)$ to Alice
Alice uses $priv_A$ to decrypt the ciphertext to recover $n_B$
Then, both Alice and Bob compute $h( n_A, n_B )$ to obtain the shared secret.

In this case, the private values are $priv_A$ and $n_B$; the messages that are exchanged are the values $pub_A, n_A$, and $Enc_{Pub_A}(n_B)$.  It is not at all clear how someone could define an operator that would take an unrelated message/private value pair (e.g. $priv_A$ and $Enc_{Pub_C}(n_D)$, you can consider all four possible pairs), and combine them into a meaningful value.


Is deterministic encryption appropriate for low entropy plaintext when CPA is not a concern? We have a trusted application that observes sensitive identifiers, e.g. credit card numbers. We want to send data associated with these identifiers to an untrusted analytics service that will occasionally generate and send alerts back to the trusted application.

We've considered storing a table mapping sensitive identifiers to an opaque ID (e.g. UUID) to pass to the untrusted analytics service. But since there are billions of sensitive identifiers, the application can't store all the mappings due to storage constraints. We need the opaque ID to be stable over time, since the analytics service will be keying off of that to correlate data we send it. We also need the opaque ID to be reversible, so that the trusted application can determine what sensitive identifier was involved in an alert.

What we're planning on instead is to use a deterministic encryption scheme, though we're concerned about how well it fits our use case: often deterministic encryption is discussed in the context of key wrapping schemes, but the identifiers we see are far less random and have structure. On the other hand, we also see that chosen plaintext attack (CPA) is typically a concern, but in this case we aren't going to allow the attacker (i.e. the analytics service) to ask the telemetry service to encrypt arbitrary plaintexts.

We also don't want the untrusted analytics service to be able to figure out plaintexts or the key(s) used in a deterministic encryption scheme, even if it sees a large number of ciphertexts.

Given these constraints, what scheme best satisfies our use case? In particular, is AES-SIV applicable in this case?

Yes, deterministic encryption would be a good solution to the problem you outlined.

Do however note, that an analytics service for credit card transactions will probably get information about payments like the time, location and amount. This can easily be used to create a profile for a specific ID. Given some extra information, for example from marketing companies, a deterministic ID can often be related to people. Whether this is an interesting consideration or not probably depends on the rest of the system.


Chosen plaintext attack on textbook RSA decryption Let $(n,d)$ be an RSA private key and $(n,e)$ the corresponding public key.

Generate a secret random $r$ from $(\mathbb{Z}/n\mathbb{Z})^*$
Compute $C’ = C (r^e) \bmod n$
Submit $C’$ as a chosen ciphertext and receive back
 $M’ = C’ ^ d \bmod n = M r$,
 since $C’ = (C \bmod n) \times (r^e \bmod n)
      = (M^e \bmod n) x (r^e \bmod n)
      = (M r)^e \bmod n$.
Deduce $M$ with a division modulo $n$ since $r$ is known: $(M r) r^{-1} \bmod n$.

I am trying to understand a chosen plaintext attack on textbook RSA decryption.
If I follow the method above, I must generate a random $n$ from a range of $n-1$ values. How I am I going to know which of my $r$ values is the one I need, because the $n$ value very big? My $e$ value is 65537 and my ciphertext value is very big.

You seem to have some misconception here. Obviously, you are investigating chosen ciphertext attacks (CCAs) on textbook RSA instead of chosen plaintext attacks (CPAs). To help you with your understanding I am discussing CPA on textbook RSA first. To analyse all these kinds of attacks we formally model the attack as a game between an adversary (trying to break the property) played with a so called challenger.

CPA for textbook RSA

In a CPA game, an adversary can compute arbitrary encryptions of plaintexts of its choice as it is given the public key by the challenger and at some point submits two distinct plaintexts $m_0$ and $m_1$ to the challenger. The challenger then flips a coin to determine a bit $b$ and provides an encryption of $m_b$ (the challenge ciphertext $c^*$) to the attacker and the attacker has to output a guess $b^*$. The adversary wins if the probability that $Pr[b=b^*] -1/2$ is non negligible (in the security parameter). This means that the adversary needs to succeed significantly better than just guessing the bit.

Clearly, textbook RSA does not provide IND-CPA security, since it is deterministic. When the adversary receives the challenge ciphertext $c^*$, he simply encrypts e.g. $m_0$ and if the so obtained ciphertext matches $c^*$, then we have $b^*=0$ and $b^*=1$ otherwise. Note that the probability of winning this game for textbook RSA is 1.

CCA for textbook RSA

This notion is stronger than CPA and this is modelled by giving the adversary additional access to a decryption black-box (oracle) throughout the game, i.e., the adversary is allowed to submit ciphertexts and gets back the respective message, but does not get to hold the decryption key directly.

The only restriction is that the adversary is not allowed to ask the decryption oracle to decrypt the challenge ciphertext $c^*$.

Now lets look at your given procedure. What you describe is a strategy for winning the CCA game for textbook RSA. Note that if the adversary receives the challenge ciphertext $c^*$, he is not allowed to send $c^*$ to the decryption oracle directly. But what the adversary can do is to "blind" the challenge ciphertext with a "blinding value" $r\in \mathbb{Z}_n^*\setminus \{1\}$, i.e., it submits $c'=c^*r^e \pmod n$ to the decryption oracle (note that this is allowed as $c'\neq c^*$). Then the adversary gets back $m'$ from the decryption oracle which has performed a decryption to obtain $m'=(c^*r^e)^d=m_br \bmod n$. Now if the adversary has chosen $r$ as above, i.e., such that it is invertible in $\mathbb{Z}_n$ (which is the case iff $r$ is relatively prime to $n$, i.e., $gcd(r,n)=1$), then the adversary can compute $r^{-1}$ and compute $m_b=m'r^{-1}$ and wins the CCA game with probability 1.

There are subtle differences between IND-CCA1 and IND-CCA2 security, but this explanation should be sufficient here.

Note that when employing a proper padding scheme to textbook RSA such as OAEP, the decryption oracle will only return a decryption if the decryption works correctly, i.e., the decryption oracle checks if the padding of the message is proper. For a "good" padding scheme the probability of ciphertext $c'=c^*r^e \pmod n$ yields a proper decryption is negligible and thus RSA-OAEP provides IND-CCA security as the above discussed attack does not work (with overwhelming probability).


AES encryption for images Why AES based encryption is not recommended for encrypting images with high redundancy in their content? for example, the encryption of an image which shows a bird in the blue sky. Most of the pixels are blue in that case.

What do you mean "AES is not recommended for highly-redundant images"?

Perhaps you're referring to "ECB mode is not recommended for highly-redundant images" (and yes, AES can be used for ECB mode).

Yes, AES in ECB mode is not recommended for highly-redundant images, because it doesn't disguise when two 128 bit plaintext blocks are exactly the same.  Here is a famous example of a drawing of the Linux penguin encrypted using ECB mode:

As you can see, you can make out significant details of the original image.

AES in other modes (CBC, CFB, Ctr, GCM) doesn't have this weakness, and so are strongly preferred.


Can there be more than one valid private exponent for a given p, q, and e in RSA encryption? For example, given:

p = 173, q = 149, e = 3

Using phi(n) gives d = 16971

While using lambda(n) gives d = 4243

Both values satisfy the checking equation (de)%phi=1, so are both correct, and if so, is one better than the other?

Both values satisfy the checking equation (de)%phi=1, so are both correct, and if so, is one better than the other?

Actually, $(3 * 4243) % phi = 8484$; however $d=4243$ is a valid private exponent, because both $(3 * 4243) \bmod (p-1) = 1$ and $(3 * 4243) \bmod (q-1) = 1$

In any case, as I stated in a comment, if there is a valid private exponent, there there are an infinite number of valid private exponents.  If $d$ is value, then so is $d + k (p-1)(q-1)/\gcd( p-1, q-1 )$, for any integer $k$.

  Since there are an infinite number of valid private exponents, are any of them theoretically better than others?

Cryptographically speaking, they are all equivalent, and so in that sense, no one is any better than any other.

Practically speaking, well, in some rare cases, there may be, but in a surprising number of cases, it doesn't make a difference.

We generally use a CRT optimization when performing RSA private operations; with this, we precompute the values $d_p = d \bmod p-1$ and $d_q = d \bmod q-1$, and those those values exclusively (not referring to $d$ otherwise).  And, any valid value of $d$ will give you the exact same value for $d_p, d_q$, and so it doesn't matter which value of $d$ you started with.

In some rare cases, we may use the value of $d$ directly (perhaps we value simplicity over performance, perhaps we don't want the holder of the private key to know the factorization [1].

In that case, computing $C^d \bmod N$ would likely be a bit faster if $d$ where smaller; in that case, the value $d = e^{-1} \bmod \text{lambda}(p-1, q-1)$ might be somewhat preferable...

[1] On the other hand, if someone gets the values of both $d$ and $e$, they can factor, and so there may be little interest in this.


Is my authentication system adequate? I have clients sending data to a server.  The data is not encrypted, but that's OK.  I want to make sure the server only accepts data from authorized clients.

The server knows all of the clients' passwords.  The clients generate a fairly random string (the first 6 characters of a UUID, gotten through the Python uuid.uuid4() function).  They do md5(random_string + password), and send this and the random string along with their data.  The server takes the random string, the password, and does the md5 itself to verify that the client does indeed know the password.

Is this home-made system adequate?  Again, I just want clients to be verified, I'm  not worried about encryption of the data.

They do md5(random_string + password), and send this and the random string along with their data.

What would happen if the attacker recorded the above data, and then sent 'md5(random_string + password)', 'random string' (both from the recorded data), and then included their preferred data.  The system would check that the random string checks out, and so trust the data.

What I would recommend is something like:

HMAC( random_string, data ), data

(where data would include something that would identify the client, if necessary)

That way, the attacker can't just cut/paste the authentication information; it is a function of the data being authenticated.

BTW: there is no reason to use MD5.  The weaknesses known in MD5 do not apply in your case, however that's not a good enough reason to use it; I'd suggest using SHA-256 instead (possibly truncating it if 256 bits is too long)


Why is $Mac_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$ not a secure MAC? I am preparing for an exam and trying to solve the following question I found on the internet:

  Let $F_k$ be a pseudorandom function. Show that the following MAC for messages of length $2n$ is insecure. The shared key is a random key $k \in \{0, 1\}^n$.

  $\operatorname{Mac}_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$

  where $m_1, m_2$ are binary strings of length $n$ and $\overline{m_2}$ is $m_2$with all its bits inverted. What is the minimum number of queries that the adversary has to make to the MAC-oracle to forge a MAC?

To solve both questions I have tried to construct two messages for which the attacker requests tags and then combine the messages and corresponding tags in a way that gives a valid message and tag. Regrettably, this didn't work out since the second part of the tag combines both parts of the original message. Am I on the wrong track with my approach?

We want to forge the tag for $m = m_1 || m_2$. The tag we need to produce is:

$$\operatorname{Mac}_k(m_1||m_2)=⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$$

We'll query the oracle with the message $m_1^\prime || m_2^\prime$, which needs to be different from $m_1||m_2$ to count as forgery. Consider $m_1^\prime || m_2^\prime = (m_1 \oplus \overline{m_2}) || m_2$, which is different from $m_1||m_2$ iff $\overline{m_2} \neq 0$.

This message has the tag:

$$\begin{align}
  \operatorname{Mac_k(m_1^\prime||m_2^\prime)}
  &=⟨F_k(m_1^\prime),F_k(m_1^\prime \oplus \overline{m_2^\prime})⟩ \\
  &=⟨F_k(m_1 \oplus \overline{m_2}),F_k((m_1 \oplus \overline{m_2})\oplus \overline{m_2})⟩ \\
  &=⟨F_k(m_1 \oplus \overline{m_2}),F_k(m_1)⟩
\end{align}$$

swapping the two outputs produces the tag for $m=m_1||m_2$.

Thus we can produce forgeries using only a single query to the MAC oracle.


Salting when encrypting? I was attending a database encryption session at a developers conference. The presenter (who was a published author on the subject) said that MS SQL Server did not support salted hashes in the database, but it does support salting with encryption. This was the first I heard of salting in encryption. I asked for clarification to make sure that was what he was saying.

Is this something anyone else has heard of before? Is this an important practice that I have just never heard of before?

Looking at the MSDN link given by Tangurena, they use the word salt in this paragraph (and the following ones):

  To prevent discovery of plain text content by comparing encrypted values (the second
  attack), most encryption algorithms include a salt value. Specifying a different salt
  value generates a very different encrypted output. When using the .NET cryptography
  classes, you can specify the salt as the initialization vector argument.
  In SQL Server, a random salt value is always applied to the encryption.

A block cipher (given the same key) always maps the same plaintext to the same ciphertext.

When constructing a stream cipher from a block cipher, we usually use one of the secure cipher modes to avoid that same input blocks give the same output, which would be a point of attack. (See the ECB example image mentioned there.)

A database encryption works a bit different than a stream encryption: you normally want to have access on each record individually without having to decrypt the whole table/database.
But we still want to avoid same records/fields giving the same ciphertext.

To do this, we use the same trick as for the stream ciphers: for each block of data to encrypt, we generate some random initialization vector. But here it is saved together with the data instead of derived from the previous block(s) like in a stream cipher. This is input into the block cipher, as well as the key and the plaintext, for both encryption and decryption.


Is there an anonymous non-interactive authorisation scheme with peer-side auth. signature generation? I implemented a pseudonymous PKI scheme (by K. Zeng @Springer Link), where all peers can change their public keys including its signature on their own. I am looking for a way to extend it with some authorisation functionality in that way, that an Authorisation Instance can provide specific credentials to a peer. (e.g. give their message credibility, or allow some special message types). Since such a credential could be linked with the identity of the peer, it also should be renewable without the reinvolvment of the Authorisation Instance. Some of the peers only us local communication and, therefore, are not able to contact the Authorisation Instance or the CA.

The papers I read so far, only offered interactive solutions in the form of a challenge response or required the involvement of the Authorisation Instance again. Maybe I searched for the wrong keywords.

I could solve my question using the fundamental work of Eric Verheul: Self-Blindable Credential Certificates from the Weil Pairing.

What I didn't know was the basic principle of self-blinding. In its simplest form, a peer (sk: $x\in Z$, pk: $X=g_1^x\in G_1$) communicates with an authority (sk: $a\in Z$, pk: $A=g_2^a\in G_2$) to get a certificate for his pk. cert: $C=X^a \in G_1$.
Now the peer is able to self blind his public key and the certificate using a random $k \in_R Z$:  $X_b=X^f\in G_1$; $C_b=C^k \in G_1$. This can be verified using $e(X_b,g_2)=e(C_b,A)$ which is $e(g_1^{axf},g_2)=e(g_1^{xf},g_2^a)$.

To add authorisation, a hash of the authorisation information $c=hash(Authorisation Information)$ can be included: $C=X^{a+c}$. Now the verifier needs to recalculate $c=hash(..)$ to verify the authorisation: $e(X_b,g_2)=e(C_b,A \cdot g_2^c)$.

(Just for the record: this example is not secure, since the peer could remove its key from the certificate and then sign any other PK too.)


How to construct the blind factors in practice? I'm Implementing a protocol that uses masking techniques (or blinding factors), so we can mask a value $y_0$ as $m_0=y_0 \cdot r_0$ where $y_0 \in \mathbb{Z}_p$ and $r_0 \stackrel {R}\leftarrow \mathbb{Z}_p$ (let $_p$ be a prime number) and the $m_0$ can be unmasked as $m_0\cdot r^{-1}_0=y_0$ at any time.

My Question is: what function do I need to use to get $r_0$ (or $r_i$ in general)?

Can I Use Pseudo-random generators (PRG)? Why?

Blinding technics are well know now to defeat most attacks against SCA.
You need a random number generator (True or Pseudo) to generate unpredictable random $r_i$.
Additionnal precautions against Zero Attacks values can alo be taken.
Try this: $m_0=y_0 \times r_0 \; + \; r_1 \times p \; mod \;(r_2 \times p)$


HMAC SHA256 vs RSA SHA256 - which one to use Salesforce recently announced they are moving away from HMAC SHA256 to RSA SHA256.

Why did they make that move? Any technical factors?

Is HMAC really easy to break?

PS: I am not a security expert.

From a security standpoint, HMAC-SHA256 is exceptionally secure, so the move is unlikely to relate much to cryptographic security unless they were using the construction incorrectly, which is improbable.

I freely admit that I know almost nothing about Salesforce, but I can guess at the rationale behind the decision: since HMAC is a symmetric primitive, both sides of a channel need to have a shared, private key. With an asymmetric primitive like RSA, on the other hand, the verifying party needs only the public key (certificate), so the private key is held only by the party who needs to sign.

This means that a Salesforce employee could not, as a hypothetical scenario, steal an authentication key and masquerade as a customer without changing the codebase (which often leaves an audit trail), since the private key is held only by the client. The tradeoff is that RSA is much slower than HMAC, but that doesn't always matter.

Now, as I said, I know almost nothing about Salesforce, so I don't know if this was their thinking or not. But coming from a purely cryptographic POV, that would be the most logical explanation, I think. That said, if you are a customer, you might ask them — maybe you'll get an interesting response from an engineer.


Can we retrieve his private key using his public key in ECC? A paper wallet is the name given to an obsolete and unsafe method of storing bitcoin which was popular between 2011 and 2016. It works by having a single private key and bitcoin address, being printed out onto paper. Assume you have found the paper wallet of Satoshi Nakamoto. However, some of the paper is torn, specifically the last 72 bits are missing.

Is there any better solution than brute force?
If you get access to his wallet, how will you transfer money from his wallet to yours without raising suspicion?

On ECC, the private key is a value $k$ in the range $[0,q-1]$ where $q$ is the order of the group generated by a point $G$, with $q$ a prime number, and $Q = kG$ is the public key.

The best known algorithm to solve this is Pollard's rho algorithm which runs asymptotically in $O(\sqrt{q})$.

In your situation, part of $k$ is known, except the $72$ least significant bits. Writing $k = k_12^{72} + k0$ with $0 \leq k_0 < 2^{72}$, then $k_1$ represent the known bits and $k_0$ the unknown part you are looking for.

We have
\begin{array}{rcl}
Q & = & kG \\
& = & (k_12^{72} + k_0) G \\
& = & k_12^{72}G + k_0 G
\end{array}
So $k_0G = Q'$ where $Q'= Q - k_12^{72}G$ is known. Now, instead of looking for $k$ in the range $[0, q-1]$, you are looking for $k$ in the range $[0, 2^{72} - 1]$ which has a much much smaller size.

For that, you can look at Pollard's kangaroo algorithm which can search for the discrete logarithm in the subset $[0, 2^{72} - 1]$ in an asymptotically complexity $O(\sqrt{2^{72}})$ which is $O(2^{36})$ and is feasible.


Using Poly1305 MAC key multiple times I know that for Poly1305-ChaCha20 reusing the key does reveal information about the plaintext. How it is for the Poly1305 MAC algorithm? Revealing information about the plaintext is not a problem at all, as it is available in plaintext anyways.

Question: Does a reuse of the Mac key reveal information about the key itself ?

Source: https://tools.ietf.org/html/rfc8103

Does a reuse of the Mac key reveal information about the key itself ?

One would certainly hope not - Message Authenticate Codes are supposed to be able to be safely used with the same key multiple times.

There is one caveat - the Poly1305 algorithm does need a nonce, which must be different whenever you MAC a message (specifically, you cannot reuse the same (key, nonce) pair to MAC two different messages) - if you do, you do leak enough information for someone to generate a forgery.


Are the SHA family hash outputs practically random? Say I hashed the output from a random number generator (with nonce), would the resulting SHA256 hash be as random as the inputted number?

And If I used the first 5 hex characters, and then used the first 5 ignoring the very first character and so on repeating removal of the first character, would each number be just as random?

Example of what I mean, here's a 512 bit hex string.

26657320797d4f5b385d43274a246178263f3b686b645e375b45643442

Is any segment of 5 characters chosen from random locations in the string guaranteed to be a fairly random number?

I am trying to make a pretty simple random number generated based on a hashed seed.

Say I hashed the output from a random number generator (with nonce), would the resulting SHA256 hash be as random as the inputted number?

Let's suppose you flipped a perfectly fair coin. You flip it 1024 times to create a bit string of 1024-bits.

Because the coin is perfectly fair, this means that each strings of 0s and 1s will appear with precisely the same probability.

What happens if we apply SHA-512 to these strings? Well, in order for SHA-512 to give a completely uniform 512-bit output, it would have to be the case that if we hashed every 1024-bit string then each 512-bit hash value would have to appear precisely $2^{512}$ times.

There is no proof that SHA-512 behaves in this way. I would be very surprised if this turned out to be the case!

As such, the output of hashing a truly random stream is a stream which is bias. This bias will be very small indeed, but it will be there. So the answer to that specific question is no.

In practice, the bias is so unbelievably small that it doesn't matter. In fact, many hardware RNGs hash the entropy pool to produce output bytes.

However, it's worth noting that using such an RNG as the basis for generating a  one-time-pad actually ruins the security proof! It would be technically insecure but good luck exploiting it.


Probabilistic padding to avoid Håstad’s Broadcast Attack Can someone explain why probabilistic padding like OAEP is particularly useful for avoiding Håstad’s Broadcast Attack? I don't really get the reason why.

If you use the same padding on the same messages, sent to multiple different public keys, then you have satisfied the criteria of the Håstad attack.

Randomizing the padding as in OAEP means that you don't use the same padding for each message.  Even better, in a modern system like RSA-KEM, there's no ‘padding’ per se, or even any ‘message’ involved directly in the RSA part of the computation—the sender just

picks $0 \leq x < n$ uniformly at random,
uses $H(x)$ as a secret key for an authenticated cipher to encrypt an arbitrarily long message, and then
sends $x^3 \bmod n$ alongside the authenticated ciphertext.


How do I produce a stream of secure random numbers from AES-Counter mode? I have just made my own program to encipher, using AES in counter mode, and have validated it using NIST data. So I know I have done it properly.

I have read that AES-CTR can produce a stream of random numbers. To achieve this, what do I feed in as the plaintext? Will any text do? Does it matter if the plaintext has repetitions?

You can get up to around $2^{64}$ random bits from counter mode (before you hit the birthday bound due to the lack of a collision), simply by running it as is. If you've got a full implementation of counter mode, the plaintext can be anything you like, because the stream (ie the output of the $E_k(ctr)$ calls), should appear uniformly sampled from $2^{128}$.


Should the most significant byte of a cryptograhic key be nonzero? Is it safer to give a non zero value to the most significant byte (MSB) of a cryptographic key to ensure its length (not 31 instead of 32 for an EC private key on a 256-bit curve for example)?

Or is it counterproductive because it decreases the entropy?

I ask the question for the MSB but it could be for several of the first bytes.

Many keys do not consist of a single value. Other key types, such as most symmetric keys, don't have a most significant bit or byte as the key value isn't interpreted as an integer. So this question would be different for each key type and encoding.

In general though you would just decrease the "entropy" or key size. This is certainly the case for ECC, and probably most other schemes that use groups theory / modular arithmetic. So yes, that's certainly counterproductive.

Note that if you view the key value as a number that you would only have to set the MSB bit to 1 to ensure that the key value is at least $2^{(n-1)}$ - assuming that the key uses unsigned values of course.

Cryptosystems should define how keys are created. You'd better make sure you keep to the rules of the cryptosystem or security may well go down the drain.


How to test distribution of a hash function? From what I've found, it is generally accepted a cryptographic hash function like SHA-2 has an evenly, randomly distributed output.  Is there a way to test this without running through the entire 2^512 keyspace?  Generate a large number of high-quality 512 bit random numbers?  What about random 64 character "keyboard ascii" strings?

Well, for one, SHA-2 (either SHA-256 or SHA-512) doesn't have a 'keyspace'; that's because it doesn't have a key.  SHA-2 takes an arbitrary bitstring is input, and generates an output; while there are limits on how long the bitstring can be, those limits are so huge ($2^{64}-1$ bits for SHA-256, $2^{128}-1$ bits for SHA-512), those limits can in practice be ignored.

With that nit aside, your question is 'given arbitrary inputs (that is, inputs that are not specifically selected with the SHA-2 hash in mind), does the SHA-2 hash functions really generate outputs that are evenly distributed?

To test that, you can use any input distribution that strikes your fancy (as long as inputs aren't repeated; that would bias the statistics, and as long as you're not selecting inputs specifically because of what their SHA-2 hashes are).  You can certainly consider random 512 bit (or whatever size) bit strings, or random 64 character strings.  I would personally advise you to look at "related inputs", that is, inputs that are similar (for example, a 512 bit counter that increments for every hash) -- similar inputs are more likely to stress the SHA-2 function.

Now, one final comment: while you can verify a weakness in SHA-2 with this procedure (although it's extremely unlikely you'll find anything); you cannot verify that SHA-2 is actually well-distributed.  Just because the tests you run cannot find anything doesn't mean that a different set of tests wouldn't.


How do we compute IV+1 in CTR mode? This may be a very simple question, but I have not found info about this in any place. My question is about CTR mode: When it says $IV+1$… How do we make this operation?

For example, if I have the IV value 69dda8455c7dd4254bf353b773304eec (hex-encoded), what would be the result of $IV+1$?

I think that we must consider $IV$ as a hex number by itself and add the $1$ hex number (in general, add the $L$ hex number), but I’m not sure. I hope that someone can help me understand this.

The reference for this is NIST SP800-38A, especially its appendix B.

Basically we consider the IV a binary value of the width of the block cipher (64-bit for DES, 128-bit for AES), and add 1 to that, except for one detail: there is no carry at some application-specified rank, defining the maximum number of blocks that can be enciphered with a single IV; if that limit is exceeded, we are in trouble (as if we reused a One Time Pad).

A possible setup for AES would be to draw the line at half the 128-bit words size, which "limits" to $2^{64}$ 128-bit blocks. That is $2^{68}$ bytes, or 256 Exbibyte, or 295 Exabyte, or a little over 49 million 6-TB hard disks (the biggest commercially available at time of writing); moving these would require about 1400 double-size (40') containers of 28 tons each.

The other 64 most significant bits can be used as session number. If we draw such session numbers randomly, one each second, for a decade, odds are 1/370 that two session numbers are equal (and we have a small problem there).

It is also perfectly fine to increment over the full 128 bits, and start from a random 128-bit value.

In any practical case: the IVs after $\texttt{69dda8455c7dd4254bf353b773304eec}$ would be $\texttt{69dda8455c7dd4254bf353b773304eed}$ - IF everything is expressed using big-endian convention!

Update: It is also possible to define non-standard ways to increment an IV. One with a low hardware overhead would be cycling a maximal-length LFSR from an initial non-stationary state, which can be implemented with 1 or 3 XOR gates (depending on if the degree allows a trinomial or not) within a single clock delay, rather than some wide adder perhaps with some carry lookahead for high clock rate.


OFB or CTR mode without an IV I'm reading the SSL specs here.

The interesting thing seems to be that RC4 is not re-keyed with a new IV for each message. The stream cipher state is simply carried over to the next record. Why is this secure? Shouldn't messages be encrypted with different IVs? Honestly, this is one part I don't fully understand about IVs: each message needs a different IV, but what counts as a message? A full stream of records? One record?

The CBC modes do have different IVs for each block.

My question is, how about a stream ciphery mode of operation, like OFB or CTR? Do I need new IVs for each smallish record, or can I do what SSL does with RC4 and just carry over the cipher state? Is that in any way insecure? WEP seems to do the new-IV-per-packet thing, and that seems to have caused its downfall. Why?

The answer from owlstead and its comments covers WEP part quite nicely.

This answer concentrates on CTR and OFB.

Strictly speaking, CBC, CFB, CTR, and OFB modes always use IV or counter. I'm assuming that the question was more like is it possible to use CTR or OFB mode securely without transmitting IV. I.e. for instance, start at all zeroes IV/counter and increment the counter for each message. This appears to be possible and secure. (As long as you're careful enough to never reuse same counter+key combination.)

Details for selecting IV for CTR and OFB modes

The answer for IV(/nonce in CTR and OFB modes is found in document NIST SP 800-38A: Recommendation for Block Cipher Modes of Operation, which describes these modes. This document tells in Appendixes B and C various recommendations by NIST for choosing IV/counter for CBC, CFB, CTR and OFB. Long story short,
for CTR and OFB modes, it is sufficient that IV/counter used is always unique for the same key, as long as it is also unique for each invocation of the encryption operation.

In other words, counter is ok for CTR and OFB. In OFB mode, it is not safe to use cipher text from a previous operation as IV, a practice that has been often used with e.g. CBC mode. The language of NIST specification may be misleading. There is evaluation of cipher modes of operation from Rogaway, which you may find easier to read and understand, and containing a lot of additional detail.


Verifying signature owner (without verifying the actual document) Programming in Java.

I have an RSA key-pair, a document, and a signature created with the Java Signature class, using SHA512WithRSA. In order to verify the signature, of course, I need to provide the

public key,
signature,
document.

Is it possible to verify the owner of the signature, using only:

public key
signature

No.

An RSA signature is just a single number, encoded in a certain way. The number represents $x^d$, where $x$ is a padded hash of the document and $d$ the private exponent. If you know a public key $(m,e)$, you can calculate $x = (x^d)^e \mod m$, but without a document (or at least its hash) there is nothing to compare it with to verify anything.

The only thing you can check is whether the signature matches the size of the key (e.g. both 2048 bits). If it doesn't, it clearly isn't from that key, but that's it.


Reverse the order of encryption and decryption in CBC mode. Does this work? To encrypt a message, one uses the algorithm for doing a CBC decryption. To decrypt a message, one uses the algorithm for doing a CBC encryption. Does this work?

Welcome randomjsmash!

Reversing encryption and decryption would give you a very weak encryption scheme.

First, it would make the initialization vector effectively useless. An attacker could simply unmask the first encrypted block and subsequent blocks do not depend on the initialization vector.

Second, guessing a single block correctly (e.g. assuming it contains only space characters used for indentation) would allow an attacker to unmask the following block. If the attacker were able to do this repeatedly, she would immediately see if blocks of plaintext repeat.

Being able to see repeating patterns will enable an attacker to perform statistical analyses and can quickly lead to a complete loss of confidentiality.


What do recent announcements about solving the DLP in $GF(2^{6120})$ mean for RSA After just reading the post Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?

I was a bit confused. DSA, ElGamal and others are based on the assumption that DLP is a hard problem to solve. The DLP problem can be defined in different cyclic structures, but making progress in one of this structures does not imply any progress in breaking DLP in other structures?

Also, the question
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
contains the following:

  So, given your question "Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?" the answer would be yes. Furthermore, if you can solve DLP for composite moduli, you can also solve it for prime moduli.

So, we now have a improved algorithm that can solve the DLP problem for $2^{6120}$ composite moduli? Does this mean anything for RSA 1024, 2048? DSA? Or are the DLP assumtions only valid in the cyclic structure where there are used?

And why is the exponent that large? RSA, Diffie Hellman all use exponents 1024, or 2048?.

(This question could be flagged as duplicated. But because i could not pose these questions as answer i asked a new question.)

I hope the question is clear. And as always, thanks for your help!

Göloğlu, Granger, McGuire, and Zumbrägel broke the DLP in the Galois finite field with $2^n$ elements for $n=6120$, and Antoine Joux did it for $n=6168$, with modest computing power. These recent announcements directly imply that cryptosystems (if any) based on the DLP in a field with $2^n$ elements are no longer secure, including for $n$ big enough that this finite field was previously thought to be of cryptographic interest (e.g. for pairing schemes), at least when $n$ is of the forms explained here enabling the new attacks.

One way to see the Galois finite field with $2^n$ elements, $GF(2^n)$ or $\mathbb{F}_{2^n}$, is as the set of $n$-bit vectors representing the coefficients of a binary polynomial of degree $n-1$, with as additive law the addition of binary polynomials, and as multiplicative law (of interest in the DLP) the multiplication of binary polynomial followed by reduction modulo some suitable binary polynomial of degree $n$.

RSA and DSA work on different algebraic structures:

RSA works on the finite unit ring of integers modulo $N$, with $N$ a public composite of secret factorization, which factors are huge primes. Notice that the number of elements in this ring is $N$, and thus not of the form $2^n$.
DSA works on the finite field of integers modulo $P$ for a public prime $P$ (such that $P-1$ is divisible by some suitably large prime, which is the order of a multiplicative subgroup; thanks to Samuel Neves for pointing my earlier serious mistake on that). Notice that the number of elements in this field is $P$, and thus not of the form $2^n$.

Because of these different algebraic structures, I can confidently tell that the algorithms used in these recent announcements are not directly usable against RSA and DSA. In my not so informed opinion, for the same reason, they are not directly usable against schemes based on the DLP on elliptic curve groups, including when the base field of the elliptic curve is some of the $GF(2^n)$ that are common practice for ECDSA. In fact I can not spot any cryptographic scheme in wide use that is directly impacted.

As of future advances against RSA, DSA, and Elliptic Curve cryptographic schemes, that may be enabled by these recent developments, my opinion is near worthless, for I'm not a competent number theorist. But I can still commit my feeling: I'm not too worried for the security of RSA, DSA, DH; and ECDSA or ECDH over elliptic curve groups with base field $GF(P)$, or even $GF(2^n)$.

Additions: The $n$ in the new attacks is large (compared to $2048$ or $4096$, previously thought safe and very safe levels) because the attackers can, and bigger values better demonstrate the power of their techniques.


AES as Integer Program I read that AES can be broken by solving a Linear Integer Program (IP).

From a given encrypted text, how can one construct this IP?
How big is the system?

First I find the question legitimate and trying to evaluate the complexity is not an easy problem. But regarding how it looks like, I would mention beforehand that AES or any other crypto algorithm could be written in many different ways.

See for example https://www.iacr.org/archive/asiacrypt2002/25010159/25010159.ps

BTW any crypto function appears like a map $\{0,1\}^n \times \{0,1\}^m \longrightarrow \;\{0,1\}^n$, with appropriate identification of message and key spaces. We then can mathematically modelize with the theory of boolean functions.

For a chosen m-bit key; $y_i=f_{k,i}(x_1,\cdots,x_n)=\sum_{(u_1,\cdots,u_n)}a_u.x_1^{u_1}\cdots x_n^{u_n}=\sum_u.a_ux^u$, with a compact representation where $u=(u_1,\cdots,u_n)$ and $u_i \in \{-1,0,+1\}$, and $u_i^{-1}=1-u_i$ represents the ONE-complement of the bit $u_i$.

This representation by the boolean function is to indicate the complexity of for synthetisation of a crypto algorithm (even in hardware we can easily build a circuit dedicated to DES, AES or even PKC).
The reduction methods employed in logic design analysis (KARNAUGH, QUEEN_McCLUSKEY,...) are generally limited to a restricted number of variables.
However, boolean functions is an active field of research in cryptography and attacks. See for example how Linear and Differantial cryptanalysis manage the question.

I hope this gives a general idea of this interesting question.


Key derivation: bit lengths This is a follow-up question to

HKDF: ikm, salt and info values

Based on the feedback, I have now decided to implement my key derivation for AES-GCM-256 file encryption roughly as follows:

Everything up to scrypt is run once, the HKDF-expand part is repeated for every file to be encrypted. The random salt and info values get stored (unencrypted) with the encrypted file.

My questions:

Do you see any serious flaws?
What is your opinion about the various bitlengths? In particular: Does it make any sense at all to blow up everything to 512 bits temporarily when, in the end, I use only 256 bits for the data protection key?

Generally you should be fine with having a minimum size of 128 bits and a maximum size of 256 bits for parameters such as salts. Although you should halve the security parameter because of the birthday problem, I think most cryptographers would still choose 256 bits salts as maximum.

It is unlikely that the birthday problem can be used to enhance the security beyond the, say 192 bit security it offers after about $2^{64}$ files. So you would have a very large margin with 256 bits. Salts are sometimes even set to 64 bits - for instance in the OpenSSL command line for encryption - but like anything of 64 bits, that may be on the low side by now.

WRT the security of the construction rather than the salt size

Beware that advertising a security strength of 256 bits for password based encryption is rather insincere. Passwords commonly have a security strength far below 64 bits. Even a strong key strengthening function such as scrypt will not add significant strength to this.

Such issues may be partially resolved by using public key encryption where the public key is used for encryption and the private decryption key may be kept in an less accessible location until it is used. That private key may need to be wrapped as well, possibly with a scheme such as specified in the question. OpenPGP is an (old) format that could be described this way.


OFB mode and CFB mode error propagation in 64bits I am trying to understand (in simple terms), how error propagation works in the transmission of ciphertext in both OFB and CFB using a 64bit mode. I am having a hard time understanding the mathematical concepts put into simple terms. Thanks.

First, approximately nothing in modern cryptography cares about the notion of error propagation in block cipher modes of operation—it is an archaic relic of the dark ages of crypto engineering that left us with hopelessly confusing concepts like ‘block cipher modes of operation’ thrust into the faces of hapless application engineers.  If you want to detect errors you should use authenticated encryption (unless you have a strong reason to suspect they will be uniform rather than malicious in which case an error-detecting code like a CRC is better).

So unless you're answering an exam question in a class that you might want to drop anyway, it's not likely to figure into anything in the real world.  There's hardly ever any reason to use CFB or OFB anyway: CTR is simpler and faster and more widely deployed as part of the authenticated encryption scheme AES-GCM.

Also, while the block size doesn't affect the answer to this question about CFB mode and OFB mode, you should never use a 64-bit block cipher (even if it has larger keys, like 3DES or Blowfish or IDEA; the block size, not the key size, is the problem) until you understand how bad it can be and why the badness is inapplicable to your needs.

That having been said…

The basic idea of CFB is to use the encryption of the IV as a one-time pad for the first block, and use the encryption of the first ciphertext block as a one-time pad for the second block, and so on: if the plaintext is $P = P_1 \mathbin\Vert P_2 \mathbin\Vert P_3 \mathbin\Vert \cdots$, then the ciphertext is $C = C_1 \mathbin\Vert C_2 \mathbin\Vert C_3 \mathbin\Vert \cdots$, where

\begin{align*}
  C_1 &= P_1 \oplus E_k(\mathit{IV}), \\
  C_2 &= P_2 \oplus E_k(C_1), \\
  C_3 &= P_3 \oplus E_k(C_2), \\
      &\vdots
\end{align*}

The basic idea of OFB is to use the encryption of the IV as a one-time pad for the first block, and use the encryption of the first pad block as a one-time pad for the second block, and so on:

\begin{align*}
  C_1 &= P_1 \oplus E_k(\mathit{IV}), \\
  C_2 &= P_2 \oplus E_k(E_k(\mathit{IV})), \\
  C_3 &= P_3 \oplus E_k(E_k(E_k(\mathit{IV}))), \\
      &\vdots
\end{align*}

What happens if, during transmission, $C_2$ gets replaced by $C'_2 = C_2 \oplus \varepsilon$ for some error pattern $\varepsilon$?  Then we will have $C' = C_1 \mathbin\Vert C'_2 \mathbin\Vert C_3 \mathbin\Vert \cdots$, which, on decryption, gives $P' = P'_1 \mathbin\Vert P'_2 \mathbin\Vert P'_3 \mathbin\Vert \cdots$.  Let's examine how $P'_i$ is related to $P_i$.

The equation for $P'_1$ depends only on $C'_1 = C_1$ and $\mathit{IV}$, so $P'_1 = P_1$ is unaffected, both in CFB mode and in OFB mode.
In CFB mode, $P'_2 = C'_2 \oplus E_k(C_1) = \varepsilon \oplus C_2 \oplus E_k(C_1) = \varepsilon \oplus P_2$.  Likewise, in OFB mode, $P'_2 = C'_2 \oplus E_k(E_k(\mathit{IV})) = \varepsilon \oplus C_2 \oplus E_k(E_k(\mathit{IV})) = \varepsilon \oplus P_2$.  So the same bits flipped in $C'_2$ from $C_2$ get flipped in $P'_2$ from $P_2$.
What about $P'_3$?  Find an equation for $P'_3$ from the relations above in CFB mode and in OFB mode, and see if you can figure out how $P'_3$ is related to $P_3$.
What about $P'_4$?  Does the answer change appreciably from the answer for $P'_3$?


Are post-quantum cryptographic ciphers *also* secure if the P=NP conjecture holds true? First of all, I only understand the P versus NP debate on a rather shallow level as I am not a computer scientist. So perhaps the answer to the question is straightforward but if not, I would be interested to know more.
I believe the consensus amongst computer scientists, complexity theorists, and programmers today is inclined more towards P $\neq$ NP than the equality. Nonetheless, I also find that the Internet is rife with doomsday pictures if

the P = NP conjecture were indeed proven true, or/and
large scale quantum computers (running Shor's algorithm) do become a reality.

To tackle the 2nd problem, the field of post-quantum cryptography has been developing ciphers that are resistant to cryptanalysis by Shor's algorithm and variants. However, I have not been able to find any convincing answer to the question: Do the post-quantum ciphers also address the 1st problem?
As such, I checked the elementary description of a few ciphers, e.g., the McEliece cryptosystem, which is explored under the banner of post-quantum cryptography. Some of them are apparently based on NP-hard problems (such as the shortest vector problem) which mean that these ciphers won't become vulnerable (even in theory) even if the P =NP conjecture holds true. But is that the also case with all current as well as future post-quantum cryptographic mechanisms?

Do the post-quantum ciphers also automag/tically address the 1st problem?

Not really, however to explore that in any detail, we need to explore what the 1st problem is.

If $P=NP$ is proven true, what does that practically mean?  Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems can be trivially broken.

Why is this?  Well, for two reasons: one, if we know $P=NP$ is true, we know that any problem within NP can be solved in polynomial time; it doesn't say we know how it can do it.  If the proof of $P=NP$ doesn't give an algorithm (e.g. the proof shows that $P \ne NP$ leads to a contradiction), the knowledge that there is a polytime algorithm doesn't help us to solve any particular problem.

Secondly, even if we knew a polytime algorithm to solving an arbitrary problem within $NP$, it doesn't say that it runs in any sort of practical time.  If the algorithm runs in $O(N^{1000})$ time, it is infeasible to run against any realistic problem, and hence does not practically impact the security of any cryptographical system at all.

On the other hand, what $P=NP$ might mean is that there is a practical algorithm for solving any reasonably sized problem; by practical, I mean that it is feasible to run the algorithm against a reasonable sized problem.  If this were the case, all but a handful of cryptographical algorithms would be broken.

Here's why: known cryptographical systems are based on one of three security assumptions:

Informational security; the attacker literally does not have enough information to recover the plaintext; an example of this is One Time Pad (OTP)
Quantum security; the laws of physics prohibit the attacker from listening into the message without detectably disturbing in; Quantum Cryptography (QC) is in this category
Computational security; the attacker has all the information he needs; however recovering the plaintext would require more computation than he has; virtually all cryptographical systems are in this category

A practical way to solve an arbitrary $NP$ problem would invalidate everything in the computational security category, as everything in that category can be reduced to a series of $NP$ problems.  Hence, in the absolute worse case scenario, we'd be left with OTP, QC and not much else.

So, in summary, just saying $P=NP$ doesn't give us enough information about what the practical aspects would be.  However, 'post-quantum' algorithms, that is, algorithms that cannot be practically broken, even given access to the algorithms that can be run on a quantum computer, don't bring anything special to the table.

Now, you state that:

  Some of them are apparently based on $NP$-hard problems (such as the shortest vector problem) which means that these ciphers won't become vulnerable (even in theory) even if the $P=NP$ conjecture holds true.

Actually, you misunderstand what $NP$-hard means; it doesn't mean that the problem is harder than an $NP$ problem; what it means is that if you can solve that problem, you can solve any problem in $NP$ (and so it is at least as hard as any $NP$ problem).  However, it doesn't state whether it goes the other way; if you can solve an $NP$-complete problem, you may or may not be able to solve your $NP$-hard problem.  In practice, we often dub a problem as $NP$-hard (and not $NP$-complete) if the problem is not a decision problem (that is, the answer to the problem isn't limited to "Yes" or "No"), and so pedantically not within $NP$ (and hence not within the set of $NP$-complete problems).


Aggregated encryption I have one problem about cryptography which I don't if someone already solved it. I want one device (master) to receive one encrypted package from each one of the other $n$ devices (normal) and I want the master to be able to decrypt each package without being able to identify from which device it came, knowing that the master knows from which device he received the encrypted package.

Is it possible to do this if the encrypted packages were not shuffled betewen the $n$ normal devices, like some kind of group decryption in which the information is preserved but the order is randomized, so that the device of origin is untraceable? Can it be achived without comunication betwen the normal devices?

Also I couldn't find any tags besides encryption that were appropriate to the question, could anyone help me choose another tag?

This is at least feasible if you allow a one-time setup where related keys are distributed among the $n$ devices and the master device. There is a primitive known as aggregated encryption which has the following properties:

The $n$ devices $(D_0, \cdots, D_{n-1})$ each receive a secret key $(s_0, \cdots, s_{n-1})$.
The master device receives an "aggregated secret key"; concretely, this will in general be $s = \sum_i s_i$.
Each device $D_i$ can encrypt some message $m_i$ with the key $s_i$.
Given $n$ encrypted messages $(E_0,\cdots, E_{n-1}) = (E_{s_0}(m_0), \cdots, E_{s_{n-1}}(m_{n-1}))$ and the aggregated secret key $s$, the master device can decrypt $\sum_i s_i$, and cannot learn anything more.

This is relatively easy to build using cryptosystem with appropriate homomorphic properties. The article I link to builds it from the ElGamal cryptosystem, however there also exists constructions from the Paillier cryptosystem, which will be more suited to your problem.

Now, given such a primitive, there is a natural way to ensure that the master device can learn all messages, but without knowing from which device they come: in the one-time setup phase, also give to each device $D_i$ his secret index $j = \pi^{-1}(i)$ ($\pi$ is a uniformly random permutation of $\{0, \cdots, n-1\}$, $\pi^{-1}$ is the reverse permutation, $\pi^{-1}(i)$ will be the "pseudonymous index" of the device $D_i$). Let $\ell$ be a bound on the size (in bit) of each message $m_i$ (I assume $\ell$ to be publicly known) Then, to send $n$ message while concealing the identity of the device each message came from, each device $D_i$ with message $m_i$ computes and sends:

$E_i = E_{s_i}(2^{\ell\cdot\pi^{-1}(i)}\cdot m_i)$

Given $(E_0, \cdots, E_{n-1})$ and his aggregated key $s$, the master device can only recover

$M = \sum_{i=0}^{n-1} 2^{\ell\cdot\pi^{-1}(i)}\cdot m_i = \sum_{j=0}^{n-1} 2^{\ell \cdot j}\cdot m_{\pi(j)}$

Which is exactly the value $m_{\pi(0)} || m_{\pi(1)} || \cdots || m_{\pi(n-1)}$ (when padding each message $m_i$ with zeroes such that it is exactly $\ell$ bit long), id est, all the messages of the devices in some fixed secret permuted order.

Note that an ElGamal-based scheme would not work here since you need your aggregated scheme to support a very large message space, but the Joye-Libert scheme has no restriction on the message space, and should work fine here.


If you have a file and XOR every bit with a random bit, can you extract any information? Say you have a file that is not random, and you XOR every bit with a random bit (not pseudo, but really random). Can someone who sees only the result extract any information from it? Obviously, it won't be 100% accurate, but I imagine you can do some sort of stochastics and get a vague idea. If yes, how? If no, is there a mathematical proof?

This cipher is called a one-time pad. It is unbreakable ("perfect secrecy") assuming that:

The pad (the collection of random bits) really is truly random
The pad is never reused to encrypt other messages

So, no information can be extracted from $\text{file} \oplus \text{random bits}$.

The basic idea of the proof is that an attacker can test every possible key, but they have no way of knowing which plaintext is actually correct. If I encrypt "attack" with a one-time pad, then any six-character string could just as equally have been encrypted in the first place.


What are the practical differences between SCRAM and PAKE (OPAQUE) for simple authentication? As far as I can tell from reading about SCRAM and OPAQUE is that Wikipedia puts both of them in the category of challenge-response authentication.

It's clear to me that SCRAM has an IETF RFC, whereas OPAQUE only has a draft.

However, what are some practical differences between them? For example, are both suitable for use in an SASL mechanism? What do each of them leak to the other party? What are their strengths and weaknesses?

The goal of SCRAM is to determine whether the two endpoints share a common secret. SCRAM achieves this by having both parties compare/exchange $\textrm{HMAC}(s,i)$ where $s$ is the secret and $i$ is a counter/nonce. There is more to it than this, but this is the main essence. If $s$ is a high-entropy cryptographic secret, then this is fine: seeing some HMAC outputs doesn't help an eavesdropper/impostor guess other HMAC outputs.

But if the shared secret is low-entropy like a password, I would say that SCRAM by itself is not suitable. The protocol transcript of a SCRAM interaction gives an eavesdropper enough information to test offline whether their guess for $s$ is correct. So SCRAM is susceptible to offline dictionary attacks. My understanding is that usually SCRAM is run inside of some encrypted tunnel, to protect from external eavesdroppers. But if I am a passive man-in-the-middle of that encrypted tunnel (which seems reasonable since there would be no need for SCRAM if we've already authenticated the endpoints!), I'll learn enough from the SCRAM transcript to allow offline dictionary attack.

SCRAM only does authentication, but OPAQUE is a full-fledged PAKE, which gives much more functionality:

key agreement: the endpoints establish a key in the presence of an eavesdropper, if their secrets match. Note that SCRAM uses a hash function (in HMAC) as its only cryptography. it is well known that secure key agreement is not possible from hash functions alone. This fact justifies why PAKEs are more expensive / use public-key crypto techniques.
designed for low-entropy secrets: a PAKE must resist offline dictionary attacks on the shared secret. The only way that an attacker can test a guess for $s$ is to interactively run the PAKE with one of the parties (online dictionary attack).


Authenticate encrypted seed for KEM + AEAD hybrid cryptosystem Say I want to encrypt something using RSA / KEM and an authenticated cipher. I encrypt using the following scheme:

generate random seed z using n - 1 bits - where n is the size of the modulus N
interpret the seed z as unsigned number and encrypt using the public key e: w = RSA(e, z)
derive a session key and IV using s = KDF(z, "skey") and iv = KDF(z, "iv")
encrypt the plaintext message m' using (c, t) = AEAD(s, iv, ad, m), where t is the authentication tag and ad is (additional) authenticated data
output w | c | t

Would it be advantageous to include the value of w - the encrypted key seed - in the authenticated data ad?

It probably doesn't hurt to include the encapsulation as additional data for the AEAD, but there is no need.  The generic KEM/DEM composition,

\begin{align}
  &(C_0, k) \leftarrow \operatorname{KEM}_{\mathit{pk}}() \\
  &C_1 \leftarrow \operatorname{DEM}_k(M) \\
  &\operatorname{return} C_0\mathbin\|C_1,
\end{align}

provides adequate security by the standard theorems, e.g. Cramer–Shoup 2001, Theorem 5 on p. 41.

You can safely separate the concerns of

generating the encapsulation $C_0$ and the key $k$ with RSA, and
one-time authenticated encryption under $k$,

as separate subroutines that communicate only $k$.

See Shoup's ISO proposal for more practical details of composition and instantiation with less math.

Incidentally, it is also unnecessary to generate an IV, since the key is used only once: you can safely use an IV/nonce of zero for the AEAD as a DEM.


Designing Secure Multi-Party Computation Sub-Protocols Based on Homomorphic Encryption When designing SMPC protocols using secret-sharing, it is a common approach to compose a protocol from several sub-protocols (each proven secure under the formal definition of security w.r.t. semi-honest or malicious adversaries) by applying the sequential composition theorem. These sub-protocols obtain shared input and provide shared output.

When designing SMPC protocols (independent of a specific framework) using a (semantically secure, probabilistic) homomorphic cryptosystem, e.g., Paillier, it is desirable to modularly compose protocols, too. In order to prevent the leakage of intermediate computation results, usually it is necessary to define sub-protocols in such a way that they get (homomorphically) encrypted input and provide (homomorphically) encrypted output. In some of these sub-protocols, ciphertexts $c$ are computed (e.g., the encrypted result of a multiplication of two encrypted integers) which can not be simulated by generating ciphertext $c’$ of the same plaintext (i.e., $\text{Decrypt}(c) = \text{Decrypt}(c’)$) from simulator's input only. Some authors which propose such kind of sub-protocols let the simulator simulate such ciphertext by an arbitrary ciphertext or a random encryption of $0$ (under the corresponding public key) and refer to the semantic security of the underlying cryptosystem in the corresponding security proof when arguing that the simulated view is computationally indistinguishable from the view of a (real) protocol execution.

The question is whether it is correct to simulate such ciphertext by a random ciphertext or a random encryption of $0$? Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bit-length is polynomial in the security parameter), and thus allowing the distinguisher to decrypt? With the ability to decrypt, the distinguisher would be able distinguish between a random ciphertext (or a random encrypted of $0$) in the simulation and a ciphertext of the correct plaintext in the (real) protocol execution.

Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bitlength is polynomial in the security parameter), and thus allowing the distinguisher to decrypt?

This is up to your security model. For example in a protocol that is designed to provide forward secrecy, yes, you would need a method in the proof that allows the adversary to get the private key. After that, they would be able to distinguish between encryptions of 0 and the real encryptions, so something else must be done in the proof to handle this situation. Look around for examples of composability proofs in the forward secrecy model for guidance on how to do this.

If, on the other hand, your security model is not designed to handle key leakage, then you don't really have to handle it in the proof since that is impossible in both the simulation and the "real" protocol execution.


Is full Homomorphic encryption quantum resistant? Since most of our asymmetric encryption algorithms are going to be out-of-date in a couple of year due to Shor's algorithm, I was wondering about the future of FHE schemes.
I have found this paper, which states:

"It is impossible to construct secure group homomorphic encryption in the
quantum world, if the plain-text and cipher-text spaces form abelian groups."

And I'm asking: are there any candidates which are also quantum resistant?

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal lattices, BGV (based on ring-LWE), and this NTRU-based approach.  All three are based on hard problems that are not susceptible to Shor's algorithm.


AES Affine Transformation in $GF(2^4)$ in $GF(2^8)$ the AES affine transformation is defined as
\begin{equation*}
b( x ) = ( x^7 + x^6 + x^2 + x ) + a ( x )( x^7 + x^6 + x^5 + x^4 + 1) mod (x^8 + 1)
\end{equation*}
where the polynom $( x^7 + x^6 + x^2 + x )$ represents the constant term and $( x^7 + x^6 + x^5 + x^4 + 1) mod (x^8 + 1)$ is the matrix, which is multiplied with the inverse a(x). This results in a function
\begin{equation*}
AT(a) = \begin{bmatrix}
       1& 1& 1& 1& 1& 0& 0& 0 \\
       0& 1& 1& 1& 1& 1& 0& 0 \\
       0& 0& 1& 1& 1& 1& 1& 0 \\
       0& 0& 0& 1& 1& 1& 1& 1 \\
       1& 0& 0& 0& 1& 1& 1& 1 \\
       1& 1& 0& 0& 0& 1& 1& 1 \\
       1& 1& 1& 0& 0& 0& 1& 1 \\
       1& 1& 1& 1& 0& 0& 0& 1
      \end{bmatrix}
      \begin{bmatrix}
       a_7\\a_6\\a_5\\a_4\\a_3\\a_2\\a_1\\a_0
      \end{bmatrix}
       \oplus
      \begin{bmatrix}
       0\\1\\1\\0\\0\\0\\1\\1
      \end{bmatrix}
\end{equation*}
where $a_7$ is the most significant bit of the inverse. My Question is now, if I use an isomorphic mapping
\begin{equation*}
\delta = \begin{bmatrix}
  1& 0& 1& 0& 0& 0& 0& 0 \\
  1& 1& 0& 1& 1& 1& 1& 0 \\
  1& 0& 1& 0& 1& 1& 0& 0 \\
  1& 0& 1& 0& 1& 1& 1& 0 \\
  1& 1& 0& 0& 0& 1& 1& 0 \\
  1& 0& 0& 1& 1& 1& 1& 0 \\
  0& 1& 0& 1& 0& 0& 1& 0 \\
  0& 1& 0& 0& 0& 0& 1& 1
      \end{bmatrix}
\end{equation*}
for the input of the AES Subbyte to calculate the inverse in $GF(2^4)$, how would the affine transformation look like or how can I calculate this? After the affine Transformation in $GF(2^4)$ I want to use the inverse isomorphic mapping
\begin{equation*}
\delta^{-1} = \begin{bmatrix}
  1& 1& 1& 0& 0& 0& 1& 0 \\
  0& 1& 0& 0& 0& 1& 0& 0 \\
  0& 1& 1& 0& 0& 0& 1& 0 \\
  0& 1& 1& 1& 0& 1& 1& 0 \\
  0& 0& 1& 1& 1& 1& 1& 0 \\
  1& 0& 0& 1& 1& 1& 1& 0 \\
  0& 0& 1& 1& 0& 0& 0& 0 \\
  0& 1& 1& 1& 0& 1& 0& 1 \\
      \end{bmatrix}
\end{equation*}
to get the result of the S-Box back to $GF(2^8)$.

There are alternative representations of $GF(2^8)$ where the multiplicative inverse can be computed by computing the inverse in $GF(2^4)$, along with a handful of other operations (several $GF(2^4)$ multiplies, additions and a square).  Does your $\delta$ convert from the standard AES representation into such an alternative representation of $GF(2^8)$?

(Background: a representation is how we translate members of the abstract object known as $GF(2^8)$ into bitpatterns.  When we talk about, say, a prime field $GF(p)$, there's one obvious mapping between members of $GF(p)$ into the integers $[0, p)$, and it's hard to think of when another mapping would have any advantage.  However, when we talk about $GF(2^8)$, there are lots of plausible ways; different representations make specific operations cheaper.  The AES representation makes multiplying by the fixed element $2$ fairly cheap, at the expense of not giving an easy way of computing the multiplicative inverse).  Other representations make computing the multiplicative inverse cheaper.

Assuming that is what your $\delta$ is doing, the obvious way to compute the sbox is to do:

$$SBox(x) = AT(\delta^{-1}(Inv(\delta(x))))$$

That is, we translate the value into our alternative represention, compute the inverse in that representation, translate the value back into the standard representation, and then continue with the standard sbox computation.  You can compute the affine transform in the alternative represention; however it'll look like a random multiply by a fixed matrix, and be more expensive than the $AT$ in the standard representation).

If you feel like you have to compute the entire sbox in the alternative representation, then you can separate the affine transform into the linear multiplication $M$ and the constant vector $C$ (so $AT(x) = Mx + C$), and compute the values:

$$M' = \delta \times M \times \delta^{-1}$$

$$C' = \delta C$$

And so the operation $AT'(x) = M'x + C'$ is the affine operation entirely in the alternative representation.  However, as above, multiplying by $M'$ won't likely be as cheap as multiplying by $M$ (whose regular structure allows for a lot of simplification).


Yuval's birthday attack I found this paper:
https://www.researchgate.net/profile/Ganesh-Gupta-7/publication/271704029_What_is_Birthday_attack/links/54cfbdcc0cf24601c0958a1e/What-is-Birthday-attack.pdf
The following attack is outlined on page 9:
Input
-----
Two types of messages - legitimate message 1 ; fraudulent message 2 ; m bit
length; one -way hash function H

Output:
-------
1′, 2′ Is a minor modification of 1, 2 with (1′) = (2′).

1) Generate  = 2^(/2) minor modifications of 1′of 1.
2) Hash each such modified message, and store the hash-values such that they
can be subsequently searched on hash -values. This can be done in () total
time using conventional hashing.
3) Generate minor modifications 2′  2 , computing (2′) for each and checking
for any matches with any 1′ above; continue until a match is found.

I'm confused about step 3.  How would (1′) = (2′)?  I thought the birthday problem meant finding collisions such that (1) = (1′), and (2) = (2′)?

Yuval's attack is slightly different from the standard birthday attack where we look for a repeated output in a single family of inputs. Instead we look for a repeated output across two families of inputs with at least one member of each family producing the repeated ouput. The probabilities are slightly different, but in a complexity sense are both $O(\sqrt H)$ for output ranges of size $H$ (or $O(2^{m/2})$ for $m$-bit output values) where in the worst case outputs are approximately uniformly distributed.
One can see this in an approximate sense as generating $n$-outputs in each family creates $n^2$ pairs of values with one half of each pair coming from each family. Each pair has a $1/H$ chance of matching the two halves. We can approximate the chance of finding a repeat as
$$1-\left(1-\frac1H\right)^{n^2}$$
and for $n\sim\sqrt H$ this will be about $(1-1/e)$. Note however that this is not a rigorous estimate as the probabilities are not independent. More rigorous derivations are possible (see Girault et al., Eurocrypt '88).


For RSA cryptography, how long does it take to factor out P -1024 if given Q - 1024 and N - 2048? So doing a little research on RSA, and knowing the public key contains N. So breaking down the steps to cracking it, I'd have to search for P and Q (which takes a very long time as I understand it), (where P*Q = N). aka, prime 1 and prime 2.

So it takes a long time to find a suitable prime pair. For me I see 2 actions and I want to know which action takes the longer time.

Finding a 1024 prime number.
Having 1 prime number and dividing N by testable prime number to see if it produces another prime, aka prime 2.

So is the time mostly spent finding prime 1 and THEN trying to factor out N, or is the time spent finding a large prime, but its easy to divide N by prime 1 and see it not work?

Sorry if this is confusing, I am having a hard time constructing the question.

You seem to be under the impression that factorizing (finding P and Q) means to try many primes and hope to find the right one, aka the "brute force" solution. This is not the case, it would take forever. Eg. 1024bit means

  179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

possible numbers. Even with the best computers, it would take far longer than the universe exists. And to start with, 1024 is in the past, nowadays 4096 is common.
...point is, there are better (and more complicated) factoring methods, and with quantum computers it gets much better again (sad for cryptographers :/).

Anyways, to answer your direct question: "Neither".
"Finding" a prime number actually means

  Take any number and run some checks if it could be prime. If the check says
  "could be" often enough, then let's say it is a prime.

Why? Because getting hard evidence that a 4096bit number is prime is very slow too.

So, finding a prime means running checks. Checking if the second number (after division) is prime means running the same checks. There is no difference other than the division.


Book recommendation about MPC? I have hard time finding introductory book talking about details of secure multiple party computation. Is there any recommendations? Thanks for the help.

Hope this is not off topic.

The only book I know of regarding Secure Multiparty Computation is Secure Multiparty Computation and Secret Sharing by Ronald Cramer, Ivan Bjerre Damgård and Jesper Buus Nielsen. Yet, I could hardly classify it as introductory.

This is its official site.


Length of password requirement using openssl aes-256-cbc I am using the following OpenSSL command to AES 256 encrypt a file:

openssl aes-256-cbc -salt -in secret-file -out secret-file.aes
  enter aes-256-cbc encryption password:
  Verifying - enter aes-256-cbc encryption password:

As far as I understand, the encryption password should be 32 characters/256 bits, but passing a single character a seems to work just fine.

What is happening behind the scenes here? Can you really pass any length encryption password? What are the trade offs?

When using a utility to encrypt data, you are not directly using the password you enter as the encryption key. Instead, the key is passed through a KDF, or Key Derivation Function, which converts it into the appropriate length. This allows you to use a password smaller or larger than the cipher's key size. In the case of OpenSSL, a single iteration of either MD5 or SHA-256 (depending on version) is used.

A very simple example of a KDF (although not one considered secure for these purposes) would be the SHA-256 function applied directly on the input. Your one-letter password is hashed into a 256-bit value which can then be used directly as the key. The same thing happens if your password is longer.

SHA-256("a") = ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb

Note that the OpenSSL command line utility is not secure, as it is designed for testing the library's functions. It is not to be used for general purpose encryption. The biggest issue is that the KDF it uses is not slow (it uses only one hash iteration, whereas a secure one like PBKDF2 can use tens of thousands or more), which makes brute force and dictionary attacks far more efficient. However, it has other problems such as the lack of integrity. You should use a tool designed specifically for secure encryption, such as GnuPG (which uses a secure KDF called S2K) with its symmetric encryption functionality.


Is it OK to reseed a Deterministic Random Bit Generator from itself? I want a deterministic PRNG for simulation purposes, and I don't want to have to worry about spurious correlations like those the DMCT is designed to protect the Mersenne Twister against.  So even though I don't care about cryptographically secure random numbers, a cryptographically secure Deterministic Random Bit Generator seems like the way to go.

For this purpose, I am thinking of using pycrypto's Crypto.Random.Fortuna.FortunaGenerator.  It only allows $2^{16}$ blocks of pseudorandom data before reseeding because it uses an AES stream in counter mode.  Since I care only about its resemblance to uniform independent draws and not about the entropy which would secure it from cryptographic attack, is there any harm in seeding the generator from its own output?

No, in your situation (where you don't care about security), there isn't any harm in seeding the generator from its own output (or, for that matter, reseeding it by just incrementing the original seed, and resubmitting it).

The chief issue would be if you would fall into a loop (that is, you start repeating outputs); if the seed you generate is 128 bits or more, that is highly improbable for any reasonable number of reseeding.

Now, as you are well aware, a CSRNG is overkill for your purpose; however the question is whether it is cheap overkill.  If the total amount of time your simulation takes is short, or if the bulk of your computation is in things other than generating the random string (and so taking a bit longer in the generation part doesn't significantly slow you down), then it is cheap overkill.


Can the statistical width of the avalanche effect be calculated? This question follows on from my answer to calculation-of-the-avalanche-effect-coefficient earlier.  I have reproduced the graph for this question.

Consider the red line which represents the number of bits changed for a single flipped input bit to SHA-512.  This is for 100,000 random bit flips.  The graph is normal, as expected for a full avalanche effect.  From preparing this graph, I can say that the mean (of course) is 256 bits, which is 512 /2.  As expected. (I actually get 255.5 but that could be my fault).

The standard deviation of this normal curve is approximately 11.3 obtained empirically.  That's for a SHA hash with a block size of 512 bits.

Q.  Is there a calculable mathematical relationship between the standard deviation and the block size, or must it always be determined empirically?

Q. Is there a calculable mathematical relationship between the standard deviation and the block size, or must it always be determined empirically?

This is a well studied problem in probability.

If we consider each output bit as an independent random variable (and if they're not independent, your hash function is broken), each such random variable has a standard deviation of $0.5$ (if $0$ and $1$ have equal probabilities; again, if this is not true, your hash function is broken).  The sum of $N$ such independent samples will have a standard deviation of $0.5 \sqrt{N}$.  In your case, $N=512$; this gives us a standard deviation of $11.3137...$, which is just what you see.


Period, correlation and auto-correlation of non-linear feedback shift registers based sequences Use of Linear Feedback Shift Registers(LFSR) is discouraged due to complexity of order of it's length.

Recently Non-Linear LFSR has been talked about.

I am curious how the properties of LFSR based m-sequence generators hold in this case:

Auto-Correlation- low
Cross-Correlation- Very low
Periodicity $~ 2^n-1$

How NLFSR performs on these metrics? Are they suitable to be used for multiple access systems or say in spreading sequences.

How difficult is it to hack into these systems compared to Berkelamp-Massey algorithm?

The reason such generators are used is to avoid the Berlekamp Massey attack by introducing high linear complexity. However, even though there are many publications on these, the theory is far from complete.

One line of research is finding NLFSRs that generate de Bruijn sequences, this goes back to the 1970s.

For your specific question, there is an almost tailor made solution in terms of autocorrelations. The GMW sequences (Gordon Mills Welch) are nonlinear with high linear complexity and autocorrelation same as m-sequences. They are constructed by using an intermediate field and a power function as a permutation of the intermediate field. So instead of $$s(t)=tr^n_1(\alpha^t)$$ as in m-sequences take $n=km,$ with $k\geq 2$ an integer and consider the sequence
$$s(t)=tr^n_m([tr^m_1(\alpha^t)]^u)$$
which is your basic GMW sequence, provided $gcd(2^n-1,u)=1$ so that the power map is a permutation.

Cross correlations are a bit harder to control, depending on how many sequences you want, but there are some results in the third reference which may make it easier (beyond experimentation).

The Spread Spectrum Handbook covers GMW sequences from an engineering point of view. J-S. No generalized GMW designs, Klapper et al introduced Generalized GMW sequences, etc. The talk slides by Helleseth here are a good point to start in terms of general background.

Some references:

R. A. Scholtz and L. R. Welch, GMW Sequences, IEEE Trans. on Inform. Theory, 30(3):548-553, 1984

H. Fredricksen. A Survey of Full Length Nonlinear Shift Register Cycle Algorithms. SIAM Review, 24(2):195–221, 1982.

Li, Hu and Zeng, A Criterion for Determining the Crosscorrelation of Binary
Sequences from GMW Constructions, IEEE International Workshop on Signal Design and Applications.


Interpretation of certain results of NIST Test Suite I am using NIST Test suite on a PRNG and have a confusion regarding some specific results. Following is the part of the results:

RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES

 C1  C2  C3  C4  C5  C6  C7  C8  C9 C10  P-VALUE  PROPORTION  STATISTICAL TEST
  0   0   0   0   1   2   3   3  15  76  0.000000 *  100/100     BlockFrequency

My question is what is the significance of above result when p-value is 0.0 for Block Frequency Test but proportion is showing 100/100 test sequences passed the test and should I consider this test to be passed of failed? I have checked other questions regarding the NIST Test Suite but they don't answer this specific query.

Randomness is pesky, and can wax and wane between samples.  That's why there is no one specific categorical test that can validate an IID sequence. You need to statistically combine several (perhaps contradictory ones)  together to gain a broader perspective. The P values in columns C1 thru C10 are distributed as:-

Each column is a P value of width 0.1. So what seems to have happened is that all your individual P values  fell 0.4 < P < 0.99, which is the NIST 0.01 significance level. So individually they passed, hence 100/100.

But when you plot this distribution of P values, it looks unlikely. The test suite is designed so that all of the P scores are uniformly distributed 0 - 1 under an is-random null hypothesis.  And when you calculate a probability of these scores occurring randomly (via a Chi test), you get your P = 0.000000 (plus star!).  So you failed the test. Badly :-(

There's more interpretative stuff in §5 of the Special Publication 800-22 document.  I won't say any more regarding your PRNG as there is limited information in this question.


How to show that a function is not a PRP? So I have to answer these questions, but I honestly have no idea what I am doing or where to begin. Can I get some advice on how to tackle these?

Consider a PRP candidate function $f$ on $K = X = \{0, 1\}^n$ which is a permutation on $X$ for every key in $K$, but for all $k, x \in \{0, 1\}^n$, it satisfies $\operatorname{parity}(f_k(x)) = \operatorname{parity}(x)$.

Show that $f$ is not secure as a PRP.
Show that the CBC encryption mode with block cipher $f$ is not indistinguishable.
Show that the CTR encryption mode with block cipher $f$ is not indistinguishable.

To show that a family of functions is not a PRP, you have to either show that the functions are not permutations or that they do not behave pseudo-randomly. As it is already established that the functions are in fact permutation you need to show the latter.

For a family of permutations to be a PRP means that it is computationally infeasible to distinguish a random member of the family (i.e. the function with a randmly chosen key) from a truly random permutation with non-negligible probability.
So what you need to do is present an efficient distinguisher. I.e., describe an algorithm that can in fact decide whether it is given access to a member of the family or to a random permutation.
To do that, you should consider the property that the parity of $f_k(x)$ is always equal to the parity of $x$. So for any fixed $x$ $$\Pr[\operatorname{parity}(f_k(x)) = \operatorname{parity}(x)]=1.$$ Now consider what the same probability is for a truly random permutation $g$.
$$\Pr[\operatorname{parity}(g(x)) = \operatorname{parity}(x)]=??$$


Fooling Proof-of-Storage Protocols. What's the difference with Length-Extension attack? I've searched a bit for this question, but I haven't found anything, so I've decided to post it here.

Lately I've been reading "Serious Cryptography: A Practical Introduction to Modern Encryption" by Aumasson. In chapter 6 he talks about Hash Functions and as examples, of what can go wrong, he explains the "length extension attack" and "fooling proof-of-storage protocols". He explains that, for example BLAKE2 isn't vulnerable to the first attack because it includes a flag that if it's the last block, it does some things different, so the output cannot be used as the entry for next blocks.

Then he explains the proof-of-storage protocols, namely:

The client picks a random value, C, as a challenge.
The server computes Hash(M || C) as a response and sends the result to the client.
The client also computes Hash(M || C) and checks that it matches the value received from the server.

And why it should be Hash(C || M) instead:

  The premise of the paper is that the server shouldn’t be able to fool the client because if the server doesn’t know M, it can’t guess Hash(M || C). But there’s a catch: in reality, Hash will be an iterated hash that processes its input block by block, computing intermediate chaining values between each block. For example, if Hash is SHA-256 and M is 512 bits long (the size of a block in SHA-256), the server can cheat. How? The first time the server receives M, it computes H1 = Compress(H0, M1), the chaining value obtained from SHA-256’s initial value, H0, and from the 512-bit M. It then records H1 in memory and discards M, at which point it no longer stores M.
  Now when the client sends a random value, C, the server computes Compress(H1, C), after adding the padding to C to fill a complete block, and returns the result as Hash(M || C). The client then believes that, because the server returned the correct value of Hash(M || C), it holds the complete message—except that it may not, as you’ve seen.

My first question, maybe a stupid one, is: Why would the server do that? Why "fool" the client?

And the second one, how is that different from a length extension attack? to which BLAKE2 is not vulnerable, but it is for this one?

Thanks a lot! :)

Why would the server try to "fool" the client?

The server could be paid by the client on the basis of terabyte⋅day stored (that's the pricing model of Amazon S3), but only pretending to store, to make easy money.

The goal of a proof-of-storage protocol is to repel crooks from the remote storage business, and reassure the client that the data is safe, without actually restoring backups (which is expensive, at least due to communication costs, and because there might be an access fee beyond that). Also, checking data returned from the server requires the client to have a way to distinguish that the data is genuine, which requires either the genuine data (expensive, and partially negating the benefits of delegating storage), or some precautions taken at a moment when the genuine data was available. Notice that a rogue server could be successful at guessing which segment of the genuine data will be asked as a test, and/or could use sophisticated algorithms to generate plausible missing data from actually available data; and even make checksums in recognized archive formats (gz, zip..) check OK.

More insidious: the server's operator could pretend to keep data on two storage medium in two different locations, but actually use one, and generate fake data in the rare case of a bad block on the sole hard disk with the data. That roughly halves energy, space, and investment costs, thus makes profits skyrocket, and is hard to prove remotely. Regular use of a proof-of-storage protocol will at least catch the most greedy implementations of that fraud (but not those using some RAID5 on a single site).

  How is that different from a length extension attack?

A pure length-extension attacks computes a new hash $H'=\mathcal H(M\mathbin\|C)$ given $H=\mathcal H(M)$ and $C$; while the modified length-extension attack outlined replaces $H$ with a slightly larger amount of information: the internal state of $\mathcal H$ slightly before finalization of the computation leading to $H$. This allows that modified attack to work for any $C$, while for most hashes a pure length-extension attack works only for some very particular $C$ (in the case of SHA-256: starting with a precise string of at least 65 bits uniquely dependent on the length of $M$).

Thus the pure length-extension attack is not enough to foul the would-be proof-of-storage protocol proposed, but a modified length-extension attack is.