Does it make sense to have a compression function that uses 64-bit of the message to create an output of 64-bit? I have a very simple compression function, which looks like this in C++:

unsigned long long compress(unsigned long long current_block, unsigned long long last){
  for(int i = 0; i<16; i++){
    last += current_block;
    last = last ^ (last << 13);
    last = last ^ (last >> 11);
  }
  return last;
}

It's my own first try of a compression function :)
Now, this function is the core of a cryptographic hash function. All values are 64-bit. The function splits the message into 64-bit blocks, which get passed to the compression function (current_block) together with the sum (addition modulo $2^{64}$) of the last compressions (last). The initial value (the value that is used for last when the compression function is called the first time) is 0.
About the hash function itself: It is a Merkle–Damgård construction and the messages are padded with the length of the original message (64-bit value).

So, now I want to prove that this compression function is not preimage resistant (first and second) and not collision resistant. In order to do that I want to ignore the padding and just try to find the weaknesses of the compression function itself and then think about improves I could make.
In these days it is of course computationally feasible to brute force a 64-bit hash (particularly with a birthday attack), so I understand the term "collision resistant" as "an attacker needs to try all $2^{64}$ possibilities" (in case of a preimage attack).

What I've done so far
It's obvious, that compress(0, 0) == 0, so I could add as many 0-blocks as I want to the beginning of the message. This problem could be solved by using a different initial value.
It seems to be quite difficult to reverse the compression function, because it does 16 additions and 16 mixings, which creates quite a complex relationship and every bit of the input (current_block) can affect every bit of the output.
A general problem I thought of: Couldn't it happen, that we run into a loop? That would happen, if the result after the mixing in one round would be equals the starting value last. In this case, we would have quite a simple relationship as we need only to break one (or a few) mixing rounds. If this problem exists, I think it could be solved by adding a round constant (changing every round) in each round.

Questions I have
Does it make sense to have a compression function that uses 64-bit of the message to create an output of 64-bit? I see no problem with it, but I'm not sure about it as many common hash function use a much bigger message part to compress (MD5 does 512-bit => 128-bit).
Can we expect collisions with the same last-value, like compress(x, 0) == compress(x', 0) ?

This hash function has a 64-bit output.  Therefore, it is not collision-resistant.  It is easy to find a collision in any hash function with a 64-bit output.  Since this appears to be a homework, I'm going to leave it to you to figure out why this is the case.

In general, please don't just post a homework question and expect us to solve it for you.  We're not here to solve your homework for you.  Instead, the expectation on this site is that you will show us in detail what you've tried and how far you've gotten, and explain where you got stuck.  Then we might be able to help get you unstuck.  But just posting the problem description from your homework, nothing more, and expecting us to hand you the solution on a platter is not what this site is for.  This isn't a "solve-your-homework-for-you" site.


Why is feed-forward mechanism used in hash functions? The compression function of SHA-1 when used in Davies-Meyer mode adds its input to the chaining values at the final step. For the first message block, the IV is used as the input and in the next step, the previous block's output (as specified by Merkle-Damgård) is used. These values are fed to the last round of the compression function.

Why would removing the feed-forward part (i.e.,the final step where the input value is added to the result to get the final output) make the hash function insecure? Apart from the fact that the compression function would not satisfy desired randomness properties (being a permutation for each fixed message).

If you remove the feed-forward part, then you reduce the strength of the hash against preimage attacks.  We expect a hash with an $N$ bit output to require $O(2^N)$ steps to find a preimage (that is, an input that hashes to a specified value).  However, without the feed-forward, we can find a preimage with $O(2^{N/2})$ steps.

Here's why: without the feed-forward, the compression operation is reversible; if you know the output of the compression function and the block of data being hashed, you could compute the input to the compression function.

Here is how this works: suppose we have SHA-256 (to take a concrete example), and we want to find a preimage for a specific value $x$.  We consider two block messages (after padding); we construct $2^{128}$ initial blocks $A_i$ and compute what the state $a_i$ of the SHA-256 hash after each such initial block.

We also construct $2^{128}$ final blocks (which include the SHA-256 internal padding) $B_j$ and compute what the state $b_j$ of the SHA-256 hash would be previous to that (assuming that the final state of the SHA-256 hash is $x$.

We scan through the lists $a_i$ and $b_j$ looking for a match; if we find a specific pair $a_i = b_i$, we then know that the message $A_i B_j$ will hash to the value $x$; that's because the initial block $A_i$ will set the SHA-256 state to $a_i$, and then the final block $B_j$ will convert that state $b_j$, which is the same as $a_i$ to the desired final state $x$.  Thus, we found a preimage to a 256-bit hash with about $2^{128}$ steps.

In essense, we use an internal collision to find the preimage.  Adding the feed-forward makes this attack impossible.

(One note: if you try this attack against SHA-384, you find it takes $2^{256}$ steps, not $2^{192}$ as this analysis would seem to imply.  It is still easier than the $2^{384}$ steps would would expect from a 384 bit hash.


Why BGW Multiplication Gate Works? I am reading Pragmatic MPC (link) about the BGW protocol.
I also cross-reference here (click on lecture link for slides) *The BGW Construction for the Information Theoretic Setting – Benny Pinkas
I do not understand why the multiplication gate calculation can work.

First, let's say of $N$ parties, party $P_i$ has shares of wires $\alpha$, $\beta$ as $[v_{\alpha}]$, $[v_{\beta}]$. He can multiply them together to get
a point on the polynomial $q(x) = p_{\alpha}(x) p_{\beta}(x)$.
 But everyone's values together could then only be reconstructed with $q(x)$, where $q(x)$ is degree $2t$.

Useful fact: we say there exists $\lambda_i$ for $i =1 $ to $N$ (or can index to $2t+1$, but I didn't know why) such that $q(0) = \sum_{i=1}^N \lambda_i q(i)$ (I guess party $P_i$ has the value $q(i)$ in his possession). The $\lambda_i$ are the "appropriate Lagrange coefficients".

Every party $P_i$ can share their value $q(i)$. They pick $g_i$ such that $g_i(0) = q(i)$. (This polynomial was unnamed in the book, but maybe makes things more explicit). Then $P_i$ shares to all the parties so they have shares $[q(i)]$.

If we then think of what $P_i$ is receiving, he gets shares of $g_j(0)$ for each $j$, for him that means he gets the value $g_j(i)$.

Then, each $P_i$ on inputs $g_j(i)$ uses these points
to create the share for himself
$[q(0)] = \sum_{i=1}^N \lambda_i [q(i)]$. For party $P_i$, this means he can figure out
$q(i) = \sum_{i=1}^n \lambda_i g_j(i)$.

The value $q(i)$ turns out to be their share $[v_{\alpha}v_{\beta}]$.

I understand that these $\lambda_i$ should be the same as the one for the useful fact. Why?
Where did the useful fact come from?
I also took a look at a paper (didn't read through) of A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation
link where they say that the $q(x)$ (they call it $h(x)$) has a "specific structure". What does it mean?

Where do $\lambda_i$'s come from?

Consider a polynomial of degree 4, $p(x) = p_4 x^4 + p_3 x^3 + \cdots + p_0$. We can write polynomial evaluation as a linear operation on the coefficients:

$$
\begin{bmatrix}
p(1) \\ p(2) \\ p(3) \\ p(4) \\ p(5)
\end{bmatrix}
=
\begin{bmatrix}
1^0 & 1^1 & 1^2 & 1^3 & 1^4 \\
2^0 & 2^1 & 2^2 & 2^3 & 2^4 \\
3^0 & 3^1 & 3^2 & 3^3 & 3^4 \\
4^0 & 4^1 & 4^2 & 4^3 & 4^4 \\
5^0 & 5^1 & 5^2 & 5^3 & 5^4
\end{bmatrix}
\begin{bmatrix}
p_0 \\ p_1 \\ p_2 \\ p_3 \\ p_4
\end{bmatrix}
$$

The matrix in the middle is a Vandermonde matrix and hence it has full rank.

Now this also means that the rows of the Vandermonde matrix form a basis. So another vector like $[1~0~0~0~0]$ can be written as a linear combination of those rows, say:

$$
\begin{bmatrix}1 & 0 & 0 & 0 & 0\end{bmatrix}
=
\begin{bmatrix}\lambda_1 & \lambda_2 & \lambda_3 & \lambda_4 & \lambda_5\end{bmatrix}
\begin{bmatrix}
1^0 & 1^1 & 1^2 & 1^3 & 1^4 \\
2^0 & 2^1 & 2^2 & 2^3 & 2^4 \\
3^0 & 3^1 & 3^2 & 3^3 & 3^4 \\
4^0 & 4^1 & 4^2 & 4^3 & 4^4 \\
5^0 & 5^1 & 5^2 & 5^3 & 5^4
\end{bmatrix}
$$

Multiply on the right by the vector of coefficients and you can see that

$$
p(0) = p_0 = \sum_i \lambda_i p(i)
$$

More generally, if you have $d+2$ distinct points $x_0, x_1, \ldots, x_{d+1}$, then there exist coefficients $\lambda_1, \ldots, \lambda_{d+1}$ with the following property: For any degree-$d$ polynomial $p$, you can write $p(x_0) = \sum_{i=1}^{d+1} \lambda_i p(x_i)$. The $\lambda_i$ coefficients are the coefficients of the "Vandermonde vector" of $x_0$ when written in the basis of the Vandermonde matrix on $x_1, \ldots, x_{d+1}$, which is indeed a nonsingular matrix.

What is "specific structure" ?

It says right there in the next sentence (p14 of this):

  In addition, $h(x)$ generated in this way is not a “random polynomial” but has a specific structure.  For example, $h(x)$ is typically not irreducible (since it can be expressed as the product of $f_a(x)$ and $f_b(x)$), and this may leak information.

If I were to rephrase what they say: Given degree-$t$ Shamir sharings of $a$ and $b$, everyone can locally (i.e., without communication) multiply their shares. The result is a degree-$2t$ sharing. But there are two problems:

If this wire is used in subsequent multiplication gates, we need the value to be shared on a degree-$t$ polynomial.
The wire might not used in subsequent multiplication gates. Consider the case where it is an output wire, then the only thing we do in that case is open all the shares (to reveal the output). Now it is true that the degree of the polynomial doesn't really matter. But the distribution of the polynomial matters because the entire polynomial is revealed when the shares are announced.

Here the polynomial is known to be a product of two deg-$t$ polynomials. So if the polynomial is revealed, its factors are also revealed, and it could become obvious that $a$ is the constant term of one factor and $b$ is the constant term of the other factor. In other words, the protocol would leak $a$ and $b$ whereas we only wanted the product $ab$ to be revealed as output.

I'll note that the second "problem" can also be resolved by adding a random $2t$-sharing of 0 (instead of doing an interactive degree-reduction step). But in either case, the "raw" result of locally multiplying shares is not suitable for direct use. The protocol must include some mechanism to "sanitize" it.


How to calculate entropy of a combined key I know how to calculate the entropy of a key that relates to its selection process. For example if the key space is $1000$, entropy of a randomly chosen key is $1000$. Suppose now you have two keys $X$ and $Y$. The finale key $Z$ is a concatenation of $X$ and $Y$. There are two ways to combine. One is to use XOR and other way is to use a Key Based Key Derivation Function (KBKDF) such as HKDF. I want to know how to calculate the entropy of $Z$ when…

$Z$ = $X$ XOR $Y$
$Z$ = HKDF($X$,$Y$)

In the XOR case should I use mutual information of $X$ and $Y$?

With proper hashing the entopy of $Z$ is roughly the sum of both individual entropies, capped to the strength of the hash-function. For SHA-256 the limit is 256 bits, for SHA-512 it's 512 bits. Since entropy above 256 bits is meaningless, this isn't a practical limitation.

For XOR computing the entropy of $Z$ is tricky and depends on how your keys are distributed. It's probably only as strong as the stronger of the two key, which is clearly worse than the sum. If the keys are correlated it might even fail catastrophically.

=> Use HKDF with a good underlying hash


Induction is problematic in computational cryptography - Why? In Dr. Lindell's lecture The Yao Construction and its Proof Of Security, in briefly explaining the hybrid argument, he makes the statement that mathematical induction is a problem in computational cryptography. He is explaining that a hybrid argument is "like" mathematical induction, but not the same.

As far as I know, mathematical induction and hybrid arguments are not the same because for a hybrid argument, you need a finite ($k$) sequence of distributions for the proof to work (that is, eventually bounding the sum of the $k$ negligible differences by the max difference * $k$, which is negligible). For an infinite sequence, this doesn't work.

Does anyone know what Dr. Lindell means? I have a suspicion that it's a deeper point related to computability, but I'm not sure.

Thanks!

The problem with induction is what it typically hides. I'll give an example. Assume that I want to prove that $n$ samples of $X$ is indistinguishable to $n$ samples of $Y$, assuming that a single sample is indistinguishable. Instead of doing a hybrid argument, I prove by induction. The base case is immediate, since a single sample is indistinguishable by assumption. Next, I assume for $i$ and prove for $i+1$. In this claim, I prove that for every PPT adversary $\cal A_{i+1}$ who can distinguish $i+1$ samples with non-negligible probability, there exists a PPT adversary $\cal A_i$ who can distinguish $i$ samples with non-negligible probability (or a distinguisher who can distinguish a single sample, but let's leave that for now). It seems that this suffices for the proof to go through.

However, what happens if $\cal A_i$ runs in twice the time than $\cal A_{i+1}$ (this is of course fine since they are both polynomial time)? Then, when I "unwind" the induction, I will get the following. Assume that there exists a probabilistic polynomial-time adversary $\cal A_n$ who distinguishes $n$ samples with non-negligible probability; let $p(n)$ be its running time. Then, by applying the inductive argument repeatedly, I obtain that there exists an adversary $\cal A_1$ who distinguishes a single sample, but runs in time $2^n\cdot p(n)$, thereby contradicting nothing.

Another problem that can happen is as follows. Assume that our proof of the inductive step is such that $\cal A_{i+1}$ distinguishes with non-negligible probability $\epsilon(n)$ and as a result $\cal A_i$ distinguishes with non-negligible probability $\epsilon(n)/2$. This is of course fine since both probabilities are still non-negligible. However, when we unwind the induction, if $\cal A_n$ distinguishes with non-negligible probability $\epsilon$, we will have that $\cal A_1$ distinguishes with probability $\epsilon/2^n$ which is negligible. Thus, no contradiction is achieved.

In order to overcome this, one can prove explicitly in the inductive step that the running time difference between $\cal A_{i+1}$ and $\cal A_i$ is additive, meaning that there is an additional polynomial factor only. Then, over $n$ (or any polynomial) steps of the induction, the additional running time overall is still polynomial. Likewise, if there is a reduction in the distinguishing probability, then the result at the end is still non-negligible.

I have used induction once in a paper; see pages 22-23 of http://u.cs.biu.ac.il/~lindell/PAPERS/session-key.ps, so it can be done. But one must be careful.

(A note: all of the above I learned from Oded Goldreich.)


Exponentiation In PBC library I need to compute a function $h^l$, where h is an element of G2 and l is a rational number. How can this be done using the PBC library?

I have converted the h to an element in G2

As far as I have seen, for exponentiation, PBC has two functions :

element_pow_zn, and
element_pow_mpz

The first function is used when both the operands are of type element_t. The second function will be used when the power is of type mpz_t.

I read in the pbc manual that the mpz_t type is for integers in GMP, while mpq_t is for rationals. Can I use any of the functions in PBC to acquire the required exponentiation? If yes, how will I have to declare the elements?

UPDATE

Will such an initialization work :

mpz_t a, b, l;
element_t ea, eb, el, bi, t1, res;
....after computing a , b, I can use
element_set_mpz(ea, a);
.
.

element_invert(bi, b);
element_pow_zn(t1, h, a);
element_pow_zn(res, t1, bi);

I don't think $h^l$ where l is a float number is a well defined operation in a finite group, regardless of what context you want to use this group for.
A group is a set of elements G with a binary operation $\cdot$ (multiplication) defined, often denoted as (G,$\cdot$) satisfying four properties. You can find more information here: http://mathworld.wolfram.com/Group.html.

Then, exponentiation is defined as repeating multiplication on a group element a certain number of times. For example, $h^n=h\cdot h\cdot h \cdot ... \cdot h$ (repeating $n$ times). So you should be able to see that for example repeating multiplication 3.1415956 times is not well defined.

Specifically, for pairing, G2 is a group over the twist curve. In this group, one operation is defined. Usually, this operation is called point addition. However, in PBC, if you look at the document, it is said that "The addition and multiplication functions perform addition and multiplication operations in rings and fields. For groups of points on an elliptic curve, such as the G1 and G2 groups associated with pairings, both addition and multiplication represent the group operation (and similarly both 0 and 1 represent the identity element). It is recommended that programs choose and one convention and stick with it to avoid confusion." (http://crypto.stanford.edu/pbc/manual/ch04s04.html).

So, the operation you are talking about is not well defined.


RSA exhibits symmetrical properties — is it possible to form a cryptanalytic attack? This question is broken into two sections really:

Symmetry in RSA

I have been analyzing raw RSA and I have noticed some interesting symmetrical properties of the algorithm.

Assume that $M$ is a positive integer between $2$ and $N\over2$, ($N$ is the RSA modulus). Then:

$$
   M_s = N - M
\\ C = M^e \pmod N
\\ C_s = M_s^e \pmod N
$$

This means that $C + C_s = N$, $M + M_s = N$, $C - M = C_s - M_s$ and  therefore $C_s = N - C$. Also,
$$(N-M)^e \mod N = N - (M^e \mod N)$$

Let the RSA modulus ($N$) be the circumference of a circle radius $r$. Converting each $M$ value from $1$ through to $N - 1$ into segments of the circumference, each with an equal angle between segments, then it will be possible to convert each $M$ and its corresponding $C$ into Cartesian coordinates ($X, Y$) using the formula:

$$ (X,Y)= \left(r \cdot \cos({M\over360}) , r \cdot \sin({M\over360}) \right) $$

Using $X$ and $Y$ to plot a line across the circle from $M$ to its corresponding $C$ value. In some cases when calculating $C$, $C$ will be equal to $M$ (for example when $M = 1$). In these cases draw a loop back to $M$.

In all cases the end diagram will be symmetrical through the diameter of the circle from 0 to 180 degrees.

Example: RSA using $P=11 and Q=7$

(These small numbers were chosen deliberately in order to show the symmetrical pattern. The symmetrical property is the same with large primes, but because there are so many more $M$ values the image becomes a blur of lines, which are indistiguishable from one another. It is also impossible to spot the loop backs (see below)).

This also means the one can accurately predict the cipher text of a symmetric partner of $M$.

Inherently weak primes and RSA

Some prime numbers are very weak with regards to RSA. Examples include $P = 257$ or $Q = 193$. This is because $P-1$ is smooth, e.g. $P-1$ is smooth to $2$ ($2^8$), $Q-1$ is smooth to $3$ ($2^6, 3^1$). When these two primes are combined as $N=PQ=49601$, this produces $16705$ “loop backs” (where $C = M$). The interesting thing about this is the value of $M$ when the “loop back” occurs. For this combination the first ten loop backs are:
$$1, 3, 8, 9, 11, 13, 14, 20, 23, 24$$

Why is this significant?

If $Z = C \pmod M$ then in most cases $Z = M$. Where this doesn’t happen we can say that:

If $Z = 0$ then $T_1 = C$ else $T_1 = Z$

This means that in most cases $T_1 = M$. Thus we can say:

If $T_1 \neq M$ then $T_2 = \gcd(T_1, N)$
If $T_2 = 1$ then $T_3 = M – C$

In most cases $T_3 = P$ or $Q$. When $T_3 \neq P$ and $T_3\neq Q$:
 - $T_4 = GCD(T_3, N)$
 - $T_4$ will be either $P$ or $Q$.

$T_5 = {T_3 \over T_4}$.

The value of $T_5$ will always be one of the loop back $M$ values, e.g. $1, 3, 8, 9, 11, 13, 14, 20, 23, 24, \dots$

Although this is easy to demonstrate with small value weak prime numbers, the same case is applicable to large value RSA with strong primes. These are harder and more time consuming to calculate because of the vast size of the data to be collected. To perform this analysis one must iterate over every $M$ value between $2$ and $N – 1$.

Example: Loop back image for $P=257, Q= 193$

My question:

Is it possible to use any of this information to form a cryptanalytic attack against RSA?

The first observation in the question boils down to: in textbook RSA, the encryption of $N-M$ instead of $M$ yields $N-C$ instead of $C$.

This is a special case of a more general property of textbook RSA, that the encryption of $M\cdot M'\bmod N$ yield $C\cdot C'\bmod N$, whenever enciphering $M$ yields $C$ and enciphering $M'$ yields $C'$; combined with the elementary fact that enciphering $M'=N-1$ yields $C'=N-1$.

These properties are the basis of numerous attacks on textbook RSA, including some of these (and of attacks on real RSA signature schemes with ad-hoc padding, such as on ISO/IEC 9796-2 scheme 1). This is why textbook RSA should not be directly used for anything else than random messages, or messages sufficiently close to that.

A second observation in the question considers the case of $N=P\cdot Q$ with $P-1$ smooth.

The worst thing if that happens is that it is easy to factor such $N$, using Pollard's p-1 factoring algorithm (giving a total break, making the considerations in the question of secondary importance). However this is not a serious weakness of RSA, for the odds of accidentally selecting such a $P$ are vanishingly small for usual order of magnitude of $P$; see the Dickman function for a numerical estimate.

Further, we can avoid such $P$ with relative ease; this remains standard practice at least for $P$ up to 512 bits (see appendix B.3 in FIPS 186-4, and in particular the requirement in B.3.1 A: "p and q with lengths of 512 bits shall be generated using the conditions based on auxiliary primes"). The only case when this might matter (there is not quite a consensus here) is when one generates ziiillions of keys, with $\log_2P$ below or close to 512, and a marginal risk that even one public key is vulnerable to Pollard's p-1 factoring is unacceptable (the adversary's best use of CPU time might be to attack each key with Pollard's p-1, rather than a few keys with other factoring methods).


Difference RSA keypair creation openSSL and openPGP? Creating a 2048bits RSA keypair I figured that doing this using

openssl takes as an input 32bytes of "randomness" from /dev/urandom
pgp (openPGP) takes as input 300 bytes of "randomness" from /dev/random

My questions is. Does the number of randomness influence the cryptographic qualities of the resulting keypairs?

The difference is inconsequential in this context.

If you do some "processing" (e.g. generating a RSA key pair) using a deterministic and publicly known algorithm (e.g. OpenSSL's code) where the only parameter which is not known to the attacker is a random $n$-bit seed (e.g. $n$ = 256 for 32 bytes from /dev/urandom), then there is a theoretical possibility of an attack by exhaustive search on the seed: the attacker tries to guess your private key by trying out all possible seed values, until he finds one which yields your actual public key when fed to the deterministic key pair generation algorithm. The cost of that exhaustive search is, on average, $2^{n-1}$ tries. When $n$ grows, this cost soon becomes too prohibitive to be envisioned by the attacker.

Indeed, a 2048-bit RSA key can also (and still theoretically) be broken through integer factorization. How the cost of integer factorization relates to the cost of exhaustive search is not an easy question, because the involved algorithms have quite distinct characteristics (exhaustive search uses almost no RAM and is easy to make parallel, while integer factorization gobbles gigabytes or more of RAM and some parts of it are very hostile to parallel computing). You may peruse this site for various estimates from different groups of smart people. Bottom-line is that a 2048-bit RSA key can be deemed "as strong" as a symmetric key in the 100 to 115-bit range (which translates to an uncertainty by a factor of more than 30000, which shows how fuzzy these estimates are).

From this, we can conclude that any seed length beyond 115 bits is overkill: as long as the seed is "really random" (i.e. completely unknown to the attacker) and its length is at least 115 bits, then exhaustive search on the seed is not worth the effort for the attacker, since integer factorization will be easier (2048-bit integer factorization is not doable with existing technology anyway, but neither is a 100-bit exhaustive search). OpenSSL's 256 bits are thus total overkill with a wide margin; GnuPG's whooping 2400 bits even more so.

Then there is the recurrent debate about /dev/urandom vs /dev/random. To make things short, neither is "stronger" than the other (despite widespread myths), but /dev/random may imply usability issues (blocking at inopportune times) which can turn into actual security issues, so its use is discouraged. In that sense, OpenSSL does the Right Thing, and GnuPG errs. See this page for a well-explained summary of why /dev/urandom should be preferred.


Where is SRP-Z from? The Stanford license for SRP says:

  Broader use of the SRP authentication technology, such as variants
  incorporating the use of an explicit server secret (SRP-Z), may
  require a license;

Yet I cannot find a succinct description of the SRP-Z protocol and why it might be useful. As a follow up question assuming it is useful and patented when does the patent expire?

This question both describes the SRP-Z variant and mentions that the patent should expire in three years.
I think the patent in question is this one, but I'm not sure: US 6539479. If it is, it seems to actually have expired earlier this year due to non-payment of fees. Looking it up on the USPTO PAIR says:

Status:   Patent Expired Due to NonPayment of Maintenance Fees Under 37 CFR 1.362
Status Date:  04-20-2015

It is still possible it could be revived after such expiry, but IANAL, etc.


What is a "set synchronized CSPRNG"? I'm looking to implement a performant revocation method for JWTs. I'm reading a paper, in which the following section's second paragraph states:

  If we use the client hashing approach described previously, we have a greater volume of keys to deal with. One possible approach would be to generate the secret using a set synchronized cryptographically secure pseudorandom number generators, creating a kind of rolling code for each group of clients. This would mean that only the key change events have to propagate, not the actual keys themselves, greatly reducing the associated performance cost.

What is a set synchronised cryptographically secure pseudorandom number generator (CSPRNG)?

I know what a CSPRNG is, in that it is a random number generator with an acceptable degree of randomness. But what is the set synchronised part? Does it relate to synchronised sets in Java? What does being set synchronous achieve in this context?

A CSPRNG is really just a name for an algorithm that, given a specific seed (where the seed has a certain amount of entropy) generates a pseudo random stream from that. A stream cipher that generates a key stream independent from the plaintext can be thought of as a CSPRNG in that sense.

So say you have a fully random 128 bit seed, then you can use that seed to generate an almost endless amount of key stream. This key stream can then be split up into separate keys.

In practice you should not confuse this with a CSPRNG or random number generator that is supplied by the system itself. The problem is that the internal operation and reseeding-strategy may introduce changes between different streams: generally such algorithms are only used to generate random values after all.

To be honest this seems more a good application for a ratchet scheme than one for a random number generator as you know it. Of course, if you take the theoretic approach, somebody could argue that - from a theoretical standpoint - the ratchet scheme constitutes CSPRNG.

Directly related to this is also the notion of KDF's, key derivation functions, which can calculate multiple keys from one specific master keys. However, in this case the key not dependent on the previous keys. It could be that a key management scheme requires one or the other, or both.


HMAC-SHA256 for hashing of credit card PANs? Assume you had no option (really) but to store thousands of credit card PANs in a file.  You do not need to decrypt them ever, but you do need to use it for checking if a given (new) PAN exists in that list.

To protect the PANs, the idea is to HMAC-SHA256 them.  This scheme naturally relies on the HMAC secret remaining secret.  Please assume for this question we can take that as given (HSM).   Also, that the secret is a truly random 64 byte secret.

Is there any kind of attack that could be realistically mounted to crack this?  One can reduce the search space by knowing that credit Card PANs have an obvious pattern - from 15/16 digits,  one can remove the luhn digit, and the first (say) 6 digits (BIN).

An attacker would pick a likely BIN, and then iterate through the 10^9 possible PANs, hashing them against every possible key.

This looks to me like it would take longer than the universe's expected life, even with incredible hardware.  Exhaustive hashes required = 10^9 * 2^512.

Having prior knowledge that a given PAN is definitely on the list,and thus dividing the number of hashes by 10^9, does not make any real difference.

Have I missed anything here, or is this reasoning correct?

Under your assumptions, everything will be secure, as long as HKDF is secure and your key is secure (assuming attacker has only offline access to data, not be able to for example check if given credit card number was already entered). Currently even 2^128 is far out of our reach. But I wouldn't say that this will remain until end of universe. It is possible that in future we will find SHA-2 weaknesses and be able to use them to crack your solution.

Your scheme can however be easily broken if key was stolen. If this is consideration, you can reduce output size and increase risk of collision while making attacker struggle with same thing. However, I have no idea if this allowable in your scheme since you didn't give any details on how such thing would be used.

All in all, I would be most scared of flaw that would give attacker ability to do, what you can do: Check if number is on list, because of breach and access to HSM interface (which can also suppress any warnings of hash rate etc.).


How to select parameters based on some condition I am implementing a protocol for authentication where parameters need to be selected with $gcd(\mu,\phi)=1$ where $\phi=(p−1)(q−1)$. What is the best way to select the parameters while implementing

I'll first assume $\phi$ is known, which would be the situation in RSA at key selection.

A common method could be to select (odd) $\mu$ at random in some appropriate interval until $\gcd(\mu,\phi)=1$ is satisfied. In the context of RSA, it is fine (if we ignore performance an interoperability issues) to choose an RSA exponent at random in $[3\dots\phi-3]$ that is coprime with $\phi=(p−1)(q−1)$.

Another option would to restrict to prime $\mu$, which increases the odds that $\gcd(\mu,\phi)=1$: for random choice of large primes $p$ and $q$, a moderate prime $\mu$ has odds $({\mu-2\over\mu-1})^2$ to be acceptable. For example, $\mu=65537$ (the most common choice for RSA) would likely be fine.

When candidates for $\mu$ are examined in prescribed order, from the choice of $\mu$ a little information leaks about $\phi$; this is usually a non-issue.

If we somewhat must arrange that $\mu$ be chosen without knowledge of $\phi=(p-1)\cdot(q-1)$, one option is to select distinct primes $p$ and $q$ of some bit size $b$ such that $(p−1)/2$ and $(q−1)/2$ are primes; in this way, any odd $\mu$ less than $b-1$ bits verifies $\gcd(\mu,\phi)=1$.


How to generate a 128 bit IV from a 32 bit value for AES-128 OFB I have no clue how to determine suitable 128 bit IV (initialization vector) from a 32 bit IV. Encryption AES-128 OFB. The 32 bit IV has value  0x9a23773c (transmitted in front of the data). Any ideas?

OFB mode directly uses the IV as input to the block encryption - in this case by AES. So generally there is no 32 bit IV possible, it must be exactly the same size as the block size of the block cipher. OFB does not define any way to go from a 32 bit nonce to a 128 bit IV - if such an operation is defined then it is defined outside of the OFB definition in NIST Special Publication 800-38A: Recommendation for Block Cipher Modes of Operation.

Usually however the 32 bits are simply defined as leftmost bits of a 128 bit value, with zeros appended to the right hand side. Putting the values on the right hand side may also be a possibility however. Actually the bits can be put through any operation and put in any place as long as the result remains unique. But it seems unlikely that such an operation takes place at it would not have any function. Just try copy the bytes into the front or the back of a 128 / 8 = 16 bytes buffer and try if you guessed correctly.

Or ask the person that created the protocol of course, it never hurts to ask such a thing because they should have defined it for you.


Is EncFS good for online storage services? Conclusion from an EncFS audit:

  EncFS is probably safe as long as the adversary only gets one copy
  of   the ciphertext and nothing more. EncFS is not safe if the
  adversary   has the opportunity to see two or more snapshots of the
  ciphertext at   different times.

I don't quite understand this sentence: "to see two or more snapshots of the ciphertext at different times". Given a scenario, e.g. my Dropbox was hacked, and the hacker has access to my EncFS encrypted texts, and probably the history of it as well. Is that what was mentioned as "two or more snapshots" and "different times"?

Given a scenario, e.g. my Dropbox was hacked, and the hacker has access to my EncFS encrypted texts, and probably the history of it as well. Is that what was mentioned as "two or more snapshots" and "different times"?

Whether it applies depends on how the storage system would work. As far as I can tell, EncFS itself has no backup/versioning capability. Assuming that is the case, a storage system which supports history could implement it in one of two ways:

Do the versioning on top of EncFS. So the versioning system itself is stored in the encrypted filesystem.
Do it on a level below EncFS. So different versions of the filesystem exist.

In the former case, an attacker who only gained access to the system once could not see two copies of the ciphertext. In the latter they could.

In the real world, it is possible both would be used. E.g. if versioning is done on top of EncFS, but whole system backups are also stored. An attacker who got access to backups would be in a better position to break the encryption.

However, the audit details several weaknesses that even an attacker who only got access to a single snapshot could exploit, so I would disagree with the conclusion you quoted. For example, an attacker could punch holes in files without being noticed, and if the filesystem was large enough could find IV collisions leaking information on plaintext.

  Is EncFS good for online storage services?

I would argue that it is not. It is probably better than nothing and if only passive attackers need to be protected against it may even be secure. However, even the README points to some more modern alternatives. (Without saying EncFS is insecure or anything.)


How is key length of feistel cipher calculated? In Feitsel Algorithim

If our block size is n, then our key length would be n x 2^n .

But this does not make sense for me.
For example: Let's assume that we have 4 bit block size. If our block size is 4, how can the key length be 64 bit?

You have some confusion here: The formula N * (2 ** N) for key size is for ideal block ciphers that select one of (2 ** N)! permutations. Shortly after that formula, your book starts to go into the Feistel construction (emphasis is mine):

The Feistel Cipher
Feistel proposed [FEIS73] that we can approximate the ideal block cipher by utilizing
the concept of a product cipher, which is the execution of two or more simple ciphers
in sequence in such a way that the final result or product is cryptographically stronger
than any of the component ciphers. The essence of the approach is to develop a block
cipher with a key length of k bits and a block length of n bits, allowing a total of 2 ^ K possible transformations, rather than the 2 ^ N! transformations available with the ideal
block cipher

So the idea is to compromise on the huge key length and sacrifice the ability of picking one of all possible permutations, to utilize a smaller key that can select one of enough possible permutations. A cipher will typically use a key length that is equal to it's target block size, to simplify the key addition layer.


Authenticated EC key exchange without a signing/signature scheme? From my little understanding of EC-based authenticated key exchange protocols,  I believe that it is not possible for authenticated key exchange without a signing/signature scheme. Is this correct?
Consider a scenario where neither client nor server have any certificates, and server has the pre-shared secret of User/client. In this scenario, what is the technique/protocol for using ECDHE-based authenticated key exchange?

For a pre-shared secret, you just use a secure MAC to authenticate the key exchange, e.g. for the exchanged public ephemeral keys $A$, $B$ and the resultant shared secret $S$, one side could send $HMAC(PSK, S, A, B)$ and the other $HMAC(PSK, S, B, A)$.  Each side can easily verify that the other is using the same exchanged values and shared secret, and that the message could only have come from someone with the same PSK.  They could then use $HMAC(PSK,S)$ for the encryption key, for example.

There are several public-key methods of authenticated key exchange that can work using EC, basically using DH with an ephemeral session key and a public key.  Although the use of the public key can be thought of as signing the key exchange, it's done in an integrated fashion so there's no explicit signing step, the proofs exchanged are as much a proof of the ephemeral keys as they are of the public keys.

An example is SRP-Z (the mutually-authenticating version) with keys instead of passwords (the method uses modular addition, but that's not necessary if the public key isn't subject to a dictionary attack, i.e. it's a strong key rather than a password).  You could also just use ordinary SRP if the verifier is kept secret and a strong key is used (instead of deriving the key from a salt and password), with the same reasoning as above.

Other examples are YAK, which has a very similar structure to SRP-Z, STS, and KEA+.

KEA+ is patented, as is SRP (though SRP is licensed for free for the non-Z form).


Finding a keylength in a repeating key XOR cipher In an old cryptography FAQ, I found the following step described for determining a the length of the key a cipher was repeatedly XORed against:

  Discover the length of the key by counting coincidences.
  (See Gaines [GAI44], Sinkov [SIN66].) Trying each displacement of
  the ciphertext against itself, count those bytes which are equal.
  If the two ciphertext portions have used the same key, something
  over 6% of the bytes will be equal. If they have used different
  keys, then less than 0.4% will be equal (assuming random 8-bit bytes
  of key covering normal ASCII text). The smallest displacement which
  indicates an equal key is the length of the repeated key.

The wording of the bolded text is the part I'm confused with. Given that my plaintext equals the string "This is a secret message", would I be comparing the first n number of bytes with a second set of n number of bytes that is offset from the first (e.g. the xor'd version of "Th" with "is", if I was comparing 2-byte chunks of the cipher against itself)?

If not, what's the correct way to interpret this passage? Thank you.

You'd be trying each possible displacement (offset).

Suppose the ciphertext is CXEKCWCOZKUCAYZEKW.  Here's displacement 1:

CXEKCWCOZKUCAYZEKW
 CXEKCWCOZKUCAYZEKW

At displacement 1, there are no matches (nothing where the a letter in the top line is equal to the letter immediately below it).

Here's displacement 2:

CXEKCWCOZKUCAYZEKW
  CXEKCWCOZKUCAYZEKW
      ^

You can see that, at displacement 2, there is one match.

Here's displacement 3:

CXEKCWCOZKUCAYZEKW
   CXEKCWCOZKUCAYZEKW

At displacement 3, there are no matches.

In this way, you can count the number of matches at each displacement.

The idea is that, if you line up the ciphertext with itself displaced by $k$, where $k$ is the period of the keystream (i.e., the length of the key), then you get a match in the ciphertext (offset by $k$ places) if and only if there is a match in the plaintext (offset by $k$ places).  Now it's a property of English language that the frequency distribution of English letters is not uniform: some are more likely than others.  If you pick two positions at random from an English text, there's about a 6% chance (say) that those two positions have the same letter.  Consequently, when you've guessed $k$ correctly, there's about a 6% chance that any particular ciphertext letter matches the one $k$ positions later.

In contrast, when you line up the ciphertext with itself displaced by something displacement that does not match the key length, the chances of a match at any particular position are much smaller (1/256, if ciphertexts are bytes; 1/26, if ciphertexts are letters).


RSA: Decrypting message with public key and private key I am trying to decrypt a message which its ciphertext in Hex A3 BB 05 00.
The original plain text is 8 bits and it is encrypted by a 32 bits RSA key.

I have successfully found the public key is $(e=947,n=2671079)$ and the private key is $(d=713604)$.

Then, I try to convert the Hex string to integer 00 05 BB A3 (Little Endian) $=375715$.

Finally, I calculate $C^d \mod n = 375715^{713604} \mod 2671079 = 544824$.

  Calculate in python: C**d % n

My problem:

1) what does $544824$ mean? Is it the original plain text or I need to further converting this number?

2) The plain text should be 8 bits, why the result I get is larger than 8 bits?

thanks!

Your ciphertext is A3 BB 05 00

In RSA, the ciphertext is always larger than the original data. In this case, the keys are 32 bits, which is 4 bytes, and A3 BB 05 00 is four bytes


What is the relationship between a NIZK protocol and a digital signature scheme? I am reading about the Fiat-Shamir heuristic to take a $\Sigma$-protocol into a non-interactive zero-knowledge proof (NIZK). I am now wondering whether there is a relationship between a NIZK proof and a digital signature scheme?

Specifically, can we take a NIZK proof obtained from applying Fiat-Shamir to a $\Sigma$-protocol and turn it into a digitial signature scheme? (Are there specific requirements for the underlying $\Sigma$-protocol?)

Recall that in strong existential unforgeability for
digital signatures, we want it to be the case that even after seeing many signatures under different instances, it should still not be possible to create a new signature unless you know the secret key (equivalently witness in a NIZK).

So, one can use a NIZK to design a digital signature (of knowledge), but the underlying NIZK needs to provide a more stronger version of soundness (a standard NIZK only provides soundness) that technically is known as simulation-sound extractability. Intuitively, simulation-sound extractability in NIZKs is equivalent to concept of strong existential unforgeability. More precisely, simulation-sound extractability implies that it is only possible to prove instances to which you know a witness, even when you have already seen a number of simulated proofs (signatures).

To sum up, a digital signature of knowledge can be designed using a NIZK that guarantees simulation-sound extractability.


Are CDH and Square-DH equally hard? CDH problem roughly says that choose $U=g^u, V=g^v$ uniformly at random from  cyclic group $G$, it's hard to compute $\operatorname{CDH}(U,V)=g^{uv}$.

Square-DH problem roughly says choose $U=g^u$ uniformly at random from  cyclic group $G$, it's hard to compute $Z=g^{u^2}$

If I can solve the CDH problem, then it's very clear that Square-DH problem can also be solved easily: $\operatorname{CDH}(U,U)=g^{u^2}$. While, if Square-DH problem can be solved, then we can solve CDH problem of $UV$:
 $$g^{{(u+v)^2}}=g^{u^2+v^2+2uv}=g^{u^2}g^{v^2}\operatorname{CDH}(U,V)^2,$$ while Square-DH problem of $U$ and $V$ can be solved.  So by dividing $g^{u^2}$ and $g^{v^2}$, we get $\operatorname{CDH}(U,V)^2$，and at last, compute the square root of $\operatorname{CDH}(U,V)^2$, we get $\operatorname{CDH}(U,V)$

So, can I say that they are equal to each other?

Mostly.

The two problems are actually more closely equivalent in a gap model than in a non-gap model.

Square-DH clearly reduces to CDH either way, but CDH reduces to two calls to Square-DH (you have 3, but you can use $(u-v)^2$ to make it 2).  This is fine if the Square-DH adversary is always right, but maybe the adversary only solves the Square-DH problem with probability $\epsilon$.  The reduction doesn't know whether the adversary succeeded, so it solves CDH with probability only $\epsilon^2$.

If you get to try many times to solve CDH, you have to run the Square-DH adversary $O(2/\epsilon)$ times, and make $O(\epsilon^2)$ guesses, which is somewhat loose... unless you have a DDH oracle, like in the gap model.  In that case, you can filter out wrong Square-DH attempts.  The reduction is still not perfectly tight, though.  It can solve the CDH problem in time $t$ Square-DH calls with a probability which is to first order $t^2\epsilon^2/2$ when $t\ll1/\epsilon$.  So if your adversary is inaccurate and you don't have much time, it's still a loose reduction, but if you have $\approx 1/\epsilon$ time, it becomes tight again.


Creating a random password based off of a prime number So I am making an application that basically creates strings that must be encrypted before they are stored on a user's device. If the user blindly starts running the application without creating a password before hand OR they cannot come up with a long, strong password, would this method be appropriate? (Language is java)

Create a probable prime of 512 bit length

BigInteger.probablePrime(512, new Random())

Add a random number of 512 bit length

.add(new BigInteger(512, new Random()))

Convert number into Base32

.toString(32);

The above steps will yield a Base32 string that is about 100-103 characters long and will look something like this:
2si95285qk2trk65hona7q0j27o81ph6adjs2obd2g83q9nho52tonku7s3uajtja54ri2dkbque39hil14f1nrlef0736mtda7rtll

And it is up to the user to safely store this password if they do not create one themselves.

So my question, is this a plausible method to create a random password if the user does not make one before hand or cannot create a password this long (though it is not required)?

If you just need random numbers, there's no point in generating random primes.  Just make sure that you're using a cryptographically secure random number generator, properly seeded from a secure entropy source.

Also, passwords made up of random letters and numbers are very hard to remember (and type).  For a password meant to be memorized by a human, it's much more efficient (in terms of security vs. effort) to generate a passphrase made out of random words instead.  See diceware and this xkcd strip for some well known examples.

Also, 100 random base-32 characters equals 500 bits of entropy.  That's ridiculous for a password; 128 bits of entropy is plenty for anything, and you're probably OK with 80 bits or even less, depending on what kind of threats you're expecting.  If your key derivation function does proper key stretching, that'll add some 10 to 30 bits of effective strength to your password (depending on the iteration count), allowing you to reduce its length even further.

A typical randomly chosen word has about 10 to 14 bits of entropy, depending on the size of the word list (a diceware passphrase has just under 13 bits of entropy per word), so generating a passphrase of five or six random words and using a key-stretching KDF should be safe  enough.


what's the advantages of identity-based systems over certificate-based ones? Actually, I'm not familiar to how  identity-based and  certificate-based systems work, so ,can anyone give me a detail and comprehensive answer to this question? Moreover, in what environments the  identity-based systems is recommended(or needed) and why?

Public key crypto vs. identity-based crypto made short:
In traditional public key cryptography, a user $A$ generates a
private/public key pair $(sk_A,pk_A)$ and since this key pair has
absolutely no indication to which indentity (user $A$) it belongs, it
is necessary to certify the public key, i.e., bind the public key
$pk_A$ to the user $A$'s identity. This is commonly done by lettig some
trusted authority sign $pk_A$ with additional identifying information
of user $A$ after user $A$ proves by some means that he really is user
$A$ (the result is what is called a certificate).
Identity-based cryptography aims at letting the users public key
be its identity (e.g., the email address) and so to remove the
requirement for certificates. In ID based cryptography a user $A$ uses
his identity (e.g., his email address) as public key. Now, however,
since this information could be used by anybody as an identity it is
clear, that there needs to be some other entity involved in generating
the respective private key. We require a trusted authority (the key
generation center) to compute the private key $sk_A$ that corresponds
to the public identity string $ID_A$ and this trusted authority has to
check whether $ID_A$ (e.g., the email address) indeed corresponds to
$A$ and then issues the private key $sk_A$ corresponding to the
identity $ID_A$. Since the private keys are generated with respect to some public parameters, every party in the system needs to be in possession of an authentic copy of the public parameters (this is similar to a root CA certificate in certificate-based crypto).
Pros and Cons
In theory, the main advantage of identity-based crypto and in particular identity-based encryption is that you do not need to obtain the public key of the recipient but simply can use the recipients identity (=public key) for encryption and the recipient actually does not even need to be in the possession of the respective private key at the point of time when the ciphertext is produced.
In practice, this, however may be not that easy to achieve as theory makes it look like.
Actually, there are various issues which are discussed in the papers I have linked in my previous comments, but I think the most relevant issues are:

Key generation: In traditional public key crypto users generate their keys locally and they are only known to them, while in
the identity-based setting the keys are generated by the trusted authority (inherent key escrow - the party may decrypt all user's
ciphertexts and or may issue signatures on behalf of users. Since the latter is also a problem in certificate-based systems, i.e., the CA
can always produce valid certificates for users and thus sign on their behalf, the decryption issue seems to be far more
problematic). In theory, there is the possibility of distributed key generation in context of identity-based systems, i.e., more than one key generation centres are involved in private key generation, but I doubt that they will really see wide deployment/application.

Revocation: Certificate-based approaches, e.g., PKIX, employs certificate revocation lists or certificate status protocols to check whether a private key has been compromised. If one wants to use the full power of identity-based systems, then ideally the identity (public key) is some information everyone knows, e.g., an e-mail address. But what happens if the corresponding private key gets compromise? Close the email address and choose a new one to get issued a new private key (that does not seem to be really possible in practice for various reasons). Thus, identities need to contain some additional information such as a key expiration date, e.g., mail@bla.com||expiry_date. Now, this forces public keys to be strings that are no longer that well known to other users and require look-ups (sounds similar as whats done in certificate-based crypto). Furthermore, what happens when the key is compromised before the expiry_date? One needs some mechanisms to signal and check that keys have been compromised (sounds similar as whats done in certificate-based crypto). So where are the theoretical advantages now?

Moreover, in what environments the identity-based systems is recommended(or needed) and why?

I would say that, since distributed key generation has not really shown to be used in practice,
identity-based crypto is more for closed environments (enterprises, maybe sensor networks) and not for open environments. Essentially, in any situation
where key escrow is not such an issue, key renewal can be efficiently performed and revocation checks can be made efficient, identity based crypto may be an alternative.
Anyways, it seems that a hybrid between identity-based crypto and certificate-based crypto seems more realistic.
There is also something in between:
Certificateless public key cryptography is inbetween these two
approaches. It aims to get rid of the problem that the key generation
center gets to know the entire  private keys of all users.
In this approach the key generation center only
computes a partial private key of user $A$ based on the identity $ID_A$ and the user then combines this partial private key with some secret information (only known to him). Then the user needs
to take the public parameters of the key generation center and combines
the secret with this parameter to obtain the user's public key. The
advantage here is, that this public key does no longer need to be
certified, since it contains the identity $ID_A$ of user $A$ and if the
key generation center is trusted (and the public parameters of the key
generation center are authentic) one can assume that the user
associated to $ID_A$ really corresponds to $A$ and holds the
corresponding private key.


How to encrypt a message such when a certain condition is met it can be decrypted? Assume, there is a certificate authority whose public key: $pk$, is known. Also, the certificate $c$ is known, but not the signed certificate.
I want to encrypt a message: $m$, such that whoever has a signed certificate can decrypt the message. Note that the signed certificate may not be present at encryption time. To clarify, the signed certificate must be valid and related to $c$ and $pk$.
Question: What encryption can support the above scenario?

I'm aware that witness encryption may help but it's so inefficient.

Edit
Application: assume, party $A$ has a message $m$, it encrypts it: $Enc(m)$, such that when he dies, whoever gets his death certificate (i.e. a signed messages from a certain authority that confirms his death) can decrypt the ciphertext: $Enc(m)$.
So the question is what encryption scheme can the encryptor use?

You can use a standard asymmetric encryption like RSA. Certificates merely serve the purpose of linking things to other things, approved by some (hopefully trusted and trustworthy) entity.

What you're probably thinking about is an ID certificate which links an identity to a public key. This key is in no way encrypted. It simply occurs in a field of the certificate. Signing the certificate does not change its fields. It just adds a signature of everything else.

This means that anyone with access to the certificate has access to the public key, be the certificate signed or not. Signing the certificate mere means: "I approve of this."

Regarding your edit: When you want to decrypt something, you have that something and it's not enough to attain the plain text, given the encryption is secure. You need some other information. Note that I don't say what that other information is but we know for certain that additional information is needed because if it wasn't anyone who obtained the ciphertext could compute the plain text which would mean that the encryption is not secure.

We now need to determine a possible piece of additional information α. That information has to come from somewhere. It doesn't just emerge for no reason because some outside event happened.

You dictated in your edit that that α has to be found on the death certificate. To have any chance of encrypting something using any such information, we need to require at least that these conditions are met:

As the encrypter, need to know some mathematical property of α. Note that we don't necessarily need to know α itself.
α needs to be of a nature such that there are plenty of possible variations for different α with the same structure. Otherwise an attacker could brute-force α.
The attacker must not know α or be able to reduce the solution space to a small number of known elements.

If it's not possible for the encrypter to collaborate with the authority issuing the death certificate, there is no α we can find because we can only use the information found on any normal death certificate: Name of the issuer, name of the person who died and other personal information like date of birth or address, date of death, location of death, file number, and signature of the issuer.

The name of the person and their other personal information is not a secret. As the encrypter, we don't have control over the signature of the issuer nor ever the file number as we cannot collaborate with the authority. The attacker will already know what authority issues the death certificate, so the issuer is known. So we're left with date and location.

As the date is only stated with the precision of days and we can be sure to know the date of death as an attacker, except for an uncertainty of approximately 100 years which is 36524 days and therefore 36524 possibilities (if we're generous). As the location of death is only stated to the precision of the municipality where the person died, there aren't many options for this either. Even for large countries like the US, there only are 19492 options. So we have a total solution space of 36524*19492 = 711925808 < 10^9 elements.

This is far too small to exclude brute-force attacks and this assumes we have total control over where in the country the person dies and how old they become which is both impractical.

So there are no possible α we can choose one from and therefore there cannot be any such encryption.


Ways to protect flash player against MITM diffie hellman We have a server, which sends content encrypted with AES128 or RC4 to a flash client over an insecure HTTP channel. The encryption key is negotiated using Diffie Hellman.

The problem:

Diffie Hellman can be MITM-ed.
flash client can be easily reversed (can be obfuscated though), so if I use a hardcoded key, it can be easily retrieved

Is there any way to strengthen the weakest links, in this case, the key exchange and the flash client?

The usual solution for the Man-in-the-Middle problem of Diffie-Hellman is to combine it with a public-key authentication solution.

This could either work by including the server's public Diffie-Hellman key (which then must be a long-term key, not a short-term or even session key – this way you lose your forward-security) in the client, or including a signature key (DSA, RSA, ECDSA) with the client, where the server uses the corresponding private key to sign everything what was exchanged. (All those ways of authentication are used in SSL/TLS ciphersuites, by the way.)

Of course, this then poses the problem how the client (i.e. your flash application) comes securely to the browser in the existance of a MitM – so you'll have to also use some authentication solution on the transfer of this, using another public key, maybe certified by some key the users already know (and trust).

By then, you can just use SSL/TLS for the whole communication, both for delivering your flash client as well as to receive the secret data from the server.


How to convert RSA public keys to one key to use for text hashing? I've recently asked a question about RSA encryption. One of the things that I don't understand is the usage of two public keys.

In the example on Wikipedia, a message is encrypted like:

c(m) = m ^ e % n

This means that I need e and n to do an encryption. Also, in the article m is defined as plaintext but represented as an integer.

My two questions are:

How do I combine e and n to be one public key?
How should plaintext be formatted to be used in the Wikipedia example?

PS: RSA public key generation is based on this Wikipedia article.

PPS: Here is an example of an online RSA generation tool, I don't understand how those hashes are created based on the Wikipedia example.

An RSA public key is made of 2 parts, the modulus n and the exponent e.  They are both required, and neither alone can be considered "the key".  Often e will be one of just a few different values, but this is mostly convention and shouldn't be assumed.

RSA does work on integers; if your data is of another form, you have to specify how to convert it.  For instance, if you have text you might encode it to a byte array with UTF-8, then take blocks of bytes such that the number if bits is less than the length of n, and then treat that byte array as one big integer (either little-endian or big-endian).

But you probably don't want to be doing this math yourself, and there are a lot of pitfalls (padding, etc) to trap the unwary.  You should be using a library that someone has already implemented.


Function with no fast path and with fast proof When a function is iterated and each time a previous result is used as input to the next iteration (feedback), so that there is a limited benefit from parallel computing, is there such function that:

requires polynomial time to get the result of N iterations
has an Nth result that can be verified in constant time to be the Nth result for a given start value

Assuming that Alice iterates the function:

Problem with Makwa: At first Bob must use and throw away p and q.

Problem with LCS35: At first Bob must construct the puzzle.

But I need a function so that Alice can choose an arbitrary number or data to begin iterating with, not something prepared by Bob. Only when Alice has done N iterations Bob will join and verify.

The following paragraph applies even if the honest prover does not use iteration.

Strictly speaking, only a constant-size part of the input can be read from in

constant time, so one could always find a suitable result in constant time.

For a deterministic verifier that makes at most k probes to an alleged result

consisting of M w-bit words, one can find a suitable result with  2$\hspace{.02 in}$w$\hspace{.02 in}\cdot$k  parallel

simulations of the verifier, each of which uses only  $(\hspace{.02 in}2\hspace{-0.05 in}\cdot \hspace{-0.04 in}k)\hspace{-0.04 in}+\hspace{.02 in}$O(1)  words of overhead.

If instead the verifier is probabilistic, then either  $\binom{M}{\hspace{.02 in}k\cdot \hspace{.02 in}(1+\hspace{.03 in}\Omega(1))\hspace{-0.03 in}}$$\cdot$2$\hspace{.02 in}$w$\hspace{.02 in}\cdot$k$\cdot$(1+$\hspace{.03 in}$Ω(1))  parallel

simulations will be enough, or the adversary can very-efficiently go from an actual result

to one that makes the verifier's acceptance probability be between Ω(1) and 1-$\hspace{.02 in}$Ω(1).

However, it may well be possible to achieve what you're asking about with a probabilistic

word RAM verifier, by simply accepting that "the adversary ... be between ... ."

PCPs of proximity with highly-efficient verifiers do something that is somewhat similar.


Hash algorithm with the least chance for collision Out of these algorithms…

MD5
SHA1
SHA224
SHA256
SHA384
SHA512

… which has the least chance of collision, and which is the most secure at the time of writing this?

As Richie Frame noted in the comments, you basically listed them in order of ascending collision resistance.

The latter hashes have greater collision resistance due to their increased output size. With the exception of SHA-1 and MD5, this is denoted by the number in the name of the algorithm. For example, SHA-512 produces 512 bits of output.

The size of the output influences the collision resistance due to the birthday paradox.

To quote Wikipedia:

  The "birthday paradox" places an upper bound on collision resistance: if a hash function produces N bits of output, an attacker who computes only $2^{N/2}$ (or $ \sqrt{2^N}$) hash operations on random input is likely to find two matching outputs.

So SHA-512 should have the greatest theoretical collision resistance.

Note that MD5 and SHA1 should probably not be selected as a candidate when developing anything new and should only be used for compatibility purposes when required.

The SHA-2 algorithms calculate their digests in an almost identical manner, so generally we assume they are equally secure, digest sizes aside.


Security of RSA cryptosystem variant A variant of RSA cryptosystem is given as following:
$$N=p*q$$
$$ed=1 \space \space mod \space \space (p^r-1)(q^r-1)$$
$$c= m^e \space \space mod \space \space N $$
$$m= c^d \space \space mod \space \space N $$
where $r$ is an a small integer and $p , q$ are primes , $e$ is public exponent , $d$ is private exponent
Trivial Q. Does replacing $\phi(N)$ with  $(p^r-1)(q^r-1)$ produces a vulnerability?

In the case you choose $e$ first, you get a private exponent $d$ equivalent to the usual one. Since it is private, no vulnerability can arise. In other words, it is not possible even to distinguish whether you use standard RSA or this variant.
In the case you choose $d$ first, then $e$ may leak a lot of information. For example, in the Boneh-Durfee attack on small $d$, the bound $N^{0.292}$ is actually derived from $e$. If $e$ is larger, it is probably possible attack to attack larger $d$ than in standard RSA.
A simple attack for $d < n^{r/4}$. Consider as usual the exponents equation:
$$
ed = 1 + k(N^r-p^r-q^r+1).
$$
Consider it modulo $N^r+1$:
$$
ed + k(p^r+q^r) \equiv 1 \pmod{N^r+1}.
$$
we can see linear unknowns $d < N^{r/4}$ and $k(p^r+q^r) < N^{3r/4}$ (because $k < d$). By reducing the equation using LLL, we can get an equation with smaller coefficients, which will hold in integers:
$$
b d + ak(p^r + q^r) = a,
$$
where $a,b$ are known. Reducing the equation modulo $a$ we'll recover $d$.
Note that we get the same bound as in the Wiener's attack on standard RSA ($d < N^{1/4})$. Applying the Coppersmith-based Boneh and Durfee method will likely improve the result similarly.


The security of Zero knowledge proof performance I recently learned to study the security of zero knowledge proof. As you can see on the wiki (link), it seems to be the most popular example of the Ali Baba cave. I have a question about the security of ZKP (Zero knowledge proof) in the Ali Baba cave. The reasons are as follows: During the verification process, the prover will deliver the value of $e = [0,1, \ldots]$. And $e$ will have a solution to either left or right depending on $0$ or $1$. And according to the length of list $e \space (2 ^ n)$, this process is said to be more secure. However, there are only two paths, and depending on the value of $e$, the secret key value is not changed in directions $A$ and $B$. So, should not the safety of this algorithm be just $2$ ?

I don't know the term "safety". But when it's written 'the process is more secure'. It means that the probability for an adversary that doesn't know the secret (here how to go through the door) decreases "exponentially".

For example, to solve 4 challenges the adversary has to choose the side door $4$ times, so it has the probability $\frac{1}{2^4}$ to win the game.


is this implementation real salsa20? https://raw.githubusercontent.com/andres-erbsen/salsa20/master/salsa20.c

I tried it, and it's working fine. Now question: is it real salsa20?

The Salsa20 specification paper contains examples for testing for each function. quarterround 7 example, rowround 2 example, etc..
Indeed this paper is written as a tool for programmers, or the analyzers so that they can use these test vectors.

Salsa20 exists in the Crypto++ which is a C++ library originally written by Wei Dai. You can use this code to test, too.

Also, the snuffle page of the Bernstein contains code for various platforms.


Is there a field guide to ECC for the IT Security layman? I'm trying to understand ECC from an IT layman's perspective and am trying to separate the theory from the standards, and understand why certain features are implemented or not implemented in the common ECC stacks.

Question

Namely, I'd like to know when should a non-standard ECC library (or related hardware) should be used versus when a standard ECC library should be used.

Second, I'd also like to know what trade-offs were considered in the common implementations such as DHE in MSFT or Java versus what's implemented in other software

What I think I understand so far:

There are several mathematic properties that can be used in encryption
Many protocols have been created on those properties to facilitate key exchange.  The common standards are broken into the following categories

NIST - Only
The NIST / SECG overlap
SECG - Only
ECC Brainpool

Real world implementation of the above properties and standards are dictated by:

Patent concerns on the math and the key exchange (Certicom)
Security through obscurity (some haven't been released, and some "compatible" derivatives have been created)
Government approval (why did the government approve it? Backdoors, patents, the country that 'invented' it?)

What I haven't been able to figure out is:

Are some implementations faster, more secure, or more suited for (or against) hardware optimizations?
Are some standards preferred simply because a vendor (or government) paid for their patent fees and will not be legislated?

For a given implementation above, is there any risk of (or benefit depending on whose side you're on) of patented techniques like:

implementation of curves over binary fields using normal bases;
point compression;
acceleration of Koblitz curves using the Frobenius endomorphism;
various optimization tricks on dedicated hardware architectures (FPGA, GPU, ASIC).

By non-standard do you mean when to use custom curves? Like in crypto++ where you can specify your own parameters?

Given that the standards recommend certain sets of domain parameters (and interesting enough US government departments are forbidden from using their own parameters) it's sounds like the answer is no, for reasons of avoiding the risks of self implementation and the worthlessness of "security by obscurity". Tiresome, but this is how i answer all the "should I do my own" question, sorry.

I do know that NIST curves have certain computational advantages over any old curves because there are some just more convenient numbers for the Projective coordinates calculations. Also this wikipedia page seems to think the number of prime curves and binary curves affects security and implimentation efficiency (I have no idea why though, but there is a link in the "NIST-recommended elliptic curves" section )


Extracting only the entropy (I cleaned up the question a bit, It was previously titled "extracting entropy without hashing" .. thus some of the comments / answers)

I'd like to extract the entropy of data without injecting "pseudo" entropy. For example, let's say I have a series of bytes, but only the low bit is changing (or something is changing that I'm not aware of beforehand) - how can I just output that low bit?

Is there a known way to extract the random part of the data without doing custom programming for each different type of data series?

edit:  To clarify, I'm looking to extract only the random part.  Eg, assuming F is the magical function, I want:

Length (F(X)) = # of bits of min-entropy in X.

As has been pointed out elsewhere, this is probably impossible to do automagically with any reasonably assured level of confidence in its real accuracy.

The best answer is almost certainly to use a cryptographic hash.

Your reason for avoiding a cryptographic hash makes no sense to me.  Your problem does not explain the motivation for your question, but I suspect you've fallen prey to the XY problem (see also here).

You haven't told us what you're ultimately trying to accomplish, but I suspect the right answer in practice is ultimately going to be:

Use /dev/urandom to generate cryptographic-quality pseudorandom numbers.
If you have a source of entropy, feed it into /dev/urandom (e.g., cat somekindarandombits > /dev/urandom), then see step 1 above.

Internally, this effectively uses a hash.

I also recommend you read the following:

https://security.stackexchange.com/q/89/971
https://security.stackexchange.com/q/3936/971
https://security.stackexchange.com/q/14292/971


A block cipher with independent keys for each round I want to modify a standard block cipher in the following way. I replace each round key by a key picked at random. Is this block cipher as secure as the original one ?

Thank you.

EDIT

Some missing information related to the question, according to comment by OP to one of the answers:

  My question is related to the key-schedule of AES, I wonder if we can replace it by something more stringent and be sure that the security will not be not worst than the original one.

John Kelsey, Bruce Schneier and David Wagner proposed paper "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES" and they presented new attacks on key schedules of the block ciphers. About "A 768-bit DES variant uses independent round subkeys" they said:

  A 768-bit DES variant uses independent round subkeys [Ber83]. This
  variant will be much weaker in some situations: there is a very simple
  related-key attack needing just 15 related keys and 60 chosen
  plaintexts. Obtain the encryptions $E(k, p)$ and $E(k' , p)$, where k is
  obtained from k by flipping some bits in the last round subkey; this
  can be thought of as a differential $1R$ attack with a characteristic of
  probability 1. The last round subkey can be recovered with four chosen
  plaintexts, and then we can peel off the last round and repeat the
  attack on 15-round DES. This attack can also be optimized for the case
  when related key queries are very expensive to achieve a complexity of
  one related key and $2^{16}$ or so chosen plaintexts. For nearly any
  product block cipher, if it’s possible to flip bits in a cipher’s
  expanded key, it’s possible to mount an XOR differential attack on the
  last round of the cipher. This may be useful in attacking some systems
  that leave expanded keys vulnerable to change.

So if the algorithm is DES the answer is: NO.

Charles Bouillaguet, Patrick Derbez, Orr Dunkelman, Nathan Keller and Pierre-Alain Fouque proposed "Low Data Complexity Attacks on AES". They said:

We present several attacks on up to four rounds of AES requiring up to ten chosen plaintexts. Most of the attacks are based on the meet-in-the-middle approach. Some of the attacks exploit heavily the AES key schedule, while others apply even if the subkeys in AES are replaced by independent subkeys. The attacks are summarized in Table 1.

The attacks are applicable to up to 7-rounds of Rijndael. Since the minimal number of rounds in the Rijndael parameter settings proposed for AES is 10, these attacks does not endanger the security of the cipher.

By now there isn't any attacks against full-rounds of Rijndael key schedule or full-rounds of Rijndael with independent subkeys.

So if the algorithm is AES the answer is: By now YES
But the answer is depending on future researches. And in general the answer is depending on the algorithm.


power consumption in a XOR I'm trying to understand how a XOR affect traces of power consumption in a Differential Power Analysis on smartcards.

What's the difference in energy radiated in a $1 \oplus 1$ and in a $0 \oplus 1$?

If I understand correctly we have a XOR gate, and if a $1$ is xored with a $0$ then electrons in the 1 branch just continue flowing thus we still have some energy compared to a $0 \oplus 0$.

The exact details depend on the logic family but basically The difference is that the charge representing those "1" bits need to be discarded somehow. This is done by switching the output to ground, 1^0 is 1 so no charge need to go away but 1^1 is zero meaning at least two gates get discharged to ground slightly raising its voltage due to the non zero resistance in the ground return path.

Though, this really depends on the logic Family, the effect of charging the output gate lowering vcc may be dominant in some like you say. But in most any mos family, some assymetry will be noticed. ECL is notably immune due to steering currents that always flow not charging capacitors.


paradox on fully homomorphic equality checking Imagine, a client encrypts a corpus of data (say documents of text) with the public key of a Fully Homomorphic Encryption scheme (FHE) and outsources the data to an untrusted server.Now the client wants search for a particular word in the corpus of encrypted documents and retrieve the matching documents that contain the word as a result. So the client could encrypt the search word with public key of FHE scheme and send to the server. The server would evaluate a "equality circuit" for blind folded matching using Evaluate method of FHE scheme. Remember the result (in this case it is MATCH or NO MATCH) also is encrypted in FHE schemes and hidden from the untrusted server.

Now my paradox begins,
Does this mean server does not know whether the string matches the document ?

If the server does not know how will it retrieve and send those matching documents alone ?
If the server knows whether the string matches or not in this particular case  will such FHE scheme considered secure at all ?
Is this situation any better if the FHE scheme is probabilistic or deterministic ?

On a side note, the above need not be for a word (as in words of a text) equality checking, the same argument could be given for numerical equality checking (arithmetic circuits) as well. Any comments on this paradox ?

This is somewhat a paradox. It seems that if the server cannot know when equality is reached, how can it return only those documents. Surprisingly, it can be done, under the assumption that an upper bound is given on the number of documents (and at the cost of that upper bound).

Assume first that only one document matches, and this is known. Denote by ${\cal X}=X_1,\ldots,X_n$ the documents, and assume that there exist lists ${\cal L}=L_1,\ldots,L_n$ such that $L_i$ is the list of keywords in $X_i$. (This is just to simplify the explanation.) Then, let $f(a,L_i)=1$ if $a$ is in the list $L_i$, and otherwise $f(a,L_i)=0$. Clearly, $f$ can be computed inside FHE. Then, the server can compute the function $g(a,{\cal X},{\cal L})=\sum_{i=1}^n f(a,L_i) \cdot X_i$ inside FHE and return the result to the client. Since we are guaranteed that only one document matches, we have that $f(a,L_i)$ will equal 0 in all but one place. Thus, if $a\in L_j$, then the result will be $X_j$ only.

In order to extend this to the general case where an upper bound $t$ is given on the number of matches, the following can be done. Define $f_m(a,i,{\cal L})$ to be a function so that $f_m(a,i,{\cal L})=1$ if $L_i$ is the $m$th list $(1\leq m\leq t)$ in ${\cal L}$ containing $a$, and otherwise equals 0. Then, define $g_m(a,{\cal X},{\cal L})=\sum_{i=1}^n f_m(a,L_i) \cdot X_i$. Finally, the server computes and returns to the client the (encrypted) values $g_1(a,{\cal X},{\cal L})$, $g_2(a,{\cal X},{\cal L})$, up to $g_t(a,{\cal X},{\cal L})$.

In this way, the communication is just $t$ ciphertexts, and thus not everything needs to be returned.

Note that if you don't have any upper bound on the number of responses, then you can't do this, and you end up sending everything. In order to solve this, the client can first send an encryption of $a$ to the server, who then computes a function that just returns the number of lists that $a$ appears in. The client can then decrypt and send this to the server who continues as above. This does require interaction, but solves the problem of knowing a reasonable upper bound on the size of the output.


Why routers don't just use Diffie-Hellman protocol? Routers could just use Diffie-Hellman protocol with any computer who tries to connect to that router. Then it would be impossible to eavesdrop for anyone. Only router and computer would know the secret key for that session. No?

Or someone could act as a router and send his own public key and get the traffic through his computer and that is the reason routers don't use it?

Even if you were doing that you would only ensure that the communication between you and "some" router is secure. It's still possible to MITM using arpspoof for instance such that in:

[you] <--- A ---> [hacker] <--- B ---> [router]

Communications A & B are encrypted, yet you're not talking to the real router.


Wrong Test Vector for HKDF with HMAC-SHA256 I have implemented HKDF by myself and it seems to work good. I managed to replicate all the test vectors listed here but... except this one:

   Test with SHA-256 and longer inputs/outputs

   Hash = SHA-256
   IKM  = 0x000102030405060708090a0b0c0d0e0f
          101112131415161718191a1b1c1d1e1f
          202122232425262728292a2b2c2d2e2f
          303132333435363738393a3b3c3d3e3f
          404142434445464748494a4b4c4d4e4f (80 octets)
   salt = 0x606162636465666768696a6b6c6d6e6f
          707172737475767778797a7b7c7d7e7f
          808182838485868788898a8b8c8d8e8f
          909192939495969798999a9b9c9d9e9f
          a0a1a2a3a4a5a6a7a8a9aaabacadaeaf (80 octets)
   info = 0xb0b1b2b3b4b5b6b7b8b9babbbcbdbebf
          c0c1c2c3c4c5c6c7c8c9cacbcccdcecf
          d0d1d2d3d4d5d6d7d8d9dadbdcdddedf
          e0e1e2e3e4e5e6e7e8e9eaebecedeeef
          f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff (80 octets)
   L    = 82

   PRK  = 0x06a6b88c5853361a06104c9ceb35b45c
          ef760014904671014a193f40c15fc244 (32 octets)
   OKM  = 0xb11e398dc80327a1c8e7f78c596a4934
          4f012eda2d4efad8a050cc4c19afa97c
          59045a99cac7827271cb41c65e590e09
          da3275600c2f09b8367793a9aca3db71
          cc30c58179ec3e87c14c01d5c1f3434f
          1d87 (82 octets)

After one hour of debug, I figured out (and I believe) that my implementation is right and that this test vector is wrong.
I don't manage to get the right OKM value and even the PRK is wrong. To discover this I did the following:

Given that PRK = HMAC-Hash(salt, IKM) (as described in the RFC), I tried to compute the HMAC and I saw that the result value was different.

Can anyone confirm that this test vector is "bugged"?

This hastily written implementation of HKDF in C# agrees with the RFC test vectors:

    private const int SHA1 = 1;
    private const int SHA256 = 2;

    private static HMAC NewHMAC(int h, byte[] key)
    {
            switch (h) {
            case SHA1:
                    return new HMACSHA1(key);
            case SHA256:
                    return new HMACSHA256(key);
            default:
                    throw new Exception("NYI");
            }
    }

    private static byte[] HKDFExtract(int h,
            byte[] salt, byte[] ikm)
    {
            using (HMAC hm = NewHMAC(h, salt)) {
                    return hm.ComputeHash(ikm);
            }
    }

    private static byte[] HKDFExpand(int h,
            byte[] prk, byte[] info, int len)
    {
            using (HMAC hm = NewHMAC(h, prk)) {
                    MemoryStream ms = new MemoryStream();
                    byte[] T = new byte[0];
                    int j = 0;
                    while (len > 0) {
                            byte[] buf = new byte[T.Length + info.Length + 1];
                            Array.Copy(T, 0, buf, 0, T.Length);
                            Array.Copy(info, 0, buf, T.Length, info.Length);
                            buf[buf.Length - 1] = (byte)(++ j);
                            T = hm.ComputeHash(buf);
                            int clen = Math.Min(T.Length, len);
                            ms.Write(T, 0, clen);
                            len -= clen;
                    }
                    return ms.ToArray();
            }
    }

Feel free to reuse and modify it at will, in order to print intermediate values, to pinpoint the location at which your implementation diverges. Like @Andrey, I find it plausible that your code gets it wrong when applying HMAC with a key larger than the underlying hash function block size (which is 64 bytes for both SHA-1 and SHA-256): in such a case, the key should first be hashed alone, and the hash result (20 or 32 bytes, for SHA-1 and SHA-256, respectively) is then used as the actual HMAC key.

Thus, you may want to compare your HMAC implementation with the test vectors from RFC 4231, especially the last two, which exercise the "key larger than block" situation.


A Question about Notations and Groups Please consider the following question:
Determine the order of all the elements of the following multiplicative groups. You can write a C or Java program to do this.
a. $Z_{21}^*$
b. $Z_{23}^*$

Now note that $21$ is not a prime number and since the question refers to a
multiplicative group, I would expect that means the operator for the group is
multiplication mod 21. This means that the number $7$ should have an inverse. That is, there should be a number x, such that $(7x)\,mod\,\,21\,\,=\,1$. I claim that no such $x$ exists. What am I missing?

Bob

$\mathbb Z_n^*$ is the subset of $\mathbb Z_n$ with elements relatively prime to $n$ (or equivalently: with an inverse under multiplication modulo $n$). That's a group under multiplication modulo $n$. It has $\varphi(n)$ elements, where $\varphi$ is the Euler totient.

It follows that $7\not\in\mathbb Z_{21}^*$; that's what's missed in the question.


Cracking diffie-hellman I want am making an application, demonstrating an attack on a weakly performed diffie-hellman. I need to implement an algorithm that can use the shared variables in order to compute the key. Searching for resources, I keep running into the logjam attack. However I can't really filter out the number crunching from all the HTTP protocol information.

If anyone could provide som resources to point me in the right direction, or a formula to how to successfully compute the key from the known variables. It would be greatly appreciated!

Edit

I have found this resource, which seems really promising.
http://index-of.es/Miscellanous/How%20To%20Backdoor%20Diffie-Hellman.pdf

page 6 it says

  To attack a Diffie-Hellman key exchange, one could extract the secret key a from one of the peer's public key
  ya = g
  a
  (mod p). One could then compute the shared key g
  ab (mod p) using the other peer's public key
  yb = g
  b
  (mod p).

  The naive way to go about this is to compute each power of g (while tracking the exponent) until the public
  key is found. This is called trial multiplication and would need on average q
  2
  operations to find a solution (with
  q the order of the base). More efficiently, algorithms that compute discrete logarithm in expected √q steps

I translate this to

  compute each power of g
  g^1 mod(p), g^2 mod(p), g^3 mod(p)..g^n mod(p)

This would work, however it requires to isolate the exponent from the formula to work. Which is pretty difficult to me.

How would you isolate a from p^a mod(p)

An interesting cryptanalytic attack on Diffie-Hellman is the small subgroup confinement attack. The attack works if the DH parameters are chosen without caution. Here is a brief explanation on how it works.

DH works in multiplicative groups. Say we are working in $Z^*_p$. As $p$ is prime, the order of this group ($p-1$) is composite, therefore by Lagrange's Theorem there exists subgroups. The attacker basically reduces the key space to one of these subgroups having much smaller orders by interfering the communication and modifying it.

Let our DH group to be $(Z_p^*,*)$ and $\alpha$ to be the primitive root used. Normally Alice computes a random $s_a$ and keeps it secret. Alice sends $\alpha^{s_a}$ to Bob, but the attacker Eve receives it first. Eve looks up for possible subgroups by searching through factors of $(p-1)$ and finds a small factor $q$. By Lagrange's Theorem she knows there exists a subgroup of order $q$. She computes $t=\frac{p-1}{q}$ and sends Bob $(\alpha^{s_a})^t$. Bob also computes his secret random value $s_b$ and computes the shared secret $(\alpha^{ts_a})^{s_b}$. Bob then sends Alice $\alpha^{s_b}$ but Eve intercepts. Eve sends Alice $(\alpha^{s_b})^t$ and Alice also computes the shared secret as $(\alpha^{ts_b})^{s_a}$. Both have the shared secret, yes, but their shared secret is of form $(\alpha^t)^x$. Numbers of this form are generated by the subgroup with generator $\alpha^t$ which is known to be of order $q$. As $q$ is small (by our hypothesis of DH parameters have been selected poorly), Eve can simply compute the DH discrete logarithm problem by bruteforce as there are much less trials.

How to protect?

Pick $p$ such that $p=2q+1$ where $q$ also is a prime (see Sophie-Germain primes). Having this property, the group order will be $p-1=2q$. As $q$ is prime, only factors of $p-1$ are 2 and $q$. So when setting up shared secrets with DH, check if your group order is 2. If this is the case you know that you've been attacked.


Why does ε-differential privacy protect the subset of 1/ε edges in terms of graphs? In the book The Algorithmic Foundations of Differential Privacy by Cynthia Dwork, Aaron Roth on page 24, databases that take the form of graphs are discussed.

We could on the other hand consider differential privacy at a level
of granularity corresponding to edges, and ask our algorithms to be
insensitive only to the addition or removal of single, or small numbers
of, edges from the graph. This is of course a weaker guarantee, but
might still be sufficient for some purposes. Informally speaking, if we
promise $\epsilon$-differential privacy at the level of a single edge, then no data
analyst should be able to conclude anything about the existence of any
subset of $1/\epsilon$ edges in the graph. In some circumstances, large groups
of social contacts might not be considered sensitive information: for
example, an individual might not feel the need to hide the fact that
the majority of his contacts are with individuals in his city or workplace,
because where he lives and where he works are public information. On
the other hand, there might be a small number of social contacts whose
existence is highly sensitive (for example a prospective new employer,
or an intimate friend). In this case, edge privacy should be sufficient
to protect sensitive information, while still allowing a fuller analysis of
the data than vertex privacy. Edge privacy will protect such an individual’s sensitive information provided that he has fewer than $1/\epsilon$ such
friends.

How do they derive the number $\large\frac{1}{\epsilon}$ in this discussion? Does the amount of $\epsilon$ still stand for privacy loss? Thanks for your help in advance!

I think this is a reference to group privacy. See Theorem 2.2 in the Dwork-Roth book.

If you have $(\varepsilon,0)$-differential privacy for changing 1 edge, then you have $(1,0)$-differential privacy for changing $1/\varepsilon$ edges.


AES-CBC ciphertext manipulation with known IV and plaintext! I'm currently practicing on a purposely flawed login page, where I have to change the value of a cookie to enter. The cookie is an encrypted and encoded form of a simple JSON string with fields "admin", "username", "password". The admin field is set to 0, and the user/pass fields accepts anything. To login, I have to change this ciphertext such that the admin field is set to 1 when decrypted.

The encryption function works like this:

A raw string is padded, then encrypted with AES-CBC and a random IV.
Then, this cipher text appends the IV (concatenation; IV+cipher).
Then, this is Base64 encoded, and returned.

So, to decrypt, we simply decode it with Base64, and split the result so that the 16 first characters are the IV, and the remaining is the ciphertext.

Now, I want to know the ciphertext when one character of the plaintext is changed.

Specifically, in my example:

The following string is encrypted, appended to the IV, and encoded:

{"admin": 0, "username": "admin", "password": "admin"}

This apparently results in the encoded text (found in cookie):

yMqlNejXMclgcU5+wbL40RY/mvIMW+AvguoMvCv0NemhRYzWzs7EQ2DXpvwsGmFynGpNWNyotYBea+P3Z3XZIvMBoMzdMVb/FtWQ+GV/MmA=

I'd like to know what this encoded text / cookie looks like if the plaintext is changed to {"admin": 1, "username": "admin", "password": "admin"} (note, the 0 changed to 1). The username and password can be anything, only the "admin": 1 part is important.

It appears the key is fixed, but the IV is generated at random every time I try to logout and login again.

Is this possible? If so, how?

Thanks!

This question is educationally illustrative and deserves a good answer.

Because in CBC, $C_i = E_k(C_{i-1} \oplus P_i)$, and $C_0 = IV$, you can alter any bit in the first block by changing $IV$ without affecting later blocks and won't get caught because there isn't a MAC tag.

Take a look at this graph:

0123456789abcdef // numbering
{"admin": 0, "us // json token
ivivivivivIviviv // init vec
~~~~~~~~~~^~~~~~ // change

This shows once again why message authentication is important, and symmetric-key encryption should follow AEAD paradigm.


Noisy secret sharing I am looking for a secret sharing scheme that is robust against noise, the shares are going to be noisy. We do not want to reconstruct the secret perfectly and a noisy reconstruction with a bound on noise is good enough.
Assume we are using $(n,k)$ Shamir's scheme to distribute a secret among $n$ parties so that we need at least $k$ of them to recover. If we add noise to the shares, using $k$ points, the reconstructed polynomial would be very noisy. However, having access to an infinite amount of points would result in a perfect reconstruction. Are there any works that quantify this reconstruction noise?
If you know of any other idea or another sharing scheme, that would also be great!

Do you have a noise model in mind?
If the noise affects only a small portion of shares, regular shamir secret sharing is robust. You only need k complete shares.
For other scenarios, like having a few bit flips across all shares. You add any error correction code after creating the shares before distributing them. E.g Reed Solomon. so That each party still gets a single share but with extra error correction information.