derangements and permutations in cryptography Given a partial key for a mono-alphabetic substitution cipher (missing
  11 letters), calculate the number $N$ of possible keys, given that no
  plaintext letter can be mapped to itself.

Ordinarily, the number of possible keys would be the number of derangements of the missing letters $!11$. However, 5 of the plaintext letters that are missing mappings already exist as mappings in the partial key, so logically it shouldn't matter what the mapping of those plaintext letters is, because they can never map to themselves.

So, I wonder if the number of possible keys is $N = 5! * !6$. That is:

(no. permutations of 5 already mapped free letters) * (no. derangements of the remaining 6)

The problem is that 5! * !6 = 31800 which is much less than !11 = 14684570
Intuitively, the set of derangements should be the smaller subset, so surely $N>!11$.

Am I getting something wrong in my arithmetic or am I completely missing the concepts?

This is purely a counting problem. We want the number $N(n,m)$ of possible permutations of $n$ things, with the constraint that only $m$ among these things can map to themselves ($0\le m\le n$). The values in the question are $n=11$, $m=5$.

It holds that $N(n,n)=n!$ (that's the number of permutations of $n$ elements).

It holds that $N(n,0)=\text{}!n=\begin{cases}
1                            &\text{if }n=0\\
\lfloor{{n!+1}\over e}\rfloor&\text{if }n>0\\
\end{cases}$
(that's the number of derangements of $n$ elements).

The computation made of $N(11,5)$ as $5!\cdot\text{}!(11-5)=31,800$ in the question is wrong, as noted: this is less than $!11=14,684,570$, when it should be above (but still less than $11!=39,916,800$). Two mistakes have been made:

the $m=5$ things that can be assigned without constraint among $n=11$ can be so in $n!\over(n-m)!$ ways, not $m!$ ways; fixing that, we would get ${11!\over(11-5)!}\cdot\text{}!(11-5)=14,691,600$, which is more credible;
but after first assigning $m=5$ unconstrained things, the assignments for the $n-m=6$ other things depend on how we arranged the unconstrained things (if we assigned one of the unconstrained things to an initially constrained thing, the later becomes unconstrained); therefore, the above $14,691,600$ is significantly too low.

Taking a deep breath, we can see that $N(n,m)$ can be obtained as
$$\begin{cases}
1                                    &\text{if }n=0, m=0\\
0                                    &\text{if }n=1, m=0\\
n\cdot N(n-1,n-1)                    &\text{if }n>0, m=n\\
(n-1)\cdot N(n-1,1)                  &\text{if }n>1, m=0\\
m\cdot N(n-1,m-1)+(n-m)\cdot N(n-1,m)&\text{if }0<m<n\\
\end{cases}$$
Justifications:

when $n=0, m=0$: there's a single method to map nothing; consistency with $0!=\text{}!0=1$.
when $n=1, m=0$: there's no permutation of one thing that does not map that thing to itself; consistency with $\text{}!1=0$.
when $n>0, m=n$: we assign an unconstrained thing to an unconstrained thing (thus in $n$ possible ways), leaving $n-1$ unconstrained things; that's the classic factorial recursion.
when $n>1, m=0$: we assign a constrained thing to a constrained thing other than itself (thus in $n-1$ possible ways), leaving $n-1$ things among which $1$ became unconstrained.
when $0<m<n$: we assign an unconstrained thing, either

to an unconstrained thing (thus in $m$ possible ways), leaving $n-1$ things among which $m-1$ unconstrained;
to a constrained thing (thus in $n-m$ possible ways), leaving $n-1$ things among which $m$ unconstrained including the one that became unconstrained.

I get $N(13,6)=3,597,143,040$, and $N(11,5)\equiv67\pmod{97}$.

If we don't mind that $m=n+1$ creeps in, $N(n,m)$ can also be obtained as
$$\begin{cases}
(n-1)\cdot N(n-1,1)                  &\text{if }n>0, m=0\\
m\cdot N(n-1,m-1)+(n-m)\cdot N(n-1,m)&\text{if }0<m\le n\\
1                                    &\text{otherwise}\\
\end{cases}$$
or as
$$\begin{cases}
n\cdot N(n-1,n-1)                      &\text{if }n>0, m=n\\
m\cdot N(n-1,m)+(n-m-1)\cdot N(n-1,m+1)&\text{if }0\le m<n\\
1                                      &\text{otherwise}\\
\end{cases}$$
Justification of the new relation when $0\le m<n$: we assign a constrained thing, either

to an unconstrained thing (thus in $m$ possible ways), leaving $n-1$ things among which $m$ unconstrained;
to a constrained thing other than itself (thus in $n-m-1$ possible ways), leaving $n-1$ things among which $m+1$ unconstrained including the one that became unconstrained.

Based on intuition confirmed by numerical evidence that $m\mapsto N(n,m)$ is close to exponential between $m=0$ and $m=n$, I assert that
$$N(n,m)\approx n!\cdot e^{m/n-1}$$
This approximation is by excess when $m>0$. The error made is less than $4.0\%$ for $n\ge4$; less than $1.8\%$ for $n\ge8$; less than $1.0\%$ for $n\ge14$.

More rigourously stated:
$$\forall r\in\mathbb R, 0\le r\le1\implies\lim_{n\rightarrow\infty}{n!\cdot e^{r-1}\over N(n,\lfloor r\cdot n\rfloor)}=1$$


Is there any alternative for extended euclidean algorithm to perform modulo division? I'm implementing point addition and point doubling operations for elliptic curve cryptography. I have implemented extended euclidean algorithm to perform modulo division.

It appears the that extended euclidean algorithm takes almost 90% of the computation time for the whole operation. It is slowing down the entire operation.

Can anybody suggest me an alternative approach?.. Or if someone have already implemented it, tell me how did you manage to reduce the time taken??

For increasing speed, you should use of  "Barrett reduction" and "Montgomery multiplication". For more detail you can see "Guide to Elliptic Curve Cryptography". Also you can use "MAGMA". This program is  one of the best and fastest program for elliptic curve.


Is frequency analysis a useful tool against encryption by multiplication? If I transform natural plaintext by:

making each letter two decimal digits, considering the whole as a decimal number;
multiplying by the key (some integer constant), giving the ciphertext;

would frequency analysis still work?

Exemple:

Plaintext:     G o l d U n d e r S e a
Number:       071512042114040518190501 x 911
Ciphertext: 65147470365890912071546411

To get the text again simply divide by 911. Conversion of the ciphertext to letters could be added somehow.

Assuming frequency analysis is not an option, how would one break this?

Note: The question has been improved by the OP, then re-tagged and further edited for clarity. I now wish I could rescind my own vote to close it.

Frequency analysis would work on average quite poorly on ciphertext of the proposed cipher. How exactly depends a lot on the value of the key: for some weak keys likes 1, 3, 30, 30000.. it works essentially as well as for any mono-alphabetic cipher. For 103, it still works well. For any key, given enough (lots of) ciphertext, it could still distinguish the ciphertext from random.

Frequency analysis is NOT the right tool to attack the proposed cipher. It is much easier to find the key $k=911$ by trying small factors $k$ of $c=65147470365890912071546411$ (in ascending order) and keeping the one (or those very few) such that $c/k$ has all digits in its base-100 form in range $[1\dots26]$. That attack would not work well for a huge key purposely constructed as the product of many small factors. However, I guess refinements are possible.

An even more devastating problem occurs when a key is reused for different ciphertexts: we can compute the GCD of the ciphertexts, that will be a multiple of the key, and the key itself with few ciphertexts (sometime 2 or 3, growing only slightly with size of the parameters).

Therefore, the cipher is weak and has no practical interest.


Estimated entropy per bit given P-value of a statistical test, and number of bits tested? Assume that a certain statistical RNG test (say from the NIST Statistical Test Suite, Dieharder, etc..) gives us a certain P-value (per the definition [*] used in NIST Special Publication 800-22), after testing $n$ bits of a RNG; say, $P=0.001$ (indicative of failure of the test with high confidence) and $n=2^{20}$.

Based on that information alone, what can we say about the (maximum) entropy per bit $H$ of the RNG tested, with some prescribed confidence? By this I mean, more precisely: the hypothesis that the tested generator has at least entropy rate $H$ can be rejected with fair confidence; perhaps, as associated with some P-value (possibly higher than the $P$ obtained in the test, say twice that).

How can we refine this, given P-values $P_i$ for that experiment repeated $k$ times?

Update: if that's not answerable as it, does it remain so when we add some very general hypothesis on the structure of the RNG under test, like: it outputs independent bits with some unknown constant bias? Refine this additional hypothesis as needed to obtain some relation between $P$, $n$ and $H$ !

Update: I do realize that if any statistical test RNG pass, that gives no insurance at all about the entropy per bit of the RNG tested; and that if it fails with values as in my numerical example, any hint that it may give in term of entropy per bit will be that it is at most $H$, with that $H$ dangerously close to 1, thus not very telling (even with the now-reduced P-value).

[*] My understanding is that the correct definition of the P-value used for statistical RNG test is that the statistical test promises that for any $\alpha$ with $0\le\alpha\le 1$, it outputs a P-value at most $\alpha$ with odds at most $\alpha$ when applied to a perfect TRNG.

Further, I believe only the second sentence is right in this quote of NIST SP 800-22 page 1-4

  For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%. For a P-value < 0.001, a sequence would be considered to be nonrandom with a confidence of 99.9%.

Correct me if necessary!

Firstly, the way (if at all) the "$P$-value" depends on $H$ depends (of course) on the statistical test that is being used. For each test, the result will be different and I cannot really give a meaningful general discussion here because different tests consider completely different aspects of the stochastic process of output bits.

In general, indeed, the $P$-value doesn't have to depend on $H$.
Originally I (probably incorrectly) thought you were referring only to a particular test (the monobit frequency test), which is what my comment was referring to.
I'll use this particular test in my answer to illustrate that the $P$-value can depend on $H$ and hopefully you'll be able to generalize my approach to other tests that are of interest to you. The analysis will be the same for many tests, but it will often be impossible to get any closed-form expressions relating the $P$-value and $H$.

Before I start with the analysis of the monobit frequency test, I'll also answer your question about the truth of the sentence

  For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%.

A $P$ value larger than 0.001 means that we cannot reject the hypothesis that the sequence is random at a significance level of 0.001. In this sense the sentence is imprecise: it is not because our test would have produced our observation with high probability that the observation was produced by a TRNG. At all times one should remember that the formula for computing the $P$-value is derived under the assumption that the hypothesis is true.

Analysis of the monobit frequency test

I'll now discuss the monobit frequency test, which is defined in NIST SP 800-22 (section 2.1). My notation is a little different sometimes, but I think it should be clear enough (if not, please comment).

In the most general sense, even this analysis would be difficult: at most one can say that the probability distribution of the $P$-value depends on the entropy $H$, but you should probably forget about getting a simple relation (formula of some kind) in the general case.

The following part of your question (applied to the monobit frequency test) has a reasonably "nice" answer though:

  If that's not answerable as it, does it remain so when we add
  some very general hypothesis on the structure of the RNG under test,
  like: it outputs independent bits with some unknown constant bias?
  Refine this additional hypothesis as needed to obtain some relation
  between $P$, $n$ and $H$!

So we've already made the assumption of working with a particular statistical test, because we can't answer the question otherwise. Now I'll make the following assumptions about the RNG:

There is no dependence whatsoever between the output bits of the random number generator.
The RNG is outputs a $1$ with a fixed probability $q$ and a zero with probability $1-q$. To get a a nice formula, I'll assume $q = 1/2 + \epsilon$ with $\epsilon$ sufficiently small such that $\epsilon^4 \approx 0$. I'll refer to $\epsilon$ as the bias.
$n$ is sufficiently large, but this assumption is implicit in the test anyway.

What I will show is that, under these assumptions, the probability distribution of $P_n$ (this is just $P$ for a specific value of $n$) depends on the entropy $H$. Note that I'm going to use $P_n$ as a random variable and $p_n$ for an instantiation of this test statistic. Once the distribution of $P_n$ is known, we can answer the following question:

  What is the probability that the source entropy is $H$ given that the observed value of the $P$-statistic is $p_n$?

To obtain an answer to this question, we need to take the following steps

Write the bias $\epsilon$ in terms of the entropy $H$.
Compute the probability distribution of the test statistic for the biased RNG.
Compute the probability distribution of the $P$-value for the biased RNG.

Entropy and bias

The entropy $H$ of one bit of the RNG is given by

$$
H
= q \log_2\left(\frac{1}{q}\right) + (1-q)\log_2\left(\frac{1}{1 - q}\right)
= 1 - \frac{2\epsilon^2}{\log 2} + \mathcal{O}(\epsilon^4),
$$
where $\log$ is the natural logarithm.
Hence, we have approximately:

$$\epsilon \approx \pm\sqrt{\frac{\log 2}{2}(1 - H)}.$$

It shouldn't be surprising that there are two biases corresponding to the same entropy. For convenience, I'll use the positive value in the remainder of this answer. This means I assume that it is known that the RNG is positively biased.

Test-statistic

Let's call our sequence of output bits $X_i$. We're looking for the distribution of the following sum:

$$S_n = \sum_{i = 1}^n (-1) ^ {X_i} = 2\left[\sum_{i = 1}^n X_i\right] - n$$

Since the $X_i$ are assumed to be i.i.d. we have, asymptotically as $n \to \infty$:

$$S_n \sim \mathcal{N}\left(\epsilon \, n, 4p(1 - p) \, n\right).$$

Both the mean and the variance can then be rewritten in terms of the entropy $H$ (recall that for the mean, there are actually two possibilities). To express the variance in terms of $H$, note that

$$p(1 - p) = 1/4 - \epsilon^2 \approx 1/4 - \frac{\log 2}{2} (1 - H).$$

$P$-value

The $P_n$-value for our test can be computed as

$$P_n = 2\Phi\left(\frac{-S_n}{\sqrt{n}}\right).$$

So we can compute the probability that $P_n \le p_n$ for some value $p_n$:

$$
\Pr[P_n \le p_n]
= \Pr\left[2\Phi\left(\frac{-S_n}{\sqrt{n}}\right) \le p_n\right]
= \Pr\left[S_n \ge -\sqrt{n}\Phi^{-1}(p_n/2)\right].
$$

Now we can use the distribution of $S_n$ which we derived earlier:

$$\Pr[S_n \le s_n] = \Phi\left(\frac{s_n/\sqrt{n} - \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H)\log 2}}\right).$$

So we get

$$
\Pr[P_n \le p_n]
= \Phi\left(\frac{\Phi^{-1}(p_n/2) + \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H) \log 2}}\right)
$$

(in the somewhat unlikely case that my calculations contain no errors, I'll check them later).

Note that as $n \to \infty$, the above probability goes to $1$ (for $H \neq 1$) so given enough sample bits we'll eventually conclude that the sequence isn't random.
So that should also answer your question

  How can we refine this, given $P$-values $P_i$ for that experiment repeated
  $k$ times?

(at least in this specific case)


Key, plaintext block and ciphertext block permutations question Question: If a cipher’s key size is $k$ bits and its block size is $b$ bits, how many possible keys are there, how many possible plaintext blocks are there, and how many possible ciphertext blocks are there?

Studying for an exam and this popped up in a past paper without an answer, is the solution e.g. for key size $2^k$ bits? and similarly for the others will be $2^b$ bits? My friend thinks its $b^k$ so were unsure and clearly don't understand the logic behind it.

The answers very are very easy if you know about binary representations.

$k$-bit means the binary representation contains $k$ binary digits.

xx......xx : k binary digits

For each position can be 0 and 1 so, a $k$-bit can take $2^k$ distinct values.

You can similarly argue for $b$-bit block size, if you know that block size is the input  size for block ciphers.

Since block-ciphers are keyed permutations the input space equal to output space.


What is a u-coordinate within Elliptic Curve Diffie-Hellman using the Montgomery ladder I am trying to understand the below paragraph.

  Elliptic curve Diffie-Hellman is often calculated using the Montgomery
  ladder. This gives a simple and efficient calculation that is
  naturally resistant to timing side channels. The Montgomery ladder
  also allows each party's public key to be a Montgomery u-coordinate.
  Using a single coordinate instead of the whole point makes public keys
  smaller without the expense of point decompression.

I read about Elliptic curves and Montgomery ladder at Wikipedia. Can someone please explain this paragraph in naive language.Also please answer below questions.

What is Montgomery u-coordinate.
A brief explanation of requirement of point decompression.

Montgomery form and ladder

People are typically introduced to elliptic curves in Weierstrass form, namely the points $(x,y)$ that satisfy $y^2 = x^3 + ax + b$. Specifying $a$ and $b$ pick out a particular curve.

There is an alternative representation of elliptic curves, called the Montgomery form:

$Bv^2 = u^3 + Au^2 + u$

Peter Montgomery introduced this form in his 1987 paper. Here, the points are $(u,v)$ pairs and specifying $A$ and $B$ pick out a curve. You can convert from one form to the other. The $u$ here is the u-coordinate you referred to.

Why is this useful?

When doing scalar multiplication on elliptic curves over a field $\mathbb{F}_p$, you have to do a lot of modular divisons / inverses. However, in Montgomery form, $u$ and $v$ are projective coordinates. What this gets you is letting you postpone expensive division operations for as long as possible, giving nice speedups. So think of $u$ as a ratio of two coordinates, similar to (not equal to!) $x/y$.

Very roughly, the Montgomery ladder is doing a "double-and-add" operation on a point in projective space. The input to the ladder is a scale factor $k$ and the u-coordinate, and the output is only the u-coordinate of the scaled point. That's why the Montgomery ladder is called a single-coordinate ladder. If necessary and if you have both $u$ and $v$, you can compute both coordinates of the scaled point, but if you only need the scaled $u$, you get this quickly without having to spend time computing the "baggage" of the other coordinate, like with point compression and decompression.

Point Compression and Decompression

See Section 2.3 for a description of the calculation to do point compression and decompression. The basic idea is it's better to carry one number around than two if you can, so take $(u,v)$ in projective space and combine the two coordinates into a "compressed" value $\tau$ which can later be "decompressed" into $(u,v)$ or $(x,y)$ form. These compression and decompression operations involve taking modular square roots and modular inversion which are expensive. The Montgomery ladder lets you avoid this computation.


Entropy Preserving Functions Let F be a deterministic compression function that takes fixed length 128 bit inputs and outputs 8 bits. Each input to the function has 128 bits of entropy, does that mean that the output byte has 128 bits of entropy ?

Of course not; 8 bits have a maximum of 8 bits of entropy.  There does not exist a probability distribution over the 256 possible values of those 8 bits that gives an entropy value of more than 8.

What this means is that your function can have more entropy on the input than the output.  This is not uncommon, and typically happens if you have a function with fewer possible outputs than inputs (the only exception is if the probability distribution that the input occurs has some inputs with zero probability).


Which is more secure, using just bcrypt or SRP? OK, here's the two different ways I was thinking about making the authentication for the login thing to store the passwords securely.

The first is the following.

Client hashes password bcrypt(username.static_salt.password)(cost is 7)

this is mostly to make it harder for someone to get in trouble if they reuse passwords in other places/to make me feel better.

then they send it to the server. The server then hashes it with bcrypt again(cost is7) there is a per-user salt which is appened to the user's password and hashed together. Another static salt stored in the code(ie for bcrypt itself) is in there. And we have another salt stored on the server(ie no database).

The other one is to use srp6a except to use bcrypt(with the same cost as above) for H(). Which of these is more secure in the long run against an attacker once they get the database. the N is going to be 2048bits.

Also assume all of this is done over TLS/SSL. I'm personally leaning towards the first one, but I want to be sure before I commit to one or the other.

Edit: Now everyone should be using scrypt or argon2 for password hashing with unique salts.

The point of SRP is to remove the need for the SSL/TLS certificates. With SRP integrated into SSL/TLS (as per RFC 5054), you get mutual client/server password-based authentication and can do without any of the dreadful certificate business; and yet the protocol is still resilient to offline dictionary attacks.

If your SSL/TLS still uses a server certificate then there is little point in using SRP; the client already knows that it talks to the right server, and can send the password as cleartext  within the tunnel (or a hash-of-password if you really need that to sleep at night).


Cache Timing Attack SHA-3 I’ve been tinkering with SHA-3 for a little bit, and I have some questions regarding the applicability of cache timing attacks on this particular hash function.  The two sub functions that I believe are susceptible to this particular attack are THETA and CHI. I think I can prove that THETA does not run in constant time, depending on the particular method with which the algorithm is implemented, and I believe CHI does not run in constant time either. To prove that statement with CHI would require the addition of break statements in some implementations of that function. Something that I have yet to complete.

Now assuming that the attacker only has access to a static SHA-3 hash output, I doubt that any information can be gained about the input. However assuming the attacker is able to monitor the execution time of the hash function things get more interesting. Although I'm not sure how prevalent this second scenario is in real life. All that would be gained is the total execution time of all 24 rounds of THETA, but would it be possible from this value to determine the execution time of individual rounds of THETA? Or then be able to approximate inputs based on execution time?

Does anyone know of any references/articles related to SHA-3 and cache timing attacks?

SHA-3 is not vulnerable to cache timing attack.

Only implementations could be vulnerable to timing attacks.

Also it is to be noted that cache timing attacks relate secret data and cache lines refreshed. This is again implementation dependent and could not be observed through Python script.


Is this adaptation of one-time-pad still secure? Having shared a pad of length double the length of your anticipated message, splitting it into x and y.

Then using x to encrypt the message, and using y twice to encrypt the next pad, would that be insecure (seeing as the data I'm encrypting would still be random)?

No, it's not secure; after three messages, the attacker can gain information about the second and third messages.

To review this in greater detail, lets look at your proposal, and what it actually exposes to the user:

To start with, you have a secret $x_0$ and $y_0$ (I'll subscript them to distinguish the values between the iterations).  To encrypt the first message $m_0$, you generate a fresh secret $x_1$, $y_1$, and transmit:

$$m_0 \oplus x_0, x_1 \oplus y_0, y_1 \oplus y_0$$

To send the second message $m_1$, you generate more secrets $x_2$, $y_2$, and transmit:

$$m_1 \oplus x_1, x_2 \oplus y_1, y_2 \oplus y_1$$

For the third message $m_2$, you generate even more secrets $x_3$, $y_3$, and transmit:

$$m_2 \oplus x_2, x_3 \oplus y_2, y_3 \oplus y_2$$

At this point, the attacker has seen $x_1 \oplus y_0, y_1 \oplus y_0, m_1 \oplus x_1, x_2 \oplus y_1, m_2 \oplus x_2$.  If xor's all those values together, he gets:

$$x_1 \oplus y_0 \oplus y_1 \oplus y_0 \oplus m_1 \oplus x_1 \oplus x_2 \oplus y_1\oplus m_2 \oplus x_2 = m_1 \oplus m_2$$

And thus he has recovered the difference between the two messages.  And, other than the fact that the attack cannot recover the first message (because the attacker doesn't get any information on $x_0$), this is not really any better than xoring in a constant string.


Is this variant of Diffie-Hellman viable and quantum resilient? In this paper the author suggests using a variant of Diffie-Hellman which involves floating-point numbers of arbitrary size in the generation of a shared secret.  There are no primes, calculations are performed$\bmod{1}$
In simple terms:

Alice picks $x$ (a decimal number) and $a$ (a random integer). She generates $a'=ax\bmod{1}$ and sends to Bob along with x.
Bob generates $b'=bx\mod{1}$ and sends to Alice.
$a'b \mod{1} \equiv b'a\bmod{1}$, accurate to a certain number of digits depending on the size of $a$ and $b$.

I've checked and remarkably (to me at least) the symmetry works.
In the concluding paragraph, the author suggests that this method is resilient to quantum computers:

Apart from being resilient to quantum computers, the great achievement of the suggested
protocol as opposed to the Diffie–Hellman finite fields methodology is the use of the decimal part of a
transcendental number rather than large finite integers. The use of transcendental numbers does not,
by nature, restrict the number of digits in the calculation as do integers. In the case with finite fields,
the secret numbers are limited by the order of the finite field q. For brute force guessing, one only
has to systematically try all numbers less than q. With the proposed method, there is another bound
indicated by the number of digits in the transmitted numbers $a_
0$ and $b_0$
. However, the cryptanalysis
made possible by Shor’s and Grover’s algorithm does not seem to be a threat to this procedure.

Questions

Is this actually a viable method of key exchange?
Is it really resilient to quantum computers?
Is the $\bmod{1}$ calculation as described a known one-way/symmetrical function, and is it used elsewhere?

Is this actually a viable method of key exchange?

No. An eavesdropper can find the integer $b$ chosen by Bob from $x$ (as sent by Alice) and $b'$ (as sent by Bob), and the equation $b'\,=\,b\,x\bmod 1$ (meaning $\exists d\in\mathbb Z,\ b'+d=b\,x$). The shared $k$ can then be determined from the $a'$ sent by Alice, just as Bob does.
If we take the numbers in the paper's example (section 5), given the first 14 decimals $B$ of $b'$ (out of the 61 sent by Bob) and the 24 first decimals $X$ of $x$ (out of about 71 received by Bob and 30 shown), we get $b$ as follows:

$B$ is the 14 first decimals of $b'$, thus $\big|B-10^{14}\,b'\big|<1$
$X$ is the 24 first decimals of $x$, thus $\big|X-10^{24}\,x\big|<1$
$b'+d=b\,x$ implies $10^{24}\,(b'+d)=10^{24}\,b\,x$
thus $10^{10}\,(10^{14}\,b')+10^{24}\,d=(10^{24}\,x)\,b$
thus $\big|10^{10}\,B+10^{24}\,d-X\,b\big|\le10^{10}$

One method to solve such Diophantine inequality for $b$ (we don't care for $d$) uses continued fractions¹. But we can be lazy and ask Wolfram in near-natural language
|10^10*62932060503117+10^24*d-693147180559945309417232*b|≤10^10 and b>0 Diophantine
and it gives us $b=6913952452$; or use Mathematica to the same effect, Try It Online!
B = 62932060503117;                 (* 14 first decimals of b' *)
X = 693147180559945309417232;       (* 24 first decimals of x  *)
Solve[Abs[10^10*B+10^24*d-X*b]≤10^10 && b>0 && b<10^11, {b,d}, Integers]
…
{{b -> 6913952452, d -> 4792386648}}

More generally, if $a$ and $b$ have $n$ digits, and we want the shared $k$ to agree over $m$ digits with residual odds of the contrary in the order of $10^{-j}/5$ (where that $/5$ assumes rounding to the nearest), then Alice and Bob should agree on $x$ over $2n+m+j$ digits, and send $a'$ and $b'$ over $n+m+j$ digits.
The paper's example targets $m=30$ shared digits in $k$, uses $j=21$ (thus almost always reaches its target), and $n=10$, which is small enough that brute force is usable to find $b$. But the attack above (or the explicit method¹) works in time only polynomial in the number of digits used. Try It Online! with $m=50$, $j=21$, $n=70$: it still takes under 1 second to recover $b$.
The paper should have been screened by the review process of a would-be scientific peer-reviewed journal on cryptography. I conclude Article Processing Charges do not ensure quality. I am not aware of similar mishaps in peer-reviewed publications of the IACR (thus excluding eprint), but that happens more than occasionally in many other publications. See Wikipedia's article on the publisher, and the publisher's response.

Is it really resilient to quantum computers?

In a sense yes for today's quantum computers, since they are unable to compute exact results on more than a few bits. In a distant future, perhaps no. That is: the scheme is not quantum-resilient. It's not even resistant to classical computer.

Is the $\bmod1$ calculation a known one-way/symmetrical function, and is it used elsewhere?

In cryptography, schemes that manipulate reals to a precision better than an FPU register are the exception rather than the norm, and always are internally implemented as integers divided by some integer scaling factor (often a power of a base). Therefore $\bmod1$ is implemented as modular reduction modulo the scaling factor.
Modular reduction modulo an integer is a common building block for one-way functions, such as (in Diffie-Hellman) $k\mapsto g^k\bmod p$ where $p$ is prime, $q=(p-1)/2$ is prime, and $g^q+1\bmod p=0$. But modular multiplication by a public constant (as used in the question's article) is not one-way.

Following the author's comment: the question, and this answer, assume $x$ is public. If $x$ is secret, the scheme is indeed less insecure, and even secure on first use of $x$ when the right parameterization is used. But with the parameterization in the example, we don't need $x$ to find the shared value². And even with good parameterization, if $x$ is reused, security quickly breaks down. The second part of the article's  “The security benefits from distributing $x$ via a secure channel, but this is not necessary” is untenable.

¹ It took me more time than I had hoped to reconstruct an explicit method:

Using continued fractions, write $\frac X{10^{24}}$ as the simplest fraction $\frac r s$ such that $\left\lfloor\frac{10^{24}\,r}s\right\rceil=X$. This is essentially the most compact representation of $x$ as an integer fraction giving it to 24 decimal places. Here $\frac r s=\frac{698526063389}{1007760087583}$
Round $\frac{s\,B}{10^{14}}$ (here 634204188043.9984…) to the nearest integer $t=\left\lfloor\frac{s\,B}{10^{14}}\right\rceil$.
Without proof: there remains to solve for $b$ the Diophantine equation $s\,d+t=r\,b$, here $1007760087583\,d+634204188044=698526063389\,b$
Reducing modulo $s$, we get $t\equiv r\,b\bmod s$, with $r$ and $s$ coprime by construction of $\frac r s$, thus $r^{-1}\,t\bmod s=b$ when $b<s$ (without proof: which holds with high probability when enough digits of $x$ are known in order for the scheme to work reliably). Here $b=6913952452$.

² Assume we have $a'$ and $b'$ to 61 digits as in the example, but not $x$. :

Using continued fraction, express what's known of $a'$ (61 digits each) as a reduced fraction $a'=\frac e f$ with $f^2<10^{61}$, same for $b'=\frac g h$.
From $a'+c=a\,x$ and $b'+d=b\,x$ with $0<x<1$, for at-most-10-digit $a$ and $b$, it holds the Diophantine inequality $\big|b\,h\,(e+c\,f)-a\,f\,(g+d\,h)\big|<2\cdot10^{10}$ with $0\le c\le a<10^{10}$, $0\le d\le b<10^{10}$
Reducing this $\bmod f$ and $\bmod h$, it comes that for some unknown integer $r$ with $\big|r\big|<2\cdot10^{10}$, it holds $a\,g\,f\equiv r\pmod h$ and $b\,e\,h\equiv-r\pmod f$.
With $\ell\gets\gcd(f,h)$, $f'\gets f/\ell$, $h'\gets h/\ell$, and $s$ defined as $r/\ell$, it comes that for some integer $s$ with $\big|r'\big|<2\cdot10^{10}/\ell$, it holds $a=((g\,f')^{-1}\,r'\bmod h')$ and $b=((-e\,h')^{-1}\,r'\bmod f')$.
With $g'\gets(g\,f')^{-1}\bmod h'$ and $e'\gets(-e\,h')^{-1}\bmod f'$, it comes $a=(g'\,r'\bmod h')$ and $b=(e'\,r'\bmod f')$.
This now can be solved by Mathematica, Try It Online!. This gives 4 possible values for the shared $k$, and 10 for $x$.


As a cryptographic primitive, what does a nonce provide? As a cryptographic primitive, what does a nonce provide? It seems like, at least in my understanding of it, a nonce by itself would not provide any sort of cryptographic usefulness, compared with primitives such as digital signatures or symmetric key crypto.

A nonce is not a cryptographic primitive. Cryptographic primitives are algorithms that are part of a cryptographic scheme. For instance, a block cipher can be a cryptographic primitive in a block cipher mode of operation. AES is a primitive in AES-GCM. Nonces are numbers-used-once; they are just a description of unique integer values (usually with a specific encoding in bytes).

AES as a block cipher is not cryptographically secure as a generic cipher (this may surprise you). The reason for this is that once the key is reused with the block cipher it will output the same value for the same input. To be IND_CPA secure the cipher should not output any indication about the plaintext, and outputting the same value clearly indicates that the same plaintext was used.

For this a block cipher mode-of-operation can be used. Some modes of operation such as CBC require input indistinguishable from random. CTR and many modes derived from it such as AES-GCM however just require a nonce. So this is - among possibly other uses in other schemes - what a nonce provides: it makes sure that a mode-of-operation is secure even if the same key is used.

In general a nonce is used in cryptography to provide uniqueness within a function even when the other inputs remain identical.


Largest integer factored by Shor's algorithm? I'm studying Shor's quantum factoring algorithm. I was wondering what the largest integer is which they were able to factor with a small quantum computer. Does anybody have an idea about this?

wondering what the largest integer is which they were able to factor with a small quantum computer

Stunts
Before the present answer, the largest claim for quantum-related factoring seems to have been 4088459=2017×2027, by Avinash Dash, Deepankar Sarmah, Bikash K. Behera, and Prasanta K. Panigrahi, in [DSBP2018] Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer  (arXiv:1805.10478, 2018) using 2 qubits (per their measure) of IBM quantum processors with 5-qubit and 16-qubit.
That's a pure stunt without application to cryptography, brought to a higher degree than in earlier work of Nikesh S. Dattani and Nathaniel Bryans, Quantum factorization of 56153 with only 4 qubits (arXiv:1411.6758, 2014) "factoring" e.g. 56153=233×241. The method applies only to a very narrow class of integers (those product of integers differing only by 2 bits, perhaps with some other constraints). 4088459 and 56153 are determined to fit the method.
The above "factorizations" extend, without requiring any experimental improvement, the earlier record of 143=11×13 by Nanyang Xu, Jing Zhu, Dawei Lu, Xianyi Zhou, Xinhua Peng, and Jiangfeng Du in Quantum Factorization of 143 on a Dipolar-Coupling Nuclear Magnetic Resonance System (Physical Review Letters, 2012). Their technique factors an integer product of two odd exactly-4-bit integers (thus with two unknown bits per factor). The scarcity of primes in range [8,15] makes 143 the only product of two distinct primes that the technique can factor. Their experimental setup iteratively minimizes a function with a 2-bit input.
An experimental improvement to 3-bit input, with application to 551=19×29, is claimed by Soham Pal, Saranyo Moitra, V. S. Anjusha, Anil Kumar, and T. S. Mahesh's Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor (arXiv:1611.00998, 2016). The authors acknowledge that the technique probably can't factor some larger 10-bit integers. The number factored depends on the molecule (dibromofluoromethane) used.
Zhaokai Li, Nikesh S. Dattani, Xi Chen, Xiaomei Liu, Hengyan Wang, Richard Tanburn, Hongwei Chen, Xinhua Peng, Jiangfeng Du's High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spinsystem:  Application to the experimental factorization of 291311(arXiv:1706.08061, 2017) tackle 291311=523×557 using a different molecule ($^3C$-labeled diethyl-fluoromalonate).
Breaking news: I hereby claim a new stunt record. I change the last line of equation (2) in [DSBP2018] from $p_i=q_i=1;\ i\in\{5,6,7,8,9\}$ to $p_i=q_i=1;\ i\in\{5,6,\dots,87\}$, and the very same quantum experiment yields the "factorization" of the 178-bit biprime 383123885216472214589586724601136274484797633168671371=618970019642690137449562081×618970019642690137449562091, or otherwise said that $2^{178}-(13\times2^{91})+651=(2^{89}-21)\times(2^{89}-31)$.

Adiabatic quantum computing records
For something non-stunt, defined as aiming to factor a wide fraction of arbitrary composites up to some limit, the record¹ may be Raouf Dridi and Hedayat Alghassi's Prime factorization using quantum annealing and computational algebraic geometry (in Nature scientific reports, 2017) factoring up to 223357=401×557 using the D-Wave 2000Q (an adiabatic quantum computer). A year later, the debate was still raging about the size of the true quantum computer that it could emulate.

CAUTION - All the above is practically pointless!
None of the above techniques implement Shor's algorithm. They express factorization as a combinatorial minimization problem, solved using a variant of Grover's algorithm or adiabatic quantum computing. There is no argument for hope that these approaches could scale to factorization of integers of cryptographic interest.

Shor's algorithm on quantum computers
We must separately consider the title's question:

Largest integer factored by Shor's algorithm?

I'm not aware of anything above 21=3×7 claimed by Enrique Martin-Lopez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, and Jeremy L. O'Brien in Experimental realisation of Shor's quantum factoring algorithm using qubit recycling (Nature Photonics, 2012).
This beats 15=3×5 first obtained by Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood and Isaac L. Chuang in Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance (Nature, 2001), then several others.
However it is debatable if these are really factoring, or rather confirming a known factorization. John A. Smolin, Graeme Smith and Alexander Vargo in Oversimplifying quantum factoring (Nature, 2013, formerly arXiv:1301.7007 with a different title) go as far as:

(there is) danger in ‘compiled’ demonstrations of Shor's algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice.

Update (Sept 2020)
More stunts factorizations have appeared (see my critic), but the one in this answer remains the true (if under-reported) champion in this dubious category.
The progress on experimental non-stunt implementations seems to have stopped, both for combinatorial approaches using quantum adiabatic computers² and Schoor's algorithm. We do better understand the limitations of current hardware: Mirko Amico, Zain H. Salee, and Muir Kumph's Experimental study of Shor’s factoring algorithm using the IBM Q Experience (in physical review A, July 2019) conclude their work "fails to factor N=35". Experimental quantum computing currently prefers to focus not on beating classical computers at existing problems, but rather on finding problems where that happens beyond simulation of quantum computers.
An interesting new line of work makes mental experiments in factorization on hypothetical quantum computers: see Craig Gidney, Martin Ekerå's How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (arXiv:1905.09749, Dec 2019).

¹ Shuxian Jiang, Keith A. Britt, Travis S. Humble, and Sabre Kais in Quantum Annealing for Prime Factorization (arXiv:1804.02733, 2018) "present how to factorize" 376289=571×659, but I was pointed that it is not an experimental result, sorry for having been careless.
² A close call was Baonan Wang, Feng Hu, Haonan Yao and Chao Wang's Prime factorization algorithm based on parameter optimization of Ising model (Scientic letter, April 2020) which claims a new combinatorial method factoring all integers to 10000, and in the stunt category 1028171=1009×1019, but got eliminated from both lists because that's on a simulation of a D-Wave quantum computer.


Authentication of machine before installation (to stop piracy) I have a web-software project which needs a bit of protection in form of authencitation…

This web based software runs on an intranet. There is no access to the internet from these terminal machines. Nevertheless, I want to stop anybody who copies the (PHP-based) software and tries to run that software on another machine. Simpler said: it should only run in the machine in which it got installed and just stop during authentication-level on any other machine.

I would be grateful to anybody who can suggest me the logic of achieving it.

Thinking "crypto"…

One way I could imagine how you achieving at least some kind of copy-protection on your PHP-based scripts is to use solutions like these random search results: sourcecop, sourceguardian, phpcipher, … or the more well-known, and well-vetted Zend Guard or IonCube PHP Encoder who prevent reverse engineering through PHP encoding and obfuscation and thereby protecting your PHP code from unauthorized use.

But while those (partly cryptographic) script-protection solutions protect your PHP sourcecode, they (mostly) will not lock the scripts down to a single machine…

Blending in additional "security"…

To make the "encrypted PHP scripts" idea usable in your case, you could make your encrypted scripts dependent on some kind of self-coded PHP extension/module that locks itself to a single machine by letting the module verify a machine fingerprint (which includes several serial numbers, hardware configuration, etc.). Somewhat like cryptographically secure RNGs are seeded, but you would be looking for fixed and unique instead of variable and random hardware infos.

Thinking about it, you would probably be able to solve your problem by starting out with that PHP module and make it (a) machine-dependent, and (b) handle the cryptography of your encrypted scripts. If the module isn't in place and verified it's running on the correct machine, the scripts would not execute either as they would look to the PHP interpreter as if they were random digital garbage.

But the downsides of such an approach are pretty clear too, indicating that this is not an option for regular intranet projects. You would need to code (C/C++) a PHP module from scratch, you would need to get the crypto right, you would need to handle potential bottlenecks and slowdowns due to the PHP module's calculations, and much… much more.

And even then, someone who's able to reverse-engineer your module (or emulate the hardware environment parameters the module checks) would be able to "break" your protection. After all, if an attacker can grab your PHP files from your intranet server, he won't have too much of a problem grabbing your PHP module too. The rest of the attacker's job would boil down to a reverse-engineering effort.

Reality-Check…

Obviously, there are some potential options that could tackle the problem, but unless you are working on a big project for some government/corporation/institution, it'll be "overkill" to even think about practically implementing them as they will simply use up too much time and manpower to create from scratch.

From my point of view, the cheapest, the fastest, and the safest way to protect your PHP scripts would not be by means of modern cryptography, but by buying a good lock for your server-room. After all, restricting physical access is the safest way to stop an attacker from copying files from the (locked-in) intranet server. And if you're really fond of cryptography, get one of those electronic locks with a nice interface to put next to the server-room's door… it looks good and entertains you with lock-codes. ;) Throw Zend Guard or IonCube PHP Encoder on top of that and you should be able to say "mission accomplished" — but only for non-critical, civilian purposes where the sole goal is to protect your PHP scripts from being stolen and executed/run on another computer system.


Fast post-processing for broken RDRAND Let's assume that the Intel RDRAND instruction does not return fully random numbers, e.g. because it has been engineered with a backdoor for the NSA.

If the Intel RDRAND instruction is used directly by a software implementation, what post-processing could be performed to make sure that the output would be indistinguishable from random again? The procedure should not be CPU intensive as an application could as well use the OS provided random number generator if that was the case.

Presumption: the random numbers returned by RDRAND do at least comply with FIPS tests against the output for random numbers.

There is no such method.  The only reliable way to "fix" a backdoored RNG is to mix its output with another, secure RNG.

Specifically, let's consider a backdoor similar to that described by Becker et al. (2013), which essentially transforms the Intel TRNG into a deterministic PRNG using AES in OFB mode, with a 32-bit initial seed (occasionally reseeded) and a fixed key chosen by the attacker.

Between reseedings, the output stream of the compromised RNG is completely determined by the initial seed, which can take only $2^{32}$ distinct values.  Thus, an attacker who knows the hidden key can, after observing only slightly more than 32 bits of the output, look them up in a database to recover the seed (or just iterate through all possible seeds to find the correct one).

Alternatively, if the RNG output is used, say, to generate an public/private key pair, an attacker who knows the hidden key and the keypair generation method can easily generate all the possible keypairs and check which one of them matches a given public key.

The important point to realize is that no amount of deterministic post-processing can prevent these attacks — the attacker just needs to incorporate the same post-processing into their own output generation code.  The only thing that can stop such an attack is the addition of some other source of randomness, not predictable by the attacker, to the output.

(Actually, if I read the Becker et al. paper right, the specific attack they describe can be thwarted even without any external source of randomness, simply by feeding the compromised RNG output into a sufficiently large (e.g. 128-bit) entropy pool.  The reason this works is that their attack does still allow about 32 bits of true randomness to be output whenever the compromised RNG is reseeded, and mixing this into a non-compromised entropy pool will build up a considerable amount of randomness over time.  That said, presumably their backdoor could be modified to leak even less actual randomness into the output.)


Should I use HMAC or KMAC for SHA3? I am planning to implement a MAC function for the SHA3. I read that its latest variant is KMAC. I am confused by the comments in the http://keccak.noekeon.org/
website.
Its says...

  Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.

Also

  KMAC is a keyed hash function or pseudo-random function (PRF) that can be used, e.g., to compute a message authentication code (MAC) or to derive a session key from a master key. It is more efficient than HMAC by removing the need for HMAC's nested construction.

So if I want to implement a MAC function Can i just do  the first method ?? just pad the message with key and do the hash ?  Or do I need to follow the KMAC steps?

KMAC128(K, X, L, S):
Validity Conditions: len(K) < 22040 and 0 ≤ L < 22040 and len(S) < 22040

newX = bytepad(encode_string(K), 168) || X || right_encode(L).
return cSHAKE128(newX, L, “KMAC”, S).
Could anyone help ? which method we should use

So if I want to implement a MAC function Can i just do the first method ?? just pad the message with key and do the hash ?

Yes, $mac = \text{SHA3}(k||m)$ is a secure MAC if $k$ is a fixed-length key. This is an explicit design goal of SHA3.

You can also rely on HMAC or KMAC instantiated with SHA3. These will also give you secure MACs but the added complexity is not necessary.


Security considerations for partially shared password databases Programs like KeyPass and 1Password store password database files encrypted by a single password. If someone knows the protecting password ("Vault Key"), they can read the entire database ("secrets").

Being part of a family, I sometimes share passwords with my wife and others for bank accounts or Netflix which we manage jointly or personal accounts which another might need access to if one were incapacitated.

With a software like DropBox, password databases might be synchronized among family members. For different permutations of sharing, different databases might be used each with different Vault Keys. But as particiation or sharing complexity increases, the number of databases and keys grows more quickly (1 user => 1 database, 2 users => 3 databases, 3 users => 12 databases!). Even if multiple Vault Keys are supported in a single database, concurrent edits among users could cause problems for DropBox and similar.

I envision a scheme whereby each user has their own single database file, protected by a private Vault Key. Part of the database file format allows publication of selected secrets from the private list to be shared with other members. I could, for example, share my Netflix password with my wife by including it in the shared list of my database.

To enable the scheme, a private key which rarely changes would be protected by my Vault Key, which can change often. My public key is available in the clear. Each secret record in the database gets its own symmetric key which is encrypted and signed by the keys of the owner, and the secret record key is also encrypted once each by the visible public keys of anyone (any other member's database file's public key) with whom the owner chooses to share the secret record.

If my wife wants to see my Netflix password, she reads my database from our shared dropbox folder and gets the list of records and encrypted record keys. She decrypts any record shared with her using her own Vault Key-protected private key. She can't change the record because I've signed it.

So, I write to my database my own secrets. I have a list of trusted targets (each family member's public key read from /their/ database file). Each of my secrets' keys are encrypted using my own public key, but also (separately) by the public keys of each share target that I have chosen. They can read from this file and decrypt the shared secrets' keys with their private key.

She or anyone else could mangle the file, but the version control in DropBox protects against that. The encrypted database files are to be considered semi-public, since any user with access to it might have a breach.

Are there any implementations of this concept?
What are the security problems with this scheme?
What security gotchas await in a more complete description of this scheme?
Is it terrible, for example, to keep a pk/PK pair even when changing the Vault Key?  Or must it change every time?  Changing the public key would invalidate the shares from others' databases.  I guess we can keep a history of our key pairs until the others have had a chance to update their own databases for my latest key.

(Yes, Passpack allows such sharing perhaps with a different scheme, but frankly, it frightens me.)

Update: I appreciate the answers so far, but they were from a forum with a different lean.  I'm more interested in the security-implementation critique of the scheme rather than getting recommendations of products that approximate it.

What you are looking for is an authentication and access service on top of a password management system. There are a couple of solutions in this space, but they are corporate and expensive:

http://www.liebsoft.com/privileged_identity_management/
http://www.cyber-ark.com/digital-vault-products/pim-suite/index.asp
http://www.netwrix.com/privileged_password_management.html
There are about 10 other companies and products in this space.

There are also some web based versions of keepass which may fit your needs, but then you'll need to secure the HTTPS, etc.

http://sourceforge.net/projects/webkeepass/


If you have two inputs of the same length, are there theoretically collissions in both MD5 and SHA-256? Can there be two messages M, M' both of the same length such that both MD5(M)=MD5(M') and SHA-256(M)=SHA-256(M')?
Let's compare two files: if they have the same length, they are candidates for having the same content; if they share the MD5 sum they are stronger candidates for having the same content (I understand there are MD5 collisions on same-size inputs so this could lead to a false positive), but then if they also share a SHA-256 sum, can I be certain the files have the same content?

It is possible such collisions exist, but because SHA-256 is collision resistant, finding any collisions would be computationally infeasible.  You may safely assume without further checking that if two files have the same SHA-256 hash, then they contain the same content.
You can so safely assume that, given current cryptographic knowledge, that there's no reason to use MD5 at all; you can just use SHA-256.  In fact, you should actively avoid MD5 if at all possible.


Cryptography on programming In pursuit of understanding a randomly found topic I was interested in learning the connection between integer programming and cryptography and found Lenstra Jr.'s Integer Programming and Cryptography. It is bit technical for my taste. Is there an easier reference to use for a novice to learn about what cryptography and linear/integer programming has to do with one another. And what are the ongoing works in this field ?
Appreciate your time in answering this question.

It's Hendrik Lenstra [to distinguish from Arjen Lenstra, both have worked on cryptography].

And, I am afraid I don't know how much the technical details in that article can be omitted, in the sense that only notation is defined and straightforward relationships are explored.

For example, clearly, a knapsack problem is exactly equivalent to an integer linear program.

And the problem finding integral points within a set, as on page 15, if one exists, is related to problems in more recent cryptographic structures such as those used in lattice based cryptography.


Bouncycastle and Salsa rounds Salsa by Daniel J. Bernstein was meant to run with 20 rounds.
As i can configure the rounds in Bouncycastle with Salsa20Engine, do i have better security by increasing the rounds to 1000? The Performance is negligible.

In general you should avoid changing the cipher for no particular reason. It is unlikely that simply increasing the number of rounds will significantly change the security of the cipher. Although attacks are generally against a limited number of rounds, the following is stated for Salsa20 (source: Wikipedia):

  As of 2015, there are no published attacks on Salsa20/12 or the full Salsa20/20; the best attack known[2] breaks 8 of the 12 or 20 rounds.

And this is with very high memory requirements, and only partially reducing the complexity (without any practical attacks even for the reduced round version).

If Salsa20 is broken it is likely an issue with the operations within a round, or something with regard to pre- or post-processing.

So you'd gain next to nothing while sacrificing performance and - probably more importantly - compatibility.

If you want better security you can use another stream cipher - or block cipher in stream mode - to XOR the ciphers together. You could also look at (ciphers with) hardware support to provide better protection of the key and possibly the algorithm (with regards to side channel attacks).


CCA-attack is possible in RSA, but how the decryption key $d$ is known to anyone CCA-attack is possible in text-book RSA, but how the decryption key $d$ is known to anyone, as it is kept secret with receiver.

Chosen Ciphertext Attacks against RSA (such as Bleichenbacher's Attack on PKCS #1 encryption) do not actually reveal the private key.

If they don't, they why do we say that they are a threat?  Well, it's because that the keys are generally not of interest to the attacker.  Instead, given an encrypted message, the attacker actually wants to know what that message says. He's interested in the key only because the keys would reveal the message.  If the attacker can find a way to get the message without the key, he has won the game.  Bleichenbacher gives him such a way.


Encryption vs. decryption of same plaintext Does the same encryption algorithm given the same plaintext always produces the same ciphertext?

Does this cause any security flaws?

It very much depends on the encryption scheme you are using.
In a deterministic encryption scheme, the same plaintext is always encrypted to the same ciphertext (when using the same key of course).
This indeed causes a security problem for all deterministic schemes. I.e. no deterministic scheme can be IND-CPA secure.

If you take a look at the IND-CPA game, you can see why: The adversary $\mathcal{A}$ may simply choose two random messages $m_0,m_1$ and submit them to the challenger. After receiving the ciphertext $c$ he asks for an encryption of $m_0$ and receives ciphertext $c'$. Now as the scheme is deterministic, it follows that $c=c'$ if and only if $c$ is an encryption of $m_0$, therefore if $c=c'$ $\mathcal{A}$ outputs $0$, otherwise $1$.

Therefore, to achieve IND-CPA security we need probabilistic encryption. In a probabilistic encryption scheme, the encryption algorithm uses additional randomness to produce the ciphertext. See for example ElGamal encryption, where the ciphertext consists of two parts, one of which is a random group element. Also all secure modes of operations for block-ciphers introduce randomness in the form of nonces or initialization vectors.

An important thing to note about probabilistic encryption is that, because decryption must be deterministic, and a single plaintext corresponds to a larger number of ciphertexts, the ciphertext will always be longer than the plaintext.


How to calculate secret key size of a CP-ABE scheme How can I calculate the real size of key in a CP-ABE scheme. For example, I have this GSWV scheme:

Fuchun Guo, Willy Susilo, Duncan Wong, Vijay Varadharajan: CP-ABE with constant-size keys for lightweight devices.

In both papers I have that $\mathbb{G}_1=160$ bits and $\mathbb{G}_2=512$ bits, and length of decryption key is: $2\mathbb{G}$.

In this paper, the size of key is: $|S_K|=|\mathbb{G}_1|+|\mathbb{G}_2|=2\cdot 160+2\cdot 512=1344$ bits for $80$-bit security. ($\mathbb{G}_1$ and $\mathbb{G}_2$ are elliptic curve bilinear groups).

In this paper (original paper), the same key is: $|S_{K_\mathbb{A}}|=|\mathbb{G}_1|+|\mathbb{G}_2|=672$ bits.

I'm confused.

I don't understand, how can I calculate the size of key correctly if I only have $\mathbb{G}_1$ and $\mathbb{G}_2$ ?

How can I calculate the size of key in this case: $n\mathbb{G}$ ?

I'm confused if I must calculate $n\mathbb{G}=|\mathbb{G}_1|+|\mathbb{G}_2|$ or $n\mathbb{G}=n\cdot|\mathbb{G}_1|+n\cdot|\mathbb{G}_2|$.

Different researchers use different notations for elliptic curve bilinear pairing groups. For symmetric pairing this can look like:

$e: \; \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$
$e: \; \mathbb{G}_1 \times \mathbb{G}_1 \rightarrow \mathbb{G}_T$
$e: \; \mathbb{G}_1 \times \mathbb{G}_1 \rightarrow \mathbb{G}_2$
$e: \; \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ (with $\mathbb{G}_1 = \mathbb{G}_2$ for symmetric and $\mathbb{G}_1 \neq \mathbb{G}_2$ for asymmetric)

All of the symmetric variants mean the exact same thing and only differ notationally.

Now, if a scheme is constructed from asymmetric pairing, there is nothing holding you back from instantiating the scheme with a symmetric pairing, other than possible security concerns and enabling attacks on it. So, theoretically we can calculate the size of the user secret key as $|SK| = 2|\mathbb{G}| = |\mathbb{G}|+|\mathbb{G}|$ instead of $|SK| = |\mathbb{G}_1|+|\mathbb{G}_2|$. Now you only need to use one group instead of two, which is a more compact notation, but not entirely true.

The authors of both papers that you referenced probably chose this notation in order to include everything in a single table, because the page width is limited and they can't severely change the font size, because they need to follow the template of the conference/journal.

Now, your question is why the authors of the ODG scheme calculated the size of the secret keys of the GSWV scheme differently than the authors of the GSWV scheme themselves.

Let's recap elliptic curve groups. We have an elliptic curve, such as $y^2 = x^3+a\cdot x+b$ where $a$ and $b$ are curve parameters, that is defined in two-dimensional space over some (prime) field. Each point on the curve, where the above equation holds, is represented by two elements, $x$ and $y$, from the underlying field.

If the field is a 160-bit prime-order field, then elements of $\mathbb{G}_1$ can be serialized to 320-bit as a concatenation of $x$ and $y$. But we don't necessarily have to store $y$, because if we know the curve, then we can simply calculate $y$ from $x$:

$$y = \sqrt{(x^2+a)\cdot x + b}$$

Example in code from jPBC:

protected void setPointFromX() {
    infFlag = 0;
    y.set(x.duplicate().square().add(field.a).mul(x).add(field.b).sqrt());
}

So, you can reduce the size of the serialized curve element by half, but then you would need to do additional calculations in order to reconstruct the curve element from $x$ in order to use it. It's a compromise. The authors of GPSW chose to optimize for size and the authors of ODG chose to optimize for speed (or simply to let their scheme look good).


does using an HMAC protect against hash table DoS attacks? For a hash set where the values are supplied by a third party, one concern is that an attacker can run a denial of service attack by creating many values that all fall into one bucket of the hash table, causing accesses to take linear time instead of amortized constant time and overloading the system. (Since it’s a set, let’s assume that exact data matches are not stored, so you can’t fill the bucket just by writing the same value many times.) What’s the best defense against this type of attack?

Using a cryptographic hash helps because it makes it hard to generate values that have specific hashes — but if there are N buckets and N is not super large, simply generating random data will still produce a hit approximately once every N tries. So if an attacker knows (or can guess) your hash function, they could still attack your system fairly easily by precomputing a bunch of colliding values and then uploading just those values.

It seems like an HMAC / some other kind of keyed hash would be a good way to prevent an attacker from knowing what bucket their data will end up in, but will it also cause values which hashed to the same bucket using the original hash function to be distributed evenly (seemingly randomly) across buckets?

Also, if that works, I was wondering if an HMAC is necessary, or if using some other hash method that uses a secret (for instance using the keyed versions of the BLAKE2/3 hash family) would work just as well.

but if there are N buckets and N is not super large, simply generating random data will still produce a hit approximately once every N tries.

Changing the hash function won't change this fact. There should be other mitigations to a user adding a bunch of random data, such as rate limiting or changing your data structure.

How do you plan on obtaining the key for the HMAC? If it's the same for everything, then hash collisions in the underlying hash function translate to hmac collisions. If it's derived from the data, then the attacker's job is just marginally more difficult; they have to effectively compute three hashes per calculation (one for the key derivation, two for the hmac) instead of one. If it's random, how will you be able to retrieve data from the table?

As you mention in the comments, we don't care about hash collisions but rather hash collisions mod N. In this scenario, an HMAC would sufficiently stop an attacker from being able to calculate data that would hash to the same bucket. If the HMAC construction is too expensive for your application, you should be able to get away with something lighter weight like H(key||message).


El Gamal Cryptosystem Proof, Step-by-Step Explanation Needed. I feel like I don't understand what I have on this proof Can someone provide a good and thorough explanation of the El Gamal proof? Basically, I need a step-by-step breakdown of what is happening at each important part in the algorithm.

I haven't been able to find any good notes on El Gamala that explain the proof in an easy to understand format.

Here is the proof in this image:

First, we should make clear what we're proving here. The derivation you're showing is part of a proof of correctness of ElGamal encryption, not security.

Perfect correctness (also referred to as completeness) of a public key encryption scheme is defined as follows.

Let $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be a public key encryption scheme. The scheme is said to be perfectly correct if it holds that for any security parameter $n\in\mathbb{N}$, any key pair $(\mathsf{ek},\mathsf{dk})\gets\mathsf{Gen}(1^n)$, any message $m$ from the message space, and any ciphertext $c \gets \mathsf{Enc}(\mathsf{ek},m)$ it holds that $\mathsf{Dec}(\mathsf{dk},c)=m$.

To see whether ElGamal encryption is correct, we first recall the definition of ElGamal encryption. I will try to follow the notation in your notes as close as possible. From the notes it's not clear what kind of group is being used. But $e_1$ is a generator of some subgroup of $\mathbb{Z}_p^*$. Let $q$ be the order of that subgroup. (If $e_1$ is a generator of $\mathbb{Z}_p^*$, then $q=p-1$, if we are in a safe prime setting, then $q=(p-1)/2$ and prime.

\begin{align}
&\mathsf{Gen}(1^n) && \mathsf{Enc}(e_2,P) && \mathsf{Dec}(d,(c_1,c_2))\\
&d\gets\mathbb{Z}_q&&r \gets \mathbb{Z}_q&&P' := c_2\cdot (c_1^d)^{-1} \bmod p\\
&e_2 := e_1^d \bmod p&&c_1:= e_1^r\bmod p&&\text{return }P'\\
&\text{return } (e_2,d)&&c_2 := P\cdot e_2^r\bmod p&\\
&&&\text{return } (c_1,c_2)&&\\
\end{align}

To verify that the scheme is correct, we need to verify that for any choice of key pair, and message it always holds that $\mathsf{Dec}(d,\mathsf{Enc}(e_2,P)) = P$. This is where the derivation you're looking at comes in.

\begin{align}
 P' =& c_2\cdot (c_1^d)^{-1} \bmod p \tag{1}\\
=& c_2\cdot (e_1^{rd})^{-1} \bmod p\tag{2}\\
=& P\cdot e_2^r\cdot (e_1^{rd})^{-1} \bmod p\tag{3}\\
=& P\cdot e_1^{rd}\cdot (e_1^{rd})^{-1} \bmod p\tag{4}\\
=& P\cdot e_1^{rd}\cdot e_1^{-rd} \bmod p\tag{5}\\
=& P\cdot e_1^{rd-rd} \bmod p\tag{6}\\
=& P \bmod p\tag{7}\\
\end{align}

Now let's go through this line by line.

In line (1) we simply have the definition of the decryption algorithm.
In line (2) we use the definition of $c_1 = e_1^r\bmod p$ from the encryption algorithm and replace $c_1$ by its definition.
In line (3) we do exactly the same with $c_2$ and replace it with its definition $c_2 := P\cdot e_2^r\bmod p$ from the encryption algorithm.
In line (4) we now look at the key generation algorithm and replace $e_2$ by its definition from there $e_2 := e_1^d \bmod p$. Note that we have not changed anything. We have simply replaced the variables $c_1,c_2,e_2$ by their respective definitions.
In line (5) we use a basic rule of exponentiation, namely that $(x^a)^b = x^{a\cdot b}$, therefore $(e_1^{rd})^{-1} = e_1^{-rd}$.
In line (6) we again use a basic rule of exponentiation, namely that $x^a\cdot x^b = x^{a+ b}$, therefore $e_1^{rd}\cdot e_1^{-rd} = e_1^{rd-rd}$.
Since $rd-rd=0$ and anything raised to the $0$th power equals the identity, we are left with $P\cdot 1 \bmod p$ and thereby, since $1$ is the identity of the group with $P$ in line (7).

Since this derivation makes no assumptions whatsoever about $P,d,e_2,c_1$ and $c_2$, besides that they were generated according to the above definition of ElGamal encryption, it holds for any choice of key-pair and any plaintext $P$.

The derivation thus shows that decryption always works and results in the same plaintext that was encrypted, thus showing that the encryption scheme is in fact correct.

What it does not show is anything about the security of the scheme.


Is it possible to derive a public key from another public key without knowing a private key (Ed25519)? I have a following use case:
User has his master public (pk) - private (sk) key pair (Ed25519).
In DB we store a public key.
Is there any derivation mechanism D, where when knowing a derivation parameter x we can use it derive a new private key sk2 = D(sk, x) and public key (knowing only public key in DB): pk2 = Dx(pk, x) such that we can verify signature done by sk2 using pk2 ?
In other words, I would like to have a derivation mechanism I can use on the user side and server side, where server doesn't know private key.
Best if it works with Ed25519 keys.

Yes! You can use the ephemeral key derivation mechanism that is for example used in Monero (they call it stealth keys there).

Consider public key $A=aG$, with private key $a$. Then, a derived key can be generated, parametrised by the random scalar $r$:

$$A'=H_s(rA)G+A$$

and the party that knows $a$ can use the public parameter $R=rG$ to compute their ephemeral private key $a'=H_s(aR)+a$. You can for example store $R$ with your signature.

Note 1: We add $A$ resp. $a$ to the public resp. private key to ensure that the party that derives a key cannot compute the private key.

Note 2: This derivation is basically a Diffie-Hellman key exchange with a random ephemeral key $R$.

Note 3: $R$ can also be used to "check" whether the user has access to this specific key. He just needs to check whether $A'=H_s(aR)+A$ holds.


Would it matter if my miner was hashing random vs incremental values? I'm working on my miner for my "game" site that's basically a pre-image attack from a hash posted online. You submit a hash input, it's hashed, and your score is the hamming distance (the number of bits that differ) between the two values. If it matters, I'm using Skein-1024 v1.3

My miner up until now has been incrementing a value and hashing it. Increment, hash, increment, hash ad infinium. I wrote it so that when I close the miner, it saves it's current highest value that way when I restart it I won't start back over at 1 and hash all the same inputs again. I can pick up where I left off. This has proven to be some what successful. However, I'm curious if the miner might be more fruitful by generating random numbers instead of incrementing.

It seems to be a hard metric to measure. I know that most hashes will output wildly different values if their inputs are off by only a bit or two, but I feel that by incrementing the value I hash I'm usually only a few bits off. If I randomly generate values I'll probably do fewer hashes (because random number generation is more intensive than a simple num++ increment) but my gut tells me that I'll have a more diverse set of inputs and that it might produce a more diverse set of outputs. I know not to trust my gut without reason about this. I feel crazy just typing it out.

I also know that if I increment I'll never end up hashing the same value twice. Random is capable of that although the odds of generating the exact same 64 bit number twice is slim.

Can I expect different qualities of outputs from my miner by hashing random values instead of an incrementing value?

FULL DISCLOSURE: I am the owner and operator of the site above. There are no ads or even analytics on the page.

For a good hash function, like Skein, diversity of inputs has no impact on diversity of outputs. So, if you have no information about the space of possible pre-images (e.g., it is not a human generated password, it is a completely random input from your prospective), then the expected number of attempts before retrieving the pre-image is the same in either case. Should also be the same number of attempts to find an input with a specific hamming-weight from the input.

As you note, however, there are benefits to using the counter. You can easily save state. You know you will never see the same input. If you are generating random 64-bit values, the odds of seeing a colliding input is actually not as small as you would think. You would expect to see a collision after $2^{32}$ inputs.


Choose a random number that is different from a bunch of other secret numbers I'm looking for an algorithm where n participants each have a different secret number between $[0..x]$ (and where $x$ is known) and where the participants then select randomly another, non-secret, number between $[0..x]$ which must not clash with the secret of any participant and which must not reveal any number used by any participant.

That each participant has a secret number and that no two participants have the same number is a given.

Proofs that participants are acting honestly is not necessary.  You can assume that the parties are semi-honest (i.e., they will not deviate from the protocol).

So, for example (this part I'm not interested in):

Alice has the number $18$
Bob has the number $52$
Eve has the number $193$

At this point each participant knows:

its own number
that each participant has a different number
that each participant knows only its own number

Considering that as our starting point, now Alice, Bob and Eve have to reach a consensus allowing to pick randomly one (and only one) public number between $[0..200]$, which does not clash with any of the three private numbers, without revealing any information about the private/secret number of any participant.

Is there a practical algorithm allowing to do this? By "practical" I mean something that can be used today and that would run in very reasonable times.

Maybe some homomorphic scheme?

You can assume that $x$ will be small and $n<x$, but unfortunately $n$ will be large enough that a random number will have a significant probability of clashing with some participant's secret number.  In other words, $n/x$ is a relatively large fraction.

I think this would work, although whether it's practical is another matter. For large $x$ it won't be. It's basically an application of mental-poker.

First, choose a secure commutative encryption algorithm that is not vulnerable to known plaintext or chosen ciphertext attacks.

Everyone generates a random encryption key.
Everyone but Alice uses their key to encrypt their secret unique number.
Alice uses her key to encrypt every item in the list $[0,...,x]$, except her own number. She then shuffles the list.
Everyone passes their encrypted secret number/list to the next person (e.g. clockwise), who encrypts it, shuffling the list when they have it. Repeat until all the numbers and the list have been passed around. At that point both Alice's list and everyone else's number has been encrypted by everyone.
Remove all the encrypted numbers from the list. Since the encryption is commutative, each encrypted number will match itself in the list, but because everyone has shuffled the list, they don't know what those numbers originally were.
Pick the first number from the list. Have everyone decrypt it with their key and pass the result around, until they've made a whole round. Now everyone should have the same random number, which they can verify by comparing their results.

(If the number would only be decrypted once, the final decrypter could cheat and pick any number, hoping it doesn't match the others'.)

I.e. with your example values:

Alice: key $a$, Bob: $b$, Eve: $e$
Bob: $E_b(52)$, Eve: $E_e(193)$
Alice: $[E_a(0), ... E_a(17), E_a(19), ... E_a(200)]$, shuffle.
Alice $\mapsto$ Bob: $[E_a(i), ...]$, Bob: $[E_b(E_a(i)), ...]$, shuffle.

Bob $\mapsto$ Eve: $E_b(52)$, Eve: $E_e(E_b(52))$.

Eve $\mapsto$ Alice: $E_e(193)$, Alice: $E_a(E_e(193))$.

Alice $\mapsto$ Bob: $E_a(E_e(193))$, Bob: $E_b(E_a(E_e(193)))$.

Bob $\mapsto$ Eve: $[E_b(E_a(j)), ...]$, Eve: $[E_e(E_b(E_a(j))), ...]$, shuffle.

Eve $\mapsto$ Alice: $E_e(E_b(52))$, Alice: $E_a(E_e(E_b(52)))$.
Now the list, $E_a(E_e(E_b(52)))$ and $E_b(E_a(E_e(193)))$ can be revealed and the Bob and Eve's numbers removed. Since the encryption is commutative, $E_a(E_e(E_b(52)))$ will match $E_e(E_b(E_a(52)))$ somewhere in the list, as will $E_b(E_a(E_e(193)))$.
Everyone takes the first number in the list, say $E_e(E_b(E_a(42)))$. They each decrypt it, e.g. Bob: $D_b(E_e(E_b(E_a(42)))) = E_e(E_a(42))$. They pass them around like in step 4, so that eventually e.g. Bob gets $E_b(42)$, which he can decrypt and announce, comparing to Alice and Eve's results.


Ephemeral Diffie-Hellman generator selection I need to generate a EDH group on the fly in one has not been specified in a config file. Diffie-Hellman is kind of expensive in terms of computation, so I'd like to reduce the cost if possible.

Is there any benefit to selecting a generator of 5 versus 3 or 2 in an attempt to keep the costs minimized? Is this a misguided optimization?

Related: are there any libraries that allows you to specify, for example, {2,3,5} are acceptable generators for a group? Or do you normally just specify a subgroup order? (I know OpenSSL has for example, DH_GENERATOR_2, but I'm not aware its a bit mask value).

I'm not aware of any attack made much easier by using a small generator in EDH, like $g=3$ or $g=5$, even $g=2$ (but I'm not accustomed to GNFS or index calculus), as long as there is a single $g$ used for a given instance of other parameter(s). These generators are common, and (especially $g=2$) allow a modest but sizable performance improvement.

I would give a reference to the desired library, if I knew one. However it is not rocket science to implement for straight EDH, when the desired criteria is known. If we want a random huge $p$ and a generator $g$ among a small list of small $g>1$ such that $g$ is a generator of the group $\mathbb Z_p^*$ where the Discrete Log is hard, one possibility is to generate a random prime $p$ of the desired size until $(p-1)/2$ is also prime, and for one of the desired $g$ we have $g^{(p-1)/2}\bmod p\ne1$ (notice that $g^{p-1}\bmod p=1$ holds since $p$ is prime, and $g^2\bmod p\ne1$ holds since $g\ll\sqrt p$).

There a many other criteria in use, such as those set by RFC 2412, used by IKE as defined by RFC 2409, where in addition to $p$ and $(p-1)/2$ prime, it is wanted:

$g=2$ and $g^{(p-1)/2}\bmod p=1$ (rather than $\ne1$), for reasons explained by poncho;
a number of top and bottom bits of $p$ are forced to 1, in order to simplify modular reduction both by classical and Montgomery arithmetic;
the random-looking center bits of $p$ are traceable to a nothing up my sleeves number.

Another common set of criteria it that for DSA, as specified by FIPS 186-4, appendix A (also good for the Finite Field Cryptography scheme of NIST SP 800-56Ar2 and ancestors, which use DSA public key certificates in order to resist MITM). That requires more complex parameter selection; in particular, a subgroup of prime order $q$ much smaller than $p$. While still not rocket science, that parameters generation process is more involved, and constrained by the standards.


What is a wide block cipher and why does it avoid birthday bound problems? I've recently heard the claim that wide block ciphers avoid birthday bound problems. Trying to figure out what exactly "wide block encryption" is, a quick search turned up this paper which is trying to do the following:

  The focus of this paper is how to use a standard block cipher as a component
  to build a ”wide” block cipher, or, in other words, to build a secure PRP from
  another PRP operating on a smaller domain.

Also stating that

  The size of the wide block cipher is l=n∗m bits.

It specifically mentions IEEE P1619-2 (Wikipedia). But that standard seems to be paywalled. From the description on Wikipedia it sounds like it is related to disk encryption but that is not a real definition. It might just be a block cipher with a bigger block size but that seems pretty vague.

Could somebody please tell me what a wide block cipher is and why it avoids the birthday bound?

I don't think the term "wide block cipher" has a hard definition beyond

  has a larger block size than the current standard algorithm(s)

which right now in most cases would equal to

  has a block size larger than 128 bit

because AES is our current reference standard.

Now the thing with block ciphers is that they are are pseudo-random permutations and as such you can distinguish them from pseudo-random functions because you will see a collision with the latter at the birthday where you won't find that with PRPs. This can be important in scenarios where you need to generate a lot of random numbers mostly and even then I don't think the different characteristic would be exploitable in most cases.

To see how PRPs can be distinguished, assume as an example that you run CTR-mode with a PRF and a PRP, both with $n$-bit output length. You will now find that a collision in the CTR keystream occurs with the PRF at about $2^{n/2}$ invocations whereas this won't happen until after you wrap-around with the PRP.

Another application of wide block ciphers is in full-disk encryption where you can encrypt larger blocks implying that single bit-flips will destroy larger regions of plaintext thus being (hopefully) more notice-able.

The last somewhat popular application of wide block ciphers is as part of hashing functions. Imagine your average block cipher $E:\{0,1\}^k\times \{0,1\}^n\to\{0,1\}^n$, note that you can put more into the function than you take out of it. Now you expect collisions after $2^{n/2}$ invokations, ie you have $n/2$-bit collision resistance which makes non-wide block ciphers (such as AES) unsuitable for usage as a core compression function in hash functions (because $2^{64}$ operations is feasible and a similar amount of work was done for the SHA-1 collision).


Switching between AES and a highly performant algorithm I want to de/encrypt several binary files rather frequently on a normally battery-powered device. My goal is to use AES-256 when the device is AC-powered and a highly performant algorithm when it's battery-powered to save power. I appreciate that the level of security will be compromised.

Is there a performant algorithm that provides "decent" security? I see that Blowfish fares a bit better according to this analysis, but the difference is rather small over AES-128. Given that the paper is almost 10 years old, are there good alternatives out there today?

Is AES-128 supposed to be the standard for something decently secured and highly performant?

Yes, AES-128 is intended to be the standard block cipher for building a secure and efficient symmetric cryptosystem using some block cipher operating mode, like CTR for encryption or GCM for authenticated encryption; efficiency can be particularly good when there is hardware support for AES and GCM.

There might be better choices in the case at hand, like for a 32-bit CPU ChaCha (perhaps combined with Poly1305 for authenticated encryption), or one of a plethora of  lightweight block ciphers. If the device is 8-bit, and speed/efficiency paramount, one might even consider the deprecated and partially broken RC4, although its security is questionable even when discarding the beginning of the keystream.

Notice that keeping secret the key of either of these algorithm is hard in a non-security CPU assumed in the hands of an adversary, to the point of being best considered impossible facing a competent and determined adversary. And in a modern security CPU, you might have AES in hardware (thought often, optimized for security rather than speed).


Symmetric encryption vulnerable when encrypting and decrypting are the same? To my understanding, symmetric encryption is where encrypting and decrypting data can occur with the same key.

It's possible for symmetric encryption that the encrypting and decrypting algorithms are the same, but this is not always the case. If I'm not mistaken, with AES this could be the case for some block modes, not for others, but I'm not 100% certain about this. (?)

A dummy example which has this property is ROT13 encryption (which therefore also happens to be ROT13 decryption).

An encryption scheme can work as follows:

Based on some password or key, define a deterministic stream of pseudorandom noise or garbage ("entropy stream").
Output data = input data XOR'ed with the entropy stream from step 1.

In this case, encrypting and decrypting are the same.

Assuming that the entropy generator in step 1 is safe (i.e. can be considered a cryptographically secure source of randomness), is the above encryption scheme sound and safe? Or are their still downsides to it compared to other symmetric encryptions, that may not have the poperty of encrypting and decrypting being the exact same algorithm?

The short answer to your question is yes, but the devil is in the details of "(i.e.  can be considered a cryptographically secure source of randomness)".  For one thing, the "entropy stream" or any portion of it must never be reused within the same (periodicity) or any & all other input data streams.  For another, it is in principle impossible to prove randomness.  OTOH, "cryptographic security" is more tractable.

Interestingly (at least to me) there is another binary primitive that has the same reflexive property as XOR: complementation, or double subtraction.  Consider this C fragment:
    Output_byte = (512 - Input_byte - Key_byte) & 0xff;

There are other (faster) ways of doing it using logical inverse & the properties of two's complement representation, but it's still nowhere near as fast as XOR. It does, however, have the same self-inverse property that XOR does.


Common Crypto C api: Why both CCCryptorUpdate() and CCCryptorFinal()? With the C api for Apple's Common Crypto, why is it sometimes necessary to call both CCCryptorUpdate and CCCryptorFinal?

I read in the documentation that CCCryptorFinal is not needed when:
1. Encrypting or decrypting with a block cipher with padding disabled, when the total amount of data provided to CCCryptorUpdate() is an integral multiple of the block size.
2. Encrypting or decrypting with a stream cipher.

So it seems like it has something to do specifically with dealing with the padding for block cipher encrypted data, but I was hoping for more information.

Re-phrasing the comments into an answer as the question changed during comments:

CCCryptorFinal is necessary when CCCryptorUpdate is being used and padding is specified in order to know when the last block is being encrypted so the padding can be added.

The advantage to splitting up the process might be to use smaller buffers, etc, Consider encrypting a multi-GB file.

Additionally there are encryption modes that are not supported by the one-shot CCCrypt which only supports ECB and CBC modes.


CBC-MAC insecure with random IV Prove that the following modification of $\operatorname{CBC-MAC}$ does not yield a secure fixed-length $\operatorname{MAC}$:

Modify $\operatorname{CBC-MAC}$ so that a random $IV$ is used each time a tag is computed (and the $IV$ is output along with $t_l$). I.e., $t_0 \leftarrow \{0, 1\}^n$ is chosen uniformly at random rather than being fixed to $0^n$, and the tag is $t_0, t_l$.

Answer. The scheme is not secure. In particular, let $m$ be a one-block message and let $(IV, t)$ be its $\operatorname{MAC}$-tag received from the oracle. Then, the tag $(m, t)$ is a valid $\operatorname{MAC}$ for the message $IV$. (More generally, for any $m'$ the tag $(IV \oplus m', t)$ is a valid $\operatorname{MAC}$ for the message $m \oplus m'$. This means that it is possible to generate a forgery for any desired single-block message.)

From the paper CIS 5371 Cryptography, Home Assignment 4

My question is how is the tag $(m,t)$ a valid forgery. This is my understanding:

If I used numbers so $m=101, IV=110, m\oplus IV=011$, but the forgery says that I can use m, so that $m=101, IV=101, m\oplus IV=000$, which is obviously not the case. Could someone explain?

Then, the tag (m,t) is a valid MAC for the message IV.

In other words, given a tag $(IV,t)$ for a message $m$, you can construct a tag $(m,t)$ for the message $IV$. So your understanding is wrong. It is not $m\oplus m$ in the forgery, it is $IV\oplus m$ which is the same as $m\oplus IV$.


Can machine learning/AI lower the security existing cryptographic protocols similar to quantum computers? Initial thinking would be not unless the protocol revealed sensitive local information that could then be analysed by an ML algorithm and applied globally.

local meaning I see messages from Alice and Bob extract some information x,
then apply x to all other users.

Not an expert in ML, this was just initial thoughts.

No.  Machine learning and AI techniques do not fundamentally change the computational capabilities of an adversary like a quantum computer does, no matter how much hype is in the air around ML and AI.


How to configure a client browser cert to be authenticated by a server? I currently am being asked to partake in a strange authentication format while working with a client, and was hoping for clarification.

The client is using HTTPS with client certificate authentication, therefore I will install their provided certificate within my browser as a form of authentication.

As a second step, they are also asking that I create my own certificate and have a CA sign it, and then provide them with the certificate and CA so that the server is configured to authenticate with the client.

While I can create a certificate with openssl from the command line, have it signed, and send it to them, how is this authenticating/verifying my browser at this point?

You have to use the certificate (which will have your public key) which you had generated, to configure your browser. This certificate can be used by your browser to authenticate itself with server.


When would one prefer a proof of knowledge instead of a zero-knowledge proof? I've just realized I find it hard to distinguish between these two terms (proof of knowledge, and zero-knowledge proof), specially where only the latter seems to be used in many cryptographic protocols.

Zero-knowledge proofs are usually defined as those methods by which the prover manages to prove to the verifier that a given statement is true, without revealing any additional information apart from the fact that the statement is true. For example, let's say I want to prove knowledge of the plaintext of some ciphertext I've generated, so that everyone can check that the plaintext is of a certain form (a value within a certain range, for instance). It seems clear to me that in this case I'd be interested in using a zero-knowledge proof, because I don't want anyone else learning what my plaintext was, or which random value I used to encrypt it (I'm assuming I used a public key encryption scheme).

On the other hand, proofs of knowledge seem to be just defined as those proofs in which the prover convinces a verifier that he/she knows something (without stating any constraint about what the verifier can or cannot learn from his interaction with the prover). From the definitions, these two terms seem to be pretty different. However, I find it hard to see in which context one would be interested in using just proofs of knowledge, instead of zero-knowledge proofs.

Formally, this is all very complicated, but informally:

An interactive proof is a conversation between a prover and a verifier that ends with the verifier either accepting or rejecting.

The interactive proof can be zero knowledge, in which case a cheating verifier does not learn anything new by talking to the honest prover.

The interactive proof can be a proof of knowledge, where a cheating prover cannot convince an honest verifier to accept unless he (essentially) knows some secret.

The interactive proof can of course be both zero knowledge and a proof of knowledge.


Need help solving a puzzle (from a layperson) As the title says, I'm a layperson when it comes to cryptography, so my question may not make absolute sense. Apologies in advance if this is vague.

Here is the puzzle I'm presented with:

  You were smart to look here.

  Can you take on the next step?

  ecdsa-sha2-nistp256

  AAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBOKGEKYjpEGmRrtoGdf79CJljyk1y/GbMFCXt9AoKnk5Lw9r5Snv63xYZ5WLBNkozVe4sNLXIaUGti/pMOy4akk=

From this point, three "hints" were provided:

1) Run the ecdsa public key trough a base64 decoder.

When running the public key through various online base64 decoders, the result has been varied on each site. I get everything from Korean characters to random box characters. So I'm somewhat stuck at hint 1.

2) Open the base64 decoded value in hex editor.

3) Public key should be a 65-byte array, starting from byte with value 4, next 32 bytes would be x value, and the next 32 the y value.

A final clue is this: "First have the name of the digital signature algorithm, then the name of the curve, and then the public component of the key. Got it?"

Can anyone here make sense of all of this? Thanks in advance for any help. I'm happy to answer any questions that could help you in solving this.

The hints provide a lot of information about the puzzle.

  1) Run the ecdsa public key trough a base64 decoder.

  When running the public key through various online base64 decoders, the result has been varied on each site. I get everything from Korean characters to random box characters. So I'm somewhat stuck at hint 1.

  2) Open the base64 decoded value in hex editor.

Base64 encoded data is not necessarily text (ASCII, UTF-8 or otherwise). The easiest thing to do is to decode this into standard hexadecimal bytes. So converting the Base64 string to a Hexadecimal string results in

000004d958d91cd84b5cda184c8b5b9a5cdd1c0c8d4d800000021b9a5cdd1c0c8d4d800000104138a1842988e9106991aeda0675fefd089963ca4d72fc66cc1425edf40a0a9e4e4bc3daf94a7bfadf1619e562c1364a3355ee2c34b5c86941ad8bfa4c3b2e1a9240

  3) Public key should be a 65-byte array, starting from byte with value 4, next 32 bytes would be x value, and the next 32 the y value.

This hint is telling us to extract the public key. The data provided is 104 bytes in length but the public key is only 65 bytes. It begins with a 04 byte (that's what "byte with value 4" means), so we look for that pattern in the data.

There are two such places where there is a 04 byte, so let's start with the first one.

If we assume the first 04 that we see corresponds to the public key, then our public key will be:

04d958d91cd84b5cda184c8b5b9a5cdd1c0c8d4d800000021b9a5cdd1c0c8d4d800000104138a1842988e9106991aeda0675fefd089963ca4d72fc66cc1425edf

If we assume the second 04 that we see corresponds to the public key, the the public key will be:

04138a1842988e9106991aeda0675fefd089963ca4d72fc66cc1425edf40a0a9e4e4bc3daf94a7bfadf1619e562c1364a3355ee2c34b5c86941ad8bfa4c3b

  A final clue is this: "First have the name of the digital signature algorithm, then the name of the curve, and then the public component of the key. Got it?"

This clue refers to this string:

  ecdsa-sha2-nistp256

ecdsa stands for Elliptic Curve Digital Signature Algorithm. This indicates the digital signature algorithm that was used.

sha2 indicates that a function in the SHA-2 hash function family was used for signing the message. When signing a message with ECDSA, the message must be hashed with some hash, commonly SHA-256. I will assume this means to use SHA-256.

nistp256 refers to the elliptic curve that was used in ECDSA. It provides us with the other parameters that we need to compute and verify an ECDSA signature.

That is all of the information that can be gotten quickly from the provided hints and initial information. You will have to look through the remaining 39 bytes of data to solve the rest of the puzzle.

Further examination of this shows that it is an SSH public key.