Transforming a key into a seed with the most entropy I'm making a very simple encrypter in C# which is basically a Stream cipher.
The user enters a key(password), converted to a seed for a pseudo-random generator, and the pseudo-random generator generates the numbers used to shift the characters. The decrypt process goes the same, but then in inverse.

Here's the pseudo-code I use:

1. Get the characters
2. Initialize a seed with the value 0
3. Loop through each character, adding the characters' value to the seed
4. Return the seed

But that has a problem. What if I have a (poor) password, like Hello.
The encrypted output would be the same if I used eHlol or loeHl.
You can write this password in 5! = 120 ways. That's not good!

So I came up with a solution:

1. Get the characters
2. Initialize a seed with the value 0
3. Loop through each character, adding the characters' value times it's position to the seed
4. Return the seed

But that's not good either. With a large password, you would get huge skips in numbers if you modify the last number. That's bad, because you want the most permutations possible for a random number generator.

Example:

Last character(12) has a value of 10
10 * 12 = 120
Then you change it to 11
11 * 12 = 132
          ^ gap of 12

Then I changed step 4 into this:

4. Return the seed divided by the length of the key

That's not a good option either, because with large passwords it wouldn't really matter what the value was of the first character in order to make a difference.

Example:

Password size: 10
1/10 = 0
8/10 = 0

So what's a good method for user-based passwords?

What you're looking for is called a key derivation function, and more specifically a key stretching function.

A key derivation function takes some variable-size material and turns it into a fixed-size key in a deterministic way, such that calling the same function on the same input yields the same key, and the original material cannot be reconstructed from the derived key except by trial and error.

A key stretching function is a particular kind of key derivation function that adds an element of slowness. This is necessary when the input consists of low-entropy data such as a password. The legitimate user only has to calculate the result once, but an attacker who attempts to guess the password has to make the calculation once per guess, so the slowness hurts the attacker more than the legitimate user. Note that the function must be designed so that each attempt requires a complete new calculation: there is no work that can be factored between computing f(Hello) and f(Hellp).

In addition to taking the password as input, you should pass a unique label (a string that doesn't need to be kept secret), so that if you ever want to derive a different key from that password, you can pick a different label. The label should typically include at least the name of your application, the user name or ID, and a version counter. The label also needs to be unique in that nobody else in the world uses the same label, because if the same label is reused many times, an attacker could pre-compute stretched keys for common passwords for that particular label.

A key stretching function is also known as a password-based key derivation function. These functions are also what is needed to hash passwords (the salt in password hashing corresponds to the label in key stretching). Common choices are PBKDF2, bcrypt and scrypt.

Note that the stretched key will not have more entropy than the password, only as much entropy as the password. That's the best you can hope for. Making the stretching operation slow reduces the impact of brute force attempts, but it cannot eliminate them. If you produce a 128-bit key from a password that's chosen from a 4000-word dictionary, the resulting key still only has 12 bits of entropy — less if the password wasn't chosen randomly.


Vulnerability of low value generated key I have read here that Elgamal is resistant to brute-force attack, because the group to where the key is selected is very large. But since the key generation is random, (i assume)there is a chance that the key generated is lower than the recommended.

example, the recommended keylength is 1024 bits, but the key generated ($x$) was really small, way under 512 bits. The adversary can see that the $g^x$
is indeed small (smaller than $g^{2^{1024}}$ and $g^{2^{512}}$), limiting his/her search.

My question is, would a public key encryption be vulnerable to brute-force attack the moment it generated a low value key ?
If it is, what are the countermeasures ?

The chance that such a key is generated randomly is negligibly low. These 512 bits of security are for both the higher order and lower order bits. The chance of generating such a value is one in $2^{512}$ (each time you try, assuming that each value in the 1024 bit number is about equally valid). That means you can try forever before getting such a low value.

Just try and run your random bit generator and wait for it to generate 512 bits of zeros in succession. That's similar as guessing a 512 bit key. It is simply not going to happen. No such key exists or will exist if it was generated randomly.

As it is impossible to create such a key at random, there is very little reason searching for such a key either, or to limit the value to a minimum. That kind of effort is better put into making sure that the random bit generator is working correctly and to make sure that the key pair generation process isn't erroneous in itself.


What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman? How are the three problems Discrete Logarithm, Computational Diffie-Hellman and Decisional Diffie-Hellman related?

From my understanding, since the Discrete Log (DL) Problem is considered hard, then so is CDH.
And since CDH is considered hard, then so is DDH.

On the Wikipedia article for DDH it mentions that DDH is considered a stronger assumption than CDH. What does that mean?

The problems:

The Discrete Logarithm problem: Given $y$, find $x$ so that $g^x = y$.
The Computational Diffie-Hellman problem: Given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (but not $x_1$ and $x_2$), find $y = g^{x_1·x_2}$.
The Decisional Diffie-Hellman problem: Given $y_1, y_2, y_3$, decide whether they are of the form $y_1 = g^{x_1}$, $y_2 = g^{x_2}$ and $y_3 = g^{x_1·x_2}$ for some $x_1, x_2$ (which you don't have to find). Assume with 50% probability they are really of this form, and with 50% probability simply randomly selected, and you have to guess right with significantly better probability than 50%.

All three of these are defined in any (multiplicatively written) group, and are hard in some groups, while easy in other ones. (Actually, we don't really need a group, a semigroup with some generator $g$ is enough. But it is more interesting in groups.)

Which one is harder?

Now, if you have a machine (program, oracle) which solves (efficiently) the Discrete Logarithm Problem in some group, you can easily construct a solver for the Computational Diffie-Hellman problem (in the same group):

just compute $x_2$ from $y_2$ and calculate $y = (y_1)^{x_2}$.

There is no (generic) known way for the other direction.

If you have a solver for the Computational Diffie-Hellman problem, you can also decide the Decisional Diffie-Hellman problem:

just compute $y$ to $y_1$ and $y_2$, and checking $y = y_3$.

There is no (generic efficient) known way for the other direction.

This means, DDH is at least as easy (or even easier) as CDH, and CDH is as least as easy as DL. Or, other way around, DL is at least as hard as CDH, and CDH is at least as hard as DDH.

An even another way of looking at it is the "assumption to be hard", where "hard" is defined as "not doable for a reasonable user".

If DDH is hard, then CDH must be hard too (but not necessarily the other way around).
If CDH is hard, then DL must be hard (but not necessarily the other way around).

Thus, the hardness of DDH is a stronger assumption (is valid in fewer groups) than the hardness of CDH, which itself is still stronger than the hardness of DL.

As Thomas Pornin mentioned in a comment, there are some elliptic curve groups where DDH is easy, but CDH and DL are (assumed to be) hard, and which are used in pairing based cryptography. This is a good indication (though not yet a proof) that the DL and CDH problems are really strictly harder than DDH.


How safe is a prime with $P=2 \cdot Q \cdot R \cdot S \cdot t+1$ for discrete logarithm? How to enhance/compare? To get some certain properties for my use case I need a prime $P$ which has the form:

$P=2\cdot Q \cdot R \cdot S \cdot t+1$
with $Q,R,S,t$ primes as well.

Why that form - Use case

Together with this three factors $q,r,s$ are used. The values $v$ of interest have the form
$v(a,b,c) = q^ar^bs^c\bmod P$,

Those factors have the following properties:
$q^Q \equiv 1 \bmod P$
$r^R \equiv 1 \bmod P$
$s^S \equiv 1 \bmod P$

and the equation holds:
$q^{a+dQ}r^{b+eR}s^{c+fS} \equiv q^{a}r^{b}s^{c} \bmod P$, with any $d,e,f \in \mathbb{N}$

so

$|\{v(a,b,c), \forall a,b,c \in \mathbb{N}\}| = QRS = \frac{P-1}{2t}$

If another factor is added:

$v(a,b,c,T) = q^ar^bs^c T\bmod P$, with any $T\in\mathbb{N} < P$

you can achive:

$|\{v(a,b,c,T), \forall a,b,c,T <P \in \mathbb{N}\}| = P-1$
Two different $T$ have $0$ or all values equal.

That those properties work the prime $P$ need to have the form:

$P=2QRSt+1$

(constructed myself, there might be better options)

It also works with $t=1, T=1$. With this half of all values ($(P-1)/2$) can get generated.

How safe is such a prime?

A user and also possible attacker has access to the source code and all runtime variables. For a given $v$, which is not computed at the local PC (its just a random number) the attacker should not be able to determine the values $a,b,c$ and $T$ in:

$v(a,b,c,T) \equiv q^ar^bs^c T\bmod P$

or to be more exact, he should not be able to derive one $v'$ out of another $v$

$v'(a',b',c',T') \equiv v \cdot q^{a'}r^{b'}s^{c'} T'\bmod P$

The attacker knows all other values $P,Q,R,S,q,r,s,t$

$Q,R,S$ need to be about the same size, $t$ is much smaller $t\ll Q,R,S$, in use case less than $t<1000$;

I read about safe and strong primes. Both don't hold for that kind of prime form. How much safety get lost with that form? Would it help if

$Q,R,S$ are safe/strong primes

if $P+1$ has a large prime factor

You know about other enhancements?

Comparison to normal discrete logarithm

The form above is different to the normal discrete logarithm problem form like:

$v'\equiv g^x \bmod P'$ and finding $x$ for a given $v'$

I'm not familiar with all discrete log. solving algorithms. Does it make a difference if there is only one base ($g$) or three of it ($q,r,s$)? Three harder or faster solving?

Assuming $S$ is a safe prime and largest out of $Q,R,S,t$. Could you compare the mean solving time complexity of

finding $a,b,c,T$ for a given v solving:

$v \equiv q^ar^bs^c T\bmod P$

with finding d for a given $v'$

$v'\equiv g^d \bmod S$, with g prime root of $S$

Or is it harder/faster? How would a normal form look like which has about the same solving time (to get an idea how much worse my form is)?

(toy) example

$P=35531=2 \cdot 11 \cdot 17 \cdot 19 \cdot 5+1$
$r=4999, q=21433, s=3181$

It does work with Silver-Pohlig-Hellman algorithm

As theREALyumdub pointed out in comments that Silver-Pohlig-Hellman might be an option I did some test and it did work. Thanks for that hint.

In case $t=1$ we get the results $a,b,c$ right out of the algorithm. For other $t$ the results $a,b,c$ aren't correct. Some extra work need to be done there. It does work if you multiply value $v$ with the inverse of used $T$ first. However this $T$ is unknown in use case. Chances are high there is a better way but the naive way is good enough for my case. As I wrote in post $t<1000$ so we could just multiply with a random number and get the correct result with chance $\frac{1}{t}$.

So it is not harder than:
finding d for a given $v'$

$v'\equiv g^d \bmod P$, with $g$ generator of a subgroup with size $G=\max(Q,R,S)$

Remaining questions:

Does it make a difference if you solving only for a subgroup? Or is equation above, as hard as
$v'\equiv g^d \bmod G$

Is there any way to speed up finding the correct $T$ factor? While a
constant factor of 1000 is asymptotically equal but in real world it can make a huge difference.

However this transition used in Silver-Pohlig-Hellman algorithm destroys the idea of hiding the dimensions in one number. Three separate equations with big prime factors would do the same job.

Although the question is not fully answered it's enough for me. The remaining questions above are not specific to this case. I might create some new threads about those. If so, I will link them here.

$v = T\cdot g^a\mod P$
proof if same factor $T$ was used -->  $v_{T_1}^{QRS} \equiv v_{T_2}^{QRS} \mod P$  iff same group

links show easy to do -> this kind of prime and usage has not benefits :(


identity based cryptography (IBE) without key escrow I am trying to find a method of implementing identity based cryptography to generate key pairs without the use of a trusted PKG that holds the private keys. Has there been any solutions to overcoming this challenge?

It's not possible to completely get rid of the PKG, but one can limit the amount of trust on a (single) PKG through distributed key generation --- see BF01,§6. On the other hand, one could hold the PKG accountable in case it behaves malicously --- see Goy07.


How can we create the AES S-box using a different irreducible polynomial? The substitution-value of input byte $\mathtt{C2}$ is $S[\mathtt{C2}]=\mathtt{2F}$. This comes from applying the Euclidean algorithm to $A(x)A^{-1}(x)\equiv 1\pmod{p(x)}$, where $A(x) = x^7+x^6+x$ (from $\mathtt{C2}$) and $p(x) = x^8+x^4+x^3+x+1$ (the $AES$ irreducible polynomial). On finding remainder $r=1$ we apply the extended Euclidean algorithm to find $A(x)^{-1}=x^5+x^3+x^2+x+1$ or $\mathtt{2F}$ as expected.

However, this is a lot of work by hand. I am not a programmer but I have managed to write $AES$ in Excel. I would like to change the irreducible polynomial for another suitable one, but I would then need to create a corresponding $S-box$ and doing this by hand is a lot of work. So my questions are:

Is there an online program that can do these calculations?
Is there a quick way to do it in Excel?
Since the irreducible polynomial will be different from the original, how do I find the matrix for the corresponding affine transform?

Thank you for any help or advice.

I would like to change the irreducible polynomial for another suitable one

Suitable in what way? Are you trying to make a cipher with improved hardware performance or resource usage? Trying to increase the security of the cipher? Any change would result in a similar cipher but would no longer be AES.

1: I believe Sage can perform the calculation if you can write the correct script, and I believe they have an online version

2: not easily, you need to generate multiple tables, then do all the math. I can do it quickly in VB6, and Excel uses a VB type script language, but it may not be comprehensive enough to get it done, and since it would not be compiled, it would be slower, and you would still need to write a substantial amount of code

3: you have to choose it. The affine transform in AES was chosen based on the polynomial so that the s-box would meet certain criteria, you could simply brute force all of them (there are about 65000) and choose the best result. That is the last step, and the most computationally expensive, doing it in excel would take an absurd amount of time, probably years.


Adversary to Any Collision Resistance Hash Function I'm reading a notion Any Collision Resistance for Hash Functions. In the lecture define a collision finder CF.

  CF is said to $(t,\epsilon)$-break the family of hash functions $F_K$
  if the running time is at most $t$, and the probability that CF, on
  input K, outputs a collision $M,M'$ for $F_K$ is at least $\epsilon$. Here the probability is take over $K$ (key space) and CF's random coins.

My question is What does it means that the probability is take over $K$ and CF's random coins?

CF is a randomized algorithm with input $K$. As a randomized algorithm, it is allowed to do random decisions in its calculations – this can be thought of flipping a coin. The results of these coin-tosses (i.e. a list of heads and tails) – can be thought as another "input".

For each key $K$ and each list of coins, the algorithm either finds a collision or doesn't.

Now we assume some random distribution of both (usually a uniform distribution of the keys, and an uniform distribution of each of the coin tosses), and can determine the probability of the success.

This probability is what is meant in your definition.

For example, if you have a hash function family $F_K$ with $2^{50}$ keys, a (quite dumb, but fast) algorithm would be to toss 200 coins to generate two 100-bit strings and output them. They either are a collision or are not, and it depends both on the key and the tossed coins whether it works. Calculate the number of combinations of "good" keys and tosses on one hand, divide by the total number of keys times the total number of possible coin toss results (this is $2^{50} · 2^{200}$). Assuming that for half of the keys exactly one collision (of 100-bit inputs) exists (and for the other half of the keys there is none), we would have $$P(\text{algorithm finds collision}) = \dfrac{2^{49} · 2 }{2^{50} · 2^{200}} = \frac{1}{2^{200}}.$$ (This is 2 instead of 1 in the first fraction, because if $F_K(a) = F_K(b)$, we also have $F_K(b) = F_K(a)$, and the algorithm could find any of them.)


Fiat-Shamir transform to Sigma protocols to turn into NIZK I'm reading about the Schnorr's zero-knowledge proof for DLOG and the Sigma protocol for DH tuple proof, and I want to know how one applies Fiat-Shamir transform to both of them, to turn them into NIZK proofs.

I know that Prover would need to hash some public parameters to get the challenge, and then compute a proof for that challenge, so that the Verifier can also compute the same challenge using the hash from the public values, and can verify the proof, and there is no interaction between them. But, which of the public parameters one needs to hash to get a challenge? More precisely, how does the challenge look in NIZK proof, and is the proving and verification steps left the same? Also is the security guaranteed due to the random oracle model and usage of hash functions or there is something else going on in the NIZK proofs?

The idea is that the hash function replaces the random pick of the verifier at step 2. So you must hash the public statement ($h$ for protocol 6.1.1, $(u,v)$ for protocol 6.2.2) with  the commitment sent by the prover at step one ($a$ for protocol 6.1.1, $(a,b)$ for protocol 6.2.2).

The prover cannot guess the challenge $e$ before he generates the commitment  $a$, because  the commitment is used to generate the challenge.
The intuition is that since the random oracle act as an honest verifier, it is equivalent to interact with an honest player or with the random oracle. There is no other change.

If the prover hashes only the public parameter, then he can choose the challenge $e$ before he generates the commitment $a$. For instance, in protocol 6.1.1, the prover can forge a proof $(a,z)$ such that $g^z=ah^e$ by computing $e=H(h)$, choosing $z$ at random  and computing $a=g^z / h^e$.

On the other hand, hashing the public parameters prevent the attacks where an adversary has access to a proof oracle that forges proofs for chosen statements. For instance, for any chosen $x$, knowing a proof $(a=g^r,z=r+H(a)w)$ for the statement $h'=hg^x=g^{w+x}$ (where the statement is not used in the hash) for the non-interactive version of protocol 6.1.1, you can forge a proof $(a, z + H(a)x = r+H(a)(w+x))$ for the statement $h$.

Finally, the non-interactive proof for protocol 6.1.1 can be defined as follows:

chose $r$ and compute $a=g^r$
compute $e=H(a||h),$ where $H$ is a hash function and $||$ denotes the concatenation.
compute $z=r + ew$
return the proof $(a,z)$


Certificate validation on an IoT device using few bytes I'm trying to validate if an IoT device is authentic or it's a fraud. The problem is I only have 17 bytes to do that verification.

What if I let the IoT device sign the message with the private key and the client will check in a server if that message was signed with the correct private key like the RSA algorithm.

But the problem is that I don't think only 17 bytes is secure. I'm asking if you guys know some method/algorithm to do this verification with only 17 bytes max, thank you for all your help.

Generally you'd let the device establish a symmetric / secret key first, e.g. using ECDH and then use that secret key with a MAC algorithm to perform the message authentication. In that case 16 bytes / 128 bits is plenty.

For direct signatures, the BLS signature scheme is probably still the best out there, but for 128 bit level encryption - the lowest we commonly aim for - you'd still need a 384 bit signature.


Conditional decryption Is it possible for one party to encrypt some data and have another party (unknown to the first party) view that original data if a certain condition is met?
I cannot find any information about this despite numerous searches.  I  might have the terminology wrong, or perhaps... it is impossible!
I read about zk-SNARKS, and as I understand it, this technique is used to prove a computation on an encrypted value or perhaps show the opening of some commitment in a set.
I thought perhaps you could set a condition in a circuit.  Say (for simplicity), using a (public) input integer x less than 100 (or maybe part of a set or something), you could print secret data y. But that would mean the encrypting party would have to produce an unsatisfied partial SNARK somehow. Then the person that wants to attempt decryption would have to input their integer later.
I guess it's not a great example unless the input is provably random, but is there some technique to do this? I only mention SNARKS as it's the only thing I could think of where you can have arbitrary conditions like this. In reality, I was thinking of something where the data revealed could be any size, like a huge text file or something other than an integer y.

"Conditional decryption" title could be confusing.
A ciphertex verification was demonstrated at Bitcoin workshop Financial Crypto 2016, to be a valid solution of a Sudoku instance. No third (another) party required.
Technically, we prove satisfiability of an R1CS system with a SNARK proof, and "computation on an encrypted value" could be expressed as R1CS equations, leading to just one single proof. One could also create "some secret plaintext is less than parameter AND this ciphertext is valid for that plaintex and some secret key" circuit.
Sure one could make a comparator circuit with a parameter (100 in your example), in hope to get a secret in logarithmic number of verification queries, alledgely rendering encryption useless. However, there is no oracle with SNARKs, only one single snark-proof for specific parameter value (for example, =100). If a prover would create too many comparator snark-proofs himself, he will break his encryption.


Is braid-based cryptography proven insecure when looking towards post-quantum cryptography? Braid groups has drawn the attention of cryptographers for a few years, as a promising platform for post-quantum cryptographic protocols. The security of the proposed schemes mostly relied on conjugacy problems, and attacks against this problem were discovered, and cryptographers lost interest in those braid groups. But as far as I know, those attacks don't completely break the security of braid groups. For example, conjugacy problems can be solved by computing the USS (Ultra Summit Set) of a braid, but this set can have exponential size in the length of the braid (for some classes of braids).

I don't know much about other attacks on braid groups, but do they definitely put an end to any applications of braids to cryptography? If we could highlight properties of braids comparable to bilinear pairings for elliptic curves, allowing some of the related advanced protocols in a post-quantum world, would they become more interesting or are they definitely too weak for cryptography?

EDIT:

Note that my question didn't mean to say "is anyone still interested in braids", but rather "do we know attacks (that I am not aware of) on conjugacy related problems for braids that definitely label them as 'not suitable for cryptography'". I am certainly not looking for (or expecting)
 as an answer any opinion about how interesting they are.

I believe that the conjugacy search problem is broken by probabilistic attacks (see chapter 7).  I am not sure if this completely ends braid cryptography, however, since there are other difficult problems in braid groups that have not been studied extensively.


Why are polynomials chosen with coefficients in $GF(2^{8})$ in Section 4.3 of NIST FIPS 197 for implementing AES? I was trying to understand  AES (Rijndael) from a very mathematical perspective. I'm quite new to abstract algebra and Galois Fields. I understood that we are considering a byte (8 bits) as a polynomial in $GF(2^{8}) $ where the coefficients are either $0$ or $1$ i.e. they are elements of {0, 1} and all operations are done modulo the Rijndael polynomial 0x11b ($x^{8} + x^{4} + x^{3} + x + 1$).
But Section 4.3 confused me a little when they are explaining that the coefficients themselves are considered as "bytes" i.e values from $0$ to $255$ . Can anyone please explain to me, why is this context switching possible, or why is it done?

  Four-term polynomials can be defined - with coefficients that are finite field elements - as:
  $a(x) = a_{3} x^{3} + a_{2} x^{2} + a_{1} x + a_{0}$ (4.5)
  which will be denoted as a word in the form $ [a_{0} , a_{1} , a_{2} , a_{3} ]$. Note that the polynomials in this
  section behave somewhat differently than the polynomials used in the definition of finite field
  elements, even though both types of polynomials use the same indeterminate, x. The coefficients
  in this section are themselves finite field elements, i.e., bytes, instead of bits; also, the
  multiplication of four-term polynomials uses a different reduction polynomial, defined below.
  The distinction should always be clear from the context.

Every help will be greatly appreciated!!!

The irreducible polynomial you showed above will create a polynomial field. (0x11b=283=100011011).
-now last nearest degree of 2 is ${2^8=256}$ hence all the operation of a field within the range of ${0,1..,255}$,

It is a Byte operation because the range ${0,1,2,...,255}$ can be represented as a byte(8 bit) and the field operation are performed and reduced to modulo ${x^8+x^4+x^3+x+1}$
Here, The statement ${\{0,1\}^8}$ means it can be a binary number of 8 bits.
But in case of normal polynomial the coefficient can be from set N,Z,R,C. which is not the case in AES.


Is Wikipidia wrong about Schnorr Signatures? Wikipidia says Schnorr signature generation is defined like this:

Y = x * G //this is the key we are trying to provide a signature for
k = random scalar
r = k * G
e = Hash_to_scalar(r || message)
s = k - xe
signature = (s, e)

This seems correct, but then to verify it's defined as:

r = s * G * e * Y
e = Hash_to_scalar(r || message)

Shouldn't it be:

r = s * G + e * Y
e = Hash_to_scalar(r || message)

because:

r = k - xe * G + ex * G == k * G; //this works
r = k - xe * G * ex * G != k * G; //this doesnt work

Or have I made a silly mistake somewhere?

The equation in Wikipedia is r = s*G + e*Y, and not r = s*G * e*Y

Thus, r = s*G + e*Y = (k - xe)*G + e*(x*G) = k*G - xe*G + xe*G = k*G


Does secp256r1 or secp256k1 use a=-3? I saw a post here which I think states that for P256, a is equal to -3.

Why is elliptic curve parameter $a=-3$ somehow special

I am not sure if this is correct, or maybe I am misunderstanding something about elliptic curves?

I thought that a=0 for secp256r1 and some big number for secp256k1?

If we change the value to a=-3, then we no longer have secp256r1 and secp256k1 right?

The equation for secp256k1 is $y^2 = x^3 + 7$, so that $a = 0$ and $b = 7$.

The equation for secp256r1, also known as NIST P-256, is $y^2 = x^3 - 3x + b$, where $b$ is 41058363725152142129326129780047268409114441015993725554835256314039467401291; here $a \equiv -3 \equiv p - 3 \pmod p$ where $p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$ is the characteristic of the field underlying secp256r1.

If you change the curve parameters, you get a different curve.


Can you give me a summary of cryptographic hardness assumptions? Until recently, I had a link to a website which summarizes up-to-date cryptographic hardness assumptions.
But, unfortunately I cannot find it.

The webpage is categorized well problems such as, DL problem, Factorization, Finite field, DH problems.
More importantly, such problems are very well organized.
For example, DH problem and most of its variants are listed with problem definition, introduced source (authors, paper name, etc.), and its applications.

What I had was not pdf file nor book chapter, just a webpage.
As I remember, its web structure is similar to http://hyperelliptic.org/ECRYPTII/vampire/

I think such a summary would be very helpful.

One of the links in the comments points to this paper, which has a very extensive list of various hardness assumptions used in cryptography. At the end of this post is an addendum that includes problems not found in the mentioned paper. The following is basically the table of contents from the paper:

Discrete logarithm problem

DLP: discrete logarithm problem
CDH: computational Diffie-Hellman problem
SDH: static Diffie-Hellman problem
gap-CDH: Gap Diffie-Hellman problem
DDH: decision Diffie-Hellman problem
Strong-DDH: strong decision Diffie-Hellman problem
sDDH: skewed decision Diffie-Hellman problem
PDDH: parallel decision Diffie-Hellman problem
Square-DH: Square Diffie-Hellman problem
l-DHI: l-Diffie-Hellman inversion problem
l-DDHI: l-Decisional Diffie-Hellman inversion problem
REPRESENTATION: Representation problem
LRSW: LRSW Problem
Linear:  Linear problem
D-Linear1:  Decision Linear problem (version 1)
l-SDH: l-Strong Diffie-Hellman problem
c-DLSE: Discrete Logarithm with Short Exponents
CONF: (conference-key sharing scheme)
3PASS: 3-Pass Message Transmission Scheme
LUCAS: Lucas Problem
XLP: x-Logarithm Problem
MDHP: Matching Diffie-Hellman Problem
DDLP: Double Discrete Logarithm Problem
rootDLP: Root of Discrete Logarithm Problem
n-M-DDH: Multiple Decision Diffie-Hellman Problem
l-HENSEL-DLP: l-Hensel Discrete Logarithm Problem
DLP(Inn(G)):  Discrete  Logarithm  Problem  over  Inner  Automorphism Group
IE: Inverse Exponent
TDH: The Twin Diffie-Hellman Assumption
XTR-DL: XTR discrete logarithm problem
XTR-DH: XTR Diffie-Hellman problem
XTR-DHD: XTR decision Diffie-Hellman problem
CL-DLP: discrete logarithms in class groups of imaginary quadratic orders
TV-DDH: Tzeng Variant Decision Diffie-Hellman problem
n-DHE: n-Diffie-Hellman Exponent problem

Factoring

FACTORING: integer factorisation problem
SQRT: square roots modulo a composite
CHARACTERd: character problem
MOVAd: character problem
CYCLOFACTd: factorisation in Z[θ]
FERMATd:  factorisation in Z[θ]
RSAP: RSA problem
Strong-RSAP: strong RSA problem
Difference-RSAP: Difference RSA problem
Partial-DL-ZN2P: Partial Discrete Logarithm problem in Z∗n
DDH-ZN2P: Decision Diffie-Hellman problem over Z∗n
Lift-DH-ZN2P: Lift Diffie-Hellman problem over Z∗n
EPHP: Election Privacy Homomorphism problem
AERP: Approximate e-th root problem
l-HENSEL-RSAP: l-Hensel RSA
DSeRP: Decisional Small e-Residues in Z∗n2
DS2eRP: Decisional Small 2e-Residues in Z∗n2
DSmallRSAKP: Decisional Reciprocal RSA-Paillier in Z∗n2
HRP: Higher Residuosity Problem
ECSQRT: Square roots in elliptic curve groups over Z/nZ
RFP: Root Finding Problem
phiA: PHI-Assumption
C-DRSA: Computational Dependent-RSA problem
D-DRSA: Decisional Dependent-RSA problem
E-DRSA: Extraction Dependent-RSA problem
DCR: Decisional Composite Residuosity problem
CRC: Composite Residuosity Class problem
DCRC: Decisional Composite Residuosity Class problem
GenBBS: generalised Blum-Blum-Shub assumption

Product groups

co-CDH: co-Computational Diffie-Hellman Problem
PG-CDH: Computational Diffie-Hellman Problem for Product Groups
XDDH: External Decision Diffie-Hellman Problem
D-Linear2:  Decision Linear Problem (version 2)
PG-DLIN: Decision Linear Problem for Product Groups
FSDH: Flexible Square Diffie-Hellman Problem
KSW1:  Assumption 1 of Katz-Sahai-Waters

Pairings

BDHP: Bilinear Diffie-Hellman Problem
DBDH: Decision Bilinear Diffie-Hellman Problem
B-DLIN: Bilinear Decision-Linear Problem
l-BDHI: l-Bilinear Diffie-Hellman Inversion Problem
l-DBDHI: l-Bilinear Decision Diffie-Hellman Inversion Problem
l-wBDHI: l-weak Bilinear Diffie-Hellman Inversion Problem
l-wDBDHI: l-weak Decisional Bilinear Diffie-Hellman Inversion Problem
KSW2:  Assumption 2 of Katz-Sahai-Waters
MSEDH: Multi-sequence of Exponents Diffie-Hellman Assumption

Lattices

Main Lattice Problems

SVPγp:  (Approximate) Shortest vector problem
CVPpγ:  (Approximate) Closest vector problem
GapSVPpγ:  Decisional shortest vector problem
GapCVPpγ:  Decisional closest vector problem

Modular Lattice Problems

SISp(n,m,q,β):  Short integer solution problem
ISISp(n,m,q,β):  Inhomogeneous short integer solution problem
LWE(n,q,φ):  Learning with errors problem

Miscellaneous Lattice Problems

USVPp(n,γ):  Approximate unique shortest vector problem
SBPp(n,γ):  Approximate shortest basis problem
SLPp(n,γ):  Approximate shortest length problem
SIVPp(n,γ):  Approximate shortest independent vector problem
hermiteSVP: Hermite shortest vector problem
CRP: Covering radius problem

Ideal Lattice Problems

Ideal-SVPf,pγ:  (Approximate)  Ideal  shortest  vector  problem  /  Shortest polynomial problem
Ideal-SISf,p q,m,β:  Ideal small integer solution problem

Miscellaneous Problems

KEA1:  Knowledge of Exponent assumption
MQ: Multivariable Quadratic equations
CF: Given-weight codeword finding
ConjSP: Braid group conjugacy search problem
GenConjSP: Generalised braid group conjugacy search problem
ConjDecomP: Braid group conjugacy decomposition problem
ConjDP: Braid group conjugacy decision problem
DHCP: Braid group decisional Diffie-Hellman-type conjugacy problem
ConjSearch:  (multiple simlutaneous) Braid group conjugacy search problem
SubConjSearch:  subgroup restricted Braid group conjugacy search problem
LINPOLY : A linear algebra problem on polynomials
HFE-DP: Hidden Field Equations Decomposition Problem
HFE-SP: Hidden Field Equations Solving Problem
MKS: Multiplicative Knapsack
BP: Balance Problem
AHA: Adaptive Hardness Assumptions
SPI: Sparse Polynomial Interpolation
SPP: Self-Power Problem
VDP: Vector Decomposition Problem
2-DL: 2-generalized Discrete Logarithm Problem

Problem Details

The full paper provides details about each assumption. Here is an example entry:

CDH: computational Diffie-Hellman problem

Definition:  Given $g^a, g^b ∈G$ to compute $g^{ab}$.

Reductions:

CDH $≤_{p}$ DLP
DLP $≤_{subexp}$ CDH in groups of squarefree order.

Algorithms: The best known algorithm for CDH is to actually solve the DLP.

Use in cryptography: Diffie-Hellman key exchange and variants, Elgamal encryption and variants, BLS signatures and variants.

History:
Discovered by W. Diffie and M. Hellman.

Remark:
A variant of CDH is:  Given $g_0,g_0^a,g_0^b ∈G$ to compute $g_0^{ab}$. This is $\equiv_{p}$ CDH.

References:

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on
Information Theory, vol.  IT-22, No.  6, Nov.  1976, p.  644-654.
U.M.  Maurer  and  S.  Wolf,  Diffie-Hellman  Oracles,  Proceedings  of  CRYPTO  ’96,  p.
268-282.
D. Boneh and R.J. Lipton Algorithms for Black-Box Fields and Applications to Cryp-
tography, Proceedings of CRYPTO ’96, p.  283-297.

The complete text is far too long to copy paste here, but this provides a pretty good example of how extensive and thorough it is.

Addendum: Unlisted Problem(s)

The following problem(s) were not listed in the above reference:

MIHNP: Modular Inversion Hidden Number Problem
AGCD: Approximate Greatest Common Divisor
SIP: Small Inverse Problem

Subset Sum/Knapsack problem

Subset Sum problem

$(0, 1)$ knapsack problem (The standard version of the problem)

Bounded knapsack problem
Unbounded knapsack problem
RMSS: Random Modular Subset Sum

Note about parameters

Hardness assumptions only hold when parameterized correctly. Inappropriate parameters can lead to easily solved instances of hard problems.


Simplification of a pairing The paper Expressive, Efficient, and Revocable Data Access Control for Multi-Authority Cloud Storage contains the following simplification:

  $$e(C_i,\text{GPK}_{uid})\cdot e(D_i, K_{\rho(i),uid})\cdot e({C'}_{i}, {K'}_{uid,aid_k}^{-\text{GSK'}_{uid}})\cdot e(g, {D'}_i)^{-1} = e(g,g)^{au_{uid}\lambda_i}$$

I'm not able do this simplification step by step. Note: I removed some of the unnecessary indices.

$$e(C_i,\text{GPK}_{uid})\cdot e(D_i, K_{\rho(i),uid})\cdot e({C'}_{i}, {K'}_{uid,aid_k}^{-\text{GSK'}_{uid}})\cdot e(g, {D'}_i)^{-1}$$

$$=e(g^{a\lambda_i}\cdot H(x)^{-v_ir_i},g^{u})\cdot e(g^{\frac{r_i}{\beta}}, g^{u't\beta}\cdot H(x)^{v_i\beta(u+\gamma)})\cdot e(g^{r_i}, g^{-tu'})\cdot e(g, H(x)^{v_i\gamma r_i})^{-1}$$

$$=e(g^{a\lambda_i}\cdot H(x)^{-v_ir_i},g^{u})\cdot e(g^{r_i}, g^{u't\beta}\cdot H(x)^{v_i\beta(u+\gamma)})^{\frac{1}{\beta}}\cdot e(g^{r_i}, g^{-tu'})\cdot e(g, H(x)^{v_i\gamma r_i})^{-1}$$

$$=e(g^{a\lambda_i}\cdot H(x)^{-v_ir_i},g^{u})\cdot e(g^{r_i}, g^{u't}\cdot H(x)^{v_i(u+\gamma)})\cdot e(g^{r_i}, g^{-tu'})\cdot e(g, H(x)^{v_i\gamma r_i})^{-1}$$

How can I arrive at $e(g,g)^{au\lambda_i}$ from this?

What am I missing so that I can do this simplification? I don't think I can come any further with the bilinearity $e(g^a,g^b)=e(g,g)^{ab}$.

Symbols:

$e: \mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G_T}$
$H: \{0,1\}^*\rightarrow\mathbb{G}$
$a,u,u',\beta,\gamma,r_i,v_i,\lambda_i,t\in \mathbb{Z}_p$
$x\in\{0,1\}^*$
$i$ denotes a specific attribute

Surely bilinearity helps and and you have to be aware of the fact that $e(g^a,g^b)\cdot e(g^a,g^{-b})=e(g^a,g^b)\cdot e(g^a,g^b)^{-1}=1$.

You see that from your last equation
$$=e(g^{a\lambda_i}\cdot H(x)^{-v_ir_i},g^{u})\cdot e(g^{r_i}, g^{u't}\cdot H(x)^{v_i(u+\gamma)})\cdot e(g^{r_i}, g^{-tu'})\cdot e(g, H(x)^{v_i\gamma r_i})^{-1}$$

you get

$$=e(g^{a\lambda_i},g^u)\cdot e(H(x)^{-v_ir_i},g^{u})\cdot e(g^{r_i}, g^{u't})\cdot e(g^{r_i},H(x)^{v_iu})\cdot e(g^{r_i},H(x)^{v_i\gamma})\cdot e(g^{r_i}, g^{-tu'})\cdot e(g, H(x)^{v_i\gamma r_i})^{-1}$$

and by rearanging the terms a bit and using bilinearity, the fact that you have a symmetric pairing (switch arguments) and the fact mentioned above you will notice that only the first term remains and that is your desired result.


Creating UID's using hash functions - most appropriate hashing algorithm? I have circa 1 million datapoints, each with a unique integer ranging from 6 to 24 digits:

exampleDataPointOne: 655092
exampleDataPointTwo: 333402221
exampleDataPointThree: 332021
...
exampleDataPointN: 903232211

I want to run each of these unique integers through a hash function, with the objective of 1) maintaining the uniqueness, 2) obscuring the underlying integer value and 3) having a hash output with a length of <= 34.

I've looked around for potential hash algo's that are a good fit, such as BLAKE, md5 and the sha family of hashes.

Given my requirements, what is the most advisable hash algorithm to use?

I want to run each of these unique integers through a hash function, with the objective of 1) maintaining the uniqueness, 2) obscuring the underlying integer value and 3) having a hash output with a length of <= 34.

You need to be very clear about what you mean by "obscuring."  The basic problem here is that your values look like they're likely to be subject to brute force guessing attacks—just like passwords are.  This means that if you apply a public, unkeyed hash function to your values, you subject yourself to the same sorts of attacks that are very successful against passwords—particularly attacks against unsalted passwords.

If by "obscure" you really mean that an attacker should not be able to figure out which number corresponds to each hash, then your solution needs to incorporate a secret key, and that key needs to be protected.  This is much, much, much, much more important than whether you use SHA-2 or Blake2.  (PS: Don't use MD5 for anything!  And if you need to incorporate a secret into the computation, don't do it in an ad-hoc manner—use HMAC-SHA2 or Blake2's optional key support).


Are these functions pseudo random? Why or why not? So I am stuck on this problem and have absolutely no intuition as to what the right answer is or how to prove it. Any help would be appreciated.

Let $F$ be a length-preserving pseudorandom function. For the following construction of a keyed function $F':\{0,1\}^n\times\{0,1\}^{n-1}\rightarrow\{0,1\}^{2n}$, state whether $F'$ is a pseudorandom function.

a. $F_k'(x)=F_k(0||x)||F_k(1||x)$

b. $F_k'(x)=F_k(0||x)||F_k(x||1)$

The little bit of intuition that I have makes me think that a isn't pseudo random but b is because in a you know that a 1 was originally in the middle so maybe that helps, but I don't know why. Its mostly just a wild guess.

(here || denotes concatenation)

Whether $F′$ is a pseudorandom function revolves around: can it be efficiently distinguished from a random function? That is, can you design an experiment (distinguisher) that has better-than-random chance to recognize a box computing $F_k′(x)$ given $x$ for some random unknown fixed $k$, from one which computes some random function (a random oracle)?

For one of your two cases, you can, thus $F'$ is not a pseudorandom generator. To prove that, just find and expose how your distinguisher works, and prove that it works better than random.

Hint 1: one way is to find some number of distinct $x$ such that $F_k$ will be evaluated with the same input, and detect that with fair odds from the output of $F_k'$.

Hint 2: In the present situation, said number is at least 2.

Hint 3: The proof that the distinguisher works better than random requires $n>2$, which can be assumed.

For the other case, you can't make a distinguisher , thus $F′$ is a pseudorandom generator. The usual formal proof technique is contraposition: assume a distinguisher for $F′$, and derive a distiguisher for $F$, which by hypothesis does not exists.

Here, there's a more intuitive approach: $F_k'(x)$ is made by concatenation of outputs of $F_k$; and such outputs are indistinguishable from random (for one not knowing $k$), except that the same input to $F_k$ yields the same output. Thus if the outputs of $F_k$ are for distinct inputs whenever we evaluate $F_k'$ for distinct inputs, then the overall output of $F_k'$ for distinct inputs is indistinguishable from random, and $F'$ is pseudorandom.


Can quantum algorithms solve the approximate GCD hard problem efficiently? Some cryptographic schemes are based on the hardness of this problem. The answer to this question determines if those schemes are quantum resistant or not. There are a number similar questions but they consider the classic security not the quantum security.
Thank you

In the $(\gamma, \eta, \rho)$-AGCD problem, all the samples are of the form
$$x_i := pq_i + r_i$$

for $q_i$ uniform from $[0, 2^\gamma / p [ ~ \cap \mathbb Z$;

$r_i$ uniform from $]-2^\rho, 2^\rho [ ~ \cap \mathbb Z$;

and $p$ a fixed random prime of $\eta$ bits.

This problem is believed to be quantum secure. See, for instance, this paper published in PKC 2017.

Moreover, a variant of the AGCD problem in which the noise term is sampled from a continuous Gaussian distribution, then it is rounded to integer (instead of being uniform in the integer interval from $-2^\rho$ to $2^\rho$) was proven to be basically equivalent to the LWE (see this paper published in EUROCRYPT 2015), and LWE is also believed to be quatum secure.

However, you have to be careful with other variants of the AGCD problem that are commonly used. For example, the "first is noiseless" variant (known by noise-free AGCD), in which $x_0 := pq_0$, that is, a multiple of $p$ without noise, is used in several papers and is obviously not quantum secure, as one can quantumly factor $x_0$.


Does digital randomness require energy? I can't find anything related on Google. I hope this is the correct site to ask this question.

I have been thinking about Randomness. Basically, generating randomness using a Computer Program. It is impossible without a source of randomness. The entropy of the numbers is limited to what the source provide and its reliability.

So you can't get random numbers out of thin air. Does this mean that randomness requires 'energy'?

Sure energy is not enough to get real random numbers but is it a requirement for getting them?

Everything that happens on computers requires some energy. This includes the very act of looking up random values from any source.

There is a mythical beast called reversible computing which is basically computing without using up energy. It's unclear whether it can exist at all; but laws of physics (as we currently understand them) imply that reversible computing must also be logically reversible. This is known as Landauer's principle: if some information is erased in a process, then entropy (the physical notion) rises and this requires usage of some energy. Thus, computing a hash function necessarily requires some energy.

Note that this notion is about the conservation of information: it's not obtaining randomness that matters; it's about what you do with it.


Can it be done? Securing physical badges with cryptography I need to hand out physical access cards to a group of people. My main objective is to guarantee at every location where this cards will be checked that no information in the card has been modified. I print those cards so I have all the user information (name, lastname, ID number, etc).

My idea is to use some sort of algorithm to input all this data and generate a maximum of 15-20 digit barcode that I can print in the card.

The cards will be checked using scanners similar to those used for passport control, which means that the operator will have the ability to obtain all the information in the card by OCR.
Without distributing my input algorithm (and risking someone else being able to replicate it), is there a way to have him check that no information has been modified on the card?

I'm open to all suggestions regarding my need as nothing is implemented yet. However, I cannot connect the verification points with a central server for checking, they are remote locations with no internet. The cards should hold data on themselves that allows to verify that no data has been modified. The cards don't have chips or magnetic stripe, so I'm locked to using OCR.

Any solutions?

Thanks in advance!

This is actually a fairly standard cryptographical problem, with standard solutions.

The easiest solution would be to use a Message Authentication Code; this is a function that takes a key and a message (in your case, the text on the badge), and produces a random-looking code.  What you would do is initially pick a random key, and give that key to both the guy producing the badges, and also install it into the scanner.  When you create the badge, you take the text and the key, send it through the MAC, and generate a value, which you also put on the badge.  When the scanner reads the badge, it takes the text it reads (excelt for the MAC value), and the key, send that through the MAC, and generate the value, and see if that's the value on the badge.

Obviously, this very straight-forward, and we have MACs for which the best known way to generate a forgery is to select a random value, and hope that value happens to be the correct one (which can't be verified until you actually scan the badge); if you have a 10-15 digit value, this would almost certainly be detected.

This meets all your requirements, and just has one problem; the MAC key needs to be installed in the scanner.  If it's possible that someone can steal a scanner, open it up, and recover the MAC key, this breaks the entire system.

If this is a viable attack, then the next step is to use a signature operation (such as ECDSA as mentioned in the comments); this works similarly to the MAC, except you generate two keys, a private one (which you use to create the badges), and a public one (which you use to verify the badges).  The public key can verify a badge, but (here's the cryptographical magic) it can't be used to create new ones.  The problem is the signature size; public key signatures are always rather larger then the corresponding MACs.  The comment says that an ECDSA signature could fit into about 32 bytes; this assumes an EC curve that could be broken by a large institution (circa $O(2^{64})$ effort), and so might not serve your purpose.  A 64 byte ECDSA signature, on the other hand, should be good against any adversaty; if you can fit 64 bytes into a QR code, that might be a viable alternative.


There is a protocol similar to SRP but where a part of the secret is stored on the client side? SRP is very useful but if our DB is leaked, an attacker could brute force a user's password with his associated salt/verifier found in the DB. I'm searching a solution to prevent this.

My first idea is to not store the salt/verifier in DB, but inside a separate binary file encrypted with our company password. The password isn't hard-coded in the source code, it's loaded (ideally in TPM) from our external USB key when we start the RESTful service. This prevent some kind of attacks but not all.

May be we can solve the problem only if the server himself can't check alone when a password is good or not. I mean, the solution is may be to store one piece of the secret on the user's device. Like if in the SRP protocol, the salt wasn't sent by the server but sent by the user's device. Of course, it's not good if the user send each time the same bytes to the server because of possible MITM interception (even if we mitigate the risk because we uses HTTS, HSTS, HPKP and TLS 1.2 minimum required).

My question is, there is a recommended protocol to do this kind of « shared-verification » please?

The best way I've found currently is this one (inspired by the FIDO UAF/U2F challenges) :

When the user sign up:

A random salt of 32 bytes is generated,
the user's password is derived with Argon2id and the salt,
the salt is saved on the user's device DB (indexedDB),
we use the derived key as a private ECDSA P-512 key and deducing the matching public key associated,
we send this public key to the server, the server store it in the DB

Then, when the user sign in:

The server generate a 512 random bits as a challenge,
the user's device derive the inputted password with Argon2id and the saved salt,
we use the derived key as a private ECDSA P-512 key and sign the server's challenge,
we send the signature of the challenge to the server,
the server use the user's public key to verify the challenge

With this solution, even a sysadmin of our staff can't brute force the password of a user in the DB because he doesn't have all the required elements to known when the password match. Of course, we can also store the user's public key encrypted with our password in a separated binary file to increase the security.

And yes, I known this technique requires that the user authorized each device he want to uses to save each time a new salt on the indexedDB, it's not a problem for our case.

Another idea, more simple, should be to keep SRP, but rather than using the derived user's password directly in SRP, to firstly use a random binary mask (XOR) on the password. The mask is saved on the user's device indexedDB.

I known the « don't roll your own », it's why I'm asking if there is a recommended protocol for that please? :)

Actually, if you assume that the client is able to store a secret long-term, it becomes rather easy; just have the client store the private key (possibly encrypted by the password); the server gets the public key.

Then, when it comes time to authenticate, the client takes the password, decrypts the private key, and then uses the private key to authenticate to the server (and ideally generate some shared symmetric keys that can be used to protect the following traffic; defeating MITM is important).

Someone who breaks into the server (and possibly records some transcripts of the authentication exchanges) gets no information about the passwords, all he sees is a series of public keys.  And, with a bit of care, someone who breaks into the client may get no information about the password either (if we are careful to pick a public key algorithm whose private keys look random; ECC is good with this).

Now, one aspect that your protocol doesn't address is 'how does the client make sure he is logging into the valid server'; the easiest way for that is to store the server's public key in with the data the client is keeping around anyways.

With that, one simple way may be the simple STS protocol; the client picks a random DH key, and sends its public key share (signed by its private signature key).  The server picks a random DH key and sends its public key share (signed by its private signature key).  Both sides verifies the received signatures, generate the shared DH secret, and so have keys which can be used to protect further traffic.

Alternatively, you could go a bit fancier and use TLS with client certificates; that's more work, but is certainly standard; it may make preventing dictionary attacks on someone who captures the client a bit more challenging, though...

Of course, the drawback to this 'store some of the secret on the user's device' solution is the assumption that the user will always use that device to log in; he can't use any other.  I suspect that constraint may be why we don't see it more often...


Session based AES with random key and static salt I'm currently using aes to encrypt/decrypt messages to and from a web service.

When the user establishes a session he sends a random  generated secret via rsa public key.

This secret is used to establish a secure channel using AES (CBC).

I'm using Rfc2898 to derive a key with a static salt (the salt is hardcoded and never changes). The IV is randomly generated for each message and prepended in cleartext.

Is it ok to use a static salt (Since I'm using a random generated secret for each session)?

Currently you seem to be using a Password Based KDF (PBKDF); you are using PBKDF2, as defined in Rfc2898. You don't need to do this as randomly generated data is already fine for creating an AES key. So - as you don't need a PBKDF - you don't actually need a salt.

If you need more keys or key data then what is actually required is a Key Based KDF (KBKDF), as your shared secret already contains enough entropy. Passwords usually don't, that's why they require the key strengthening delivered by PBKDF (by using a salt and iteration count). HKDF doesn't require a salt either, but its security properties are significantly enhanced if you do provide a salt.

Note that CBC should not be used by itself to create a secure transport protocol. CBC does not provide integrity nor authenticity. And if error (padding) oracles apply - which is likely - then it doesn't even provide confidentiality, leaving you with nothing. You need to at least add a MAC - HMAC is preferred - and a MAC key. To generate two keys...see the second paragraph and provide two different labels (or "OtherInfo"), one for each key.


What is the connection between "replay attack" to CCA security? Often in analyzing systems, the emulation of Replay Attack becomes important. Are systems that protected against CCA attacks also immune against replay attack, or it is a different criterion?
Thanks

These are different - protection against a replay attack could for example be done by recording that a message was already handled or by including a timestamp in the message and not processing the message if it is too old.

Note that for a replay attack the attacker doesn't get the plaintext, but does get access to at least 1 previously sent message. In CCA the attacker doesn't not have access to previously sent messages, and can request back the plaintext for chosen ciphertexts.


Obfuscating functions that are mostly zero Let $f_k(x)$ be a boolean function of two arguments with two properties:

The function $f$ can be efficiently computed.
The output is always 0 or 1, and for any fixed $k$, if we choose $x$ randomly, $\Pr[f_k(x)=1]$ is tiny (say, exponentially small).

Question: Is there a generic way to, given $k$, obfuscate an arbitrary such function?  In other words, can all functions with this property be obfuscated?

Here's what I know.  The function $f_k(x)=1$ if $x=k$ or $0$ otherwise can be obfuscated (it's called a point function).  The function $f_k(x)=1$ if $d(k,x)<t$ or $0$ otherwise can be obfuscated, where $d(\cdot,\cdot)$ is the Hamming distance and $t$ is a constant threshold (see the fuzzy vault scheme of Juels and Sudhan).  These are simple examples of functions that meet these properties and can be obfuscated.  Perhaps all functions in this class can be obfuscated?

I also know that there is no generic scheme that can obfuscate all functions -- but perhaps it's possible to find a generic scheme that obfuscates all functions in this class.

Motivation: This would be useful for verification of biometrics.  Think of $k$ as the template for the user, and $x$ as the biometric that's submitted to the system; $f$ verifies whether the user should be accepted.

Password verification is a simple case of this that corresponds to $f_k(x)=1$ iff $x=k$; here $k$ is the saved password stored when the user set up their account, and $x$ is the password entered by the user during the authentication process.  Password hashing is a method of obfuscating this verification function.  The fuzzy vault scheme is suitable for biometric schemes where we think the sensor might introduce random bit errors.  But there are other biometric schemes that might involve more complex procedures for verifying the proposed biometric, and I'm wondering if there is any generic result that demonstrates all such verification schemes can be obfuscated.

I'm fine with any reasonable form of obfuscation (including indistinguishability obfuscation).

I provide a summary below of what is currently known (to my knowledge) regarding obfuscation of various class of "mostly-zero" functions.

From Indistinguishability Obfuscation

What we can obfuscate: all efficient functions

Which notion of security: indistinguishability obfuscation

Underlying assumptions: new, exotic, and relatively poorly understood assumptions.

Is it efficient? Nope.

You state in your question:

  I also know that there is no generic scheme that can obfuscate all functions -- but perhaps it's possible to find a generic scheme that obfuscates all functions in this class.

However, as far as we know, it is perfectly possible that all efficiently computable functions (hence in particular all functions you are interested about) can be obfuscated with an iO scheme. We have a bunch of concrete candidates, and there has been a large body of work on the underlying assumptions. Providing a complete treatment would be out of scope for this question (I count more than 160 papers on the subject since 2013), but roughly, all known constructions of iO rely on exotic assumptions: either the existence of graded encoding schemes, whose security is poorly understood and with many (many) existing attacks, the latest being this one, or recent assumptions regarding the weak pseudorandomness of some extreme families of low depth pseudorandom generators -- some assumptions made in the three latest results (1, 2, 3) in this area have already been broken. Furthermore, none of the iO schemes we currently know of would be concretely efficient. Still, as a theoretical feasibility result, all functions you care about can be obfuscated (under exotic assumptions), where the obfuscation security notion is that of indistinguishability obfuscation.

From Multilinear Maps

What we can obfuscate: evasive low-degree polynomial modulo a prime

Which notion of security: virtual black box obfuscation (the strongest possible notion)

Underlying assumptions: new, exotic, and relatively poorly understood assumptions.

Is it efficient? Nope.

Barak et al. study in this paper the possibility of achieving even stronger notions of obfuscation (such as virtual grey box obfuscation, or virtual black box obfuscation) for the class of evasive functions. A class of function is evasive if, for any fixed input $x$, a random function from the class evaluates to $0$ on $x$ with overwhelming probability. While their results are mainly negative, Barak et al. also provide an interesting positive result:  under a new perfectly-hiding multilinear encoding assumption, which is the same kind of assumption that is used in constructions of iO schemes (hence suffers from comparable weaknesses and gives comparable (in)efficiency), there exists a virtual black box obfuscator for evasive functions that tests if a low-degree polynomial evaluates to zero modulo some large prime. Virtual black box obfuscation is the ultimate security notion for obfuscation: while iO states that it should be infeasible to distinguish two functionally equivalent obfuscated circuits, VBB states that everything that the adversary sees, given the VBB obfuscation of the function, can be simulated given only black-box access to the function. It is known that VBB is in general impossible to achieve; hence, this work shows that this impossibility does not seem to hold anymore for this restricted class of evasive functions.

From LWE

What we can obfuscate: conjunctions, compute-and-compare functions

Which notion of security: distributional virtual black-box

Underlying assumptions: the well-studied (conjectured quantum-resistant) LWE assumption (or entropic variants of it)

Is it efficient? Not really, but depending on the primitive to obfuscate, it can be doable.

There has been recently a large body of work identifying interesting classes of "mostly-zero" functions, which can be obfuscated under the plain (or variants of) LWE assumption, which is a well-studied assumption.

1) Conjunctions. Several papers have proposed schemes to obfuscate functions of the form

$f : (x_1, \cdots, x_n) \rightarrow \bigwedge_{i \in I} y_i$,

where each $y_i$ is either $x_i$ or $1-x_i$, and $I$ is a subset of $[1, \cdots, n]$. This paper shows how to obfuscate this class of function under an "entropic variant" of the ring-LWE assumption. Obfuscating a 64-bit function takes a few hours, and evaluating the obfuscated program takes a few seconds. The security notion achieved is that of distributional VBB obfuscation, a variant of the notion of VBB obfuscation which also relies on the entropy of the obfuscated function.

2) Compute-and-compare functions. This is a very nice result achieved independently in this paper and in this paper. Assuming only the plain LWE assumption, they show how to compute a very large class of interesting evasive functions: the functions that have two secret values $(\alpha, \beta)$ hardcoded and, on input $x$, evaluate an arbitrary function $f$ on $x$ and output $\alpha$ if and only if $f(x) = \beta$ (and $\bot$ otherwise). This captures as a particular case conjunctions, point functions, but also much more. Their construction also achieves distributional virtual black-box obfuscation.

From Group-Based Assumptions

What we can obfuscate: conjunctions, pattern matching, hyperplanes membership

Which notion of security: distributional VBB

Underlying assumptions: from entropic DDH to the generic group model

Is it efficient? It can be reasonably efficient

Many constructions have also been designed under various assumptions in standard discrete-log-hard abelian groups. Most notably:

1) Conjunctions can also be obfuscated in the generic group model, and achieve distributional VBB, as shown by this very nice recent paper.

2) Pattern Matching. Two recent works have considered the task of obfuscating functions that test whether a given input string contains a pattern, with "wildcards" (i.e., the pattern can contain wildcards * that correspond to "any value there"), and achieve distributional VBB for patterns having some entropy. These are very nice results, and are in addition relatively efficient compared to everything that I've discussed so far. The first of these paper achieves security in the generic group model, while the second achieves security in the standard model, under a knowledge-of-exponent style assumption (i.e., something plausible, but far from being the most well understood assumptions).

3) Hyperplane Membership Testing. Eventually, this paper shows how to obfuscate hyperplane membership testing (i.e., checking whether an input vector belongs to a secret obfuscated hyperplane), which generalize point functions to a much larger class. The obfuscation is relatively efficient and is proven secure under a strong variant of the DDH assumption.

Note: there exists also DDH-based obfuscation scheme for re-encryption functions, but those do not fit into your notion of mostly-zero functions.

From One-Way Functions

What we can obfuscate: point functions

Which notion of security: distributional VBB

Underlying assumptions: exponentially strong one-way functions, one-way permutations, or deterministic encryption

Is it efficient? Yes

To conclude this overview, the weakest of all these "mostly-zero" functions that you want to obfuscate are point functions, which are equal to zero everywhere, except on a specific point. Such functions can be obfuscated, depending on the exact notion of obfuscation achieved, assuming the existence of exponentially strong one-way functions (here) or one-way permutation (here), or deterministic encryption (here) all being highly plausible assumptions (the second one being even a fundamental assumption of cryptography). Obfuscation of point functions has been studied in depth and has many applications in cryptography. Note that to achieve stronger notions of obfuscation for point functions (e.g. to achieve composability, or non-malleability), one typically rely on stronger DDH-like assumptions (e.g. here and here).


How openssl padding for AES cfb IV? From a few documents I have read and a few questions about padding here, I think if I passed a encrypted text fewer than BLOCK SIZE, openssl would pad it per PKCS7. And use that padded encrypted text as IV for next data block.

But when I followed the example (changed method to cfb), I noticed that in decrypt, ctx->iv after EVP_DecryptUpdate was the last part of ciphertext padded in the way I could not figure out.

ciphered text (hex): db 11 d7 9c a8 f2 1c 29 07 dc 6d 62 13 7a 5e bf 3a c2 fa 2f a1 0f 73 90 ae bd cf 57 cf 1f 82 a2 24 ac d1 de 29 6a e2 95 9c 0f ec
IV after decrypt (hex): 24 ac d1 de 29 6a e2 95 9c 0f ec 9a 95 f0 e3 14

So where does "9a 95 f0 e3 14" come from?

Cipher Feedback mode turns the block cipher (AES) into a self-synchronizing stream cipher which feeds back the full ciphertext block as the next IV.

If you encrypt something smaller than a multiple of the block size, it will not use all of the block cipher output to create the ciphertext, just the amount it needs. Therefore there is not a padding requirement either. However it still needs the full output of the block cipher to "feed back" and create more stream output.

In your case, the ciphertext blocks are:

db 11 d7 9c a8 f2 1c 29 07 dc 6d 62 13 7a 5e bf
3a c2 fa 2f a1 0f 73 90 ae bd cf 57 cf 1f 82 a2
24 ac d1 de 29 6a e2 95 9c 0f ec

As you can see, the last one was truncated after 0xEC, since it did not need it. The remaining 5 bytes of the block cipher output stream are the final 5 bytes of your next IV. In reality if you decide to encrypt more data using the same stream, those 5 bytes will be XORed against the plaintext to create ciphertext, which will change them prior to feedback into the block cipher.

CFB, OFB and CTR modes are stream cipher modes, and therefore do not require padding. There is nothing stopping you from forcing padding, but unlike ECB/CBC modes, you don't need it for data that is not a multiple of the block size.


Does Proxy re-encryption can re-encrypt large data? Many resources talk about the benefit of Proxy Re-encryption (PRE) and I also implement my PRE using Elliptic Curve key pair. But after I set up Global parameters, I can encrypt very small data maybe less than 1KB. My question is with EC key pair normally, can we encrypt large data maybe about 10MB?

Normally the data is not encrypted under PRE directly. The sender can encrypt the data using a random symmetric key using a secure symmetric cipher (e.g. AES), then encrypts the symmetric key under the sender's PRE key. The proxy can re-encrypt this ciphertext into a new ciphertext such that the receiver can decrypt it.


PRNGs which are not CSPRNG From Definition of CSPRNG, it has two characteristics

It satisfies the next-bit test.
It withstands 'state compromise extensions' - part of all of the state being compromised does not allow for reconstruction of the prior stream of random numbers.

I am looking for PRNGs which fail the 2nd Characteristic. Infact they are PRNG but not CSPRNG.

Item (2) is not part of the definition of a standard CSPRNG. If you look at where this definition was taken from in Wikipedia, this item refers to a "forward secure CSPRNG". So, this is a definition of forward security and not the standard notion.

Also, the next-bit test is one way of defining, but certainly not the only way.

In any case, it is easy to construct a CSPRNG that is not forward secure; simply always store the initial state.


FHE over the Integers - reduction to approximate gcd problem I have three quick questions concerning the reduction of the scheme to the approximate gcd problem:

What exactly do the authors mean by $q_p(z_1')$ being the odd part of the gcd? (last line of step 3)
In step 4 (recovering p): Where does the $\pi^2/6$ come from? I'm guessing it has something to do with prime distributions, but I couldn't find anything on google. Also, $\pi^2/6 \approx 1.6 $  and not $0.6$, so is the formula wrong?
Thanks @Thomas, found it on wikipedia: The probability that two random numbers are relatively prime is $1/\zeta(2) = 6/\pi^2 \approx 0.6$, so the paper just has nominator and denominator switched.
Also in step 4: Am I correct that $\overset{\sim}{z} = z_1'$, i.e. the non-zero output of the first round of the binary gcd algorithm?

Link to the paper: https://eprint.iacr.org/2009/616.pdf

I'm referring to section 4.1.

Before my answer, I would like to review the original binary GCD algorithm @wikipedia. Roughly speaking, this algorithm replaces division with binary shifts and subtraction.

For two positive integers $u$ and $v$, the following identities hold:

$\gcd(0,v) = v$ and $\gcd(u,0) = u$.
$\gcd(u,v) = \gcd(v,u)$.
If $u,v \in 2\mathbb{Z}+1$ and $u \geq v$, then $\gcd(u,v) = \gcd((u-v)/2,v)$.
If $u,v \in 2\mathbb{Z}$, then $\gcd(u,v) = 2 \cdot \gcd(u/2,v/2)$.
If $u \in 2\mathbb{Z}$ and $v \in 2\mathbb{Z}+1$, then $\gcd(u, v) = \gcd(a/2,b)$.

By using those identities, the binary GCD algorithm $\mathsf{BGCD}(u,v)$ is defined as follows:

If $v > u$, then swap them.

If $v=0$, then output $u$.

Let $b_1$ be the parity bit of $u$ and let $b_2$ be the parity bit of $v$.
If both $u$ and $v$ are odd, then $u \gets u-v$ and $b_1 \gets 0$.
If $b_1=0$, then $u \gets u/2$. If $b_2=0$, then $v \gets v/2$.
(Recursion) If $b_1=0$ and $b_2=0$, then output $2 \cdot \mathsf{BGCD}(u,v)$. Otherwise, output $\mathsf{BGCD}(u,v)$.

Answer 1

  What exactly do the authors mean by $q_p(z_1')$ being the odd part of the gcd? (last line of step 3)

Let us consider two positive integers $a$ and $b$, and its GCD.
Then, there is an unique integer $k$ and odd integer $c$ satisfying $\gcd(a,b) = 2^{k} c$.
The authors call this $c$ the odd part of $\gcd(a,b)$.

The reduction algorithm, say $\mathsf{Alg3}(z_1,z_2)$, in Step 3 is defined as follows:

If $z_2 > z_1$, then swap them.

If $z_2 = 0$, then output $z_1$ and $z_2$.

Let $b_i$ be the parity bit of $q_p(z_i)$, that is, $b_i = [q_p(z_i)]_2$.
(Call the LSB oracle implemented by $\mathcal{A}$.)
If both $q_p(z_i)$ are odd, then $z_1 \gets z_1 - z_2$ and $b_1 \gets 0$.
For each $i = 1,2$, if $b_i = 0$, then $z_i \gets (z_i - \mathsf{parity}(z_i))/2$.
(Recursion) Output $\mathsf{Alg3}(z_1,z_2)$.

As the authors wrote, this algorithm (approximately) performs the binary GCD algorithm over quotients on input $q_p(z_1)$ and $q_p(z_2)$.
Since we are interested only in the case $\gcd(q_p(z_1),q_p(z_2)) = 1$,
 the algorithm removes "If" from the step 5 in $\mathsf{BGCD}$.
In addition, the doubling in "If" will introduce another noise.
By this removal, $\mathsf{Alg3}$ (approximately) outputs $z_1'$ whose quotient $q_p(z_1')$ is the odd part of $\gcd(q_p(z_1),q_p(z_2))$, when the current $z_2'$ in Step 1 is $0$.

Answer 2

  In step 4 (recovering p): Where does the $\pi^2/6$ come from? I'm guessing it has something to do with prime distributions, but I couldn't find anything on google. Also, $\pi^2/6 \approx 1.6 $  and not $0.6$, so is the formula wrong?

  Thanks @Thomas, found it on wikipedia: The probability that two random numbers are relatively prime is $1/\zeta(2) = 6/\pi^2 \approx 0.6$, so the paper just has nominator and denominator switched.

As @Thomas wrote, the probability is that two random numbers are relatively prime.
If so, $\gcd(q_p(z_1^*), q_p(z_2^*))$ is $1$ and the odd part of it is also $1$.

Answer 3

  Also in step 4: Am I correct that $\tilde{z} = z_1'$, i.e. the non-zero output of the first round of the binary gcd algorithm?

Yes.


I wanna know what exactly SP array does Please only look at for loop in source code below, especially SP1,SP2,SP3.......
Is it similar to what S-box does?(Ignore the other)

int fval, work, right, leftt;
int round;
int keysi = 0;

leftt = inInts[0];
right = inInts[1];

work   = ((leftt >>  4) ^ right) & 0x0f0f0f0f;
right ^= work;
leftt ^= (work << 4);

work   = ((leftt >> 16) ^ right) & 0x0000ffff;
right ^= work;
leftt ^= (work << 16);

work   = ((right >>  2) ^ leftt) & 0x33333333;
leftt ^= work;
right ^= (work << 2);

work   = ((right >>  8) ^ leftt) & 0x00ff00ff;
leftt ^= work;
right ^= (work << 8);
right  = (right << 1) | ((right >> 31) & 1);

work   = (leftt ^ right) & 0xaaaaaaaa;
leftt ^= work;
right ^= work;
leftt  = (leftt << 1) | ((leftt >> 31) & 1);

for ( round = 0; round < 8; ++round )
    {
    work   = (right << 28) | (right >> 4);
    work  ^= keys[keysi++];
    fval   = SP7[ work        & 0x0000003f ];
    fval  |= SP5[(work >>  8) & 0x0000003f ];
    fval  |= SP3[(work >> 16) & 0x0000003f ];
    fval  |= SP1[(work >> 24) & 0x0000003f ];
    work   = right ^ keys[keysi++];
    fval  |= SP8[ work         & 0x0000003f ];
    fval  |= SP6[(work >>  8) & 0x0000003f ];
    fval  |= SP4[(work >> 16) & 0x0000003f ];
    fval  |= SP2[(work >> 24) & 0x0000003f ];
    leftt ^= fval;
    work   = (leftt << 28) | (leftt >>> 4);
    work  ^= keys[keysi++];
    fval   = SP7[ work         & 0x0000003f ];
    fval  |= SP5[(work >>  8) & 0x0000003f ];
    fval  |= SP3[(work >> 16) & 0x0000003f ];
    fval  |= SP1[(work >> 24) & 0x0000003f ];
    work   = leftt ^ keys[keysi++];
    fval  |= SP8[ work         & 0x0000003f ];
    fval  |= SP6[(work >>  8) & 0x0000003f ];
    fval  |= SP4[(work >> 16) & 0x0000003f ];
    fval  |= SP2[(work >> 24) & 0x0000003f ];
    right ^= fval;
    }

right  = (right << 31) | (right >> 1);
work   = (leftt ^ right) & 0xaaaaaaaa;
leftt ^= work;
right ^= work;
leftt  = (leftt << 31) | (leftt >> 1);
work   = ((leftt >>  8) ^ right) & 0x00ff00ff;
right ^= work;
leftt ^= (work << 8);
work   = ((leftt >>  2) ^ right) & 0x33333333;
right ^= work;
leftt ^= (work << 2);
work   = ((right >> 16) ^ leftt) & 0x0000ffff;
leftt ^= work;
right ^= (work << 16);
work   = ((right >>  4) ^ leftt) & 0x0f0f0f0f;
leftt ^= work;
right ^= (work << 4);
outInts[0] = right;
outInts[1] = leftt;

Other than the oddity/bug in final note, this seems to be a classical, speed-optimized implementation of standard DES (for what we see; there could be variations in the S-table content, exact bit twidling in permutation P, or key scheduling).

The code has:

IP, final permutation and IP-1 per Richard Outerbridge's method.
Pre-rotation by 1 bit before the round loop, undone afterwards, in order to  need no shift (rather than a 1-bit rotation) for SP8, and shifts counts that most are multiples of 8 (which excellent compilers for 8-bit CPU love).
Two DES rounds per partially unrolled round loop, so that the 8 loops perform 16 rounds.
Pre-computed 6-bit subkeys grouped as two 32-bits words (with 8 unused bits in each), merged in parallel for 4 S-boxes at a time. Correspondingly, it is applied subkeys on the input of expansion E.
Expansion E reduced to rotating the appropriate part of right or left into the low-order 6 bits, and masking to keep these bits before indexing the S tables. This uses that E is highly regular, and combines with E.
Permutation P merged with the S-boxes, which is the game-changing optimization of DES in software. SPj is DES's S-box j with expansion E (modified to account for the 1-bit pre-rotation) applied on the output, that is indexing SPj[x] yield E(SPj(x)), give or take the 1-bit pre-rotation. A table's output width thus grows from 4-bit to 32-bit. There's a data size penalty: S-boxes now eat 16384 bits of table rather than 2048.
Note: It is not used the size optimization that keeps the bitwise-OR of the eight 32-bit tables and extracts the bits with eight 32-bit masks, which used to be classical in heavily size-constrained CPUs.

Note: a variant does without fval, clarifying per my taste. I sneaked in some comments.

for ( round = 0; round < 8; ++round )
    {
    // apply E, subkeys, S and P for odd  S-boxes, rounds changing leftt
    work   = keys[keysi++] ^ ((right << 28) | (right >> 4));
    leftt ^= SP7[ work        & 0x3f ];
    leftt ^= SP5[(work >>  8) & 0x3f ];
    leftt ^= SP3[(work >> 16) & 0x3f ];
    leftt ^= SP1[(work >> 24) & 0x3f ];
    // apply E, subkeys, S and P for even S-boxes, rounds changing leftt
    work   = keys[keysi++] ^ right;
    leftt ^= SP8[ work        & 0x3f ];
    leftt ^= SP6[(work >>  8) & 0x3f ];
    leftt ^= SP4[(work >> 16) & 0x3f ];
    leftt ^= SP2[(work >> 24) & 0x3f ];
    // apply E, subkeys, S and P for odd  S-boxes, rounds changing right
    work   = keys[keysi++] ^ ((leftt << 28) | (leftt >> 4));
    right ^= SP7[ work        & 0x3f ];
    right ^= SP5[(work >>  8) & 0x3f ];
    right ^= SP3[(work >> 16) & 0x3f ];
    right ^= SP1[(work >> 24) & 0x3f ];
    // apply E, subkeys, S and P for even S-boxes, rounds changing right
    work   = keys[keysi++] ^ leftt;
    right ^= SP8[ work        & 0x3f ];
    right ^= SP6[(work >>  8) & 0x3f ];
    right ^= SP4[(work >> 16) & 0x3f ];
    right ^= SP2[(work >> 24) & 0x3f ];
    }

Off-topic note: The question's code contains the idiom >>> which is an indication that it is it Java (where this means logical shift right).
If so, some >> needs to be changed to >>>, at least in (right << 28) | (right >> 4) and similar, because in Java >> is specified to leave the high-order bit of (32-bit) int unchanged, which is not the intention.
On the other hand, if this is C, all int should be changed to unsigned, or better uint32_t, because using >> on a signed variable is not fully specified in C, giving results that depend on the compiler's mood.


Would asymmetric cryptography be feasible in World War II? Assuming people in the forties would have known asymmetric cryptographic methods like RSA, would they have been able to make sensible use of them?
There were no real electronic computers at the time, but the things achieved in Bletchley Park and elsewhere mean that some processes could have been automatised.

Sure, you can do Diffie-Hellman or RSA by hand if you have to.
And you don't need the bit length we use today with powerful adversaries.
I'm not an expert on WW2 computational machines but I won't be surprised if something to do modular exponentiation could be built using WW2 technology given sufficient motivation.
A modern cryptographer in WW2 could make truly unbreakable ciphers. With authentication, key exchange, good randomness, and all the good stuff we have now.


Making PRNG cryptographically secure thru shuffling? Is it practical to make a PRNG cryptographically secure if I shuffle the randomly generated numbers (say 256-bit) several times before hashing it, even if a hacker knows when I generate the numbers?

Note: They say PRNG is not cryptographically secure because the generation depends on the state of the generator, that it is somewhat deterministic and not random enough. Can the simple act of shuffling a 256-bit PRNG (length is around 77-78 numbers, i.e. probability of generating all 9s is close to zero) be good enough to make it cryptographically secure?

More specifically, if I use Python's random.getrandbits() to randomly generate a length of 256-bit numbers and then use random.shuffle() on it several times, can this help make the numbers cryptographically secure? Can this even resist quantum hacking?

I assume what you are asking is if I take a non-cryptographic random generation, is it enough to shuffle and then hash to get something cryptographically secure. In general, the answer is most certainly no. To start with, a non-cryptographic random call typically has very low entropy. I assume that random.shuffle() is also a non-cryptographic function, and so you are adding low-entropy randomness to low-entropy randomness; the result still has very low entropy and can be brute forced. At the end, you hash the result. I am assuming here you want to use a cryptographic hash function. In such a case, under reasonable modeling, if the input to the hash function has high enough entropy then you are fine; otherwise you are not. I assume here you are not.

In any case, as with all cryptography, it is very very very hard to get this right and you should not try to invent it yourself until you are an expert.


QKD - Does BB84 Protocol rely on a prearranged code? First of all, sorry if the title is not that clear, I'll provide an in-depth explanation behind my question.
So, basically, I was reading about quantum cryptography and came across BB84. The protocol uses photon pulses composed of polarized photons, which spin in a specified direction. That may be rectilinear spin (i.e. horizontal/vertical) or diagonal spin (i.e. left-diagonal/right-diagonal).
If performed correctly, this is in theory, unbreakable. Because quantum mechanics laws don't allow measurements to be done without damaging the photons used in the communication.
Here's how it works:

Alice sends Bob a sequence of photon pulses, each one randomly polarized in one of the four possible directions (listed above).
Bob measures the pulses by setting his polarization detector in one of the two possible spin types (rectilinear or diagonal), randomly. He cannot measure both, because quantum mechanics doesn't allow this. If the detector is not correctly set, he will get a random measurement. *(Note: Remember that the rectilinear polarization detector will detect both horizontal and vertical spinning photons, and vice versa the diagonal detector will detect both left-diagonal and right diagonal spinning photons) *.
After the measurement is done, Bob will send Alice the detector configuration he used (ex. the first photon was measured with a diagonal detector, the second was measured with a rectilinear, etc.) over a public channel.
Alice responds, in the public channel, to Bob. By saying which of the configurations were correctly set. (ex. the first was diagonal and correct, the second rectilinear and incorrect, etc.)
Bob and Alice then take the correct configurations, and they convert those to a prearranged code, which could be, as an example, that a correctly guessed diagonal detector is 0, and a correctly guessed rectilinear detector is 1. This way an encryption key will be composed.

This is how I understood the algorithm, so it may very probably be not entirely correct. Please correct me at any point if needed!
Anyway, after explaining how I see the algorithm, my question is: **does this basically rely on a shared secret? ** I mean, the prearranged code to convert the polarization measurements to bits should be, as the name says, prearranged. If Eve listens on the public channel and gets both Bob's measurements and Alice's response, which lists the correct polarizations, and she knows that a diagonal pol. converts to a 0 while a rectilinear pol. converts to a 1, she can reconstruct the key without interfering with the quantum channel.
If this is true, why would we go for quantum key distribution? If we need a secretly prearranged code to make it work? That would have to be kept secret to prevent keys from recovering right?

Bob and Alice then take the correct configurations, and they convert those to a prearranged code, which could be, as an example, that a correctly guessed diagonal detector is 0, and a correctly guessed rectilinear detector is 1. This way an encryption key will be composed.

I believe that's where you got it a bit off.  A correctly guessed rectilinear detection is not a consistent 1; instead, they might have the convention that a horizontal polarization is 0 and a vertical polarization is 1; similarly, a 45 degree polarization might be 0 and a 135 degree polarization might be 1.

  If Eve listens on the public channel, and gets both Bob's measurements...

Eve most certainly does not get Bob's measurements.  Bob does tell the world (well, Alice, but we can assume Eve is listening in) what he set his detector to (whether it was on the horizontal/vertical setting, or whether it was diagonal), but Bob certain doesn't tell what the detector actually measured.

So, suppose Alice sends a rectilinearly polarized photon to Bob.  If Bob set his detector to rectilinear, he'll tell that to Alice (after the photon has been detected); Alice will tell Bob that his guess was correct.  Alice knows what polarization she sent, and Bob knows he measured it correctly; they both know whether it was a horizontal photon (a 0), or a vertical photon (a 1).  Which is it?  Well, neither Alice or Bob are telling.  Someone in the middle can't be sure (unless they tried to measure it themselves; in that case, there's a chance that they got the polarization wrong when they re-emitted the photon, and hence will introduce detectable errors).

My opinion: I don't personally think this QKD stuff is actually practical (that is, it doesn't solve any problem that can't be better solved using more traditional methods), however it can work.


How difficult is it to brute force d in RSA: d = (1/e) mod φ in a CPT attack? Given that  RSA key generation works by computing:

n = pq
φ = (p-1)(q-1)
d = (1/e) mod φ

If I was an attacker who wanted to brute force d, could I brute force d given just the public key, the plaintext message, and the generally known facts of RSA such as

φ is always less than n = pq
n is known by the attacker by the public key
e is known by the attacker
The implementation of d = (1/e) mod φ is reasonably efficient

The attack would be brute force φ by iterating from a max value of n, and decrease the value for φ and compare that to the known plaintext of m.  An optimization of this would be to skip all values of φ that fall into the conditions of

Prime numbers ( φ is a product of pq and therefore not prime)
Where GCD(φ, e) != 1
Omit values that would result in a small d (FIPS 186-3 requires $d > 2^{nlen/2}$)
Odd values and be omitted (see comments below)
etc... (what else can be added?)

Question

How can I calculate or estimate the difficulty of attacking d when only the public key [edit and plain text message] is known?  (no optimizations)
With the optimizations listed above, and those you may be aware of, what is the difficulty of attacking d?
What is a more efficient manner of attacking RSA with a known plain text attack?

How can I calculate or estimate the difficulty of attacking d when only the public key is known? (no optimizations)

Generate a few hundred pairs $(n,\varphi(n))$ for whatever key size you are interested in, then compute the average distance  between the pairs. That would give you a guess as to how many values on average you will need to get $\varphi(n)$.

Symbolically we get something like $pq-(p-1)(q-1)=pq-pq+p+q-1=p+q-1$ That number has approximately the same number of bits as the larger of $p,q$. So for RSA-2048, we use 1024 bit primes, so the difference will have around 1024 bits. So your work factor would be around $2^{1024}$.

  With the optimizations listed above, and those you may be aware of, what is the difficulty of attacking d?

For all intents and purposes it will be the same. The factors by which these optimizations reduce things are small comparatively (e.g., not trying odd values, you eliminate half of the choices which when talking security bits that is only 1 bit)

  What is a more efficient manner of attacking RSA?

Factoring is the most efficient method known to date. A 768 bit RSA modulus was factored in 2009 using the number field sieve. That is the largest to date.


Can I crack an AES string if I have all these parameters? This is for a challenge at followthewhiterabbit.trustpilot.com:

  Knowns:

  The algorithm is AES (Rijndael)
  Blocksize: 128
  Keysize: 256
  You only need to find the first 6 bytes of the key, the rest are 0’s, so:
  [?,?,?,?,?,?,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  All bytes in the key has an integer value between 0 and 16.
  The initialization vector is (base64 encoded): "DkBbcmQo1QH+ed1wTyBynA=="
  The text is just plain ASCII english

  The encrypted text (base64 encoded):

  [base 64 block follows]

Can I crack an AES string if I have all these parameters? If so, how should I do it?

Since there are only $16^6 \approx 16.8$ million keys, you can try them all and decrypt the message with each. In general you would have to know something about the plaintext to identify which of those decrypted candidates is the correct one.

In this case it is known that the message is English ASCII, so the top bit of each plaintext byte will be 0. The chance of an $n$-byte message succeeding that test by chance is $2^{-n}$, so with more than 24 bytes of data (as you have) it is likely you will find a unique key that decrypts it into ASCII. The padding could include a 1 bit, so you might want to ignore the last block until you've found the key.

Remember to try different modes of operation if the first doesn't work – there is an IV, so it isn't ECB. If the ciphertext length was not a multiple of the block size, it would likely be CTR mode, but yours is.


Attacks from releasing decrypted CCM payload before verifying tag CCM specifies (Section 1.7) that no plaintext data should be released before the MAC is verified.

Why is this recommendation given and what attacks are possible against CCM if data is treated like a streaming operation and decrypted data is released before the MAC is verified?

Is this recommendation given because of user temptation to use unverified data without checking the MAC?  Or are there deeper ramifications?

Is this recommendation given because of user temptation to use unverified data without checking the MAC?

Yes. Note the word "released" instead of "stored".

  Or are there deeper ramifications?

That should not be possible; CCM uses CBC-MAC with known length and CTR mode encryption. There are - to my knowledge - no known plaintext attacks possible on these algorithms (given that the underlying block cipher is secure, of course).


Is there any trapdoor that can solve elliptic curve subgroup membership problem? Given an elliptic curve $E$ over a finite field q(q is a prime), and $<G>$, the cyclic subgroup of $E$, where G is the generator. Is there any trapdoor $T$, that given a random group element $P\in E$, we can decide if $P\in <G>$ in probabilistic polynomial time with the help of $T$?

Here is one (somewhat impractical) possibility:

We pick an Elliptic Curve that has a group size $n$ that is a secret factorization $n = pr$ (I'd say $pq$, except you already gave a separate meaning to $q$)

As our generator $G$, we pick an element of order $p$.

The trapdoor information is the value $p$

It would appear to be a hard problem to determine whether a random element $P$ is in the subgroup $<G>$; however with the knowledge of $p$, we can compute $pP$; that will be the null element iff $P$ is in the subgroup.
Now, $n$ has to be large enough for factorization to be infeasible (as anyone looking at the elliptic curve can run a point counting algorithm to obtain $n$); that means that $q$ (the prime the curve is based on) must be 2048 bits (or larger); hence computations on this curve will be expensive.  It also begs the question "why are you using an elliptic curve at all, rather than (say) the group of quadratic residues in $\mathbb{Z}_{2pr+1}^*$ with $2pr+1$ prime"


X509 CertificatePolicies, IssuerAlternativeNames, BasicConstraints extensions. What is done when Issuer signs? I have got one theoretical question related to extensions of X509 Certificate. More precisely I have question about what is happening when issuer signs subject's certificate with has several extensions, especially I am interested in three extensions, certificate policies, issuer alternative names and basic constraints.

Is Issuer Alternative Names extension being filled with issuer's Subject Alternative Names extension when signing certificate?

Is Certificate Policies extension being unchanged when sign is done by issuer?

EDIT: I have given only an interface of application, where I should implement logic behind it. So I am given extensions fields which I can fill only when I generate initial self-signed certificate. Basic constraints comes with "is critical" checkbox, "is CA" checkbox and "path length" integer field. So I am confused when I fill those data when I generate self-signed, and when Issuer after that signs my previous certificate, what is happening with this extension.

The certificate policies are generally set by the CA. It is not something that is present within a certificate request (and if you would include it your request would hopefully be rejected or the included policies ignored).

Yes, the issuer alternative name would generally be identical to the subject alternative name of the parent certificate. But as the extension cannot be critical and isn't explicitly mentioned for certificate path validation, I see little reason to validate that it is.

You actually forgot to tell us that this is for a self signed certificate that you want to have signed.

This is not something you would usually do; in general you would generate a new key pair and certificate request and use that. Reusing the key pair is possible but should generally not be performed. It is not possible to change the issuer of a certificate without invalidating the previously set signature which includes this data element.

As for the criticality of the basic constraints: if you set the constraints it for a self signed leaf certificate rather than a root CA certificate I would set "is critical" to true (anything will parse these two constraints by now), "is CA" to false and finally path length constraint simply to 0.

If you do send your self signed cert to a CA and it will process your cert, then it will probably simply ignore the values set.