How to compute a challenge c using Fiat Shamir? I have a prover and verifier. They are engaged in a zero-knowledge proof protocol. A verifier sends a challenge $c$ to the prover so he can compute a proof using the value $c$. How to use Fiat Shamir so that a prover can compute that challenge $c$ from some public parameters without interacting with the verifier?

The challenge is generated by hashing the public parameteres in order of their usage in the proof generation. Consider a hypothetical ZKP proof generation that takes 7 steps.
$ P \to V: x$ means prover sent $x$ to verifier.
$P \leftarrow V: y$ means verifier sent $y$ to prover.

$P \to V: P_1$
$P \leftarrow V: c_1$
$P \to V: P_2$
$P \leftarrow V: c_2$
$P \to V: P_3$
$P \leftarrow V: c_3$
$P \to V: \text{Proof}$

The prover sends $P_1$ to verifier in step 1 and verifier replies with challenge $c_1$ in step 2. Then the prover sends $P_2$ and verifier sends another challenge $c_2$ and then prover sends $P_3$ and verifier sends another challenge $c_3$. The prover finally sends the proof in step 7. Here $P_1$, $P_2$ and $P_3$ are commitments to some data. The list of exchanged messages between prover and verifier is called the transcript. $[P_1, c_1, P_2, c_2, P_3, c_3, \text{Proof}]$ is transcript of the protocol.
Now if the prover wanted to make it non-interactive, he could generate challenge by hashing the transcript till that moment. Thus challenges are generated as

$c_1 = \operatorname{hash}(\text{any public data}+P_1)$
$c_2 = \operatorname{hash}(\text{any public data}+P_1+P_2)$
$c_3 = \operatorname{hash}(\text{any public data}+P_1+P_2+P_3)$


How to encode bivariate polynomial in Predicate Encryption and Inner Product? From the paper Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products, the vector of the secret key is generated from a polynomial $p(x)$. I understand the univariate polynomial, but what does the vector of a bivariate polynomial look like? For example:

univariate polynomial

$$p(x) = (x - a) \cdot (x - b) = x^2 -(a+b)x + ab$$

Secret vector $p = (1, -(a+b), ab)$
Vector $w$ (with attribute $a$) = $(a^2, a, 1)$ (I am not sure if I understand it correctly)
Inner product: $\left<p,w\right> = a^2 - a^2 - ab + ab = 0$

bivariate polynomial

$$p(x) = (x_1 - a) \cdot (x_2 - b)$$

Secret vector $p = ?$
Vector $w$ with attribute $a = ?$

Many thanks.

In general, to encode a polynomial $p(x) = a_n x^n + a_{n-1} x^{n-1} + ... a_1 x + a_0$, $$\mathbb{p} = (a_n, a_{n-1}, ... a_1, a_0)$$ and $$\mathbb{w} = (x^n, x^{n-1}, ... x, 1)$$

So for your univariate case, $\mathbb{w} = (x^2, x, 1)$. You can see that $\left<\mathbb{p}, \mathbb{w} \right> = p(x)$, and you substitute the attribute as you need. So I think your univariate case is correct.

For the bivariate case, it's the same, but with mixed powers. You'll have terms like $x_1^i x_2^j$, where $i+j \leq n$. So in the general case where $n=2$ with two variables / attributes, you have:

$$ p(x_1, x_2) = a_{20}x_1^2 + a_{11}x_1 x_2 + a_{02} x_2^2 + a_{10}x_1 + a_{01}x_2 + a_{00}$$

In your case, you have:

$$ p(x_1, x_2) = x_1 x_2 - x_1 b - x_2 a + ab$$

So $a_{20} = a_{02} = 0$, $a_{11} = 1$, $a_{10} = -b$, $a_{01} = -a$, and $a_{00} = ab$. Finally,

$$\mathbb{p} = (0,1,0,-b,-a,ab)$$

and

$$\mathbb{w} = (x_1^2, x_1 x_2, x_2^2, x_1, x_2, 1)$$

Again, you can see that $\left<\mathbb{p}, \mathbb{w} \right> = p(x_1, x_2)$.


Is ed25519 a "hash signature" Writing my last question, I saw the hash-signature tag.

I tried to research it best I could, but I'm simply overwhelmed in this field.  I don't think it means to simply hash data before signing, but any detail beyond that is beyond me.

Is ed25519 a hash signature with respect to the tag?  If so, is it believed to be resistant to quantum computers?

Ed25519 or more general the EdDSA (Edwards-curve Digital Signature Algorithm) approach can be considered as a variant of ElGamal signatures (such as Schnorr or DSA). They all are signatures following the hash-then-sign approach. This simply means that you can sign arbitrary length messages by hashing them to a constant size string using a secure cryptographic hash function and then applying the signing algorithm to the hash value. Such as other ElGamal type signature schemes like ECDSA, when implemented using elliptic curve groups, the security relies on the elliptic curve discrete logarithm problem on the respective curve group.

The hash-then-sign approach, however, must not be confused with quantum resistant hash-based signatures such as Merkle signatures, Lamport signatures or the Winternitz one-time signature scheme. Such signatures do not rely on any (number theoretic) computational hardness assumption such as factoring or discrete logarithm assumption and thus are not susceptible to quantum attacks.


Is it possible to narrow down the possible keys used for AES CBC encryption, knowing a given plaintext and its ciphertext, where IV=0? I'm brute forcing a ciphertext with a given dictionary to figure out which key was used. However, it's been hinted at that there is a way to narrow down the dictionary to a smaller subset of possibilities.

I know the plaintext, its ciphertext, and the IV (0). It was encrypted using AES-128-CBC and no salting was used during encryption.

At first I thought I was onto something because of:
$C_j = E_k(P_j \oplus IV)=E_k(P_j)$ for IV = 0. But I was dead in my tracks right after. Is this situation even plausible or am I barking up the wrong tree?

Very simple, attacks on the block cipher mode of operation do not translate to attacks on the block cipher itself. The block cipher is simply a component within the mode of operation after all.

The only time where the block cipher may come under attack is if the key is somehow changed to a related key in the scheme. This is somewhat of an issue for AES-256 if it is used as component for a secure hash algorithm, where the key schedule becomes an issue. That has absolutely nothing to do with CBC mode for a particular key as in your question.

AES, as a block cipher, is supposed to be not vulnerable against known plaintext attacks. As such, the key cannot be found by knowing any information about the plaintext. So you are indeed dead in your tracks.


Hierarchical access control using CP-ABE Is it possible to use CP-ABE to provide a layered (hierarchical) organization?

For example, If I have 100 records, I will encrypt the first 10 records (lowest level) to be decrypted using certain attributes. The next level can for instance decrypt up to 20 records.

Encryption depends on a secret $s$ for the first ten records and a different secret s' for the next 10 records. How could I give the higher level in an organization a key that could decrypt all 20 records?

I am trying to avoid giving people in the higher level the secret of the lower level.

I can discern two cases here:

A strict hierarchy
A partial hierarchy

Using 1, "Hierarchical access control" as a term used with encryption implies that some users have more decryption power than others. Especially in access control modelling, hierarchy is usually "strict". This means that if A > B (A is "higher", and has "more" decryption power than B) then A can decrypt everything B can. If there are items B can decrypt but A cannot, A and B would not be on the same path in the hierarchy tree (i.e. A and B are in this case always comparable).

Using 2, the hierarchy would not be strict: there would be cases where A and B are not comparable, but in most cases it can be stated whether A > B or B < A.

For case 1, CP-ABEs offer a feature called "delegation". In a CP-ABE terms, this is relatively straightforward: if A > B, then the secret (attribute) key set of B will be a subset of that of A. (Remember though, that the mapping of real-life attributes to the scheme access structure may not be straightforward). Thus it should be easy to create a strict hierarchy.

Additionally, monotone CP-ABEs have the property that for an arbitrary scheme-supported set of users it is always possible to construct a hierarchy (possibly by adding virtual users).

However, if you want to use just cryptography to implement a strict access control hierarchy, hierarchical identity-based encryption (HIBE, e.g. https://eprint.iacr.org/2005/015.pdf) would be conceptually simpler, and probably more efficient).

Case 2 does not seem a matter of the cryptographic scheme, but a matter of the actual access control policy. If the policy does not include negative statements, most CP-ABE schemes will be able to support it (per encryption).

A completely another question is, what kind of access control features it is in general possible to enforce by content encryption only (Blu-Ray IPR yes, to some extent, but not for example general workflows).


simulating rc4-256 with rc4-128 OpenSSL supports rc4 with 128-bit keys and rc4 with 40-bit keys. It does not support rc4 with 256-bit keys.

My question is...  is it possible to modify the state of the pseudo-random generation algorithm (PRGA), given a 128-bit key, to match the initial state a PRGA with a 256-bit key?

NO. Without changing the API, it is not possible to coerce a 40-bit-key or 128-bit-key implementation of RC4 to behave like a 256-bit-key one, because there is no way to inject any key material in the RC4 state after initialization.

Dave_Thompson_085 has an interesting comment for OpenSSL specifics.


Prior art: SSH key authn over TLS? I’m developing an application that runs over TLS. In addition to password-based authentication we’d like to be able to use SSH keys.
Is there any prior art in using SSH keys for authentication over TLS? Does anyone know of any potential problems with implementing such a scheme?
Thank you!

UPDATE: After a bit more research, I’ve got a fleshed-out concept:
RFC 5705 key material exports appear to serve the same role as SSH session identifiers. Thus, the following:

C: Grab NN random bytes from TLS’s key export.
C: Sign those bytes using the private key.
C: Send the signature and the key in, say, an HTTP handshake.
S: Verify the signature via the public key, and verify that the key is authorized.

Would this work, be resistant to replay attacks, etc.?

Unlikely.
Although they could use the same set of cryptographic algorithms, SSL/TLS use ASN.1-encoded certificates, and recently raw keys (but still using ASN.1 OID algorithm identifiers), but SSH on the other side use its own application-specific format. So the biggest potential problem with your idea would be interoperability.


Why do general encryption key generators also take the algorithm as input? To my understanding the key generation logic only needs a source of randomness and the length of the key to be generated as input. However, we still provide the algorithm (names) like AES, DES, Blowfish etc. Is it mainly for validation purpose to ensure that the input key size is correct? So, if e.g. the algorithm is AES, the key length has to be 128, 256 or 192?

Or is there more to it, that I'm not aware of?

Is it mainly for validation purpose to ensure that the input key size is correct. So, for e.g. if algorithm is AES, the key length has to be 128, 256 or 192.

Yes, indicating a name to an algorithm may be used to check for valid generation parameters, including the key size that is generally present.

For Java - the principal language assumed in the initial question - it was commonly possible to assign invalid key sizes - at least before the key is generated. In that case the code may unfortunately only fail at a later stage when the key is used. In other words, it is not a given that the implementation adheres to the fail fast design principle. There have certainly be implementation differences between versions with regards to such tests.

It is important to check if the fact that sizes are validated is specified as such in the API. Many API's will however not be clear on that, which means that you will have to test or trust the implementation; it is probably better to check for valid key sizes yourself if they are made configurable.

  Or is there more to it, that I'm not aware of?

You may not want to use a key that was generated for one specific algorithm to be used for another. Nowadays symmetric algorithms will often use fully random keys, but that wasn't always the case. For instance, DES - and by extension triple DES -  will have parity bits that should be set. Those parity bits should not be set for AES keys as they would decrease the amount of possible key values and thus the key strength.

Another reason for indicating the algorithm is for keys to be stored in hardware modules or other key stores. For instance, in a HSM the key is not just stored as a byte array. It also includes the type of the key, so it can only be used by the algorithm it was intended for. For such HSM's it is required to indicate the object type during key generation. This is only an issue for API's that allow for hardware engines / providers (this question was initially Java specific) to be configured.

In principle you could also abuse the algorithm name to indicate other configuration parameters, such as the key store. Generally you would use different generation parameters for that though. Of course you would also want to make sure that other possible generation parameters besides the name / key size are correct for the specific algorithm that you selected - which is another use case for specifying a name up front.


Simple RSA proof of correctness using Bézout's identity To show that $m^{ed} \equiv m \pmod{pq}$ with $de \equiv 1 \pmod{\phi(pq)}$ and $p\neq{q}$,

Choose $e$ coprime to $\phi(pq)$ so that $\gcd(e,\phi(pq)) = 1$ and

$$m^{\gcd(e,\phi(pq))} \equiv m \pmod{pq}$$

Using Bézout's identity we expand the gcd thus

$$m^{\gcd(e,\phi(pq))} = m^{ed + \phi(pq)k} \pmod{pq}$$

where $d$ appears as the multiplicative inverse of $e$ and we expand the exponent

$$m^{ed + \phi(pq)k} = m^{ed} (m^{\phi(pq)})^{k} \pmod{pq}$$

By Fermat's little theorem this is reduced to

$$m^{ed} 1^{k} = m^{ed} \equiv m \pmod{pq}$$

which is the original claim.

Please review this simple proof and help me fix it, if it is not correct.

Update: there is a serious gap in the reasoning after applying Bézout's identity, which concludes that there exists $d$ and $k$ with $ed+\phi(pq)k=1$. The fragment "where $d$ appears as the multiplicative inverse of $e$" attempts to link the $d$ thus exhibited to the $d$ used in RSA. But why would these $d$ share more than their name, especially since the $d$ and $k$ exhibited by Bézout's identity are not unique, and (at least the usual form of) Bézout's identity does not state a relation between these multiple solutions?

We want either a different statement of Bézout's identity, or getting rid of it altogether. That's easy: start from the definition of $d$ in RSA (whatever that is), and prove that a suitable $k$ must exist, using fact 3 below.

It is thought to prove that in RSA, decryption consistently reverses encryption. But hypothesis at time of starting this answer  where insufficient for that, as they did not insure that
$$\;p\ne q\;\text{ or }\;\gcd(m,pq)=1\;$$
This is required in RSA (illustration: try $p=q=5$, $\phi(pq)=20$, $e=3$, $d=7$; encryption of $m=10$ followed by decryption yields $0$ rather than $10$ ).

Now $p\ne q$ is made explicit, satisfying said requirement. But it is not apparent where this is used.

Not coincidentally, the proof still has a serious gap at the point where $1^k$ appears, which implicitly uses that  $m^{\phi(pq)}\equiv1\pmod{pq}$, because:

This proposition is wrong for some $m$, including $m=2q$ .
Fermat's little theorem is invoked as a justification, but an hypothesis in FLT is that the modulus is prime, while $pq$ is not.
FLT makes no mention of $\phi$ , and the definition of $\phi$ is not invoked in the proof.

Useful standard facts (for all variables in $\mathbb Z$ unless otherwise noted):

If $p$ and $q$ are coprime, then $pq$ divides $x$ if and only if both $p$ and $q$ divide $x$ .
If $p$ and $q$ are distinct primes, then $p$ and $q$ are coprime.
The definition of $u\equiv v\pmod w$ is that $w$ divide $v-u$ ; or equivalently that there exists $k$ such that $u+kw=v$.
For $w>0$, the definition of $u=v\bmod w$ used in RSA encryption and decryption is that $u\equiv v\pmod w$ and $0\le u<w$ .
FLT: if $p$ is prime, then $y^p\equiv y\pmod p$ .

That allows deriving the helpful:

if $p$ and $q$ are distinct primes, and both $p-1$ and $q-1$ divide $j-1$, and $j>1$, then $y^j\equiv y\pmod{pq}$ .

Proof hint: use fact 1 with $x=y^j-y$ , and other above facts.

Independently: it is used, but not stated, that the definition of RSA considered uses $d$ such that $ed\equiv1\pmod{\phi(pq)}$ . Another popular definition uses $ed\equiv1\pmod{\lambda(pq)}$ , where $\lambda$ is the Carmichael function. This definition is used in PKCS#1 and FIPS 186-4. It is mathematically satisfying, for it is necessary and sufficient, when $ed\equiv1\pmod{\phi(pq)}$ is merely sufficient.

Also, the proof would be clearer if it was restated:

$p$ and $q$ are primes;
the definition of $d$ used in RSA, and the definition of $\phi$ or $\lambda$ if they appear (in which case those are bound to be used in a correct proof!)
$N=pq$ ;
whatever hypothesis on $m$ (commonly, that is $0\le m<N$, with further restriction to $\gcd(m,N)=1$ if the condition $p\ne q$ is not used);
use of textbook RSA encryption $m\to c=m^e\bmod N$ ;
use of textbook RSA decryption $c\to m'=c^d\bmod N$ (with a distinct notation for the original message and deciphered messages);
what's to be demonstrated (this answer assumes that it is $m'=m$ for all $m$ satisfying the hypothesis made on $m$ ).

Also: there's a missing bit of reasoning, going from $m'\equiv m\pmod N$ to $m'=m$ .

Finally: textbook RSA is not a secure encryption algorithm (assume encryption of the name of someone in the class roll, which will be interrogated tomorrow; one can easily determine from the ciphertext and public key if that's her/him, or even who this is if the class roll is public).


Can Diffie-Hellman generate values in a specified range? Is there any way to generate values only between $0$ and $255$ with the Diffie-Hellman method? I need to create keys for communication algorithms with $32$ and $16$ numbers between that range.

The idea is to exchange the keys between the participants using the results of the Diffie-Hellman key agreement algorithm. Then we create the keys on the clients side, so they can use the keys.

Letting $x$ be any number,
$$3^x \bmod 17 = W$$

$W$ can be any number between $0$ and $17$. I need $W$ to be a number between $0$ and $255$.

The only values we can obtain from Diffie-Hellman are values between $0$ and a prime number.

So, if i want $255$, i can use $251$ or $257$ and work with those. This is what is called the prime modulus. Then we have the generator, that is a primitive square root of the prime modulus. This value only is the primitive square root if after doing all the maths we obtain all the values from $0$ to $251$, if we use the prime modulus of $251$.

This is the way we compute the square primitive root.

  If $p$ is prime, then $b$ is a primitive root for $p$ if the powers of $b$ include all of the residue classes mod $p$.

So, $x$ being any number, $11^x \mod 251$ equals to any number between $0$ and $251$. If we used the $257$ we need to see what if the primitive square root of this value, and substitute the $11$.


Difference between Constructor and Destructor terms I was thinking that in the formal model (or symbolic model?) the destructor terms were used to model processes that could abort generating some errors or something like that. But then, I realized that it doesn't make sense because Processes are different structures, they are not terms.

So, I found this slide that defines destructors and constructors terms on the page eight as follows:

Constructors are used to build terms
Destructors manipulate the terms

But it is still unclear to me. Any function manipulate terms and they may be used to build terms... Thus, are these two sets of terms not disjoint?

Well, could someone explain the difference between these two types of terms and say their right definitions ?

Now I think I know what are constructor terms and destructor terms.

  Constructors are used to build terms

means that there is no correspondent term to represent the application of a constructor to others terms. They are function symbols (like $enc$, to represent encryption) that are applied to other terms resulting in another (like $enc(m, k)$ to represent the encryption of $m$ using key $k$. The term $enc(m, k)$ is not in the list of terms $T$, so, it is a built term).

  Destructors manipulate the terms

as I thought, this sentence is not clear. In fact destructors are applied to other terms just like constructors, but they are interpreted and substituted by other terms. For instance, $dec$ is a destructor term that represents the decryption algorithm and $dec(enc(m, k), k)$ is reduced to the term $m$.

And finally, what I said about destructors in the question was not too wrong... As stated in page 18 of these MPRI notes: "Destructors are used to model the fact that some operations fail."

So, for instance, $dec(enc(m, k_0), k_1)$ fails if $k_0 \not = k_1$, and the process doing the substitution may block or treat the failure.

For instance, assuming $g$ is a destructor, the process

let $x = g(M_1 , ... , M_n )$ in $P$ else $Q$

bounds $x$ to the resulting of $g(M_1 , ... , M_n )$ and then execute $P$, or, execute $Q$ if $g$ fails.


(Im)perfect Secrecy: |K| < |M| I have a basic understanding of perfect secrecy. In the case where |K| == |M|, I see that there is only one key to encrypt a given m to a given c. Therefore each m is equally likely with same probability 1/|K|.

For the case of |K|<|M|, I have some intuition that it is not possible to map a random variable on set x to be a random variable on set y if |x| < |y|. But I'd like a formal proof of this. Or maybe this is the wrong way to look at this problem - I just want to see how we can prove that |K|<|M| result in non perfect secrecy.

This case of |K|<|M| is not a homework question; it is briefly mentioned in Boneh's Cryptography I, but not proved.

This is done in Theorem 2.5 of Boneh and Shoup's under-construction textbook.

In short, suppose $|K| < |M|$. Pick some $k \in K$, $m \in M$, and let $c = E(k, m)$. Now, for all possible keys $k' \in K$, there is a set of plaintexts $\{ D(k', c) : k' \in K \} $. But because $|K| < |M|$, there will be some $m'$ not in this set, such that $\mathbf{Pr}[E(k, m) = c] > 0$ and $\mathbf{Pr}[E(k, m') = c] = 0$. But by definition of perfect security, we should have $\mathbf{Pr}[E(k, m) = c] = \mathbf{Pr}[E(k, m') = c]$ for any $m, m'$.

In other words, there are not enough keys to make every possible ciphertext from a message, or every possible message from a ciphertext. This breaks perfect security.


SHA3-512 troubleshooting - is there a worked example for hashing the "zero-length string"? (I wondered if this question should be asked on StackOverflow instead because it's a programming related issue, but it's bound to the intricacies of SHA3, which I figured was a better fit for Crypto.SE.  If this is unsuitable I'd appreciate it if a moderator could migrate this for me.)

I have faulty home-brew implementation of SHA3-512 that I'm trying to fix.  The output is the right length and changing a single bit in the input message causes an overwhelming change in the output digest (the avalanche effect appears to be working to some extent).  In other words I'm 99% of the way there, but I'm struggling to find the fault in my code.

I've been using the zero-length string "" as the input Message, as it is desirable to keep the message length minimal during debugging.

I've been working strictly to "FIPS PUB 202" as the specification for the algorithm.  (http://dx.doi.org/10.6028/NIST.FIPS.202).

Question

Does anyone know of some document or tutorial that gives a worked example of each step in using SHA3-512 to generate a digest of the message "" (or some other short message), giving detailed step-by-step values for all variables in the algorithm?

Does anyone know of some document or tutorial that gives a worked example of each step in using SHA3-512 to generate a digest of the message "" (or some other short message), giving detailed step-by-step values for all variables in the algorithm?

What you are looking for is called a "test vector" (with intermediate values) and NIST offers them for all their standardised primitives.

The one for SHA3-512 for 0-bit input is this PDF. Because it's 38 pages full of data, I won't post it here but it has the state after intermediate function application for all rounds for an empty message.


Modular Multiplicative Inverse and RSA? In trying to understand this specific part of the RSA algorithm, I found this online:

  $$e \cdot d = 1 \pmod{(p-1)\cdot(q-1)}$$
  Therefore:
  $$e \cdot d \cdot d^{-1}= d^{-1} \cdot 1 \pmod{(p-1)\cdot(q-1)}$$

  Substituing in $d^{\phi((p-1)\cdot(q-1))} \mod{((p-1)\cdot(q-1))}\ $  for $1 \pmod{(p-1)\cdot(q-1)}$, we get:
  $$e\cdot1 = d^{\phi((p-1)\cdot(q-1))-1} \mod{(p-1)\cdot(q-1)}$$

I understand by Euler's theorem, that $d^{\phi(n)}$ = 1 mod $n$

What I don't understand is the substitution part.  Most descriptions I've found online either gloss over this part of RSA or go into Extended Euclidean Algorithm.  But this method seems to be the easiest way of calculating since it ends up just being modular math.

If I substitute, wouldn't that just leave me with...

$$e = d^{-1} \times d^{\phi(n)} = d^{\phi(n)-1}$$

without the mod part.

The multiplicative group $Z_m$ of integers modulo $m$ has exactly $\phi(m)$ elements by definition. Thus for any element $a$ of $Z_m$ the equation
$$
a^{\phi(m)}=1~(mod~m)
$$
holds, where $1$ is the multiplicative identity of $Z_m$ (the residue class $km+1$ of all integers congruent to 1 modulo $m$).

In RSA, $e$ and $d$ are indeed inverses modulo $\phi(\phi(n))$ in the exponent arithmetic, since the order of the multiplicative group $Z_n=Z_{pq}$ is $\phi(n)=\phi(pq)=(p-1)(q-1).$

So the last line of the image is correct and you get
$$
e=d^{\phi(\phi(n))-1}=d^{-1}~(mod~\phi(n))
$$
in the exponent multiplicative group which is what you want, since
$$
M^{ed}~(mod~ n)=M
$$
if and only if
$$
ed~(mod~\phi(n))=1,
$$
if and only if
$$
e=d^{-1}~(mod~\phi(n))
$$
by uniqueness of inverses in any group.


Identifying identical files without reading them completely Imagine the following situation:

there are many "big" files (100Gb+) lying on 2 different remote servers
you have no direct access to these files
you can only read a small amount of each file (e.g. 10Mb) as well as it's general information (e.g. file size)
files can have different names and paths but same content/size
security is no concern - nobody will try to create fake data to force collisions
file contents are solely audio and video files in all kinds of different formats

What's the best way to tell if there are duplicate files between these 2 servers (with a certain confidence) with the data that's available?

Goals:

find file duplicates
the resulting hash has to be the same for the same filesize + contents everytime
create a database of hashes (?) to compare newly added files with already existing for duplication

My naive approach looks like this right now:

feed file size (as byte array) into sha256
read chunk at the beginning of file and feed into sha256
read chunk at middle of file (file size/2) and feed into sha256
read chunk at end of file and feed into sha256
use resulting hash for comparisons

The goal is not to 100% identify/verify those files but being able to tell with the highest possible confidence (provided the restrictions) that file1 on server1 is pretty likely file2 on server2 while providing good collision resistance.

It will never be secure to hash just part of a file. It will always be trivial to generate two distinct files which produce the same hash. (Just look for which parts of the file the lazy hash doesn't touch and modify those sections.)

If you don't need security, then you might be able to come up with some scheme that works most of the time for "natural" (not maliciously crafted) files.

One could hash the first $n$ kilobytes, prefixed with the file size, to generate a PRNG seed. Then you can use the chunk-reading strategy using the RNG to choose random starting positions for each chunk. The chunk size doesn't matter, other than for performance.

Just like how there is no one ultimate file compression algorithm which works for any kind of file, there isn't going to be one universal algorithm for the type of application you describe.

(Any compression algorithm will work well with some file contents and poorly, inflating the file size even, for other files. You get the best results by choosing an algorithm you know will be well suited to the type of data you're trying to compress.)

If you knew your target file formats, then you could design a lazy hash meant to specifically work for that format. For example, you could start reading from a position other than zero if you knew all files shared a common header or that files tended to start with the same boilerplate text.

Actually, store multiple hashes. One of the first 10kb of a file, one of the last 10kb, and one of a random sample of chunks. Check the start and end of the file for differences first so you can bail early by detecting files that contain different beginnings/ends. Fallback on the slower one if they both match. (Or just use one or two partial checksums along with a fallback to a strong hash of the full file, as I assume most software like this does.)

If you're interested in deduplicated file backups, look into Tarsnap.

Files are stored as a sequence of chunk hashes instead of as a sequence of bytes. Chunks values are also stored, but the hashes are used are used as keys in a lookup table to index those chunks. This adds overhead for random data, but allows one to store only one copy of each unique chunk even if it is part of multiple files or appears more than once in the same file.

If you want to use such a system, then just use Tarsnap or something like it. It's a big wheel to reinvent, so you're probably safer using a mature open source project. (I don't use it personally, though. And it's been a long time since I read about it.)


Security issues for integrating AAA and OTP services What are the main security issues for integrating AAA and OTP services. In our organization with about 1000 clients, we want to integrate the services. What are the main security issues about the protocols used? In fact, we must choose between a number of suggested proposals.

Usually OTP needs to send the password in clear text to your AAA server.
As the otp value is concatenated with a static password, the AAA server, which verifies the credentials, need to split the password.

E.g.: Your secret password is "secret" and your OTP generator creates "987432". Then you need to enter "secret987432".

As the client component does not know, how long the OTP value is and how long the fixed password is, the client needs to send the complete string.

It can not send a hash of this, since, the AAA server does not know, if the user entered "secret987432", which is the CURRENT valid OTP value or "secret897832", which would be the next OTP value, which - according to RFC4226 - can also be used for authentication.

So to avoid the stealing of the fixed password during authentication, you need to check if the authentication protocol is properly encrypted.


Validity of authentication scheme? Here's an authentication scheme I had in mind that combines the simplicity of HTTP Digest Authentication and the security of real crypto primitives. I have in mind the user-level authentication, ie login/password, not the TLS level.

I'd like to see if anything can go wrong with such a scheme:

Registration

User chooses password $p$
User generates salt $s$
User generates key material $m=KDF(s, p)$
User generates assymetric authentication keypair, say DSA, using $m$ as the "random" source, where randomness comes from the salt: $priv/pub$
User sends server $s$ and $pub$ as authentication material

Login

Server generates challenge $c$
Server sends challenge $c$ and salt $s$ to client
Client re-generates the private/public keypair with $s$ and $p$ and signs the challenge with the signing key
Client sends the signed challenge, server verifies with $pub$

This scheme has some advantages over other methods of authentication:

Actual password never leaves the client
User doesn't have to generate and keep a certificate, a password is enough
Instead of depending on the password only, the $priv/pub$ keypair also depends on a salt so that 2 users with the same passwords don't accidentally share anything

I guess the most important thing to consider here is whether the salt generation is "random enough" to accommodate even the worst case (everyone has the same password)

Would that scheme be sound to implement ? Are there any flaws that would make it foolish ?

Would that scheme be sound to implement ? Are there any flaws that would make it foolish ?

I believe it's sound.

Note that SRP is a proven authentication protocol that has similar security characteristics. It has more round-trips, though.

  I guess the most important thing to consider here is whether the salt generation is "random enough" to accommodate even the worst case (everyone has the same password)

A 256-bit random number is a good salt. It will never collide with another 256-bit random number anywhere, unless your RNG is broken. But a random salt is not enough.

If an attacker ever sees a signed challenge or gets the public key from the database, they can brute force the password that generates a matching key-pair. Therefore, the KDF should be a strong password based KDF, e.g. PBKDF2 with a high iteration count, or perhaps scrypt.

I used something similar in a (non-public) project. There the salt was generated by the server (because I wasn't sure clients had entropy), so it could even check that it didn't collide with any current salts. I used Ed25519 as the public key system; key generation from a seed is trivial for it.


RSA public key identification Consider a multi party system where public keys of all receivers are known. Server wants to send message to one of them using (textbook?) RSA. Adversary is given ciphertext and even Message to be send, and all $k$ public keys of participants. Can any attack tell who is the target receiver?
Or in nutshell: Given $C$, $M$ and all $k$ public keys, can an attacker tell with significant probability which public key was used to encrypt $M$ giving $C$ ?

Editor's note: The textbook RSA part is per OP's comment. It was originally plaintext RSA. Alternatively, the question makes (more?) sense with some random encryption padding.

Given $C$, $M$ and all $k$ public keys, can an attacker tell with significant probability which public key was used to encrypt $M$ giving $C$ ?

Well, he can eliminate some of the possibilities (which means with $k=2$, he has a decent chance at finding the correct one).
There are two observations he can use:

He can eliminate all public keys $K_i$ for which $C \ge K_i$.  This is pretty obvious, but (if he is lucky) might eliminate some.

For each public key $K_i$, he can compute the Jacobi Symbols $\left( \frac{M}{K_i}{} \right)$ and $\left( \frac{C}{K_i}{} \right)$; if they differ, then he knows that $K_i$ is not the correct key.

This works because we're assuming textbook RSA, and textbook RSA always preserves the Jacobi symbol (which can be efficiently computed).  For an incorrect key, this test will disqualify it with probability circa 0.5, and so about half the incorrect ones will be eliminated.


Do per connection random keys solve the stream cipher key repetition issue? Edits: added then removed additional cases that on reflection seem like a bad idea.  In fact, this whole line of thought seems like a complicated way to get a bigger nonce, which might be better accomplished with something like XSalsa20 which was designed for that.  I will accept the "just use the right tool" answer, but if anyone has anything further to contribute please do.

To prevent possible stream cipher key repetition given unreliable storage, provided only that your RNG works and at the cost of some bytes per connection, start the connection with a random cipher key that is not stored on disk and is used to encrypt the rest of the stream (i.e. as the key for your stream cipher, which might be AES-256-CTR, ChaCha20, or a Keccak based stream cipher).

Questions (assume we have a MAC and any reply will encrypt with that random key and a different, previously agreed, nonce):

Suppose you use a simple shared secret XORed with this random key to encrypt it and have a reliable random number generator.  An attacker can then easily get random key 1 XOR random key 2 and encrypted streams 1 and 2, but it seems like this shouldn't help.  Are there any specific properties that a stream cipher would need to have or not have for this to be exploitable?
If that doesn't work or you don't trust that your RNG doesn't have some characteristic that might be exploitable with that system, add a random nonce sent before the key and use the shared secret to encrypt the random key (via the stream cipher) with that nonce.  Now are there any considerations that would make this system exploitable beyond the need for your RNG to generate a good key each connection?

I'll answer per related question:

It seems like you are trying to describe a scheme that relies on a One Time Pad (OTP). To use an OTP it is required that your scheme complies to the security requirements of a one time pad. If it does, it will be provably secure (except for the leaking of time and length related data).
Now you are trying to create a slow, untested stream cipher out of your OTP scheme, because you do not comply to the OTP requirements. You are better off choosing a well known, fast stream cipher instead.

So choose a fast stream cipher and try and create a good key management scheme around it; you haven't described how you distribute your session keys.


How to calculate AES logarithm table? I would like to know how to find multiplicative inverses in $\mathrm{GF}(2^8)$. I know how to multiply two elements of $\mathrm{GF}(2^8)$ (for example, I know that 0x1b*0xaa equals 0x8c).

I follow this explanation, but I still don't understand the process. More specifically: How exactly (step-by-step) are logarithm and antilogarithm tables for AES' finite field formed?

(Note: I'm using hexadecimal numbers to denote AES field elements and decimal numbers to denote integers.)

First of all, you have to fix a generator of the AES field's multiplicative group. There's quite a lot of them:

0x03 0x05 0x06 0x09 0x0b 0x0e 0x11 0x12 0x13 0x14 0x17 0x18 0x19 0x1a 0x1c 0x1e
0x1f 0x21 0x22 0x23 0x27 0x28 0x2a 0x2c 0x30 0x31 0x3c 0x3e 0x3f 0x41 0x45 0x46
0x47 0x48 0x49 0x4b 0x4c 0x4e 0x4f 0x52 0x54 0x56 0x57 0x58 0x59 0x5a 0x5b 0x5f
0x64 0x65 0x68 0x69 0x6d 0x6e 0x70 0x71 0x76 0x77 0x79 0x7a 0x7b 0x7e 0x81 0x84
0x86 0x87 0x88 0x8a 0x8e 0x8f 0x90 0x93 0x95 0x96 0x98 0x99 0x9b 0x9d 0xa0 0xa4
0xa5 0xa6 0xa7 0xa9 0xaa 0xac 0xad 0xb2 0xb4 0xb7 0xb8 0xb9 0xba 0xbe 0xbf 0xc0
0xc1 0xc4 0xc8 0xc9 0xce 0xcf 0xd0 0xd6 0xd7 0xda 0xdc 0xdd 0xde 0xe2 0xe3 0xe5
0xe6 0xe7 0xe9 0xea 0xeb 0xee 0xf0 0xf1 0xf4 0xf5 0xf6 0xf8 0xfb 0xfd 0xfe 0xff

To build exponentiation and logarithm tables, you have to choose and fix one of the generators. Let's call this element $g$. I will use $g=\mathtt{0x03}$ in this answer, but it doesn't really matter.

Now let's build an exponentiation table, that is, an array that maps an index $i\in\{0,\dots,254\}$ to the element $g^i$.

Initialize an arrayExp[255] of AES field elements indexed by integers.
Set t := 0x01.
For all i ranging from 0 to 254, do

Set Exp[i] := t.
Set t := mul(g, t), where mul denotes multiplication in the AES field.
Set i += 1.

After this procedure, you can easily find $g^i$ using Exp without using a single multiplication: It is just Exp[i % 255]! (The group is cyclic of order $255$, so the modulo operation takes care of is larger than $254$. This is also the reason for the "missing" 256th spot in the table: It is 0x01 again.)

For example, the table for $g=\mathtt{0x03}$ looks like this:

0x01 0x03 0x05 0x0f 0x11 0x33 0x55 0xff 0x1a 0x2e 0x72 0x96 0xa1 0xf8 0x13 0x35
0x5f 0xe1 0x38 0x48 0xd8 0x73 0x95 0xa4 0xf7 0x02 0x06 0x0a 0x1e 0x22 0x66 0xaa
0xe5 0x34 0x5c 0xe4 0x37 0x59 0xeb 0x26 0x6a 0xbe 0xd9 0x70 0x90 0xab 0xe6 0x31
0x53 0xf5 0x04 0x0c 0x14 0x3c 0x44 0xcc 0x4f 0xd1 0x68 0xb8 0xd3 0x6e 0xb2 0xcd
0x4c 0xd4 0x67 0xa9 0xe0 0x3b 0x4d 0xd7 0x62 0xa6 0xf1 0x08 0x18 0x28 0x78 0x88
0x83 0x9e 0xb9 0xd0 0x6b 0xbd 0xdc 0x7f 0x81 0x98 0xb3 0xce 0x49 0xdb 0x76 0x9a
0xb5 0xc4 0x57 0xf9 0x10 0x30 0x50 0xf0 0x0b 0x1d 0x27 0x69 0xbb 0xd6 0x61 0xa3
0xfe 0x19 0x2b 0x7d 0x87 0x92 0xad 0xec 0x2f 0x71 0x93 0xae 0xe9 0x20 0x60 0xa0
0xfb 0x16 0x3a 0x4e 0xd2 0x6d 0xb7 0xc2 0x5d 0xe7 0x32 0x56 0xfa 0x15 0x3f 0x41
0xc3 0x5e 0xe2 0x3d 0x47 0xc9 0x40 0xc0 0x5b 0xed 0x2c 0x74 0x9c 0xbf 0xda 0x75
0x9f 0xba 0xd5 0x64 0xac 0xef 0x2a 0x7e 0x82 0x9d 0xbc 0xdf 0x7a 0x8e 0x89 0x80
0x9b 0xb6 0xc1 0x58 0xe8 0x23 0x65 0xaf 0xea 0x25 0x6f 0xb1 0xc8 0x43 0xc5 0x54
0xfc 0x1f 0x21 0x63 0xa5 0xf4 0x07 0x09 0x1b 0x2d 0x77 0x99 0xb0 0xcb 0x46 0xca
0x45 0xcf 0x4a 0xde 0x79 0x8b 0x86 0x91 0xa8 0xe3 0x3e 0x42 0xc6 0x51 0xf3 0x0e
0x12 0x36 0x5a 0xee 0x29 0x7b 0x8d 0x8c 0x8f 0x8a 0x85 0x94 0xa7 0xf2 0x0d 0x17
0x39 0x4b 0xdd 0x7c 0x84 0x97 0xa2 0xfd 0x1c 0x24 0x6c 0xb4 0xc7 0x52 0xf6

A logarithm table can be easily derived from this:

Initialize an array Log[0x100] of integers indexed by AES field elements.
For all i ranging from 0 to 254, do

Set Log[Exp[i]] := i.

Note that there is no index i such that Exp[i] = 0x00, so the spot for 0x00 in the table is left empty. There is no logarithm of zero (just like over the reals!).

The result looks like this:

---   0  25   1  50   2  26 198  75 199  27 104  51 238 223   3
100   4 224  14  52 141 129 239  76 113   8 200 248 105  28 193
125 194  29 181 249 185  39 106  77 228 166 114 154 201   9 120
101  47 138   5  33  15 225  36  18 240 130  69  53 147 218 142
150 143 219 189  54 208 206 148  19  92 210 241  64  70 131  56
102 221 253  48 191   6 139  98 179  37 226 152  34 136 145  16
126 110  72 195 163 182  30  66  58 107  40  84 250 133  61 186
 43 121  10  21 155 159  94 202  78 212 172 229 243 115 167  87
175  88 168  80 244 234 214 116  79 174 233 213 231 230 173 232
 44 215 117 122 235  22  11 245  89 203  95 176 156 169  81 160
127  12 246 111  23 196  73 236 216  67  31  45 164 118 123 183
204 187  62  90 251  96 177 134  59  82 161 108 170  85  41 157
151 178 135 144  97 190 220 252 188 149 207 205  55  63  91 209
 83  57 132  60  65 162 109  71  20  42 158  93  86 242 211 171
 68  17 146 217  35  32  46 137 180 124 184  38 119 153 227 165
103  74 237 222 197  49 254  24  13  99 140 128 192 247 112   7

Now, the interesting part is how to use these tables to multiply. Take two AES field elements x and y. If either x or y is 0x00, the result is 0x00 (we have to avoid this special case since Log[0x00] is undefined). Otherwise, we can reduce multiplication in the AES field to modular addition over the integers: One can easily show that
$$\mathtt{mul(x, y) == Exp[(Log[x] + Log[y]) \;\%\; 255]}\text!$$

(This is completely analogous to the well-known rule $b^eb^{e'}=b^{e+e'}$ over the reals.)

Similarly, one can obtain inverses:
$$\mathtt{inv(x) == Exp[255 - Log[x]]}\text,$$
since according to the rule for multiplication and since Log is Exp's inverse by definition,

mul(Exp[255 - Log[x]], x) == Exp[(Log[Exp[255 - Log[x]]] + Log[x]) % 255]
                          == Exp[(255 - Log[x] + Log[x]) % 255]
                          == Exp[255 % 255]
                          == Exp[0]
                          == 0x01.

(Again, this is analogous to $\frac1{b^e}=b^{-e}$ over the reals, additionally adding the group's order to obtain a positive exponent.)

So, what have we gained? We replaced multiplication in the AES field, which is quite expensive (involving a loop and conditional branches), by table lookups using only very simple and fast arithmetic.


Right usage of PBKDF2 and login system questions I'm developing the login part of my application and I was asking myself how to do it right. My application stores some users' data server-side that must be inaccessible from us, so all the content must be encrypted using AES-256 with a password derived from the user's login password and this key would never leave the user's device.
What I thought to implement is PBKDF2-SHA512 and use the first 32 bytes of output as the AES key of the user and the last 32 bytes as the hash to login.

My questions are:
How many interactions should I use given that my software will have to work on iPhone and Smartphones in general? (Note that I will force the user to use a password that is 8-char minimum in length, that has at least one uppercase char and a number)
What should I use as salt? I was thinking of using the username (that actually is the user's email address) combined with some string that uniquely identifies my application but... What's the best way to do so?
Is it useful to do it using a combination of crypto algorithm? For example making a little hash function based on AES so an attacker who has the ability to make custom hardware will have to implement more than one algorithm.
How should I save the login hash (the last 32 bytes of PBKDF2-SHA512) in the server's database? I think a simple salted hash (without stretching) would be enough given that the original password is already stretched client-side. If yes, should I use SHA-256 or SHA-512?

EDIT:
PBKDF2-SHA512 means PBKDF2 using HMAC using SHA512 (so it doesn't mean SHA512(PBKDF2).

I can't "generate" any random salt. All that I can do is to "derive" it from the login information. I thought something like HMAC-SHA512(email || password, str) where email || password is the string to be hashed and str is a string that uniquely identifies my application being used as HMAC Key. What do you thing about that? Is there a better way to to it?

Thank you!

You should not SHA512(PBKDF2(password)). Your AES encryption key and the password hash are correlated (which may be a vector of attack in the future). A better solution is:

Generate a secure random string $r_1$ of like 64 characters
Generate another secure random string $r_2$ of like 64 characters
Derive the AES key by PBKDF2($r_1$ || password, 32)
Get a password hash from login by PBKDF2($r_2$ || password, 128)

Due to the two distince random strings used as salts both, the AES key and the password hash are much harder to correlate. You can, if you want to make the derivation of the AES key/password hash harder, use multiple rounds:

Round 0: $x_0$ = password
Round 1: $x_1$ = PBKDF2(r1 || $x_0$)
Round 2: $x_2$ = PBKDF2(r1 || $x_1$) = PBKDF2(r1 || PBKDF2(r1 || password))
...
Round n: x = PBKDF2(r1 || $x_{n-1}$)

PS:

|| means to concatenate two strings
PBKDF2(str, length) means generate a hash of length 32 bytes from the string str


Why the data length is shifted 3-bit in MD4 Java implementation? In RFC 1320, It is stated that "A 64-bit representation of b (the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.)".

I have three Java implementation of MD4, and each of them first shifts the lenght 3-bit to left. I could not understand why? I am sure it is a Java related issue, but I do not know what causes that?

Implementation 1: https://svn.apache.org/repos/asf/mina/mina/branches/2.0/mina-core/src/main/java/org/apache/mina/proxy/utils/MD4.java

Implementation 2: https://llvm.org/svn/llvm-project/llvm-gcc-4.2/trunk/libjava/classpath/gnu/java/security/hash/MD4.java

You can google for more implementations, I could not enter more than 2 links because of my reputation.

Regards,
Bünyamin.

This is not a Java-related issue. All of these implementations are doing what the RFC says. Here are the relevant parts of RFC 1320 (emphasis mine):

  3.1 Step 1. Append Padding Bits

  The message is "padded" (extended) so that its length (in bits) is
     congruent to 448, modulo 512. (…)

  3.2 Step 2. Append Length

A 64-bit representation of b (the length of the message before the
   padding bits were added) is appended to the result of the previous
   step. (…)

The length in §3.2 is again the length of the message in bits. All the Java implementations you've seen calculate the length in bits from the length in bytes. One byte is 8 bits in Java (like on almost every platform, but there are platforms that group bits in bytes of different sizes), so the length in bits is the length in bytes multiplied by 8. Shifting to the left by 3 is equivalent to multiplying by 8.

It is common in cryptographic algorithms to consider the data as a stream of bits, and in particular express lengths in bits. The fact that bits may be arranged in groups of 8 called bytes is an implementation detail that does not influence the behavior of the algorithm.


Do I still need SHA256 if I already had a AES 256 key that is 44 characters long? Several months ago, I was required to research AES and SHA-256 to make a secured license system for my app. However, I was dumb enough that couldn't distinguish between the 256 bits from AES and the actual SHA-256, which resulted in me making a system that generates a 256-bit long key (44 characters long base64 key) for AES-GCM encryption and decryption without the actual SHA-256. Now, it's time for me to update the system that cooperates with an AES system in PHP. But then I found the PHP resources (it's used for research purposes so it can be changed) provided to me has actually used SHA-256 which made both systems totally different. Then my question is, is the 256-bit long key secure enough that I don't actually need the SHA-256 in the PHP system?
P.S.: If I misunderstood anything in the question, I would like to apologize since I am still new to the area of cryptography...
PHP code:
<?php
echo '
';

$hash_string = 'qIANSOwtdfF4y5Yk33ZLE5s6KwKBAeu6qzJRG84Sjjo=';
echo "password : ";
var_dump($hash_string);
echo '
';
$decode_string = base64_decode($hash_string);
$hash = hash('SHA256', $decode_string, true);
echo "hash : ";
var_dump($hash);
echo '
';
$app_cc_aes_key = substr($hash, 0, 32);
$cipher = 'aes-256-gcm';
$iv_len = openssl_cipher_iv_length($cipher);
echo "app_cc_aes_key : ";
var_dump($app_cc_aes_key);
echo '
';
echo "cipher :";
var_dump($cipher);
echo '
';

$data = '7bc9d6ae-982f-11e9-bc42-526af7764f64';
echo "data : {$data}";
echo '
';

$tag_length = 16;
$iv = openssl_random_pseudo_bytes($iv_len);
$tag = "";
$encrypt = openssl_encrypt($data, $cipher, $app_cc_aes_key, OPENSSL_RAW_DATA, $iv, $tag, "", $tag_length);
$encrypt_text = base64_encode($iv.$tag.$encrypt);
echo "encrypt :";
var_dump($encrypt);
echo '
';
echo "encrypt_text :";
var_dump($encrypt_text);
echo '
';

$decoded_text = base64_decode($encrypt_text);
$iv = substr($decoded_text, 0, $iv_len);
$tag = substr($decoded_text, $iv_len, $tag_length);
$ciphertext = substr($decoded_text, $iv_len + $tag_length);
$decrypt_text = openssl_decrypt($ciphertext, $cipher, $app_cc_aes_key, OPENSSL_RAW_DATA, $iv, $tag);
echo "decrypt_text : {$decrypt_text}";
echo '
';
?>

The method to generate AES key in C#:
public string NewKey()
{
    var key = new byte[KEY_BIT_SIZE / 8];
    random.NextBytes(key);
    return Convert.ToBase64String(key);
}

About the license system: It's on Android. When the app first opens, the app will generate a UUID and send it to the server for authorization. Then our staff will authorize manually and send an authorization code back. If there is the code, the app can then automatically license for using our courses which are arranged by our staff.

You don't say how SHA-256 is used in the PHP system, so there's really no way to know how "secure" it is.  At a guess, SHA-256 is being used as a key derivation function (KDF) on the input key material, so whether it provides any additional security will depend on the source of the input key material.  Of course, SHA-256 isn't great as a KDF - one would normally use something like HKDF (e.g. as documented in RFC 5869).

  a system that generates 256-bit long key

How this is generated is going to materially impact how secure your scheme is.

If it is generated by a cryptographically-strong random number generator (CSPRNG), then using a KDF on it is generally considered to be unnecessary.

If it is generated by a Diffie-Hellman key exchange, then it's important to use a KDF on the raw DH output.

If it's generated any other way, your whole scheme is likely to be insecure, whether or not SHA-256 is used.

But this is all based on a guess of how the various algorithms are used.

To get a better answer, you really need to tell us what the requirements are for your licensing system, what the thread model is (note that if this is a mobile app, they are considered to be run in an untrusted environment that an attacker has full control over, and various obfuscation and white-box crypto techniques are normally used too) and the details of the scheme.

  I am still new to the area of cryptography

Cryptography is one of the areas where it's always better to "buy" rather than "build" - don't roll your own.


Help with linear cryptanalysis I am new to linear cryptanalysis, so I decided to try to break a toy cipher that was designed to be vulnerable to linear cryptanalysis. Unfortunately, I can't get it to work no matter how hard I try. I've read the Wikipedia article and several papers, but they always seem vague on how to turn equations that hold over the sbox into ones that hold with high probability over the entire cipher, and I am stuck on that. What am I doing wrong?

First off, the cipher.

# RustleJimmy 2 Block Cipher

sbox = [ ((2 * i + 1) * 0x4d / 2) & 0xFF for i in range(256) ]
sinv = sorted(range(256), key=lambda i: sbox[i])

def T(block):
    # bit transpose of 8 bytes
    x = sum(block[i] << (8 * i) for i in xrange(8))
    t = (x ^ (x >> 7)) & 0x00AA00AA00AA00AAL
    x = x ^ t ^ (t << 7)
    t = (x ^ (x >> 14)) & 0x0000CCCC0000CCCCL
    x = x ^ t ^ (t << 14)
    t = (x ^ (x >> 28)) & 0x00000000F0F0F0F0L
    x = x ^ t ^ (t << 28)
    return [ (x >> (8 * i)) & 0xFF for i in xrange(8) ]

def R(byte, n):
    return (byte >> n) | ((byte & ((1 << n) - 1)) << (8 - n))

def encode(block, key):
    block = [ord(b) for b in block]
    key = [ord(b) for b in key]

    for i in xrange(8):
        block = [ block[j] ^ key[(i + j) & 0x7] for j in xrange(8) ]
        block = [ sbox[block[j]] for j in xrange(8) ]
        block = [ R(block[j], j) for j in xrange(8) ]
        block = T(block)
        block = [ block[j] ^ block[i] if i != j else block[j] for j in xrange(8) ]
    block = [ block[j] ^ key[j] for j in xrange(8) ]

    return ''.join(chr(b) for b in block)

It's a block cipher with a 64bit key that operates on 64 bits. There is no key scheduling; the entire key is used for each round. The sbox is very simple, in fact the three least significant bits are just a linear function of the input. Unfortunately, the linear portion of each round mixes and rotates all the bits so it is not obvious how to take advantage of this.

Here is what I've tried so far.

The sbox is given by $y = 77x + 38 \mod 256$ where x is the input and y is the output. Scaling and rearranging this gives $5y + 2 = 129x + 192$, allowing the equality to be expressed using only xors and 5 nonlinear carry bits. I believe 5 is the minimum possible since the fourth bit is nonlinear and it has to propagate the rest of the way.

Each carry bit can be written using the majority function on three inputs.
$$c_{xyz} = majority(x,y,z) = x \wedge y \oplus x \wedge z \oplus y \wedge z$$

This can also be written as the sum of a linear approximation and an error term.
$$c_{xyz} = x \oplus y \oplus z \oplus 1 \oplus e_{xyz}$$

Where $e_{xyz}$ is 1 with probability $\frac{1}{4}$.

Given these equations, plugging them into the full 8 round cipher and simplifying gives 64 linear equations relating ciphertext to plaintext and key bits. However, since these equations have error terms, they are not guaranteed to hold. Assuming the error terms are independent (they aren't but for simplicity I had to assume that), then the probability of an equation with $n$ error terms holding is $\frac{1}{2} + \frac{1}{2^n}$. Therefore, we need to find equations with very few error terms.

Unfortunately, the equations produced above had 80-140 error terms each. Using the greedy algorithm to find linear equations with fewer errors resulted in a reduced set with 70-123 terms. Unfortunately, this means that the probability advantage is still only $2^{-70}$, meaning it is much slower than brute force. So at this point I am stuck. What am I doing wrong? With such a weak sbox and few rounds, it doesn't seem like it should be this hard to break the cipher.

For this cipher, I suggest finding all possible linear approximations by simply enumerating them.  If $S$ is the S-box, the bias of the linear approximation $\alpha \cdot x = \beta \cdot S(x)$ is given by

$$b(\alpha,\beta) = |2 \Pr[\alpha \cdot x = \beta \cdot S(x)] - 1|.$$

Notice that you can compute $b(\alpha,\beta)$ for a single value of $\alpha,\beta$ with $2^8$ evaluations of the S-box.  Also, there are only $2^{16}$ values of $\alpha,\beta$, so it is easy to enumerate all of them and compute $b(\alpha,\beta)$ for all of them.  This should help you find high-quality approximations for the S-box.

Your next step will be to piece these together into one-round characteristics and then multi-round characteristics.  You can do that by hand, but for your cipher, you might want to look at Matsui's algorithm, which is designed to find the highest-bias linear characteristic for multiple rounds, given the biases for approximations of the S-box.

As a starting point, it may be helpful to be familiar with the notion of active S-box.  A S-box is considered active in a particular linear characteristic if it is being approximated by some linear approximation other
than the trivial approximation $\alpha=\beta=0$.  The linear diffusion layer places some constraints on the set of active S-boxes in round $r+1$ as a function of the set of active S-boxes in round $r$.  Generally speaking, the more active S-boxes, the lower the bias.  (Non-active S-boxes are free: the approximation holds with probability 1 for them, i.e., with bias 1.)

Serge Vaudenay has suggested the following approach for finding high-bias linear approximations: summarize a one-round linear characteristic by a vector $a \in \{0,1\}^8$, where $a_i=1$ if the $i$th S-box is active in that round.  Now we can look at pairs $(a,a')$ where $a$ is the summary for a linear characteristic in one round and $a'$ is the summary for a linear characteristic in the next round.  Not all pairs $(a,a')$ will be feasible, but some will be.  In this way, we can build a graph where the vertices are elements of $\{0,1\}^8$ and there is an edge $a \to a'$ whenever the pair $(a,a')$ is feasible.  Now we can look for a path of length 8 in this graph that minimizes the total Hamming weight of the vertices visited along this path; this will correspond to looking for an 8-round linear characteristic with the smallest possible number of total active S-boxes.  More precisely, it gives us an upper-bound on the bias of any such 8-round linear characteristic; if the number of active S-boxes in the path is small, there might be a good 8-round linear characteristic with high bias; but if the number of active S-boxes is too large, there's no hope for a good 8-round linear characteristic.

We can even push this idea a bit further.  We can annotate each edge $a \to a'$ with the log of the maximum bias of any 2-round approximation where $a$ represents the S-boxes active in the first round of that characteristic and $a'$ the S-boxes active in the second round.  Then, we can look for a path of length 8, where we try to minimize the sum of the labels on the edges in the path.  This corresponds to a all-pairs shortest-paths path problem in a graph with 256 vertices, and can be solved efficiently using the Floyd-Warshall algorithm.

To test whether the edge $a \to a'$ is feasible, here is a technique that might be helpful.  Let $\alpha,\alpha' \in \{0,1\}^{64}$ denote the linear approximation for the first round that we are considering, i.e., $\alpha \cdot x = \alpha' \cdot R_k(x)$ where $R$ is the round function.  Note that $a$ is a deterministic function of $\alpha$; i.e., $a_i=0$ if and only if $\alpha_{8i}=\alpha_{8i+1}=\dots=\alpha_{8i+7}=0$.  Now we can break $R_k$ into three pieces: the key xor, the S-box application, and a linear function, i.e., $R_k(x)=L(S(x\oplus k))$ where $S(\cdot)$ denotes parallel application of 8 S-boxes.  Now both the key xor and the S-box preserve the set of active S-boxes, so we really want to look at the set of feasible linear approximations $\alpha,\alpha'$ for $L$, i.e., $\alpha \cdot x = \alpha' \cdot L(x)$.  Given $a,a'$ it is easy to determine whether there exists $\alpha,\alpha'$ that are consistent with $a,a'$ and such that the approximation $\alpha \cdot x = \alpha' \cdot L(x)$ has non-zero bias.   You can solve this using Gaussian elimination: for each $i$ such that $a_i=0$, add linear constraints $\alpha_{8i}=\alpha_{8i+1}=\dots=\alpha_{8i+7}=0$, and similarly for $a',\alpha'$; now treat the remaining bits of $\alpha,\alpha'$ as unknowns.  Now notice that $\alpha \cdot x = \alpha' \cdot L(x)$ has bias 1 if $\alpha = L(\alpha')$, and bias 0 otherwise.  This gives additional linear constraints on the unknowns.  Now use Gaussian elimination to check whether there exists a non-zero solution to this set of linear equations.

Or, you can look for multi-round characteristics by hand.  That works, too.

I am assuming you have read some basic tutorials on linear cryptanalysis, e.g.,

A Tutorial on Linear and Differential Cryptanalysis.  Howard M. Heys.

You can also read some advanced literature that establishes the theoretical foundations underlying linear cryptanalysis, e.g.,

How far can we go beyond linear cryptanalysis? Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.
Statistical Cryptanalysis of Block Ciphers.  Pascal Junod, PhD thesis, École Polytechnique Fédérale de Lausanne, Switzerland, 2004.

The following paper introduces Matsui's algorithm for finding linear characteristics for DES:

On correlation between the order of S-boxes and the strength of DES.  Mitsuru Matsui.  EUROCRYPT '94.


Using SHA2 as random number generator? I need to generate secure pseudorandom numbers in an embedded system. Instead of having to port some RNG library, could I just use an existing SHA2 function as a random number generator (n-th random number is SHA2(seed + n))?
I'm worried that SHA2 hashes might not be evenly distributed (have bias towards certain sequences of bits).

While SHA2 (SHA-256, SHA-512) original design goals are limited to collision-resistance and (first and second) preimage resistance, it is not known that its computationally distinguishable from a random oracle for messages of fixed length¹. Thus $\text{SHA2}(\text{seed}+n)$ for incremental $n$ is a CSPRNG as far as we know, for a wide-enough random secret seed. If we generate $2^k$ outputs, and $+$ is addition², we need $b+k$ bits of $\text{seed}$ for $b$-bit security.
For added insurance, one could use $\text{HMAC-SHA2}(\text{key}\gets \text{seed},\text{message}\gets n)$, which requires very little extra code. Mihir Bellare's New Proofs for NMAC and HMAC: Security Without Collision-Resistance gives an argument of security³ for weaker assumption on the compression function. Main drawback is that HMAC requires more evaluations of the compression function for each output (four for a simple implementation, possibly down to two with precomputation).
I would use HMAC, with SHA-512 rather than SHA-256 for $b>120$ bit security, or/and truncate the output or XOR its two halves (which can only help security), just to err on the safe side.

Any of the above constructions has the drawback that earlier output can be found at little cost if the state of the generator is recovered.
Beware that an adversary having access to the embedded system could try to extract the random secret seed (using a JTAG port, probing, side-channel attack…), or replace it with a known value (e.g. erase that area of remanent storage).
Also, I emphasize that it is difficult to make a robust incremental $n$ facing adversaries that can cut the power at any time of their choice.
Any of the above three paragraphs might be enough to justify the complications of a TRNG with cryptographic strengthening (CSTRNG).

¹ This restriction is necessary due to the length-extension property.
² Concatenation is more usually noted $\mathbin\|$. In that case, we only need a $b$-bit seed.
³ With security level half the hash width, or the width of $\text{seed}$, whichever is lowest.


HD (Hierarchical Deterministic) Keys using Safe Curves? Bitcoin's HD (Hierarchical Deterministic) Keys as described in BIP32 allow for a master key to be created (a private key and a chain code) such that a tree of both public and private keys can be derived from a master key, each which can have additional keys derived from it. In addition, some of hierarchy can be 'hardened' to prevent further children from being created.

Bitcoin's HD Keys allow for some fairly powerful functionality in Bitcoin and address a number of important use cases, including key storage UX innovations, auditability, etc. There are also related schemes such as 'pay to contract' that use similar cryptographic approaches that HD keys use.

However, Bitcoin's curve (secp256k1) is not considered to be fully 'safe'.

The most popular safe curve 25519 unfortunately requires secret keys to have specific bits to be set and unset, making them incompatible with the linearity that BIP32 and related schemes (pay to contract) require.

Are any of the other 'safe' curves linear and thus allow for HD Key functionality?

Jason Law and Dmitry Khovratovich published a paper on how to do this with the Ed25519 curve.
http://ieeexplore.ieee.org/document/7966967/?reload=true

I don't know for sure if this exact method can be applied to curve 41417 but I bet with further research it probably could.


Construct another ciphertext that decrypts to same message without knowing key in Elgamal I read about ElGamal from various resources and I was wondering if the following is true. Would appreciate if you could elaborate on it so I can understand better:

Is it possible to construct, given an encrypted message $c_1=E(m)$, another encrypted ciphertext $c_2$ that will be decrypted to the same message without knowing the key that was used for the encryption? I mean to create a $D(c_2)=m$ where $c_1 \neq c_2$

I am asking this because ElGamal from what I understand, this cryptosystem is not defined as injective because the results of the encryption depend on some random value.

To elaborate further on my thoughts: I think that ElGamal is not deterministic in the way each message can have several legal encryptions: for each of the $p-1$ of $k$, there would be a different encryption, but of course, the decryption will be reliable and return the same decrypted message: it will return the same $x$ without dependency on chosen $k$. So basically,

$x\bmod p = x\cdot b^k\cdot (b^k)^{-1}$ but $ x\cdot b^k =y_2$ and

$(b^k)^{-1} = (\alpha^{k\cdot a})^{-1}$, and $(y_1^\alpha)^{-1}=(\alpha^{k\cdot a})^{-1}$.

So we get $x \bmod p =(y_2)(y_1^\alpha)$. Basically to encrypt we only need $(p,\alpha,b)$ and to decrypt we need the private key $a$.

I would very much appreciate understanding this.

The key is here the probabilistic Encryption

  Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts

The first probabilistic encryption was proposed by Shafi Goldwasser and Silvio Micali Probabilistic encryption & how to play mental poker keeping secret all partial information in 1982. You randomize the encryption with a random for each message so that even the same messages get different encryptions.

This is why we call encryption can be probabilistic, but the decryption is deterministic. A plaintext can have  different encryptions but all must decrypt to the original plaintext

To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

  I think that ElGamal is not determinstic in the way each message can have several legal encryptions:

Yes, ElGamal is not deterministic. During the encryption, we select a random value for the encryption that makes each encryption different for the same ciphertexts. During the calculation of the shared secret, we select a random $k \in\{1\ldots q-1\}$ and continue with the following parameters; $(G,q,\alpha,b)$ as the public key;

$G$ is the cyclic group
$q$ is the size of $G$
$\alpha$ is the generator of $G$
$b=\alpha^a$ where $a$ is the private key.

Then the encryption performed as following;

select a random $k \in\{1\ldots q-1\}$
compute $s = b^k$ - the shared secret
compute $c_1 = \alpha^k$
compute $c_2 = m\cdot s$

If we encrypt $m$ with the random $k$ than the ciphertext pair is; $$(c_1,c_2)= (\alpha^k, m\cdot s)$$ Encrypting wiht a another random $k' \neq k$ will result in a different ciphertext; $$(c'_1,c'_2)= (\alpha^{k'}, m\cdot s'=b^{k'})$$

  Rerandomization: How to create new encryption of this cyphertext without knowing the plaintext and private key.

To rerandomize a ciphertext, take a new random $k' \in\{1\ldots q-1\}$ and calculate $b^{k'}$ and $\alpha^{k'}$ now mutiply the pair.

$$(c_1 \cdot \alpha^{k'},c_2 \cdot b^{k'}) = (\alpha^k \cdot \alpha^{k'}, m \cdot b^{k} \cdot b^{k'}) = (\alpha^{k+k'}, m \cdot b^{k+k'}) = (c_1'', m \cdot s'')$$

Therefore the new encryption is based on the combined shared secret which is $b^{k+k'}$. Of course, there is a problem that $k+k'$ can exceed the $q-1$, however that is no problem since the little Fermat theorem.

The two ciphertexts are different since $\alpha^{k+k'} \neq \alpha^{k}$.

Decryption:

$s'' = (c_1'')^a$, $c_1'' = \alpha^{k''}$ then $(c_1'')^a = \alpha^{xk''} = \alpha^{k''}$
Compute $s''^{-1}$ by ext-GCD.
Compute  $m=c_{2}\cdot s''^{-1} = m \cdot s'' \cdot s''^{-1} =m$

Therefore the rerandomization works.


requirements for CFB encryption mode In my course there is a remark saying that in CFB encryption mode, the plaintext must not a multiple of the block length.

Why?

CFB mode has no such length restrictions; it can be used to encrypt an arbitrary length plaintext.

Perhaps you misunderstood what was said.


Is the CONF key sharing Problem equivalent to discrete log problem? If there a proof in the literature which says the CONF Problem is equivalent to solving the discrete log ?

Let $g$ be a generator of a cyclic group $\mathbb{G}$ of prime order $q$

CONF problem: given $q,g, g^a, g^{ab}$ find $g^b$

Discrete log problem:  given $q, g, g^x$ find $x$

No.  There's no known proof that CONF is equivalent to the discrete log, in general.  When $q$ is prime, CONF is equivalent to the Diffie-Hellman problem.  And it's a long-standing problem whether the Diffie-Hellman problem is equivalent than the discrete log; see, e.g., Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard?.

Proof of equivalence:

Note that if we can solve the Diffie-Hellman problem, we can solve CONF.  In particular, suppose $DH$ is a Diffie-Hellman oracle (so $DH(g,g^x,g^y)=g^{xy}$).  Then given $g,g^a$, you can compute $g^{a^k}$ for any power $k$: you can add in the exponent using the identity $g^{x+y}=g^x g^y$, and you can multiply in the exponent using the DH-oracle $g^{xy}=DH(g,g^x,g^y)$, so you can do the square-and-multiply algorithm "in the exponent" to compute $g^{a^k}$ from $g^a$.  Now setting $k=q-2$, we see that you can compute $g^{a^{q-2}}=g^{a^{-1}}$.  Finally, $DH(g,g^{a^{-1}},g^{ab}) = g^b$, so with one more application of the DH-oracle, we can compute $g^b$, solving the CONF problem.  Thus, CONF is no harder than the Diffie-Hellman problem.

Also, if we can solve CONF, then we can solve the Diffie-Hellman problem. Suppose $CONF$ is an oracle for the CONF problem, i.e., $CONF(g,g^a,g^{ab})=g^b$.  Then

$$CONF(g^x,g,g^y)= CONF(g^x,(g^x)^{x^{-1}},(g^x)^{x^{-1}y}) = (g^x)^{y} = g^{xy},$$

so an efficient solution to the CONF problem lets us solve the Diffie-Hellman problem.


How can disk encryption systems (like Truecrypt) resist frequency analysis when they allow random access? I don't understand how disk encryption (e.g. TrueCrypt) is supposed to resist frequency analysis.

If blocks can be randomly accessed (which they can), doesn't that mean that frequency-domain information (e.g. contiguous free space) is exposed?

The only safeguard I know against this is chaining, but if they use chaining, then wouldn't a single wrong bit destroy your entire data?

Free space and used space look exactly the same to someone who only sees one version of the ciphertext.

First, the basic idea of a secure block cipher is that you learn nothing about the plaintext block simply by observing the ciphertext block. You may be able to learn something about the plaintext from the surrounding context, such as by collecting more ciphertext blocks, but nothing about the ciphertext block itself yields information about the plaintext block.

Truecrypt uses block ciphers in XTS mode. Popular modern block ciphers are just a deterministic mapping between an input 16 bytes and an output 16 bytes, but XTS mode allows a normal block cipher to work with an additional input "tweak" value that affects the encryption. The tweak input describes the position of that block within the volume, and each one is unique. Since this tweak value affects the final ciphertext, a plaintext $P$ will encrypt differently if it is at position $i$ (and is thus tweaked by value $i$) or position $j$ (and is thus tweaked by value $j$) within the volume. So all unused space on the volume would encrypt to a different ciphertext for every block, even if they are all the same plaintext block value, such as 0. So no pattern of unused space would emerge in the ciphertext since, for all effective purposes, you would be encrypting different plaintext at every single spot. You can perform random access on XTS, as each ciphertext block is stand-alone. (However, for performance reasons, ciphertext is probably always read and decrypted in full sectors. True random access is not very efficient at the block disk level.)

XTS isn't unique in this regard, but it's is the most popular mode of operation in this sort of context right now. Other modes of operation like CBC can also provide similar security. In CBC mode, the plaintext is divided into sectors (usually 512 bytes to 4K in size, about the size of a sector) and each block is encrypted using a unique IV as input that aids the chaining process that you are familiar with. The chaining ensures that each plaintext block is encrypted differently in different contexts, and the uniqueness of the IV starts each chaining sequence uniquely. CBC doesn't have true random access, on reads you must read the previous block of ciphertext in the sector for use in decryption, and on writes you must re-encrypt the entire sector after the modified block. But since the sector sizes are small, it's "close enough" to random access.

(That is all a gross simplification, designed primarily to give an intuitive notion as to how used and unused space is treated.)

Ciphertext corruption is a minimal concern. In XTS mode nothing is chained, so only corrupted blocks become unusable. In chaining modes, generally only one other block becomes corrupted. For example, in CBC any given ciphertext block is only used in at most one other plaintext block encryption, so a damaged ciphertext block only breaks it's own plaintext and the other plaintext block it was chained with. (Stare at the CBC Wikipedia diagram until that makes sense.)

That describes the cryptographic solution, but there is a semi-complimentary ad-hoc solution as well. It takes advantage of a details of the filesystem. All blocks of the plaintext are encrypted, regardless of whether or not the filesystem stores any data in that block, and the filesystem doesn't care about the contents of unused blocks. So if each unused block has random, uncorrelated plaintext in it, then their ciphertexts will be uncorrelated. The attacker wouldn't know if those blocks had legitimate plaintext in them or just random unused data. This method should not be required for security, but it does add a nice buffer layer of security to mitigate a potential weakness in the algorithm or failure in the implementation.

Truecrypt uses that technique too. When you create a volume they give you the option of performing a "full" format in the beginning. This full format writes random data to every single sector of the encrypted volume. As you use the volume the filesystem simply overwrites the random data as it needs to use new sectors and ignores the random data it doesn't need to overwrite.

However, things change when an attacker can take multiple looks at the volume at different points in time. If they can see the volume ciphertext and take a snapshot of it, then later come back and take another snapshot of the ciphertext, they could compare the two and might be able to estimate what changed and what space is used/unused, depending on the activity that had happened on the volume in that period of time. But that becomes highly dependent on what the attacker knows about the structure of the plaintext, how much of it changes, etc, and is not relevant to an attacker who only gets too see the ciphertext at one point in time.


How many points in RSA, such that $m^e = m \bmod n$ For every RSA-cryptosystem, there exist some messages $m$, for which it holds that $m^e \equiv m \pmod n$
As to the question, how many such messages exist, this question has already been asked and answered here: https://math.stackexchange.com/questions/1298664/rsa-fixed-point
However, I do only understand the answer up to a certain point
Suppose that $n$ is only 1 prime. Then it holds that the number of unconcealable messages is $\gcd(e-1, p-1)+1$
This is because in $m^e \equiv m \pmod  p$ , either $m = 0$ or $m \not= 0$. In the latter case $m$ can be expressed as $g^t$, where $g$ is a Generator in $\mathbb{Z_p}$
$g^{t*e} \equiv g^t \pmod p$
$g^{t(e-1) \bmod p -1 } \equiv g^{0 \bmod p -1} \pmod p$
$t(e-1) \equiv 0 \pmod {p-1} $ has exactly $\gcd(e-1, p-1)$  solutions, so the total number of unconcealable messages is, together with $m=0$ , $\gcd(e-1, p-1)+1$
When we now look at real RSA, which has two prime factors in its modulus, it holds that the number of unconcealable messages is $(\gcd(e-1, p-1)+1)\cdot(\gcd(e-1, q-1)+1)$
Why is that so? I suppose it has to do with CRT, but I just cant understand why.

Why is that so?

Well, we have $m^e \equiv m \pmod n$ if and only if both of the following hold:
$$m^e \equiv m \pmod p$$
$$m^e \equiv m \pmod q$$
We know (because of reasoning you accepted) that the number of solutions to the first equation (for $0 \le m < p$) is $\gcd( p-1, e-1) + 1$; we can write out the list as $m_0, m_1, ..., m_{k-1}$ (for $k = \gcd( p-1, e-1) + 1$).
Similarly, we can write out the solutions to the second equation (from $0 \le m' < q$) as $m'_0, m'_1, ..., m'_{k'-1}$ (for $k' = \gcd( q-1, e-1 ) + 1$).
Then, the question comes down; how many ways can we paste $m \equiv m_i \pmod p$ and $m \equiv m'_j \pmod q$ so to satisfy both equations (for $0 \le m < n$).  It turns out (because $p$ and $q$ are relatively prime) that for a specific $m_i, m'_j$ pair, there is a unique value $m$ that satisfies both (and that's the Chinese Remainder Theorem).  Each $m$ which corresponds a solution is formed by such a joining, and so the total number of solutions is the number of $m_i$'s times the number of $m'_j$'s; that is, $(\gcd( p-1, e-1) + 1) \cdot (\gcd( q-1, e-1) + 1)$


Why is 224 bit ecdsa faster than 192 bit ecdsa? I ran several benchmarks using openssl on 2 different computers and I got a surprising result.

for the Nist 192 bit curve the benchmark result is

>openssl speed ecdsap192
                              sign    verify    sign/s verify/s
 192 bit ecdsa (nistp192)   0.0001s   0.0003s  11980.6   3481.6

for the Nist 224 bit curve the benchmark result is

>openssl speed ecdsap224
                              sign    verify    sign/s verify/s
 224 bit ecdsa (nistp224)   0.0001s   0.0001s  13740.5   6948.8

So verifying a nistp224 ecdsa signature is twice faster than with nistp192.

I really expected nistp224 to be slower as it handles bigger numbers.
Why isn't it so?

Both curves have similar form and primes close to powers of two ($2^{192}-2^{64}-1$ and $2^{224} - 2^{96} + 1$), so you wouldn't expect large differences in performance – all things equal, P-224 might be anywhere from 30%  to 60% slower due to the computational scaling of curve operations.
However, in practice different implementations will have different performance and some curves' will be better optimized. In this case it looks like P-192 might only have a 32-bit portable implementation and P-224 an optimized 64-bit one:

Changes between 1.0.0h and 1.0.1  [14 Mar 2012]
[...]  Add optional 64-bit optimized implementations of elliptic curves NIST-P224, NIST-P256, NIST-P521, with constant-time single point multiplication on typical inputs. [...]

(Note: I haven't actually checked if P-192 is unoptimized. You should do it with your version if you are interested.)
As for why they would optimize P-224 better, it is the minimal acceptable size according to e.g. NIST recommendations. Doesn't make much sense to spend time optimizing something that's recommended not to be used.


Using first, say, 50 letters from a public key as user identifier? I am making a messaging system where users are identified by their public keys.  It doesn't matter which friendly username they have, so I'm not going to prompt them to choose one.  Each user will have a directory that will get their messages saved to, so it would be nice if the directory that belongs to them has a short name.  I.e. I can't create a very large directory name by using the entirety of their public keys (might be too long and hit file system limits).
I was considering to use, say, sha3_244(their_public_key) and consider that hash for their home directory names.
But then I thought, how about I take the 1st 50 bytes of their public key, base32 encode it, and use this instead of the sha3_244 checksum?  Should I be worried about collisions?

Should I be worried about collisions?

If these are RSA keys, yes, at least, if people find it in their interest to collide with someone else.
It is entire practical to generate an RSA key where to top 400 bits of the modulus are some specified value.  Since you use those 400 bits as your identifier, then that means the user can pick any identifier they want, for example, the same identifier as another user.
Whether that is a concern depends on whether users would actually gain an advantage.
As for how you would generate a (say 2048 bit) RSA key with the top 400 bits being the value $X$, here's what you do:

Select your 1024 bit prime $p$ as usual

Select a prime $q$ from the range $2^{2048-400}X / p < q < 2^{2048-400}(X+1) / p$; there will be plenty of primes in a range that large.

It's easy to see that $pq$ would be a valid RSA modulus with the top 400 bits being the value $X$.


Timestamping using a hashed linked list and public known events Let's say we have a timestamping scheme of the following characteristics,

The hashes of the documents we are trying to timestamp are XOR'ed with "events" whose time of occurrence are very publicly known (i.e. the hash of the latest block on the blockchain),

$$M_{i}=(H_{D_{i}} \oplus B_{t_{i}})$$

Where,

$M_{i} =$ the hash of the document "mixed" with a known public event,

$H_{D_{i}} =$ hash of document to timestamp,

$B_{t_{i}} =$ hash of the latest block on the blockchain (a very known public event) at the time of timestamping ,

The concatenation of $M_{i}$ and the previous timestamp gets hashed together forming a new node on a hashed linked list,

$$H_{i} = Hash(M_{i} ||H_{i-1})$$

Where,

$H_{i} =$ the timestamp of the document.

Each $H_{i}$ is then published in "real time" into an independent (no relation to the timestamper) public third party platform so that anybody can potentially monitor any modification to the list. An example of this type of platform could be Twitter where each tweet is the concatenation of the current and previous timestamp,

$$T_{i} = H_{i} || H_{i-1}$$

Where,

$T_{i} =$ Public reference of the timestamping (i.e. a tweet).

That being said,

What are your thoughts of the following assertions?

Future-dating a document (even in collusion with the timestamping service) would be not feasibly because of the unpredictable nature of the public event (i.e. it is not feasibly to know what the hash of the next block in the blockchain is going to be unless someone mines it).
Backdating a document, even in collusion with the timestamping service, would not be feasibly because of the nature of the hashed linked list.

Does anybody know if a scheme like this is already described and/or implemented somewhere?
What are your thoughts about the weaknesses of a scheme like this?

Your diagram is not very clear, but XOR is not a good combiner function to use for timestamping, as it may allow backdating in some circumstances.  For instance, see the "time travel" attacks in Section 3.3 of the following paper (e.g., pp.179-180): Cryptanalytic Attacks on Pseudorandom Number Generators.  Depending upon how many inputs you have to the XOR function and the specific details of your scheme (which are not sufficiently clear from your question), generalized birthday attacks may also be possible and might allow backdating.

Instead, you should use hashing.  There are standard constructions for hash-chaining: I suggest you use them.  In particular, if the sequence of documents/data to be hashed is $D_1,D_2,D_3,\dots$, we form a hash chain by the formula

$$H_i = \text{Hash}(H_{i-1} \,||\, \text{Hash}(D_i)).$$

Then we can publish the $H_i$'s as well as each $\text{Hash}(D_i)$.  See a standard reference on hash chaining and timestamping for more details.

Update (after the question was edited):

No, this is definitely not a good idea, because $x \oplus y$ does not uniquely determine $x$ and $y$.

For instance, someone could register $H_{D_i}$ (which gets mixed with $B_{t_i}$), then later claim that they actually registered $H'_{D_i}$ (and it was mixed with $B'_{t_i}$), as long as $H_{D_i} \oplus B_{t_i} = H'_{D_i} \oplus B'_{t_i}$.  How would you detect it?  There's not a fantastic way to do it.

It would be much better to compute $M_i$ as

$$M_i = \text{Hash}(\text{Hash}(D_i), t_i, B_{t_i}).$$

Now $D_i$ and $B_{t_i}$ are uniquely determined, given $M_i$; the collision-resistance of the hash function prevents backdating or lying about how $M_i$ was formed.  This is such a simple fix, and it is so obviously better, that there's not much point analyzing in great detail the exact degree of vulnerability of xor; it's clear that using a hash is better than using a xor, so there's absolutely no reason to use a xor in this context.

So, bottom line: use a hash function, not xor.


Can HMAC confirm data existence? I have two hosts, A and B. Host A gives host B a large piece of data and deletes it. Host A then needs to periodically confirm host B is holding the piece of data.

Before deleting the data Host A precomputes multiple HMACs with a CSPRNG generated random number (a salt). When Host A needs B to confirm the data still exists, it sends a salt to B, B then computes the HMAC returns it to A.

Is this cryptographically sound?

When computing HMAC(number, data) can you use an intermediate values instead of the actual data? Keccak is used if this affects the answer.

EDIT: Cross Referencing question on security stackexchange

An attack in this context would be being able to compute valid responses to salt challenges while in possession of information lesser than the piece of data (message).

Lets assume the salt is either the same size as that of the hash function's block or is padded to that size. In essence, the first iteration of the hash function is solely computed with the salt.

Each time you challenge with a salt you are challenging with new state values of the hash function. Basically a new hash function (different default values).

To be able to attack this you would need to break the one-way property of the hash function. You would need to create associativity rules for the hash function - compute iterations of the hash function on the message in such a way that the result can be applied to an arbitrary initial state.


DES with actual 7 byte key Do we have any library or any mechanism where we can use true 7 byte key for DES instead of 8 byte key. I need it for keys analysis in DES and 8 byte key requirement for associated library is creating problem in getting actual keys analysis.

You need to split up your key into eight 7 bit pieces, and put these 7 bits into a byte each. The parity is in the least significant bit on most platforms, so the 7 bits need to go into the most significant bits. Of course, as the key is probably in bytes, you need to shift and combine the values in the bytes to retrieve the 7 bits.

It's possible the library does not require the parity bits to be set. In that case you don't need to calculate the parity. Otherwise you simply create the parity once you've got the 8 bytes.

Following code is in Java (which makes it a bit awkward because Java bytes are signed and most calculations assume integers).

// --- create 64 bit key from 56 bit key
// least significant bit can have any value
key64[0] = (byte) (key56[0] & 0xFE); // << 0
key64[1] = (byte) ((key56[0] << 7) | ((key56[1] & 0xFF) >>> 1));
key64[2] = (byte) ((key56[1] << 6) | ((key56[2] & 0xFF) >>> 2));
key64[3] = (byte) ((key56[2] << 5) | ((key56[3] & 0xFF) >>> 3));
key64[4] = (byte) ((key56[3] << 4) | ((key56[4] & 0xFF) >>> 4));
key64[5] = (byte) ((key56[4] << 3) | ((key56[5] & 0xFF) >>> 5));
key64[6] = (byte) ((key56[5] << 2) | ((key56[6] & 0xFF) >>> 6));
key64[7] = (byte) (key56[6] << 1);

// --- set parity in time independent of the values within key64
for (int i = 0; i < key64.length; i++) {
    // if even # bits, make uneven, take last bit of count so XOR with 1
    // for uneven # bits, make even, take last bit of count so XOR with 0
    key64[i] ^= Integer.bitCount(key64[i] ^ 1) & 1;
}


Access control versus authorization What is the difference between access control and authorization? They do not mean same as there is a fine line between the two.

Access control is a broader concept that includes authentication, authorisation, accounting and possibly other components contributing to the control of access. Authorisation only concerns granting or denying permissions according to a security model and policies.


Linear Approximation Table of S-Box for SPN I havejust gotten to Linear Cryptanalysis and I'm studying some material on Linear Attack's against SPN.

I see here http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf on page 11

that they calculate the Linear Approximation Table but I am completely lost how they got the values in the table.

Could someone give me an example of how one of those values are calculated? I understand it has something to do with the bias, but I have yet to see any actual example of someone calculating a value in that table which I would like to see.

In Howard Heys' tutorial, the S-box $S$ maps 4 bits to 4 bits. It is defined by the following lookup table:

x    | 0 1 2 3 4 5 6 7 8 9 a b c d e f
S(x) | e 4 d 1 2 f b 8 3 a 6 c 5 9 0 7

This can be split in 4 Boolean component functions, by considering the output bits separately. Here, the subscript 1 refers to the least significant bit:

x      | 0 1 2 3 4 5 6 7 8 9 a b c d e f
S(x)   | e 4 d 1 2 f b 8 3 a 6 c 5 9 0 7
S_1(x) | 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1
S_2(x) | 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1
S_3(x) | 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1
S_4(x) | 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0

The bias of a Boolean function expresses how 'imbalanced' a function is. In other words, how far away it is from a balanced function, i.e. one that is as  often 0 as it is 1. The bias $\mathcal{E}$ of an $n$-bit Boolean function $f$ can be computed using:

$\mathcal{E}(f) = \sum_{x\in\mathbb{F}_2^n} (-1)^{f(x)} = 2^n - 2\mathrm{hw}(f)$.

Here, $\mathrm{hw}$ denotes the Hamming weight of a function, i.e. the number of times a 1 appears. For example, $S_1(x)$ has a bias of 0, but $S_4$ has a bias of 2, as its Hamming weight is 7.

Linear cryptanalysis exploits the most biased linear relation between its input and output. However, it doesn't only consider the full input and the  full output, but sums of specific bits are selected in both the input and the output that have a strong bias. These bits are selected using masks $a,b$. The masks have a 1 for the bits that we want to consider and a 0 otherwise.

For any pair of masks $a,b$, the linear approximation table (LAT) contains the bias of $S_b + \varphi_a$, where $\varphi_a$ maps $x$ to $ax$. (The bias of this value is also often referred to as the Walsh coefficient of $S_b$ at $a$.)

Now for a concrete example: take $a = 12$, or $1100$ in binary, and $b = 1$, or $0001$ in binary. Then $\mathcal{E}(a,b) = \mathcal{E}(\varphi_a + S_b(x)) = \mathcal{E}(x_3 + x_4 + S_1(x))$. Because this is math in $\mathbb{F}_2$, these $+$'s should be read as XORs.

x      | 0 1 2 3 4 5 6 7 8 9 a b c d e f
----------------------------------------
x_3    | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x_4    | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
S_1(x) | 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1
         ------------------------------- +
         0 0 1 1 1 0 0 1 0 1 1 1 1 1 0 1

The bottom row has a Hamming weight of 10, so $\mathcal{E}(a,b) = 2^4 - 2*10 = -4$.

Now if you look at the tutorial on page 11, there is actually the value $-2$ for an input sum of 0xC and an output sum of 1. This might have caused some confusion. Sometimes, all values are already divided by 2. Then it corresponds better to the probability, as the probability is now simply the number in the LAT divided by 16. It is a matter of definition  whether you prefer to have $+16$ in the top left ($a = 0, b = 0$) or $+8$, although I guess the latter is more common.

If you prefer to look at Python code, a very simple script (not mine) that computes the LAT can be found here.

I hope this answers your question.


Comparing DES and DES-X variation: $Enc(m) = DES_{k_1}(m \oplus k_2)$ I came across this question:

Test the security of the following variation of DES-X cryptosystem, which uses 2 keys $k_1$ and $k_2$:
$$Enc(m) = DES_{k_1}(m \oplus k_2)$$

(Basically, it uses the 2nd key to xor the text before the DES encryption)

So, I've started researching it and i got confused.

In general, lots of people suggested that XORing the original text or the ciphertext provides extra security only against brute-force attacks.

However, in this very-similar-question, the first answer states that the extra XOR " has almost no advantage compared to DES (even) in term of resistance to brute force".

Both got me confused because, in this illustration of the simple DES, lots of different keys are generated to XOR blocks of the text several times, so I guess the same is happening twice in the variation above (or 3 times in case of DES-X). As I see it, something like this really messes things up.

Is this really so useless even against brute-force attacks? And if so, can you explain it a bit?

The hint that you have given is simply saying that, if you have more than one (better many) plaintext-ciphertext pairs;

First, apply the n-pad attack to recover the real $k_2$ by;
$$p_1 \oplus p_2 = m_1 \oplus m_2$$
$$p_1 \oplus p_3 = m_1 \oplus m_3,\ldots$$etc. Once you recover one of the $m_i$'s than $$ p_i = k_2 \oplus m_i$$ is enough to extract the $k_2$
Then apply the usual brute-force with $k_2$ is known.

Note: your DES-X is not using key whitening which uses 3 keys, not 2.


How can I decode a substitution cipher in the form of pictures? I'm very new to cryptography (and cryptanalysis), and I'm wondering how to decode a substitution cipher, where all of the letters are replaced with symbols, that is, pictogram cipher?

There is little difference with regards to any attack method that is already available for substitution ciphers. You can do frequency analysis, for instance. If a single symbol is used for the letter e or for space then it should be easy to find.

It's easy to see that there is no fundamental difference: just replace each symbol with a character and you're back to a normal substitution cipher.

If there are symbols that represent sets of characters or if there are more symbols for the same character then the cipher will of course be harder to crack.