Is there a point in storing hash or plaintext in the last column of Rainbow Tables As I read up on rainbow tables, I found that most sources suggest storing a plaintext - the result of Rk(hk) - in the last column, while others just store the hash hk, basically stopping one step earlier.

Is there a point in computing and storing the plaintext, instead of storing the hash? What do we gain from the extra reduction step?

The Rainbow table's average chain length determined during design time. Let cal it $t$.

If we want the table contains $N$ entries we need at least $N/t$ endpoints. To save storage, you want to make $t$ big as much as possible, but up to some point. $t$ determines the search time, $t^2$. You may want to reduce the space if you have a change, that can speed up the table lookup timing.

The storage table is a pair;

| Start Point | End Point |

In password cracking

if you store the hashes as the endpoints then we can immediately search on the endpoints for the given password hash.
if we store after the reduction, as in Wikipedia or Oechslin we need to first apply a reduction to the given hash value, then we can search.

If you are looking for 128-bit size passwords and building the table for SHA256, then for the endpoints, instead of storing the hash you can store the reduced value. In this case, you will gain approximately $\frac{128 N}{t} $ bits with a cost of applying a reduction for every new search. Therefore, if there is a space gain is available it is preferable.

Interestingly, most passwords are weak, instead of building the costly Rainbow table, a hash table that contains only the weak passwords is a better alternative.


What can I do, if my SRP password verifier was stolen? I've got a system that works like this:

Client -> Server: authenticate me

Server -> Client: ok, you are authenticated

Server -> Client: now do some computations for me

And I use SRP as an authentication mechanism. Everything works fine, until somebody steals my password verifier. If the password verifier is stolen, the attacker is able to work as a server, because both server and attacker have the same amount of data for clients authentication.

Client -> Attacker: authenticate me

Attacker-> Client: ok, you are authenticated, because I have verifier

Attacker-> Client: now do some extremely heavy computations, so I can burn your computer

What to do in this situation? Can I invalidate the stolen verifier or something?

I thought I can use this formula to compute verifier: $g^{hash(x|\text{salt}|\text{invalidation date})}$

So server will be forced to send invalidation date first, so client will know if verifier is too old. But this is very hard to implement, because of time synchronization.

And one more option. Client may store server's public key in configuration file as well as sever's host and port. Then client can send server some challenge to encrypt. But I don't know is it good solution or not.

In SRP, if the server-side password verifier leaks, that does not immediately allow login to the server. That "only" exposes the password to brute force search in a dictionary (each password test essentially does what the normal client and server do at login, only at high speed and with speedups because the server's challenge can be fixed). The attack's difficulty depends mostly on the password quality; and on if the password first goes (on the client side) thru some entropy-stretching (PBKDF2 or modern alternative), which unfortunately is not part of SRP (no mention of a slow pre-hash of the password with some standard-defined salt).

Thus if the server database with SRP password verifiers leaks, the passwords are at least as exposed to brute force search as with standard password hashing methods, and typically much more. Short of changing all the passwords, nothing can be done to that.

Said leak however does not compromise confidentiality of sessions encrypted earlier using SRP-negotiated session keys.

Update: I now understand that the question uses SRP password authentication to protect the client from a bogus server when the password verifier is secret. I was told and accept this works.

The adversary with the password verifiers can act exactly as the server (assuming the clients does not otherwise authenticate the server). I do not see a remedy that re-establish server authentication after password verifier loss, short of changing all the passwords, or authenticating the server by a method other than SRP, or changing SRP in a way that requires storage on the client.

SRP is not without virtue; in particular, if it was enforced on the client side (which is rare), and if it came with slow password hash (which is not standard), it would be safer than current practice (establishing a TLS tunnel with server authenticated using a certificate, then sending password in that tunnel); in particular making it impossible that impersonating the server at a single login attempt (by way of a forged certificate or an inattentive user not using https) directly leaks the password to an attacker.


El Gamal Signature: Attack to recover private key if $k$ is generated as $k_{i+1}=k_{i}+a$ where $a$ is a large unknown constant $k_0$ is randomly generated and subsequently $k_{i+1} = k_{i}+a$, where $a$ is a large unknown constant

I've tried formulating an attack as such:

Given 3 Messages $M_0$, $M_1$ $M_2$and  with $(r_0,s_0)$, $(r_1,s_1)$ and $(r_2,s_2)$ respectively. We can write $r_0$, $r_1$ and $r_2$ as such:

$$r_0 = g^{k_0} {\ }mod{\ } p $$
$$r_i = g^{k_i} {\ }mod{\ } p = g^{k_0}g^{a*i} {\ }mod{\ } p = r_0g^{a*i} {\ }mod{\ } p$$

$s_0$, $s_1$ and $s_2$ can then be rewritten as the following:

$$s_0k_0 = M_0-xr_0{\ } mod{\ } p-1$$
$$s_1(k_0+a) = M_1-xr_0g^{a}{\ }mod{\ } p-1$$
$$s_2(k_0+2a) = M_2-xr_0g^{2a}{\ }mod{\ } p-1$$

and making $xr_0$ the subject we get the following:
$$xr_0 = M_0 - s_0k_0$$
$$xr_0 = g^{-a}(M_1 - s_1(k_0+a))$$
$$xr_0 = g^{-2a}(M_2 - s_2(k_0+2a))$$

But I do not think we can solve this using linear equations because we do not know what is $g^{-a}$ and $g^{-2a}$.

Actually, you can recover $g^{-a}$.

You know that $r_i = g^{k_i} \mod p$ and $r_{i+1} = g^{k_i + a} \mod p = r_i \cdot g^a \bmod p$, hence $g^a = r_{i+1} \cdot r_i^{-1} \bmod p$; from there, computing $g^{-a}$ and $g^{-2a}$ is easy.

With that, the linear equations become easy to solve...


How are calculated input S-box? a) if input 1011
= 0 1 1 1
b) if input 0110
=
1 1 0 0
my answer right?

No, your answers are incorrect by my reading of the description. The leftmost bit can't change, since only the other three bits are rotated. That does make for a pretty terrible s-box, but it's an exercise anyway...


Diffie-Hellman Parameter Check: when g = 2, must p ≡ 11 (mod 24)? I'm adding some Diffie-Hellman groups to a program as specified in RFC 3526, More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE).
When I test some of the group parameters per OpenSSL's DH_check, a result is returned that essentially states: 2 is not a suitable generator for Group 5 or the 1536-bit MODP Group.
According to DH_check() claims that RFC 3526 groups have DH_NOT_SUITABLE_GENERATOR, it appears OpenSSL's tests are (from crypto/dh/check.c):

for $g = 2$, $p \bmod 24 = 11$
for $g = 3$, $p \bmod 12 = 5$
for $g = 5$, $p \bmod 10 = 3$ or $7$

The posting then goes on to state 2048, 4096, and 8192 are congruent to 23 modulo 24, not 11. I've confirmed the 2048-bit and 4096-bit MODP groups as well.
I can't find reading on the expected residues (they probably exists, I just have not come across the paper).
Is it acceptable to relax the test such that $p \bmod 24 = 23$ when $g = 2$?

Actually, there is no major difference between $p \equiv 23\  (\bmod\  24)$ vs $p \equiv 11\  (\bmod\  24)$; any minor difference boils down to "do you prefer the DH shared secret to be limited to half the possible values; or do you prefer to leak a bit of the secret exponents?".  OpenSSL prefers to leak one bit; the RFC 3526 designers decided they preferred to limit the possible values.

To explain exactly why this is true, I need to expound on the structure of $Z_p^*$ when $p$ is a strong prime; that is, if $(p-1)/2$ is also prime.

In that case, there are three types of elements:

The trivial elements 1 and p-1; obviously, you wouldn't want to use those as a base for doing DH; we'll skip those as potential bases from here on out.
Quadratic residues; these are elements $x$ for which there exist a $y$ such that $y \cdot y \equiv x\  (\bmod p)$
Quadratic nonresidues; these are elements $x$ for which there is no such $y$ with $y \cdot y \equiv x\  (\bmod p)$

Here's why the distinction is important:

If $g$ is a quadratic nonresidue, then $g$ is also a generator; that is, for every value $h$, there is an $i$ with $g^i \equiv h$.  In contrast, if $g$ is a quadratic residue, then that is not true; $g^i$ will only take on values that are quadratic residues themselves.

What this means is that if use a $g$ which is a quadratic nonresidue as a base for the Diffie-Hellman operation, then any value $[1, p)$ is possible for the shared secret; if you use a quadratic residue, then half the values are possible (those values which are themselves quadratic residues).

If $g$ is a quadratic nonresidue, then given the values $g^x$, it is computationally feasible to determine $x \bmod 2$; that is, the lsbit of $x$.  The attacker can do this by checking whether $g^x$ is a quadratic residue (for example, by checking whether $(g^x)^{(p-1)/2} = 1$; if it is, then $x \equiv 0 \bmod 2$; if it isn't, then $x \equiv 1 \bmod 2$.

In the Diffie-Hellman protocol, each side picks a secret $x$, and transmits $g^x$; if $g$ is a Quadratic nonresidue, then the attacker can use this observation to recontruct one bit of $x$; if $g$ is a Quadratic residue, this observation does not apply.

Now, what does this have to do with $p \bmod 24$?  Well, it turns out that, if $p \equiv 11 \bmod 24$, then $g=2$ will be a Quadratic nonresidue (and hence Diffie-Hellman can generate any shared secret value, but the attacker can learn the lsbit of the secret exponents).  On the other hand, if $p \equiv 23 \bmod 24$, then $g=2$ will be a Quadratic residue (and hence the Diffie-Hellman will be restricted to the Quadratic residue values, but the attacker isn't give any bits of the secret exponent for free).

And, in case you're wondering, if $p$ is a safe prime > 7, then $p \bmod 24$ will be one of those two values.

So, there really isn't all that much difference between the two; however my personal preference is for $p \equiv 23$; while leaking one bit from a perhaps 256 bit secret exponent isn't all that harmful, I don't see the point in leaking anything at all.


Blowfish-448 Secure Key Generation Algorithm I am using blowfish-448, until now the keys have been generated using a crypto random number generator full filling the 448bits vector.
I read about exploit in case of weak keys and reflection keys attack.
Mine concern is if the generation approach we are using is secure or if does exist a more secure way.

I am using blowfish-448, until now the keys have been generated using
  a crypto random number generator full filling the 448bits vector.

This is fine assuming your cryptographic (pseudo-) random number generator is actually good. If this wasn't a valid strategy, this would have produced strong warnings about using Blowfish already.

  I read about exploit in case of weak keys and reflection keys attack.

Yes, there exist weak keys for blowfish, but hitting them when utilizing the full space has negligible probability (also it appears that they don't even break the full blowfish but rather a larger part than with normal keys).

  Mine concern is if the generation approach we are using is secure or
  if does exist a more secure way.

Yes, you really should migrate off Blowfish to AES. It will (most likely) be faster and likely more secure and you won't suffer from small-block attacks like Sweet32.


Is it required to use a random IV for AES-CBC with random key per message? I'm developing a program to encrypt and decrypt a file with AES-256/CBC in Java. And I want it to be safe enough. In my case, I generated random AES key for each file to encrypt and decrypt them.

My question is if it is necessary to generate a random IV for encrypt/decrypt or it is already secure enough with a random AES key and fixed IV.

You can use a null IV for all files ONLY if each file will be encrypted with a unique key. If you want to reuse the key, it's safer use a random IV for each file.

The issue is reusing the IV with the same key, when you do that, you reveal which files have the same first bytes. When you use a different key for each file, you don't have this problem.


RSA: Range of public modulus I know the public modulus is the product of two primes. For key with length L, the public modulus N should be such 2^(L-1) <= N < 2^L.

However this implies that the most significant bit will be always 1. Doesn't this reduce the search space for the primes P and Q by half?

Shouldn't N be between 2^(L-2) and 2^L ?

Doesn't this reduce the search space for the primes P and Q by half?

I can't see how it does.  After all the attacker can see $N$, and so can determine what bits are set.  Allowing, say, a 2047 bit composite (rather than a 2048 bit) doesn't make his job any harder; he can see whether the composite in front of him is either 2047 or 2048 bits long.

What you might mean is that we generally pick the two prime factors to be both precisely $L/2$ bits long; you could try to say that reduces the attackers search space (because, for example, he doesn't have to search for a factor thats, for example, $L/2 - 10$ bits.  However, that line of reasoning doesn't appear to work out; there are far too many primes of length $L/2$ (for any $L$ that we're interested in) for anyone to search through; and the practical factoring algorithms against numbers this size (NFS, ECM) can't take advantage of knowledge of the length of the factors.


What is "Blinding" used for in cryptography? What does "blinding" mean in cryptography, and where do we usually use it? Can you describe a sample implementation?

As @CodesInChaos explains:

It might refer to blind signatures.

It also might refer to a method to harden (typically) RSA implementations against timing/side-channel attacks, by blinding the data before operating on it.
Example: suppose you are writing code to decrypt data, i.e., to compute $y=x^d \bmod n$, given the input $x$.  The naive way to do is just to compute $x^d \bmod n$; but it turns out this can be vulnerable to timing and other side-channel attacks.  One defense is to blind the data before raising the $d$th power.  In more detail, pick a random number $r$; compute $s=r^e \bmod n$; compute $X=xs \bmod n$ and then $Y=X^d \bmod n$ and then $y=Y/r \bmod n$.  You can notice that $Y/r=X^d/r=(xs)^d/r = x^d s^d/r = x^d r/r = x^d \bmod n$, which is what we wanted to compute.  However, this process makes it hard for an attacker to learn anything about $d$ using a timing attack, because the exponentiation process works on a random value $X$ that's not known to the attacker, rather than on the known value $x$.


Concept of hashing a group of data and validating if a value exists within the group When learning about cryptography and hashing, I remember seeing a concept where you could hash a number of values (ID's for example) and then validate against the hash, not storing the original IDs. Upon researching this further, I cannot find any concrete examples.

I am wondering if I misunderstood the concept when originally learning about hashing. Please review the following scenario and let me know if I misunderstood or the concept exists:

Concept

A university is running a contest for students. The university staff chose ten random student IDs as winners. Students can visit a website and enter their student ID to see if they won.

The winning student ID's are not stored in a database but rather are hashed. When a student enters an ID on the website, the ID entered is validated against this "winning hash."

Questions

Is this type of "group of values" hashing and validation a concept that exists or did I misunderstand something in my research?
If this does not exist, would the correct method be to hash each winning student ID, then when a student enters the ID to hash it and validate it against the individual stored hashes?

Thank you!

It sounds like you're describing a Bloom filter.

Note that they're designed to allow false positives (but not false negatives). They can be good to quickly check whether a value might be in a certain set worthy of a more computationally-expensive check. Imagine that you are scanning a large body of text word by word, there is a set of key words you're looking for, and there are more key words than fit in RAM. You can create a bloom filter out of all of the key words that fits in RAM. Whenever you find a word that passes the bloom filter, that means the word might be a key word, so you can then double-check the word against your list of key words on disk. This saves you from having to access the disk for every word you scan.


Can you build a One Way function from a Collision Resistant Function Family? The assumption is you have a Collision Resistant function(CRF) Family F. How do you use F to build a One Way function (OWF).

One Idea I have is to use 2 functions from the CRF Family. Both these functions have n input and n/2 output. You as a user inputs n bits ({0,1}^n) and get an output of n, by using 2 of these functions that output n/2 and concatenate them together to get n output.

This would work in creating a one-way function? or is the idea of a one-way function is that it needs to be able to be inverted, but that it is computationally difficult to do so, while a CRF you can not invert to the original answer?

So in fact, you can build a One-way function from a Collision Resistant Function.

Using a function family of CR functions F, we can create a one way function that works as follows:

pick function F from CRF family, F = ${f_k}$
$g =\ one\ way\ function$
$x_1\ and\ x_2$ picked from random

$g(x_1, x_2) = f_{x_1}(x_2),\ x_1$

The reason this works is because in order to break this one way function you would have to break the fact that $f_{x_1}$ is collision resistant.

Proof:

So let us assume there is an adversary A
that can invert CR function $f_{x_1}(x)\rightarrow y$.

$A(y) \rightarrow x$
What A returns is a pre-image of x so it can be the original x or a collision.
So now lets assume there exists an A' that can use A to break our one way function.
The way he will do so is by first allowing the random inputs of $x_1\ and\ x_2$.
$g(x_1, x_2)= f_{x_1}(x_2),\ x_1 \rightarrow y$

Now A' uses $A(y)\rightarrow x$ The output x is either = $x_1$ or a collision. With this A' has now successfully broken my scheme. But because we know that an adversary A that can find a collision/invert a collision resistant function does not exist in polynomial time we know our scheme is safe and one way because if one can not find a collision in polynomial time then one can not break the one wayness of my function in polynomial time.


Is it possible to use an S-box similar to the one used in DES in AES? How would this work? I'm reviewing some questions given to me by a professor and am stumped on this one. My initial guess is that yes, this is possible, but I do not know how to explain it, specifically for a function $\{0,1\}^8\to \{0,1\}^6$. Any help would be appreciated!

DES is a Feistel cipher that doesn't require the $F$ function to be reversible, where the S-Boxes are used. DES has a non-reversible $F$ function in which the 8 S-boxes $S:\{0,1\}^6\to \{0,1\}^4$ is used.
AES is based on Susbstition Permutation Network (SPN) where everything must be reversible. AES is using S-boxes $S:\{0,1\}^8\to \{0,1\}^8$. Therefore it is not possible to use the DES Sboxes in the AES.
Besides the functionality, even if we could interchange them, that would require to analyze, too.


Generating secure short activation code for offline applications My application is as follows

User has a hardware system (with an unique ID) that does not have
connectivity but has a keypad for input.
To make the hardware operational, the user has to go to central authority and get a code (7-8 digits) in exchange for money
The user enters this code through the keypad and the system is operational for a certain period of time after which the user has to repeat the process.

Requirements

The code has to be short and numeric (7-8 digits)
The code should work for a specific hardware only (unique to each user)
To keep things simple at the beginning, we can assume that every code generated will run the hardware for the same amount of time (as opposed to codes which give the time for which the hardware should run)
Availability of standard libraries to implement this.

Here's what I've done so far

I thought of using the ISO 7064 Mod 97,10 formula to generate codes (in the central authority) and the use the same formula on the hardware to see if it is valid. Based on this post. However, this means the same code is not unique to a hardware system. This is just an error detection algorithm.
I can generate the code using the above formula and use RSA with digital certificate. However, the output will be too long correct? Besides, this means that the central authority has to have access to public keys of all hardware systems.

Let's examine the propositions in the question:

I thought of using the ISO 7064 Mod 97,10 formula
That provides no cryptographic protection against determined adversaries. ISO/IEC 7064 merely

  specifies a set of check character systems capable of protecting strings against errors which occur when people copy or type data.

I can generate the code using the above formula and use RSA with digital certificate. However, the output will be too long correct?
Yes. RSA signatures are at minimum roughly the width of the public modulus, that is for modern security 2048-bit or $2048\log2/\log10\approx617$ decimal characters. That's way too much to key in.
Besides, this means that the central authority has to have access to public keys of all hardware systems.
No. Verification of an RSA signature requires the public key of the authority entitled to produce it. Ignoring the size problem, there would be need for a single public/private key pair, with the private key held by the signing authority, and the same public key in all devices. Devices can recognize their serial number in the signed data.

While there are signature systems more compact than RSA, all yield a signature at least 10 times above the target "7-8 digits". Thus we can't use public-key cryptography.

The standard option there will be symmetric cryptography, with a secret key in each device. Standard practice is that the device key is derived from a master key known by the issuing authority, and the device's serial number, by some key derivation function (the Smart Card industry does this since the 1980s, under the name diversification). A single master key has to be kept, yet extraction of a device's key does not compromise the others. HMAC-SHA-256 would be a suitable derivation method. $\mathsf{DeviceKey}=\operatorname{HMAC}(\mathsf{MasterKey},\mathsf{SerialNumber})$ will do.

The unlock code can be some kind of Message Authentication Code of an index incremented at each reload and held in permanent memory by the device (and the authority's emission system), and truncated. That could be the decimal expression of $\mathsf{UnlockCode}=\operatorname{HMAC}(\mathsf{DeviceKey},\mathsf{Index})\bmod10^8$.

Normal operation is that the authority gets payment, finds $\mathsf{Index}$ for the $\mathsf{SerialNumber}$ in its database, computes $\mathsf{DeviceKey}$ then $\mathsf{UnlockCode}$, increment the $\mathsf{Index}$ for this device in the database. The device checks what's keyed-in against the $\mathsf{UnlockCode}$, and if there's a match activates and increment its $\mathsf{Index}$ in permanent memory.

Some issues need to be addressed:

The $\mathsf{MasterKey}$ and the $\mathsf{DeviceKey}$s are sensitive targets, and that might be vulnerable at the authority and manufacturing site. A HSM or Smart Card might help. In particular, a Smart Card good for a limited number of $\mathsf{UnlockCode}$s could be what clerks at the authority really use.
There should be significant redundancy in $\mathsf{SerialNumber}$ or whatever identifies devices in order to avoid clerical errors at the authority; ISO 7064 might be adequate there.
There is a risk that an attacker tries codes at random to unlock a device, perhaps automatically. A countermeasure is a delay between entries, perhaps increasing after a number of consecutive errors. It is also possible that there are two codes, a short one with a limit of 3 tries (6 digits will be fine), and a long one (say 12 digits) used as backup (similar to the PIN in a mobile phone SIM, with the PUK as backup).
The device should have appropriate mitigation for a variety of threats: unauthorized use with bypass of the payment, $\mathsf{DeviceKey}$ extraction, setting $\mathsf{DeviceKey}$ to a known value, setting $\mathsf{Index}$ to earlier value allowing reuse of an earlier code, resetting the aforementioned delay between entries by battery removal or other upset, side channel.. A classical goof is comparing the code keyed-in to $\mathsf{UnlockCode}$ using strcmp or similar library/language feature that leaks the position of the first mismatch by timing, which might be observable without opening the box, e.g. thanks to a LED or the keyboard scan EMI, allowing to find an 8-digit code in about 40 tries rather than 50 millions. Security engineering is not easy!
Users will loose or temporarily misplace codes, and rather than bother asking for a duplicate, will pay for a new one. The device should thus accept a few codes ahead. And then it's desirable to accept slightly out-of-order codes; that complicates the algorithm, especially for short codes (since all codes in the acceptable window need to be distinct). A simple option if a window of $w$ codes must be accepted is that $\mathsf{UnlockCode}=w(\operatorname{HMAC}(\mathsf{DeviceKey},\mathsf{Index})\bmod\lfloor10^8/w\rfloor)+(\mathsf{Index}\bmod w)$.
More generally it is possible to encode ancillary information within the code (e.g. reload amount). While we are at that, the length of the code can be variable, perhaps larger by one or two extra digits for high-value codes, for higher security.

Note: I do not see that Format Preserving Encryption really helps here, even when there is ancillary information to convey, since confidentiality of that seems to be more of a nuisance than a useful feature.


Is this EdDSA modification secure? I am hoping to employ a signed set membership system which is valid iff each signer's contribution to the set is present.  The system should allow for two or more mutually exclusive signed sets to be merged into a new signed set without requiring new signatures.  Also, unless the set has a single signer, it should be intractable with the signed set alone to discover which elements of the set were signed by which signer.   The following describes the system:

EdDSA signatures are of the form:  $S = (r + H(M,R,A)*a)$ $mod$ $l$.

Consider the modified form: $S = (a + H(M, R)*r)$ $mod$ $l$, where we omit the public signing key A from the hash function and swap the private signing key $a$ with the private session key $r$.

Now, suppose we have two signers, $A_1$ and $A_2$, having signed a set of three elements, $(M_1,R_1)$, $(M_2,R_2)$ and $(M_3,R_3)$.  The signature is then:

$S_{set} = (a_1 + a_2 + H(M_1,R_1)*r_1 + H(M_2,R_2)*r_2 + H(M_3,R_3)*r_3)$ $mod$ $l$

and is verified iff:

$S_{set}*B = A_1 + A_2 +H(M_1,R_1)*R_1 + H(M_2,R_2)*R_2 + H(M_3,R_3)*R_3)$ $mod$ $l$

So, does this system seem to accomplish the stated goals while maintaining the security of the unmodified EdDSA algorithm?

In your signature each signer only seems to add their secret $a$ in once. An attacker who could get someone to sign first $M_1$, then $M_2$ and finally both as a set could find $a = S_1 + S_2 - S_{12}$ $mod$ $l$, i.e. all but a few bits of the secret $a$, the rest being within easy brute force search.

Not sure if that's your only problem.


How to calculate this equation? Can someone please explain to me what are the steps used to get this result (0.9154n+0.8876) from this equation
$$(2n+2){T}_{ecc}^{sm}+(2n){T}_{h}+(2n+2){T}_{ecc}^{pa}+(2n){T}_{ecc}^{sm-s} \approx 0.9154n + 0.8876?$$
where ${T}_{ecc}^{sm}$ =0.442,  ${T}_{h}$= 0.0001,  ${T}_{ecc}^{pa}$= 0.0018, and  ${T}_{ecc}^{sm-s}$= 0.0138
PS: These variables represent the Execution time of cryptographic operations in ms


How to exctract ECDH parameters from an OpenSSL-generated $G$? I'm using ECDH for generating ECDH public parameters (p,a,b,G,n), I try to get this values using openssl ecparam -in cert.pem -text -noout

For Generator $G=(x,y)$ I get :

Generator (uncompressed):
  04:aa:87:ca:22:be:8b:05:37:8e:b1:c7:1e:f3:20:
  ad:74:6e:1d:3b:62:8b:a7:9b:98:59:f7:41:e0:82:
  54:2a:38:55:02:f2:5d:bf:55:29:6c:3a:54:5e:38:
  72:76:0a:b7:36:17:de:4a:96:26:2c:6f:5d:9e:98:
  bf:92:92:dc:29:f8:f4:1d:bd:28:9a:14:7c:e9:da:
  31:13:b5:f0:b8:c0:0a:60:b1:ce:1d:7e:81:9d:7a:
  43:1d:7c:90:ea:0e:5f

My question is, how to extract $x$ (the x-coordinate of the generator $G$) and $y$ (the y-coordinate of the generator $G$) values from this answer.
by the way: when displaying ECDH parameters I get a seed value. Can someone please explain what this value is useful for?


Asymmetric algorithm with indefinite number of public keys So RSA algorithm uses pre-generated set of public and private key, and public key is usually included in private key. So public key stays always the same.

Is it theoretically possible to have some algorithm that has one private key and indefinite number of public keys that can be generated on-demand?

Assume we have goals

Decrypt/verify data signed with single private key by using any of public keys
Encrypt data using any of public keys and decrypt with single private key
Probably also same stuff vice versa (multiple private keys, single public key)

Can any of these goals can be achieved theoretically? PGP and RSA just generates constant set of keys from what I seen just now.

CA is also not an answer to my question because CA equals having single public key of root certificate, not indefinite amount.

Using tricks

As said by Natanael in his comment to your question: this is maybe possible when using elliptic curve cryptography, and is actually kind of used in Bitcoin to have the so-called "hierarchical deterministic wallets". If you want a rough idea of how this kind of child key derivation works, I refer you to this answer.

While it might also be possible to tweak RSA in order to do it, RSA is considered relatively brittle and I'll avoid venturing into modifying it today. (Maybe another day ;))

The same idea as the one used for ECDSA signatures should be easy to transpose to ECIES.
But please, notice that having multiple public keys might not necessarily help you achieve whatever security goals you have, and without knowing these, my answer might be misleading you! So, please think hard about what kind of security guarantees you'd like to have and double check you're actually going to reach them using any derivation scheme one might present you.

Also, notice the caveat: in the child-key derivation discussed in the linked answer, knowledge of $r$ allows one to compute the "main" public key $ P_k$...
And when Alice is sending Bob her encrypted message, if she wants Bob to derive the right private key, she needs to send him $r$ along with her ciphertext.

Using an established scheme

There is actually a scheme which is doing almost what you're asking already, and that's namely ECIES, because when using ECIES, Alice is computing a "shared secret key" from Bob's public key $P = g^x$ by picking a random $y$ and computing $P^y = g^{xy}$, but Alice only needs to send Bob $g^y$ along with the ciphertext encrypted using $g^{xy}$.

Notice that ECIES is just kind of using Diffie-Hellman to agree on a shared secret key to encrypt stuff. But it works.

To address all of your points

You want to:

  Decrypt/verify data signed with single private key by using any of
  public keys

For the "verification" part, this is entirely covered by BIP-32, and it definitively possible and used in practice in Bitcoin and many cryptocurrencies.
For the "decryption" part, it depends really on what you really want to be able to do. You might simply use ECIES, and then you'll be using "fresh keys" only Bob and Alice can recompute to encrypt your data. You might try to do other things...

  Encrypt data using any of public keys and decrypt with single private key

This seems difficult, without having some kind of "hidden key negotiation" à la ECIES, because for most "straight forward" schemes it might mean one would have a mean to decrypt stuff sent to any public key... Which is obviously not the goal.

  Probably also same stuff vice versa (multiple private keys, single public key)

Well, that sounds more like a key sharing. You could achieve this using Shamir's Secret Sharing, for example... But then if you want any of the private key to be able to decrypt the stuff, it means having a polynomial of degree 1, which is equivalent to just sending the main secret key to everybody, so not really a desirable feature.
I'm not aware of clever tricks to achieve this, I'm afraid.


Is Diffie-Hellman mathematically the same as RSA? Is the Diffie-Hellman key exchange the same as RSA?

Diffie Hellman allows key exchange on a observed wire – but so can RSA.

Alice and Bob want to exchange a key – Big brother is watching everything.

Bob makes an fresh RSA key pair and sends his public key to Alice.
Alice makes a random session key and sends it to Bob encrypted with Bob's public key.
Bob decrypts the session key with his private key.

Alice and Bob have exchanged a key despite the fact that anybody can observe
all the traffic. The maths of RSA and Hiffie Hellman are remarkably similar,
both involving modular exponentiation.

They both work because $(A*B)^C \bmod N$ can be done in two steps, i.e. by calculating $X = A^C \bmod N$ on one side of the transaction, and $X^B \bmod N$ on the other – this trick is the basis of both Hiffie Hellman and RSA. Which make me wonder: Are they really the same thing?

Can we algebraically prove that the correctness of RSA implies the correctness
of Diffie-Hellman?

Both RSA and Diffie-Hellman work with modular exponentiation. But they work in a different way:

In RSA, there are two exponentiations which invert each other, i.e. we have $e$ and $d$ such that $(x^e)^d \equiv x$ for all $x$. E.g. if $\square^e$ is the encryption, $\square^d$ is the corresponding decryption. To create this pair of $e$ and $d$ (or derive one from the other), we need the prime factorization of the modulus $m$ (which thus should be private).

In Diffie-Hellman, both the basis $g$ and the modulus $m$ of the exponentiation is fixed. The exponents $x$ and $y$ are randomly chosen private keys, and we use the fact that $(g^x)^y \equiv g^{x\cdot y} \equiv (g^y)^x$, where $g^x$ and $g^y$ are public, while $x$ and $y$ are (and stay) private, and $g^{x·y}$ is the shared secret.

To break RSA, we would have to get $x$ from $x^d$, $m$ and $d$ - this could be called the discrete $d$-th root problem. (The best known way to do this is to factor $m$ to get $e$ ... and if you have $e$, this also can be used to factor $m$).

To break Diffie-Hellman, we have to get $g^{x·y}$ from $g^x$, $g^y$, $m$ and $g$. The best known way to do this would be to get $x$ from $g^x$ or $y$ from $g^y$ (and $m$ and $g$), the so-called discrete logarithm problem.  (Incidentially, it is not proven that this is really the best way, i.e. that there is not a faster way to do this.)


Is there a hash algorithm that is slow to calculate but relatively fast to check? Or more generally, is there a function or algorithm that is slow to calculate/execute, has a reliable execution time, and has a result that can be tested much more quickly than the calculation took?

It sounds like you're looking for a proof-of-work system.

One way to implement such a system would be, given a message $m$, to ask for a suffix $s$ such that the hash $H(m \operatorname{\|} s)$, where $H$ is some standard cryptographic hash function and $\|$ denotes concatenation, begins with a specific prefix (e.g. $n$ zero bits).

Of course, the execution time of such a scheme is not really deterministic; we can predict the expected time it will take, but the actual time will be geometrically distributed, and so will vary a lot.
Also, the particular scheme I described is very easy to parallelize, so that using multiple processors (or parallel processors like GPGPUs) cuts down the expected solving time in inverse proportion to number of cores used.  Depending on your application, this may or may not be an issue.


Is it ever unsafe to compress an EC point? I am working with a library that outputs EC points in uncompressed form.  To save space, I'm considering modifying said library to use compressed EC points.  Assuming that I keep track of the sign bit prior to compression, is there any risk in compressing said point?

I read this Q and related answer, but want to ensure that I may not be opening the door for other issues.

I would argue the opposite: it's safer to compress a point.

The reason is fairly simple.   During decompression- whose most expensive operation is a modular square root - your are guaranteeing that the resulting point either is on the curve, zero or infinity.

One of the most frequent errors in elliptic curve operations is failing to properly validate a point before operating on it.   The most public example of this is the Bluetooth pairing vulnerability - which, had it used compressed points, would not have been vulnerable to MITM attacks.

While validation is less expensive than decompression - it's one of those "seemingly optional" steps that people can forget to do.   With compressed points there's no option.


Unique, anonymous online authentication Is there a way to authenticate users online without knowing their real identity yet preventing them from registering twice? If not, what is the least amount of information you would need? If it helps, you may assume the user has a smart phone and you have access to all its sensors. Probabilistic guarantees are quite acceptable (e.g., 1-$\epsilon$ certainty of uniqueness for small $\epsilon$).

The easiest way would be to make use of a trusted third party. In this way, users can authenticate to the trusted party (maybe with the cellphone/IMEI number) which then issues them with a "ticket" or "group/blind signature" along with a pseudo-identity, similar to those used in e-voting schemes. The pseudo-identities can then be checked for duplicates.

Without a third party, I think it will be hard for you to proof that each user is unique even if you have access to all his sensors. e.g. user can always change his current location to change the gps, temperature, illumination, and humidity sensor readings.


Is it possible to subtract/multiply numbers using homomorphic encryption? Most of the libraries I've seen allow you to add encrypted numbers. Is it possible to subtract and multiply them?

Have you read Wikipedia: homomorphic encryption and
Bruce Schneier: Homomorphic Encryption Breakthrough?

In summary:

  Is it possible to subtract numbers using homomorphic encryption? Is it
  possible to multiply numbers using homomorphic encryption?

Yes, there are many known partially homomorphic cryptosystems, each one can either multiply or add numbers.

To add two encrypted numbers, one could use Benaloh, Damgård–Jurik, or several other known partially homomorphic cryptosystems.
(Many of these "addition-only" cryptosystems can also be tweaked to support subtraction.
Asking "how do I do that" would be a great separate question).

To multiply two encrypted numbers, one could use Unpadded RSA, ElGamal, or several other known partially homomorphic cryptosystems.

  Is it possible to subtract and multiply numbers using homomorphic
  encryption?

To multiply one encrypted number by a plaintext number (which, alas, is not sufficient for fully general computation) and also add two encrypted numbers, one could use Paillier, Naccache–Stern, or several other known partially homomorphic cryptosystems.

Subtraction can be implemented by encrypted "multiply by a plaintext -1" followed by encrypted addition.
(Asking "how do I do that" would be a great separate question).

  Is it practical to express any computation whatsoever as a series of multiplies and subtracts?

Yes. In fact, computations on decimal numbers, text strings, 2D images, etc. are almost always done by converting to binary representation, using a series of Boolean computations internally, and then converting back to a human-friendly representation.
(Boolean computations can, in turn, be implemented using multiplies and subtracts, although that is slightly less efficient).

  Is it possible to encrypt a few numbers, send them to a distant server
  that uses homomorphic encryption to do a series of
  "encrypted subtraction" and "encrypted multiplication" operations
  on those
  numbers, and then sends the encrypted result back -- a message that can be
  decrypted to give the same result as a corresponding series of
  subtractions and multiplications on those numbers?

Cryptographers have been hunting for such a "fully homomorphic encryption scheme" for decades.
After a few decades of searching and coming up empty, cryptographers were starting to think perhaps fully homomorphic encryption is impossible.

The first known fully homomorphic encryption scheme was discovered by Craig Gentry and announced in 2009. It is an amazing theoretical breakthrough.

Alas, in that scheme, the "encrypted subtraction" and "encrypted multiplication" operations are so complicated that it's not really practical.

Now that one fully homomorphic encryption scheme has been demonstrated,
cryptographers have high hopes that other, more practical systems will be discovered.

The current situation is something like the current situation with manned moon missions.
People have been dreaming about traveling to the moon for centuries,
but it was long thought to be completely impossible.
In a great technological breakthrough, one method of traveling to the moon put 12 men on the moon, demonstrating that it is possible.
However, that particular method is so expensive that it is not really practical.
Still, futurists have high hopes that other, more practical systems will be discovered.


Is CMAC vulnerable to length extension attacks? Given $m_1, m_2$ such that $MAC_k(m_1) = MAC_k(m_2)$ is it possible to construct more collisions with pairs of the form $m_1|x, m_2|x$?

Here is the CMAC picture from Wikipedia where it is only part of the one-key MAC article:

I don't see how it could be because it treats the last block of the message differently but this was mentioned in the comments of another question so I wanted to clarify.

Here is the quote from poncho:

  CMAC and XCBC are similar to the UMAC case (even though a universal
  hash is not involved); if you find two messages that have the same
  CMAC value, it is likely that a simple length-extension to the two
  messages will allow the attacker to create other pairs of messages
  with the same MAC.

Bonus question: Are there other ways to exploit a collision?

Given $m_1, m_2$ such that $MAC_k(m_1) = MAC_k(m_2)$ is it possible to construct more collisions with pairs of the form $m_1|x, m_2|x$?

Yes, given two restrictions:

$MAC_k$ is not truncated (e.g. if it is based on AES, then the tag is 128 bits long).  This observation does not apply on a collision on (for example) truncated 64 bit tags (assuming that the bits deleted during the truncation don't also happen to collide).

$m_1$ and $m_2$ are either both a multiple of the block size in length, or alternatively both not a multiple of the block size in length.  For example, if we assume AES, then it works if $m_1, m_2$ are $32, 48$ bytes in length (both multiples of 16), and if they are $23, 31$ bytes in length (neither multiples of 16), but not if they are $16, 17$ bytes in length.

Here is how CMAC works (at the end of the message, which is where the interesting part it):

Block $n-1$ is processed, generating an internal chaining value $I_{n-1} = E_k( m_{n-1} \oplus I_{n-2})$

the last block is processed; the block is zero padded (if not full), one of $k_1, k_2$ is selected (depending on whether the block is full), and we do a final computation $tag = E_k( m_i \oplus k_{1,2} \oplus I_{n-1})$

Now, we assume a full block collision, that is, $tag = tag'$.  Using the above definition, we have:
$$E_k( m_n \oplus k_{1,2} \oplus I_{n-1}) = E_k( m'_n \oplus k_{1,2} \oplus I'_{n-1})$$
Removing the encryption, and noting that both sides select the same $k_1, k_2$ value, we can simplify this to:
$$m_i \oplus I_{n-1} = m'_i \oplus I'_{n-1}$$
Now, we can consider what would mapping if we compute the CMAC of the values $m || padding || x$, $m' || padding' || x$ (where $x$ is an arbitrary bits string, and where $padding, padding'$ are the zero pad to bring $m, m'$ to a multiple of block size in length; they are zero length if $m, m'$ is already a multiple of block size).
In this case, at step $n$, the two sides will compute:
$$I_n = E_k(m_n \oplus I_{n-1})$$
$$I'_n = E_k( m'_n \oplus I'_{n-1})$$
These two values are the same; the rest of the CMAC computation depends only on $x$ (which is the same on both sides), and so will result in the same tag; hence giving us another collision.


Encrypting a small value $m\in\{1,\dots,100\}$ using textbook RSA When encrypting a small value $m\in\{1,\dots,100\}$ using textbook RSA, and since that is deterministic, an attacker could try every possible number to determine $m$.

To prevent this kind of attack, one could select a big random number $x$, and send $x^e\bmod n$ and $(m+x)^e\bmod n$.

What would be a problem with this encryption technique?

If $e$ is "small" (as all typical values of $e$ are!), this is vulnerable to the Franklin-Reiter related message attack.

In a nutshell, given $c_1=x^e\bmod n$ and $c_2=(x+m)^e\bmod n$, for each possible value of $m$, compute
$$f:=\gcd(y^e-c_1,(y+m)^e-c_2)$$
in the polynomial ring $(\mathbb Z/n)[y]$. If you guessed the right $m$, then (possibly except for very rare cases)
$$f=y-x\in(\mathbb Z/n)[y]$$
and you have recovered $x$ and verified that $m$ was correct. Otherwise, $f$ will most likely be $1$. Note that this $\gcd$ is technically not well-defined in all cases, but if you actually encounter a problem with that, you have effectively factored $n$.

Of course, this assumes that $e$ is small enough for this $\gcd$ computation to be feasible, and that the set of possible messages $m$ is small enough to be brute-forceable.


Are my random numbers really "bad" or is that a statistical effect which "must" happen from time to time? My software uses a TRNG (entropy source) which is part of an MCU.

A check of random numbers generated by my software, carried out by a testing authority revealed a problem, which I have to examine now:

They ran my random numbers against NIST Test suite:
https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf

The Non-overlapping Template Matching Test failed.

It is looking for the number of occurrences of given bit sequences in a random string and compares those numbers with the expectation values. The test statistics $\chi^2$ is a measure, how well the observed number matches with the expected number of occurrences.

A big number of N*M bits is divided into N blocks of each M bits.
The pattern has length m.

The mean value of hits is

$\mu = \frac{M-m+1}{2^m}$

The variance

$\sigma^2 = M (\frac{1}{2^m} - \frac{2 m - 1}{2^{2m}})$

The test statistic is

$\chi^2 (obs) = \sum_{i=1}^{N} \frac{(W_i-\mu)^2}{\sigma^2}$

with i iterating over all N blocks and $W_i$ denoting the number of matches in block i.

The p-value is

$p = 1-\Gamma_{inc}(\frac{N}{2}, \frac{\chi^2 (obs)}{2})$
where $\Gamma_{inc}$ is the incomplete gamma function.

If the computed P-value is < 0.01, then conclude that the sequence is non-random.

I implemented this test on my own and got with a test run of 80,000 random bytes:

N=8, M=80000

A good pattern would be:

expected occurrences of 1110000 in random binary of length 80000:624
W[0]:657
W[1]:633
W[2]:620
W[3]:608
W[4]:659
W[5]:610
W[6]:607
W[7]:628
OK: P=0.697173010616

Most patterns are good, but some are very bad, like:

expected occurrences of 1110110 in random binary of length 80000:624
W[0]:554
W[1]:618
W[2]:715
W[3]:648
W[4]:602
W[5]:619
W[6]:683
W[7]:611
*****NOT OK: P=0.000101720454752

or

expected occurrences of 11000100 in random binary of length 80000:312
W[0]:310
W[1]:352
W[2]:297
W[3]:325
W[4]:332
W[5]:376
W[6]:327
W[7]:318
*****NOT OK: P=0.00404698900088

Now the question:

As I interpret the P value, it is the probability for getting the observed test statistics given the sequence is random. So P=0.000101720454752 would be extremely unlikely, so the test fails.

Most interestingly, when I increase the block size by a factor of 10 (800,000 random bytes)

N=8, M=800000

I get only good results on all patterns.

What does it really mean now? Are my random numbers really "bad" or is that a statistical effect which "must" happen from time to time? Anyway the test fails...

And why is it OK for the ten-fold data-set?

I would appreciate any comments.
Thanks.

One of the failing test discussed in the question was coded for the purpose. It could be useful to validate that code using a known-good pseudo-random source (the output of SHA-256 for incremental values qualifies). If it failed too often, the code would need a fix! The test's definition is complex, for example in 2.7.4 (2) defining how to count the number of occurrences of the pattern searched, and an error could have crept.

But I fail to imagine an error giving what's observed, and (after fixing an issue about the definition of the incomplete gamma function that had no influence for the reference test case, and a typo of mine in one count) I confirm that the question's P-values match the question's counts.

With these results (especially the second test case, with a P-value < 1/9830), at least one of the following must hold:

the generator's output is quite distinguishable from random (my guess);
that's a serious case of bad luck (how bad depends strongly on among how many tests the failing cases shown have been picked, see below);
the question's counts are somewhat wrong in a strange, irregular way;
the math in the reference is seriously bad (but I guess that would be known).

Importantly: it appears that the test is run with many patterns. In that case, the P-value threshold considered a failure should be lowered (like, divided by the number of tests); or best, the P-values should be aggregated. For aggregation, we could use Fisher's method. In theory that requires the tests to be considered independent, which would be the case if a sample RNG output is never tested with multiple patterns. Practitioners occasionally are not so careful, but that seldom is a game-changer.

Note: The reference only skims at the issue of choosing P-value thresholds (noted $\alpha$), and does not tell how to decide if the overall result of multiple tests is pass or fail. It even makes highly misleading statements on how to interpret P-values, like the second of these three sentences at end of section 1.1.5 (emphasis mine):

  An $\alpha$ of 0.001 indicates that one would expect one sequence in 1000 sequences to be rejected by the test if the sequence was random. For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%. For a P-value < 0.001, a sequence would be considered to be nonrandom with a confidence of 99.9%.

The question rightly observes

  Most interestingly, when I increase the block size by a factor of 10 (800,000 random bytes: N=8, M=800000) I get only good results on all patterns.

Especially if the generator tested is an unconditioned TRNG (see below), that would match a failure mode where the generator locally has repeating patterns, but these evolve over time.

If the source of the data tested is an unconditioned TRNG, and unless the supplier of that thing guarantees in a contract with severe penalties that no conditioning is necessary to pass any kind of test (which would be a foolish move), then failing a RNG test should be considered normal. Correspondingly, submitting this output for validation by a lab should be considered a procedural mistake: these tests are intended to test if a RNG is distinguishable from random, and unconditioned TRNGs often are!

On the other hand, if what's tested is the output of a PRNG seeded with the TRNG (as would be typical for a black-box test), and the test fails, that's indicative of (both) an extremely poor/defective PRNG and a failure of the TRNG.

Unconditioned TRNGs typically have defects, often subtle, dependent on manufacturing variations and environmental conditions. The design engineer has to factor that in. The output of an unconditioned TRNG should be used (exclusively when in operational mode):

to monitor failure of the unconditioned TRNG; the monitoring's goal is ensure that the source delivers some entropy, above some designed-in limit, without raising false alarms.
and to feed a PRNG, which results are used (not the TRNG's unconditioned output).

Further, if that PRNG is not a CSPRNG (which is typical of hardware PRNGs, often a variation around LFSR), for some critical usages the output of the PRNG should be the input of a good CSPRNG (it is often considered OK to directly use the hardware PRNG for more mundane things, like massive DPA countermeasures).

It is easy to turn a passable TRNG into a good RNG that passes all standard test. What's hard is to make monitoring that demonstrably detect failure on the field and acts accordingly, but does not falsely detect failure under normal use. True failure could be because attackers do all sort of nasty things: under/overvoltage, heat or evaporation of a liquefied gas to reduce the entropy rate of the RNG source, or superimposed clock/glitches on the power supply (and more) in an attempt to control the TRNG source and make it near deterministic. Sometime the adversary is only Murphy's law (perhaps in the form of poor contacts, long wires, unclean power supply, insufficient decoupling, manufacturing defect) but succeeds just as well.

Note: I heard a tale about a then inexperienced hardware manufacturer proposing an IC with module initially specified as a directly usable TRNG that always work; then found to sometime fail a test; and hastily replaced by a conditioned TRNG, with no access to the unconditioned TRNG specified. That reportedly made it difficult to properly monitor the TRNG: the only sound option would have been to break the conditioning, but the tale ends without clear indication that this was achieved and deployed.


Large prime numbers in encryption? I have recently been reading about encryption and the importance of prime numbers and I have some questions that I would really appreciate some answers to, if possible:

Is it correct that when creating encryption keys you take one large prime number, and then multiply it by another prime number to leave you with an even larger prime number?
If 1 is correct, then is it correct to say "the reason for the large prime number calculation is it is very difficult and time consuming to work out what the initial prime numbers were used in the original calculation"?
What constitutes as a large prime number?

The reason for this question is I have been doing some reading about encryption as stated above, and assuming the above statements are correct I think I have a really simple formula for working out what the original prime numbers used were. I have tested this prime numbers all the way up to $299993$. And I must be doing this wrong because it can not be this simple, I assume someone will point out where I am going wrong.

Is it correct that when creating encryption keys you take one large prime number multiple it by another prime number to leave you with a even larger prime number?

Any number that is a multiple of two primes is by definition not prime. This creates a semiprime: a number that has only two prime factors.

This approach is only used in a few cryptosystems, the most common of which is RSA. Many other cryptosystems exist that do not rely on integer factorization. Some of these systems (e.g., AES, ChaCha20) are symmetric algorithms unlike RSA, and some (e.g., ECC) are asymmetric like RSA. RSA is gradually being phased out in favor of modern systems based on elliptic curves.

  If 1 is correct, then is it correct to say "the reason for the large prime number calculation is it is very difficult and time consuming to work out what the initial prime numbers were used in the original calculation"?

Yes. As far as we know, integer factorization is a hard problem.

  What constitutes as a large prime number?

2048-bit RSA is a typical current recommendation. In this case, the modulus (e.g., the semiprime) is the part that is 2048 bits, so each prime is roughly 1024 bits long. For scale, a 1024-bit prime will be over 150 decimal digits long, so they are quite large.


Biometric authentication I see in some “Authentication schemes with biometric” papers that those authors wrote a phase as password and biometric update phase.
My question is that why we may needs biometric update phase?
Is not biometric (say finger print or iris or face and …) permanent properties?

Some devices I've been working with do indeed update biometric information.

The reasons is that there may be additional information:

acceptable fingerprint was scanned (required features are found), but the scan shows some area of finger not involved in previous scans.
some other additional information helping make more exact scans in the future


How exactly does AES-NI work? I am looking in to AES-NI which is now supported by many new CPU's and I have read a few papers which states that AES-CBC works faster with AES-NI, but I am unable to understand how exactly AES-NI works.

As far as I know, AES-CBC encryption is sequential, so how does AES-NI make it so faster?

(Also even after using AES-NI, is AES-CBC performed sequentially?)

AES-NI is just a fast way for the processor to execute the calculations of AES. Normally the computer has to calculate every single step of the AES key schedule and the rounds as a single instruction: Substitute it with the S-boxes, shift the rows, mix the columns, XOR the round key. This is called a software implementation. Every instruction has to be done in software from the program.

Using the AES instruction set the program can do a whole round in a single instruction. There are several different instructions to do this: New instructions, Wikipedia.
The instructions will be executed on hardware level, in the transistors of the processor. Without the whole other things a processor normally does to execute a program the encryption and decryption are much more efficient. This is called a hardware implementation. As far as I know, every block cipher is more efficient in hardware than in software. Some more, some not so much. "More efficient" means faster, less energy-consuming or both.

Yes, AES-CBC encryption still has to be done sequentially. AES-NI can only help with one encryption or decryption, but it still greatly increases the speed, because the encryption or decryption is the slowest part of CBC mode. (For the sake of completeness: You can use AES-NI for every encryption mode, not only CBC.)


AES 128 bits with 12 bytes IV vector composed of a 4 bytes counter : safe? I have a 128 bits AES cypher (GCM, Galois/Counter Mode) using a 12-byte initialization vector (IV) composed of:

8 constant bytes:

6 bytes (device ID)
2 bytes (zero)

4 bytes (incrementing frame counter)

Is this really safe? Assuming the frame counter may overflow in the long run.

As SEJPM notes in the comments, the IVs will repeat after $2^{32}$ frames.  This is bad (unless the key is changed more often than that).

In particular, if you can temporarily capture the device and make it encrypt $2^{32}$ known messages of sufficient length, you will learn the keystreams corresponding to all the $2^{32}$ possible IVs for that device.  This allows you to trivially decrypt any past or future messages sent by the device just as easily as if you had the key.

Depending on the nature of the device, convincing it to encrypt $2^{32}$ known messages may be anything from impossible to trivially easy.  Since you yourself mention that "the frame counter may overflow in the long run," it seems that it's at least within the realm of possibility.

In any case, even if this particular attack turns out to be infeasible, any situation where two different messages are encrypted in CTR mode with the same key and IV violates the basic assumptions of the security proof for CTR mode, and makes it potentially vulnerable to attacks.

To prevent such attacks, you'd need to either:

ensure that the frame counter can never overflow (under normal or abnormal operating conditions), or
ensure that the key is changed (at least) every time the frame counter overflows.

To prevent counter overflow, you can either widen the counter (e.g. adding the two unused bytes in the IV to the frame counter to make it 48 bits wide) or add an explicit overflow check (which might mean bricking your device instead of compromising security if the maximum number of message frames is exceeded, unless you have some kind of a key update mechanism in place), or, better yet, both.

Addendum: As user4982 notes above, a similar attack is also possible even without wraparound, if the frame counter can be forced (or accidentally made) to reset to zero (or to any previously used value) e.g. by cutting power to the device.

One way to defeat this attack is to store the frame counter in non-volatile (e.g. flash) memory.  Since such memory can often be slow to write to, and may not tolerate an unlimited number of write-erase cycles, one commonly used trick is to write a value that is, say, 1000 frames higher than the actual current counter value, and then wait until the actual counter catches up to the stored value before the next write.  This allows you to reduce the number of writes to non-volatile memory by a factor of 1000, at the cost of potentially skipping up to 1000 counter values every time the device is reset.

(There are other, more sophisticated methods of minimizing non-volatile memory wear as well, but they tend to depend on the specific characteristics of the non-volatile storage you're using.)

Of course, if the device already has some way of changing the encryption key, another option could be to simply change the key every time the device is reset, eliminating the need to store the counter entirely.


A practical algorithm for proof of age I'm new to the list, a layman in cryptography, but a competent programmer. Seeking your help for a practical algorithm that I can implement please.

Problem

Let a prover P hold an identity document D, e.g. a passport, that contains a date of birth field dob.

A verifier V wants to check that:

that I hold the document
that D.dob is >= <some date>

All without P exposing D or V trusting P.

thanks and regards
d.

Here's a solution using RSA as the primitive. There's probably a variant based on elliptic curves. Though maybe not. RSA is great for this kind of stuff.
The protocol
Grace the government worker gives the prover Paul an identity document. One of the document fields is an age threshold proof value. This is a standard RSA signature over some public fields of Bob's identity document (EG:name, picture etc.) that Paul would use to prove he is Paul.
Instead of using the standard RSA signature algorithm to generate the signature, Grace uses a multiple of the private exponent when doing the operation. This is equivalent to applying the private operation multiple times.
age_proof=sig^(d*age) mod N
To verify this signature we have to apply the public operation age times to get back the original signature value.
sig=age_proof^(e*age) mod N
Note that sig, e and N are known to the verifier, age and age_proof are not known.
Suppose Paul is 35. If Alice wants paul to prove he is at least 20 years old, Paul first performs 15 public RSA operations on his proof of age value. He passes this value to Alice who performs an additional 20 exponentiations and gets back the original signature.
This can be seen as a chain of signatures. Grace, by repeatedly applying the private operation to Bob's signature value creates a chain of signature values which can be traversed in the forwards direction to get to the signature value.
What the system provides
Paul has an integer x
Grace provides him with a proof value Px
Alice asks Paul to prove that x is larger than a bound y

Alice gives Paul y
Paul applies x-y public operations to degrade Px into a proof for Py
Paul gives Py to Alice
Alice applies y public operations to degrade Py into P0 which is a signature of some data about the thing that was signed (EG: Who owns the proof.)

Proof of age range
A more practical proof of age system would use two numbers. The numbers would be measured in days or hours and be the difference between the owner's data of birth and a date far in the past (say 1900AD) and a date far in the future (2200AD)
The first number, referenced to a date in the past proves youngness. The larger this number the more recent the date of birth.
The second number, referenced to a date in the future proves oldness. The larger this number the farther in the past the date of birth is and the older someone is.
This avoids the need to reissue or update cards as the card holder ages. The proof of youngness can be useful for businesses that want to implement youth discounts.


Intuition Behind Commitment-Challenge-Response a.k.a. Sigma Protocols In How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Fiat and Shamir introduce a zero-knowledge identification scheme where

The prover sends a commitment to the verifier
The verifier sends a challenge to the prover (in shape of random coin tosses)
The prover sends a response to the verifier
The verifier checks if the response is correct

This is zero-knowledge and a Sigma protocol as described by Cramer in his PhD thesis.
My only experience with commitments is in fairly flipping a coin over telephone, in which case a commitment seems perfectly reasonable.
But what is the basic intuition behind the commitment in the Fiat-Shamir case? Challenge and response are obviously part of the protocol, but why is the commitment needed? As far as I can tell, the commitment is not even revealed to the verifier in the Fiat-Shamir identification scheme!

As a concert example lets consider the protocol for knowledge of discrete-logarithm.
The aim of the protocol: P wants to prove that it knows $x$ for $pk=g^x$.

commitment: P chooses a random $r$ and commit to it by sending $R=g^r$ to the verifier.

challenge: the verifier chooses a random value $c$ and sends it to P.

P sends $z=r+cx$ to the verifer.

verification: the verifier checks if $g^z=R.pk^c$ if yes it accepts it.

Now what will happen if the prover does not commit to $R$ before sending $z$ ?
After receiving $c$ from the verifier, P chooses a random $z$ and finds $R'$ from the equation $g^z=R'pk^c$, i.e., it sets $R'=g^zpk ^{-c}$.  Then it sends $R',z$ to the verifier.
By this $R'$ it can pass the verification check, and the point is that it even does not use $x$ in $z$. This means a malicious prover who does not have $x$ can prove the knowledge of $x$!
Putting together, commitment is necessary to protect the proof system against prover such that just the honest provers can convince the verifier.


Ephemeral Encryption Keys My understanding is, ignoring implementation details, iOS disk encryption works like this: On boot (and/or every time you unlock your phone) an ephemeral session key is created that can decrypt encrypted files.

My question is, how is it possible to create ephemeral keys, without re-encrypting the files on disk?

The only solution that comes to my mind is use the ephemeral key to decrypt the "real" key that then is used to decrypt the files. And when your session expires and you need to invalidate the ephemeral key basically you delete the encrypted copy of the real key that was encrypted by the ephemeral session key.

Are there any other solutions to this? basically to create ephemeral keys without re-encrypting the data?

The answer is in what Apple means by "ephemeral session key". See the BlackHat session starting around 12:00 in.

The raw file encryption keys are wrapped with a ephemeral key when outside the SEP (Secure Enclave Processor), the actual key is never exposed to the normal application processor. The ephemeral keys are bound to the boot session of the phone.


Question on 3DES keys The official NIST publication I saw says for federal applications 3DES with three keys should be used. I have such questions:

what does it mean federal? Does it mean for industrial applications that requirement doesn't hold? What security do I get with 2 keys? by two keys I mean when K1==K3, but K2 is different? Is it average security?
Three key approach with (globally) fixed second key which is still different from each K1 and K3 pair: Imagine I have server which communicates with many clients. Is it ok if with each client i it uses distinct (K1[i],K3[i]) pairs (but K3[i]==K1[i] for each pair), and K2 I take such that it is different from each (K1[i], K3[i]) key pair in my system, but it is fixed (globally) for all clients?

EDIT: The crypto will be done by dongle so that someone will decompile my soft and get 2nd key doesn't hold as mentioned in one of the answers.

For high security applications using 3DES, NIST recommends using keying option 1 (all keys are different). This is simply because it's the safest. For any application, keying option 1 should be used. If you set K1==K3, then you are reducing your key size to 112 bits, which is less than the smallest key size for AES. Worse still, due to cryptanalysis done on DES, setting K1==K3 (known as keying option 2), NIST has said this has an effective security of 80 bits. This is barely an improvement on plain DES.

So in short, yes, NIST claims for federal applications you should use 3 different keys. But this is true for any application.

Your second proposal has an effective security of 56 bits, which is just plain DES. A globally fixed K2 means that it has no security, and once one client is broken and decompiled (and trust me, this will happen), then they have K2 for all clients. This effectively makes it have 0 bits of security. K3, being the same as K1, also has 0 bits of security. The only security comes from K1, which is 56 bits. The EFF showed us that a 56 bit key is insecure and is susceptible to a brute force attack.

You really shouldn't be using 3DES though. It's only used in legacy applications where there are absolutely no other options. AES is currently the standard. If you must, and only if you must use 3DES, use 3 distinct keys that are randomly generated per session.


Does it make any sense to hash parts of a hashing target? TL;DR;
Assuming I'm calculating SHA256 for an ECDSA, does it make sense to do SHA256(item1 + SHA256(item1') + item2 + SHA256(item2') + itemN + SHA256(itemN')) or it's the same (security-wise) as SHA256(item1 + item1' + item2 + item2' + itemN + itemN')?
(hereunder + refers to as binary concatenation of operands' content in binary format)
Details
I have a data structure similar to the one below (presenting in JSON format for readability)
{
  "Lorem": 123,
  "Ipsum": "qwerty",
  "Items": [
    {
      "Id": 4321,
      "Data": "SOME_DATA_HERE",
      "ItemSig": "A_RELATIVELY_BIG_BINARY_STRUCTURE_AND_ECDSA_SIGNATURE_OF_HELLO_FIELD_CONTENT"
    },
    {
      "Id": 8765,
      "Data": "SOME_DATA_HERE",
      "ItemSig": "A_RELATIVELY_BIG_BINARY_STRUCTURE_AND_ECDSA_SIGNATURE_OF_HELLO_FIELD_CONTENT"
    }
  ],
  "Sig": "A_PLACE_FOR_ECDSA_SIGNATURE"
}

I also have an ECC key pair. Now, I need to sign over each element within the "items" array and then over the entire structure itself.
When signing over the entire structure, I'm proving some data in that structure (contents of Lorem and Ipsum), and per each Item, I'm proving that the item was in that structure (by including Id in the signature) and proving that item's content (by including ItemSig which includes the content).
I think it worth noting that I include ItemSig instead of the item's content in the structure's signature to prove that the item was signed by the same ECC key as the structure itself. This is because there are multiple ECC keys that are valid for signing, but it's considered invalid to sign items with one ECC key while signing the structure with another.
So the question is, what's better option for structure's Sig field (and why?), ECDSA(SHA256(Content)) where

Content = Lorem + Ipsum + Items[0].Id + SHA256(Items[0].ItemSig) + Items[1].Id + SHA256(Items[1].ItemSig) + Items[n].Id + SHA256(Items[n].ItemSig), OR
Content = Lorem + Ipsum + Items[0].Id + Items[0].ItemSig + Items[1].Id + Items[1].ItemSig + Items[n].Id + Items[n].ItemSig.

From the practical point of view both approaches have similar resistance to brute-forcing. From the implementation point of view it may be simpler to apply hash only once, without hashing of every single part.
Nevertheless I would suggest you to review your design and consider other options. Suppose somebody has received your message and validation shows, that Items[0].ItemSig and Items[0].Data to not match. This can have two reasons:

Either Items[0].ItemSig was invalid before you signed it (then the signer has faked the signature).
Or the signature was correct, but you have replaced Items[0].Data before signing.
Or Items[0].Data was modified on the way from you to the receiver.

Thus it will be hard to find out where the problem has happened.
That's why I'd suggest other approach. Think of separation of concerns. Don't consider the structure of what are you signing. Sign the whole element Items. Then if somebody receives your message and something is not consistsnet, it will be easy to check: One should just check if your signature matches the Items element. If matches, means there was no modification on the way from you to the receiver, and the problem occurred on the signer of Items[0].Data before you signed.
TLDR: I'd suggest to hash the whole element Items, not the parts of it, and without hashing of every single part of it.


Does the size of a file influence the randomness if used as random input? (I am a cypto amatuer )
So in Openssl there is the "-rand" option for taking a file containing randomness for the RNG . So I thought taking a pretty big file would make it more secure .
So if you use a lets say 2048 bit random binary file form "https://www.random.org" made from cosmic noise you would be pretty safe right ? But the problem is that the if I used the file multiple times it is alway the same "random" input so i would have to make the file secret . So It would be better to change like one 0 or 1 in the 2048 bit every time using it right ? But here comes the Question : How much does changing a single character in 2048 bit affect the randomeness of the Output in the end ? Is it like hashing where the output is completely different after changing only one bit or will the output be pretty much the same ?

OpenSSL will take the file and feed it into its internal PRNG(pseudo-random number generator). That PRNG has an internal state consisting of a 1023 byte buffer and a working hash value (20 byte sha1 hash)

The algorithm used to seed the PRNG goes around the buffer, modifying the buffer in 20 byte blocks while also updating the working hash value.

Q:Should I make the file bigger?

Anything much larger than the state size of the PRNG (1043 bytes) is wasteful. Feeding in more than that many bytes of random data will not improve security (by making the final PRNG state harder to guess).

Q:Where should I put a counter value If I plan to reuse data?

Putting it at the beginning of the file might be slightly better.

Supposing you put a small integer at the end of your file. That integer would be fed into the PRNG last. That means most of the large buffer would be unaffected by its value. Only the working hash is guaranteed to be affected.

This isn't a real problem. All output is dependent on the working hash and 160 bits is more than enough entropy to foil real world attackers (even ones with quantum computers).

Should I be doing this?

No. This is a brittle approach. If an attacker gets the seed file (which you plan on re-using) they can generate all the secret keys you produced. That makes it a massive liability. If the service providing you with random data is not trustworthy they could already be doing this.

If you plan on using such a file, you must also include additional randomness from another source. You could get it from the operating system (EG: reading /dev/urandom on linux) or just bang on the keyboard for 30 seconds. More entropy sources can't hurt and will prevent this sort of failure.

Also, consider, if you trust your OS not to steal the keys why don't you trust it to supply randomness? Most operating systems do a good job of capturing and supplying randomness (as long as you wait till a few minutes after booting).


Does it increase security if the CBC chunks of a AES-256 encrypted bytestream are uploaded to different clouds? I want to backup my data according to the 3-2-1 rule. I am already back up to 2 different drives (2 different systems) at home. In addition, I would like to use cloud storage (Google, Amazon, etc.). Considering the future weakening of cryptography by advancements in computing power (e.g. key guessing by quantum computing) I want my data to be as safe as possible because once it's uploaded it's prone to decryption in the future (i can't guarantee the data is deleted if I delete it from the cloud(s)).
Does it increase the security of my data if I split the CBC chunks to let's say 2 clouds? Uploading the even-numbered CBC elements to e.g. Google and the odd-numbered elements to Amazon. Since one storage hoster is constantly missing the next part of the CBC-Chain (1/2 in total) shouldn't this increase security of the data even if the AES key is known by the hoster(s)?

First of all, AES-256 is considered the gold standard on the market by the industry.   The quantum attack on a block cipher is performed by Grover's algorithm that can provide at most quadratic speed up on the key search. The qubit requirements, setup, and running time even for AES-128 is not easily solvable in a near future, and AES-256 is safe. The below table is from

M. Grassl et. al, Applying Grover's algorithm to AES: quantum resource estimates, 2015.

\begin{array}{cccccc}\hline
& \#gates & & depth & & \#qubits\\
k & T & Clifford & T & overall & \\ \hline
128 & 1.19 \cdot 2^{86} & 1.55 \cdot 2^{86} & 1.06 \cdot 2^{80} & 1.16 \cdot 2^{81} & 2953 \\
192 & 1.81 \cdot 2^{118} & 1.17 \cdot 2^{119} & 1.21 \cdot 2^{112} & 1.33 \cdot 2^{113} & 4449 \\
256 & 1.41 \cdot 2^{151} & 1.83 \cdot 2^{151} & 1.44 \cdot 2^{144} & 1.57 \cdot 2^{145} & 6681 \\
\end{array}

Does it increase the security of my data if I split the CBC chunks to let's say 2 clouds? Uploading the even-numbered CBC elements to e.g. Google and the odd-numbered elements to Amazon. Since one storage hoster is constantly missing the next part of the CBC-Chain (1/2 in total) shouldn't this increase security of the data even if the AES key is known by the hoster(s)?

This is a security question on unidentified risks. What if both X and Y are combining their power or they are forced by the government to combine the data, so no benefit there.
What if a huge regression occurs and one of the companies goes out of business so fast. Will you able to get the other chunk? and even in a more catastrophic scenario that your copies are already corrupted.
The hard disks are failing, DVDs degrading, computer systems are not perfect, etc. Solving these is out of Cryptography, the common techniques are multiple copies and raid system like NAS.
Your main issue is the integrity and authentication of your data. To solve this issue you need authenticated encryption and for CBC you can achieve this with HMAC, or better you can use authenticated encryption modes like AES-GCM, Chacha20-Poly1305 those will provide Confidentiality, Integrity, and Authentication. Each has pros and cons mainly take care of the $(IV,key)$ reuse problem.


How to decrypt / break enigma-encrypted ciphertext with given configuraton? I'm new here--seriously I don't know anything, but my close friend sending me a code and I must solve it.

The code uses Rotor III, V, VIII;  starting point ABC; reflector BB; and pair OA LU.

Can someone give me an example and its procedure about solving a question/code using those rules?

Thank you.

If you know the configuration of the machine you can easily decrypt the message. All you need is an enigma machine, I found one of several emulators online: Enigma emulator.


Correct way to read a given permutation cipher? In some literature I am reading – where they are explaining the permutation cipher – they have two examples, which encrypt a small block of text. But they seem to contradict each other:

First example:

  permutation: ${1\text{ }2\text{ }3 \choose 3\text{ }1\text{ }2}$, plaintext: VEN, ciphertext =NVE

Second example:

  permutation: ${1\text{ }2\text{ }3 \choose 2\text{ }3\text{ }1}$, plaintext: TEN, ciphertext = NTE

Am I missing something? The second example makes sense to me, but not the first. Why isn’t the ciphertext for the first example not ENV?

The permutations in your question are given in Cauchy's two-line notation, where the upper line gives the input index to the permutation function, and the lower line gives the resulting permuted index.

For example, the definition $$\sigma = {1\ 2\ 3 \choose 3\ 1\ 2}$$ means the same as $$\sigma(1) = 3,\quad \sigma(2) = 1,\quad \sigma(3) = 2.$$  Thus, if we apply this permutation $\sigma$ to a tuple $x = (x_1, x_2, x_3)$, we obtain the permuted tuple $$x_\sigma  = \sigma \cdot x = (x_{\sigma(1)}, x_{\sigma(2)}, x_{\sigma(3)}) = (x_3, x_1, x_2).$$

In particular, if $x = (x_1, x_2, x_3) = (\text{V}, \text{E}, \text{N})$, then $x_\sigma = (x_3, x_1, x_2) = (\text{N}, \text{V}, \text{E})$.

This is easy visualize if you simply replace the indices $1$, $2$ and $3$ in the definition of the permutation with the elements $x_1 = \text{V}$, $x_2 = \text{E}$ and $x_3 = \text{N}$ to be permuted, giving $${x_1\ x_2\ x_3 \choose x_3\ x_1\ x_2} = {\text{V E N} \choose \text{N V E} }.$$

The second example in your question appears to be incorrect: given the permutation $$\sigma' = {1\ 2\ 3 \choose 2\ 3\ 1}$$ and the input $x' = (x'_1, x'_2, x'_3) = (\text{T}, \text{E}, \text{N})$, the output should be $$x'_{\sigma'}  = \sigma' \cdot x' = (x'_{\sigma'(1)}, x'_{\sigma'(2)}, x'_{\sigma'(3)}) = (x'_2, x'_3, x'_1) = (\text{E}, \text{N}, \text{T}),$$ not $(x'_3, x'_1, x'_2) = (\text{N}, \text{T}, \text{E})$.  It would, however, be correct if we replaced the permutation $\sigma'$ with its inverse $$\sigma'^{-1} = {2\ 3\ 1 \choose 1\ 2\ 3} = {1\ 2\ 3 \choose 3\ 1\ 2}$$ (which, as it happens, equals the first permutation $\sigma$) obtained by swapping the rows and (optionally) re-sorting the columns in the two-line definition of $\sigma'$.


Current standard for hash function security parameter? When designing a hash function, what should be the secure input and output lengths? In particular, what lengths do I need for collision resistance?

Hashes should work on any number of input bits (almost all I/O parameters in cryptography are defined in bits). The output size for collision resistance should be twice the security level. So for a 128 bit level, use 256 bit hashes.


Is it safe to use a key as message in keyed hashing (HMAC)? Scenario:

User gives password.
A "password key" is derived from the password (e.g. by PBKDF2). A random salt is applied.
The password key is hashed with a HMAC algorithm (e.g. HMAC-SHA256), with itself as the key.
The salt and HMAC result are stored in database, for verification of the password (for further user logins).
The password key is used to encrypt other data.

Question: Is it safe to apply step 3 in terms of: can the password key be (easily) determined because it is known that it is the message to be HMACed?

Question: Is it safe to apply step 3 in terms of: can the password key be (easily) determined because it is known that it is the message to be hashed?

Yes, this should be fine, although you might as well use a constant as the message input when calculating the HMAC. Theoretically some implementation could be more lax with regard to side channel attacks about the message than the key, though I doubt that is an issue in practice.

Knowing the self-HMAC of the key will allow an attacker to easily verify their guessed passwords, but PBKDF2 will slow them down and anyway the speedup is not significant, compared to attempting to decrypt the data with the derived key.

(There are better alternatives to PBKDF2, like scrypt, argon2, bcrypt.)


"Seed" vs "seed key" The FIPS 140-2 Derived Test Requirements has a statement:

  AS07.09: (Levels 1, 2, 3, and 4) The seed and seed key shall not have the same value.

What is the difference between a seed and a "seed key"?

"seed" and "seed key" are NIST terminology talking about the X9.31 PRNG.  In particular, it has a state that consists of:

A 3DES or AES key (the "seed key")
A 64 or 128 bit current state (the "seed")

The requirement is to check to make sure that two don't happen to be the same (and give an error indication if they are).

If you're wondering "except for the AES-128 case, don't they have different lengths (and hence always distinct)", well, this requirement got interpreted (at least, for 3DES, when I went through the FIPS process) as "compare the seed to each of the individual DES subkeys, and fail if any of them match"; I presume something similar is done in the case of AES.

And, yes, this requirement is really stupid; it's #1 on my list of "why ignorant bureaucrats should not design cryptographic requirements".

Also, you're probably better off implementing one of the 800-90 RNGs; those are faster, better designed (now that the Dual-EC RNG was removed), and don't fall under this requirement.


In the proof that weak OWFs imply strong OWFs, why must the position of $y$ be random? When proving weak OWFs imply the existence of strong OWFs, the standard construction goes by concatenating several applications of the weak OWF (see, e.g., here). That is, given a weak OWF $f$, the following is a strong OWF:
$$F(x_1, \dots, x_t) = (f(x_1), \dots, f(x_t))$$
where $|x_i| = n$, $t = n p(n)$, and $p \in \text{poly}(n)$ such that
$$\text{P}_{x \in \{0,1\}^n}(A(f(x), 1^n) \in f^{-1}(f(x))) < 1 - \frac{1}{p(n)}$$
for every PPT $A$.

The proof is by a reducibility argument in which one presupposes there is a PPT $B$ which inverts $F$ with non-negligible probability (i.e., $F$ is not strong one-way) and then constructs a PPT $A$ which inverts the weak OWF $f$ with probability greater than $1 - \frac{1}{p(n)}$.

Most versions of the construction(*) I have seen are as follows: $A$ receives input $y = f(x)$ and $1^n$, where $x \in \{0,1\}^n$ is picked uniformily (but not revealed to $A$). $A$ then picks $i \in \{1, \dots, t \}$ and $x_j \in \{0,1\}^n$ uniformily for $j \neq i$ and runs $B$ on $Y = (f(x_1), \dots, f(x_{i-1}), y, f(x_{i+1}), \dots, f(x_t))$, thus (with non-negligible probability) inverting $y$. If $B$ does not produce a preimage, the procedure is repeated a certain number of times.

My question is: Why must $y$ be in a random position in $Y$? Why cannot, for example, $i = 1$ be fixed? After all, $y = f(x)$ and $x$ is guaranteed to be picked uniformily (as every other $x_j$).

These lecture notes here hint that this is to "balance the probabilities", which is unfortunately too vague for me to comprehend.

(*) I have also found an alternative construction in Oded Goldreich's "Computational Complexity: A Conceptual Perspective" in which $A$ does not pick $i$ randomly; instead, it iterates over each possible value of $i$. However, I can see how the two are equivalent.

As you write, the proof is via a reduction that transforms any adversary $B$ that inverts $F$ with non-negligible probability $\varepsilon(n)$ into an adversary $A$ that inverts $f$ with probability at least $1-1/p(n) \approx 1$.

Assume for simplicity that $f$ is an injective function. Consider a potential adversary $B$ that internally works as follows: given $Y=(y_1, \ldots, y_t)$, it checks whether $y_1$ belongs to a certain “special” $\varepsilon(n)$-fraction of the image $f(\{0,1\}^n)$. If so, it computes and outputs the preimage $X = F^{-1}(Y)$. Otherwise, it outputs nothing, i.e, it fails to invert this $Y$. Clearly, this $B$ satisfies the above hypothesis, because $y_1$ has an $\varepsilon(n)$ probability of being in the “special” set. (How $B$ checks $y_1$ and inverts $F$ is not important, because the reduction treats $B$ as a “block box.” So we can think of $B$ as using unbounded computation to perform these steps.)

Now, consider a reduction $A$ that works as you propose, by always “plugging in” its external challenge $y=f(x)$ in the first position, letting $y_1=y$, and choosing the rest of $Y$ itself. Clearly, $B$ outputs the preimage $F^{-1}(Y)$ if and only if $y$ belongs to the “special” set, which occurs with probability $\varepsilon(n)$. Therefore, $A$ succeeds in outputting the preimage $f^{-1}(y)$ with the same probability $\varepsilon(n)$. But this is not enough: we need $A$ to succeed with much larger probability $1-1/p(n)$.

If $A$ repeats its procedure many times, always letting $y_1=y$ but changing the other $y_i$, the probability of success would not improve: whether $B$ inverts $Y$ or not depends only on the value of $y_1=y$, and this does not change. (Remember, $A$ gets only one challenge value $y$ and needs to invert on it with high probability.)

The correct reduction and proof circumvents this problem by showing that there must exist some position $i$ for which there is a large $1-1/p(n)$ fraction of $y_i$ such that, if we choose the other $y_j = f(x_j)$ at random as described, then $B$ inverts on that $Y$ with non-negligible probability (over the choice of the $y_j$ alone). By guessing such $i$ at random (or enumerating all of them) and repeating the core procedure many times, we can ensure a high probability that $B$ actually inverts on one of the $Y$ we provide it, thereby telling $A$ a preimage of $y$. (The actual proof does not depend on $f$ being injective.)


What password hash function for the next 50 years? According to this report : http://www.ecrypt.eu.org/csa/documents/D5.4-FinalAlgKeySizeProt.pdf
SHA2-512, SHA3-512, Whirlpool and Blake2b are hash functions that could be safe for the next 50 years.

For a system that will never receive security updates, to hash passwords, what of these 4 functions should I use for maximum security ?

None. Cryptographic hashes are not directly suitable to store password hashes.

You should use a password hash (also known as a Password Based Key Derivation Function or PBKDF if it is used to derive a key) such as one of the secure variants of Argon2 to store passwords, not a generic cryptographically secure hash function.

However, if you're working with passwords then not updating your security for 50 years is madness; there is a lot of debate on the security of passwords as it is. Passwords generally only deliver a certain amount of security, often in the range 30-50 bits. That already doesn't provide enough entropy, let alone in 50 years time.

Password hashes add a work factor, but in 50 years this work factor may well have become insignificant due to progress in chip manufacturing. So the additional work factor (e.g. introduced by an iteration count) has become a much smaller hurdle to take. Note that finding passwords is an easily parallelized task, so it is not very dependent on single core CPU speeds.

You could also go for 128 or even 256 bits of security and let people write down a randomly generated password / key instead (for instance as 32 / 64 hexadecimal digits). That way you could use a simple hash just to hide the password / key at rest. For this you could use one of the hash algorithms above; I'd go for SHA-3. However, due to the larger password, your password management becomes more complicated as humans will probably not be able to remember it.

This can be solved by having people use a password manager that is secured with an easy to remember / less complex password or phrase. Such a password manager should then be directly available to hackers. Another advantage of using a password manager is that the passwords can be updated if a password has possibly become vulnerable in any way.

Similarly you could encrypt with e.g. a large EC public key and protect the private key of the key pair. However, most common asymmetric algorithms are vulnerable against quantum computers. Those could well become large and interconnected enough in the next 50 years. Post Quantum Cryptography is by and large still the domain of specialists (even more than common modern crypto).


Are there any Truth Table to Boolean expression converters? I am working on Bent functions that are of interest in cryptography. I developed an algorithm that construct such functions. However, I need some tools to calculate boolean expression from the truth table. Is there such a application or applet available? (Actually I am interested in expressions without any NOTs).

It depends on what you are interested in, when building your expression. If you want to optimize for speed and/or expression size, then the problem is hard, and no good solution is known. You can either try to enumerate all expressions, looking for a match with your table (this is exponential in the size of the expression, so it becomes prohibitive real fast); or you can start with a generic expression as a tree of multiplexers then try to find local shortcuts.

You can often work with the "fake multiplexer": for inputs $a$ and $b$, and control $c$, output $a \oplus (b \wedge c)$: in this way, the bit $c$ selects between values $a$ (if $c = 0$) and $a \oplus b$ (if $c = 1$). For a function $f : n \rightarrow 1$ ($n$ input bits, $1$ output bit), you work recursively:

An expression with no input is either $0$ or $1$ (it is a constant).
You define $f_0 : n - 1 \rightarrow 1$ such that $f_0(x_1, x_2,... x_{n-1}) = f(x_1, x_2,... x_{n-1}, 0)$ (that's the function $f$ when the last bit is $0$).
You define $f_1 : n - 1 \rightarrow 1$ such that $f_1(x_1, x_2,... x_{n-1}) = f(x_1, x_2,... x_{n-1}, 1)$ (that's the function $f$ when the last bit is $1$).
You compute the boolean expression $e_0$ for $f_0$, and the boolean expression $e_1$ for $f_0 \oplus f_1$.
The expression for $f$ is now $e_0 \oplus (x_n \wedge e_1)$.

There has been such efforts for some table-based operators used in cryptographic algorithms, e.g. DES S-boxes. See also this article.

(Note: if you have only bitwise AND, OR and XOR, and not access to constants, then you cannot build all functions; in particular, you won't be able to make a $1$ out of an all-$0$ input. If you really don't want a NOT or the equivalent "$\oplus 1$", and the output of your function for an all-zero input is $1$, then there is no solution. On the other hand, if the function output for an all-zero input is $0$, then you can make a serviceable $1$ by ORing all input bits together.)

(Note 2: if you want to optimize for speed on software platforms, be aware that not all processor architectures offer the same set of operations. On some processors you have elementary XORNOT or NOTXOR. This can change the achievable speed quite a lot.)


DES Encryption Algorithm all 64 bits for key instead of 56 bits Would a DES algorithm that uses all 64 bits for the key instead of just the 56 bits be more secure? I have been thinking about it but those 8 bits used for parity are very useful and but including them in the key could potentially make it more easily cracked.

From Wikipedia, it stated that the 56 bit key was cracked in 4 days due to hardware. Now if we include the 8 parity bits to make it a 64 bit key, would that make the key crackable after 1024 days? My math: 2^8 * 4 = 1024 days. Assume we use the same hardware.

If we included the 8 parity bits, would it have made the security of DES substantially stronger?

Yes, it would be more secure if they were used correctly. But as it would require a substantially different algorithm, you really would not be talking about DES anymore.

Brute forcing usually scales exponentially with the size of the key. However, if the algorithm is substantially altered then it is required to analyze the algorithm again.

Note that AES is both faster and stronger than DES. There is no need to (substantially) alter DES now there are many better algorithms available.

(Triple) DES is mainly used for backwards compatibility now. The keysize of DES is too small key size to be of practical use; triple DES has a blocksize that is too small to be used for uses in modern modes of encryption (CTR, GCM etc).