PBKDF2 with longer than native output length - Will hashing the result help? I've seen it mentioned more than once that PBKDF2 should not be used to create a longer key than the native output (such as 160 bits when used with HMACSHA1). Since an attacker could test only the native size and rule out a password. (Example)

But what if we hash the (complete) result one more time? This would seem to solve the problem. Since without the whole calculation - no part will be known.

Am I correct?

Restating and expanding on what the linked example says: when using PBKDF2-HMAC-H for storing a password hash (salted/peppered) for later comparison, it makes no sense to make PBKDF2's output size parameter $\mathsf{dkLen}$ more than the output size $h$ octets of H (if $h\ge16$ octets or similar threshold), nor more than perhaps $20$ octets, because:

The adversary doing brute force password search will seldom find a match of the first $h$ octets: when having found the right password, or with probability $2^{-8h}$ for random other inputs. The search can thus skip the (independent) computing of the other octets for the overwhelming majority of passwords tested. The extra data past $h$ has a cost for the legitimate user, but almost none (in proportion of total effort) for the attacker. Thus the legitimate user is better lowering $\mathsf{dkLen}$ to $h$ (as long as it remains enough to repel accidental match with the wrong password, which $\mathsf{dkLen}\ge16$ insures well-enough in practice), and should increase the PBKDF2 iteration count instead, which will cost the attacker.
In practice, odds of finding a password other than the genuine one that matches the hash over more than about $20$ octets are impossibly low, and adding more octets adds no useful security from that standpoint.

So there's not really a problem to solve; when using PBKDF2-HMAC-H for storing a password hash (with a common cryptographic hash thus $h\ge16$), we can just use $\min(h,20)$ for $\mathsf{dkLen}$, and pump PBKDF2's iteration count to whatever we can afford for comparable performance in legitimate use. If $\mathsf{dkLen}$ was $l$ octets with $l>h$, we can  multiply the iteration count (thus attack time) by a factor of $\lceil l/h\rceil$ at comparable cost for the legitimate user.

However, yes, it is correct that in an application keeping a password hash for later comparison, re-hashing the result of PBKDF2-HMAC-H with H (or another hash) with $h\ge16$ octets, and truncating to $20$ octets, will similarly shorten the result, and won't harm compared to storing the whole result. Indeed, computing the whole PBKDF2 output is necessary to find the overall hash, forcing an attacker to perform for each password tested all the work a legitimate user does. Security is thus comparable to reducing $\mathsf{dkLen}$.

The only benefit that I can think of in asking for longer output, and hashing it to get the final result, is that the increased complexity will require a slightly more complex code for a brute force password cracker. But that does not even require memory proportional to $\mathsf{dkLen}$ (the final hash can be computed on the fly), thus it will not markedly increase build and operating cost of a password cracker well designed with that oddity in mind.

Note: large $\mathsf{dkLen}$ can still make sense in applications of PBKDF2 other than testing if the password is correct.

Note: contrary to what the quoted remark suggest, it is not mathematically certain that if the first $h$ octets match, the others will; that's just very likely.


Frequency analysis of Vigenere Cipher For Vigenere cipher, I understand

Find period first (say we have p = 6)
Find highest frequency of letter in each group (from 1 to 6) and assume it is "e" in plaintext

What if we have more than one letter with same frequency. For example, "j" and "y" having same frequency in p1 group. Which one should we consider when finding a key?

You should not just "pick the highest frequency character and assume it should be E" because it will probably fail most of the time, except if your ciphertext is really long.

If your alphabet is small enough (usually either 26 or 255), it would be wiser to try all the possibilities for each group, and to check if the output looks like real english (printable chars, correct frequency, etc). It will be almost as fast, and you'll be way more confident in your result.


Key establishment from secret answer to a question using Socialist Millionaire Protocol I have read this as telling that two parties sharing a low-entropy secret (such as a secret answer to a question) can use it to establish a high-entropy shared secret key across a classical insecure channel, with help of the Socialist Millionaire Protocol.

How is that achieved? Quantitatively, what's the probability for a MitM attack to succeed at least once in $n$ attempt?

Or asked differently, but equivalently: How to build a password-authenticated key exchange (PAKE) from a Socialist Millionaire Protocol (SMP)?

I have read this as telling that two parties sharing a low-entropy
  secret (such as a secret answer to a question) can use it to establish
  a high-entropy shared secret key across a classical insecure channel,
  with help of the Socialist Millionaire Protocol.

First, I think this isn't usually done, because SMP protocols tend to be not faster than key exchanges and because you can build an SMP protocol out of a password-authenticated key exchange (PAKE) by simply afterwards comparing whether the resulting keys are equal (eg by using them for a symmetric transport layer and sending a pre-agreed value both directions).

  Quantitatively, what's the probability for a MitM attack to succeed at
  least once in $n$ attempt?

I would suppose any such protocol enjoys similar security properties to your standard PAKE protocol, that is, if you break into one of the parties it's game over, but you don't learn anything about the password from the transcript and you can only test one guess for the password per connection attempt. So if the process of picking the password has entropy $E$, your chance of getting it right (per online connection attempt) should be $2^{-E}$.

  How is that achieved?

One protocol, I just came up with goes as follows:

Run un-authenticated Diffie-Hellman between the two parties $A$ and $B$ to get the shared secrets $m_A,m_B$. Note that if there is an active MitM attacker $m_A\neq m_B$.
Let $p$ be the password the two parties share. Formulate $\langle p,m_A\rangle$ and $\langle p,m_B\rangle$, e.g. as $\langle x,y\rangle=\operatorname{HMAC-SHA256}_y(x)$, i.e. pair them up somehow, so that the result of $\langle\cdot,\cdot\rangle$ may only be learned by somebody knowing both inputs.
Run a SMP protocol between $A$ and $B$ and have them compare $\langle p,m_B\rangle$ and $\langle p,m_A\rangle$ for equality. If the result is 1, output $m_A=m_B=m$ as the shared secret, if the result is $0$, output $\perp$, that is an error.

The idea is that attacks on DH result in both parties seeing different shared secrets which the SMP protocol should unveil while at the same time ensuring that if the parties actually arrive at the same DH secret, they also both know the same password and are thus authenticated by knowledge of the password.

Of course the above does not constitute a formal security analysis and thus this (inefficient) protocol should not be used without prior formal protocol analysis in production!


Question about Enigmas involutional property and its reduction of possible ciphers I'm currently learning cryptography at a university. I can't wrap my mind around how the involutional property of Engima reduces its possible ciphers while being poly-alphabetic. Can someone please explain this?

The German Wikipedia link says that if the plaintext is ABCD, then the ciphertext CADB is impossible.

We're looking at all possible permutations of ABCD and apparently the only possible permutations are:

BADC
CDAB
DCBA

The number of involutions of size $n$ satisifies the recurrence relation:

$$I(n) = I(n-1) + (n-2)I(n-2)$$

(This recurrence is easy to deduce).

Given than $I(1) = 1$ and $I(2) = 2$, we can easily compute $I(4) = 8$, which is strictly smaller than the number of permutations of size 4 (which is 24).

This recurrence allows us to quickly compute the number of involutions of size 26 as 158,432,124,870,784; much smaller than the number of permutations 26! = 604,937,191,689,908,372,404,961,280

BTW: the involutions of size 4 are:

$$ABCD$$

$$ABDC$$

$$ACBD$$

$$ADCB$$

$$BACD$$

$$BADC$$

$$CBAD$$

$$CDAB$$

$$DBCA$$

$$DCBA$$


Can a key exchange protocol exchange a one time pad instead of a key? As I understand key exchange, two parties can agree on a fixed number of secret bits in the presence of a listening adversary.  That set of bits forms a cryptographic key which is then used to encrypt data using a standard cryptographic algorithm.  And that key is repetitively used over and over, perhaps for an AES session.

What if instead of a key for cryptographic algorithms, a one time key was exchanged for use with a one time pad construct? My system would then exchange another pad for the next message.  Could you realistically securely exchange 1280 bits /160 bytes for a Twitter length message?

Note.  A true random number generator is available.

EDIT.  From initial comments, it seems that the security of the OTP key would be contingent on the security of the key exchange mechanism, say Diffie-Hellman, RSA or similar.  So I guess a fundamental part of my cunning scheme would be the ability to use a key exchange mechanism that provided > (160*8) bits of security.  Wouldn't that then mean  the security proof of the OTP was still maintained?  This is a theoretical exercise, so performance is not a consideration (unless we're talking of geological timescales that make it de facto impossible). Could it be done for example as one message per 24 hrs using a modern desktop machine?  An SOE agent might only send one message per week in WW2.  Just some temporal context.

In theory it could work, if you can ensure that the resulting key is actually generated uniformly from the full range, as long as one party chooses its input uniformly.

A rough sketch for a proof: Consider the inputs $x$ and $y$ to the key exchange $f(x,y)$. Then if you consider one input fixed the key exchange has to be a bijection. You need to proof that for every $x$, $f$ is a bijection between $y$ and $f(x,y)$.

But on the practical side, I can't think of any realization of this, where we can actually prove that. The obvious candidate is the DH key exchange. But if we use a generator $g$ for the full group, then we can't prove the above property: Assuming any fixed $x$, then $g^{xy}$ is not always a bijection, there is the counter example $x = 2$. If $g$ is a generator of a prime order group, then this property would hold. However, in this case you can only reach the elements of this particular subgroup and not all group elements. You would need a bijective mapping from the subgroup with $k$ elements to $\{0,1,\dots,k-1\}$ or similar. And that should be difficult, unless you assume you are able to calculate the DLOG. And this problem exists for both classical and EC-based Diffie-Hellman key exchange.


Why does entropy halve during its extraction? It is common to use cryptographic hash functions to extract randomness from entropy sources.  One of the quantitative criteria for this is that if 2n bits of entropy are put through a hash, n bits of uniformly distributed random numbers can be extracted.

Why is this?  Where do the other n bits of entropy go?  Perhaps naively, but if we adopt a water analogy, why can we only get 1 litre of water entropy out of a store that we've put 2 litres into?  Is it possible to explain this without complex algebra?  It seems counter intuitive that we can't get all the entropy out that was put into the hash function.

The scenario  that vexes me is what if we chained hash functions for the hell of it.  One cryptographic hash feeding the next.  If we start at the top of the pile and input 16 bits of entropy, the available entropy would half passing through each hash.  After passing through 5 hash functions, there would be <1 bit of entropy left.  I can't fathom how that could be.

I can't find the original reference to n 2n, but there are many instances of this formula scattered throughout the literature.  BUT.  I have a counter example where this is not the case.  The Quantis TRNG manages to output 75% of available entropy via matrix multiplication.  And I think that I've seen this technique used in other TRNGs.  It's simple compression of the raw entropy stream.  Both hash functions and matrix multiplication is essentially similar, so what's going on?

I'm sure that somebody can give a better answer, but I can at least point the HKDF paper as containing some references that you might want to chase.  See, e.g., Section 2, "Statistical and Computational Extractors," p. 5:

  Efficient constructions of generic (hence randomized) statistical extractors exist such as those built on the basis of universal hash functions [15]. However, in spite of their simplicity, combinatorial and algebraic constructions present significant limitations for their practical use in generic KDF applications. For example, statistical extractors require a significant difference (called the gap) between the min-entropy $m$ of the source and the required number $m'$ of extracted bits (in particular, no statistical extractor can achieve a statistical distance, on arbitrary sources, better than $2^{−{m−m'\over 2}}$ [60, 63]). That is, one can use statistical extractors (with its provable properties) only when the min-entropy of the source is significantly higher than the length of output.

See also Section 5, "Random Oracles as Computational Extractors," pp. 11-12:

  We note that random functions do not make by themselves good statistical extractors (here the key to the extractor is the description of the function itself). For example, if $\chi$ is the uniform distribution over $\{0, 1\}^{2k}$ (thus having min-entropy $2k$) and we choose a random function $f$ from $2k$ to $k$ bits, we expect $1/e^2$ of the points in $\{0, 1\}^k$ not to be in the image of $f$ (i.e., they are assigned probability 0 regardless of the sample from $\chi$), thus inducing an output distribution that is statistically far from uniform.  Furthermore, the lower bounds on min-entropy gap from [60] mentioned in Section 2 apply to random functions as well.

So the short answer is: because of established theorems about randomness extractors.


Shor's algorithm for discrete log and periodic function I am wondering about the following well-known problem:
Let $p$ is a prime number, $g$ is a generator of $(\mathbb{Z}/p\mathbb{Z})^\times$, $b \in (\mathbb{Z}/p\mathbb{Z})^\times$. Find $x$ - an integer such that $g^x = b \mod p$.
When I read about Shor algorithm for discrete log problem I always see the following function
$$ f(x_1, x_2) = b^{x_1} a^{x_2} \mod p$$ and the task is to find the period of the function, i.e. $(\omega_1, \omega_2)$ such that
$$ f(x_1, x_2) = f(x_1 + \omega_1, x_2 + \omega_2) $$.
My question is the following: why do we consider the complex function and don't consider the simplest one:
$$ f(x_1) = b^{x_1} \mod p$$
If we can find the period of the function $\omega_1 < p - 1$ then
$$g^{x \omega_1} = 1 \mod p$$
Thus from small Fermat theorem we have
$$ x \omega_1 = 0 \mod p-1 $$
That can give the discrete log problem solution

Knowing the period of the second function cannot help you, because you already know it (at least for common Diffie-Hellman setups)!

First note that the period $\omega$ of $f(x_1)=b^{x_1}\bmod p$ is the order of $b$ because $f(0+\omega)=f(0)=1$ is implied by the general definition of a period $\forall x\in\mathbb Z:f(x)=f(x+\omega)$.

Now assume that $p$ is a safe prime (as is common for Diffie-Hellman). By Lagrange's theorem, we know that all multiplicative subgroups must have order $1,2,p-1$ or $\frac{p-1}{2}$ (the only divisors of $p-1$ by construction of $p$). Note that all these 4 values are trivially publicly computable.

Now notice that $f(x)$ generates a multiplicative subgroup of $\mathbb Z^*_p$ (similarly to how the generator works in DH). So this subgroup must have one of the 4 possible orders from above, which we already know. So we have learned nothing new by finding the order of the public key.


LFSR Jump Ahead Algorithm A related question has been asked and answered here.  My question is specifically about figuring out C for very large J.  I have searched the web and found many scholarly articles on "jump ahead" and how to efficiently do so, but I am looking for a more "layman's" algorithm.

Here is the background information.  I am working through understanding the areas of weakness in using LFSR in cryptography.  To proof the concept, I have an encrypted message from a stream cipher using an N-bit LFSR.  The plain-text is ASCII, so I know the plain-text bits recurring at a specific interval (8), call it m.  From that, I get a set of non-consecutive key bits.  I have used the Berlekamp-Massey on the first 128 such bits at index multiples of m, then used the resulting coefficients and the first 64 bits passed to BM to initialize an LFSR.  I've run through the rest of the message proving to myself that the bits at multiple m are all predictable.

Now I would like to prove the remaining piece to myself, namely to get back the LFSR coefficients for the message, with only having a subset of the key bits and an associated LFSR for those bits.  In the question I made reference to, I am stuck trying to figure out $b_i=c_{(i\,m^{-1}\bmod p)}$.  In other words, $c_{(i\,m^{-1}\bmod p)}$ is a hugh jump forward with the LFSR, too large to just step to that point in the state.  As, I said, I found articles that discuss LFSR "jump ahead", but I think I need something more explicit on the approach.

For instance, a simple method (and slow), is to precompute the matrix power $A := F^J$(A Fast Jump Ahead Algorithm for Linear Recurrences in a Polynomial Space).  But I find no information on how to create the matrix $A$ from the coefficients.  To prove the concept, I don't need a fast algorithm, just something I can apply to close the loop.

An algorithm (Python, C, Java, et al), or implementation would be most helpful.  But even an article that give more complete details on the approach could serve the purpose.  Can you recommend something?

Here is a specific example using Fibonacci mode to establish conventions:

Coeffients: 1111100000010100101010001111110101111100110010110011101111001001
State:      0000111101011011011000011101100111001010000011001001100100011110
Output:     000011110101101101100001110110011100101000001100100110010001111010110011001100101111011110110001010001001110010011101010110101001001110000000101111110001001110001000010100111110111001001100001111001010011110110110010010110010001101000100001111101110011101100011001110100010111101111010101101001001000011100011001010110100010001111011110000110010100000000011100011111011110011111100110010110001100011101001111010101101101100010100110110110100000100011111001011111001111000010011011101000111110111101001111001101011101101001111110001111011111100100101010011000101011001010111001001001..

Shortened; see here for the origin.

Galois LFSR

In a Galois LFSR with polynomial $P$ of degree $n$, the state is a vector of $n$ bits assimilated to the binary coefficients of terms of degree $n-1$ to $0$ of a polynomial; we note both the state and its polynomial $S_j$ when at step $j\ge0$ .

The next state is computed as $S_{j+1}=S_j\,x\bmod P$. Equivalently, the state is shifted towards the high-order coefficient, which is output and dropped from the state; a 0 is introduced as the low-order coefficient; then if the output was 1, state bits at indexes corresponding to non-zero terms of $P$ (ignoring the high-order term $x^n$) are complemented.

It follows that in a Galois LFSR,
$$S_j=S_0\,x^j\bmod P$$
which allows efficient direct access. Polynomial modular exponentiation can uses the same methods as integer one except using carry-less arithmetic, with the simple algorithm having cost $O(\log(j)\,n^2)$.

Also, the output of the Galois LFSR in $j$ steps is the coefficients of the quotient $Q$ of the polynomial division of $S_0\,x^j$ by $P$, starting from the coefficient of degree $j-1$ for the first output bit, down to zero for the $j^\text{th}$; and it holds $P\,Q+S_j=S_0\,x^j$.

Fibonacci LFSR

The question uses a Fibonacci LFSR, as apparent by having the state at the beginning of the output. Afterwards, the next output bit is the parity of the bitwise-AND of the $n$ previous bits and the coefficients defining the polynomial. I'll use the convention that the previously produced bit is ANDed with the coefficient of degree $n-1$ of the polynomial. With that convention, the low-order (constant) coefficient of the polynomial is the leftmost bit of the question's Coeffients, and the polynomial $P$ is $1+x+x^2+x^3+x^4+x^{11}+x^{13}+x^{16}+\dots+x^{55}+x^{56}+x^{57}+x^{60}+x^{63}+x^{64}$
with the term $x^{64}$ not shown in the question (and never combined with anything by bitwise-AND when stepping the LFSR).

Caution: standard literature on Fibonacci LFSRs and Berlekamp-Massey often use the so-called reflected or reciprocal polynomial, where coefficients of order $i$ and $n-i$ are exchanged (which might change the order of the polynomial). The present answer does not use this form for the polynomial.

Without proof: with our convention, when the low-order coefficient of the polynomial is $1$ (as customary in Berlekamp-Massey), Galois and Fibonacci LFSRs using the same polynomial produce identical output sequences, only from different starting point and with different states (when the lowest-order non-zero coefficient of the polynomial has order $l>0$, the Fibonacci LFSRs reaches the same periodic sequence as the Galois LFSR after $l$ steps at most, when the Galois LFSR always enters that periodic sequence right from the start; we have the option of removing the first $l$ bits and reducing the polynomial's degree to $n-l$, so that the low-order coefficient of the polynomial becomes 1$).

We can always convert a Galois state to Finnonacci state yielding the same output by stepping the Galois LFSR $n$ times; its output (in chronological order) is the desired Fibonacci state (produced by increasing order of the corresponding bits in the polynomial, that is reflected compared to $Q$ obtained by polynomial division of $S_0\,x^n$ by $P$, by exchanging coefficients of order $i$ and $n-1-i$); that's because the Fibonacci LFSR first outputs its state (starting frow low-order, in our convention).

By the same reasoning, when the low-order coefficient of the polynomial is $1$, the Galois state $S_0$ corresponding to a certain Fibonacci state must be such that the corresponding output $Q_0$ of the Galois LFSR in the next $n$ bits is the Fibonacci state (produced by increasing order of the corresponding bits in the polynomial). It thus holds that $P\,Q_0+S_n=S_0\,x^n$. It follows that the coefficients of the Galois state $S_0$ from $n-1$ to $0$ are the coefficients of $P\,Q_0$ from $2n-1$ to $n$, where $Q_0$ is the Fibonacci state reflected by exchanging coefficients of order $i$ and $n-1-i$.

When the low-order coefficient of the polynomial is $1$, to compute the state of a Fibonacci LFSR after $j$ steps, we can thus convert its state to Galois form, fast-forward that, and convert back.

With $\widetilde{F_j}$ the Fibonacci state at step $j$ with reflection by exchanging terms $i$ and $n-1-i$, and $\lfloor U/V\rfloor$ the quotient of the polynomial division of $U$ by $V$
$$\widetilde{F_j}=\left\lfloor{\left(\left\lfloor{\widetilde{F_0}\;P}/{x^n}\right\rfloor\,x^j\bmod P\right)x^n}/P\right\rfloor$$

In more details:

Reflect the Fibonacci initial state, yielding $Q_0=\widetilde{F_0}$ (where the first outputs $0$ to $n-1$ are the terms of order $n-1$ to $0$);
Compute $P\,Q_0$ and keep bits of order $2n-1$ to $n$, yielding $S_0$ from order $n-1$ to $0$;
Compute $S_j=S_0\,x^j\bmod P$;
Compute the quotient $Q_j$ of the polynomial division of $S_j\,x^n$ by $P$;
Reflect $Q_j$ to compute the Fibonacci state $F_j$ after $j$ steps (which from order $0$ to $n-1$ is also outputs $j$ to $j+n-1$).

Note: Steps 4. and 5. are equivalent to stepping the Galois LFSR $n$ times starting from $S_j$, forming the Fibonacci state from order $0$ to $n-1$ (left to right in the question).

An alternative matrix method considers the transformation resulting from stepping the LFSR (Fibonacci or Galois) as multiplication of a (sparse) matrix. That matrix can be raised to the $j^\text{th}$ to obtain the matrix corresponding to stepping $j$ times, but the matrix is no longer sparse, and (using schoolbook matrix multiplication algorithms) the time grows $O(\log(j)\,n^3)$ rather than $O(\log(j)\,n^2)$, with space $O(n^2)$ rather than $O(n)$.

Here is hopefully C99-conforming code specialized for $n=64$ and Fibonacci form, heavily optimized for speed. Notably, the code:

Processes in parallel over 64-bit and uses no table, which I guesstimate saves like a factor of 100 in speed compared to bit-by-bit on a 64-bit CPU, on top of having a cost growing with $j$ as $O(\log(j))$.
Is branch-predictor friendly (the only test in inner loops is their end condition); this is obtained by masking rather than testing, often extending a low-order bit to 64-bit using negation: -(uint64_t)1 is 0xFFFFFFFFFFFFFFFF while -(uint64_t)0 is 0x0000000000000000, and that's standard-conformant.
Off-topic rant: If you are a compiler writer in certain large company, please make it unnecessary to use a workaround; no I won't bow to a\&(0-b) when a\&-b is more recognizable.
Stores the low-order coefficient of the polynomial $P$ in the high-order bit of variable $p$: that's a common implementation technique for Galois LFSRs, and eases conversion from bits in the order of the question to integer.

The code first performs the computation of $x^j$ in step 3, by binary exponentiation scanning $j$ from right to left (the low-order 6 bits are optimized out because $x^j$ requires a single shift for $j<2^6$); then steps 1 and 2 (the initial reflection reduces to scanning bits of $s$ in the appropriate order); then the rest of 3; then steps 4 and 5 are handled by stepping the Galois LFSR (the final reflection reduces to accumulating the result in the appropriate order).

I wanted to fit the function's code including comments in the ≈25 lines requiring no scrolling, so I (ab)used the C syntax, like using multiple operators , and separators ; on the same line.

// fffibo64:  Fast-Forward a 64-bit Fibonacci LFSR
//  Inputs:
//   p  The polynomial, of degree 64; high-order bit of p is the poly's
//      constant term, and must be 1; coefficient x^^64 is implicit
//   s  Initial Fibonacci state (that is outputs 0 to 63 starting at high-order)
//   j  Number of steps
// Output: Fibonacci state after j steps (that is outputs j to j+63 starting high-order)
#include <stdint.h>
#ifdef _MSC_VER                     // this vendor has its own views on C, workaround that
#pragma warning (push)
#pragma warning (disable : 4146)    // avoids "unary minus operator applied to unsigned type"
#endif
uint64_t fffibo64(uint64_t p, uint64_t s, uint64_t j) {
    uint64_t u,v,w,x;               // workhorse temporaries
    // compute x^^j mod p into x, with optimization for low-order 6 bits
    x=((uint64_t)1<<63)>>(j&63);    // takes care of the low-order 6 bits of j
    if((j>>=6)!=0)
        for(v=p;;) {                // for remaining bits of j, if any
            if ((j&1)!=0)           // perform x = x*v mod p
                for(u=x, x&=-((w=v)>>63); w+=w; x^=(u=(p&-(u&1))^(u>>1))&-(w>>63));
            if ((j>>=1)==0) break;  // we have handled all bits of j
            // perform v = v*v mod p
            for(v&=-((u=w=v)>>63); w+=w; v^=(u=(p&-(u&1))^(u>>1))&-(w>>63));
            }
    // perform p*reflected(s) and keep coefficients 127 to 64 of that into v
    for(w=(p+p)|1, v=0; v^=w&-(s>>63), w+=w; s+=s);
    // perform u = v*x  mod p
    for(u=v&-(x>>63); x+=x; u^=(v=(p&-(v&1))^(v>>1))&-(x>>63));
    // here u is the Galois state after j steps; step it into x, reflecting
    for(w=64, x=0; x+=x+(v=u&1), u=(p&-v)^(u>>1), --w;);
    return x;
    }
#ifdef _MSC_VER
#pragma warning (pop)
#endif

// demo of the above, producing the output stream bit by bit both sequentialy, and with
// direct access, with (hopefully) identical result.
#include <stdio.h>
int main(void) {
    uint64_t j,
        p=0xf814a8fd7ccb3bc9,   // 1111100000010100101010001111110101111100110010110011101111001001
        s=0x0f5b61d9ca0c991e,   // 0000111101011011011000011101100111001010000011001001100100011110
        t=s,x;
    for(j=0; j<800; ++j) {
        printf("%d", (int)(t>>63));
        // evolve the state t step by step
        x=p&t; x^=x>>32; x^=x>>16; x^=x>>8; x^=x>>4; x^=x>>2; x^=x>>1; t=(t+t)|(x&1);
    }
    printf("\n");
    // same sequence with direct access
    for(j=0; j<800; ++j) printf("%d", (int)(fffibo64(p,s,j)>>63));
    printf("\n");
    return 0;
}

Try it online!


Is there a companion algorithm for OTP to ensure integrity and/or authentication? One-Time Padding is (theoretically) perfect encryption algorithm. Let's assume that these problems are solved:

Fast generation of independent and identically distributed random variables
Perfect key distribution system
Key only used once.
Key destroyed after use, without side channels that would allow any non-trusted third party to attain any key bits.

However, for modern information exchange, it is not sufficient to encrypt information (this is against Eve). In addition to encryption, it is necessary to also protect

integrity (this is against broken phone or cable) and
message authenticity (this is against Mallory).

Some recommendations in cryptography recommend to use security level similar for encryption keys and message authenticity keys (i.e. use 128-bit encryption key and 128-bit MAC key). For MAC tag, it is common convention for HMAC or to use at most half of the MAC key length as the output length. Some other algorithms use full block length of the function.

For information theoretic authentication tag security, I would expect that in order to transfer message with length $N$ bits, I would need at least another $N$ bits to transfer "authentication tag" matching with the message.

Choices for Integrity or Authentication

Here are some of example schemes:

Double the bits. I.e. when instead of 0110, process plaintext 00111100 with OTP. This'll eat twice as much key material than OTP, but will protect against any single bit errors, and many of other errors, because it is easy to check at the recipient. (If only worrying about integrity.)
Process concatenation of $P$ (plaintext) and $T$ (mac tag) via OTP. There is problem how to calculate $T$. My first idea would be to use some operation on binary Galois Fields $GF(2^n)$, such as multiplication $C * C$ and use OTP to send that "checksum". (Only for integrity, but detects integrity problems with larger probability than option 1.)

Any suggestions how to efficiently calculate $T$?
Are there any schemes which would provide usual security without key length $K=2N$?
Are some of preconditions incorrect?

For authenticity it would appear that these are valid options:

3. encrypt-then-mac with an information-theoretically secure mac.

4. mac-then-encrypt with an information-theoretically secure mac.

What would be suitable information-theoretically secure mac for implementing alternative 3?
Alternative 4 uses more key material than alternative 3. Are there any situations where alternative 4 would be profitable over alternative 3?

Previous Questions About The Field

You could think of this question as sort of add-on question to:
"Having 4096 bit keys and short (< 256 byte) messages, can I simply use the key as OTP?"

You can construct a one-time MAC that has similar properties to the OTP. Better still, it uses a fixed number of bits for each message.

Here's how it works. Choose the closest prime to your message block size. Let's say you plan to process 128-bit chunks of your message. Let's say there are $L$ such blocks.

The first job is to pick the first prime larger than $2^{128}$ which is $2^{128}+51$. Call this value $q$.

The key has two pieces. Let's call these $x$ and $y$ and choose these at random from the range $1$ to $q-1$.

Your MAC is then:

$mac(m, x, y) = m_L\times x^L + m_{L-1} \times x^{L-1} + ... + m_{1} \times x + y \mod q $

You basically evaluate a polynomial with a term for each block of the message. The co-efficient is the message block and this is multiplied by the key raised to the power of the current block number. All operations are done mod $q$.

Provided $x$ and $y$ and are used precisely once, this MAC is secure against all adversaries.


Expected entropy in $P(x)\oplus x$ for random $x$, where $P$ is a random permutation Let $P$ be a random permutation of $n>1$ bits. Let $F$ be the function on the same domain $\{0,1\}^n$, defined by $F(x)=P(x)\oplus x$. When $P$ is a block cipher with key a message block, that's the Davies-Meyer construction of a one-way compression function, a variant of which being used in MD5, SHA-1, and SHA-2.

Let $H_F$ be the entropy (in bits) of the source $F(x)$ where $x$ is a vector of $n$ random unbiased independent bits. That is
$$\begin{align*}
H_F&=\sum_{y\in F(\{0,1\}^n)}-\Pr(F(x)=y)\cdot\log_2\big(\Pr(F(x)=y)\big)\\
\\
& = n-{1\over2^n}\cdot\sum_{y\in F(\{0,1\}^n)}\big(\#{\{x, F(x)=y)\}}\big)\cdot\log_2\big(\#{\{x, F(x)=y)\}}\big)
\\
& = n-{1\over2^n}\cdot\sum_{2\le\,j\,\le2^n}\big(\#{\{y,(\#\{x:F(x)=y\})=j\}}\big)\cdot j\cdot\log_2(j)
\end{align*}$$
Note: $\#{\{x, F(x)=y)\}}$ of the 2nd equation is the number of preimages of vector $y$; and $\#{\{y,(\#\{x:F(x)=y\})=j\}}$ of the 3rd is the number of vectors with exactly $j$ preimages.

$H_F$ can be from $0$ (when $P$ happens to be XOR with some constant) to $n$ bits (when $F$ happens to be a permutation, e.g. for $P:$ $00\to00$, $01\to10$, $10\to11$, $11\to01$ ).

Let $H(n)$ be the expected value of $H_F$; that is, the average of $H_F$ over all $(2^n)!$ permutations $P$. A plausible conjecture is that
$$\lim_{n\to\infty}{H(n)\over n}=1$$
How to prove this, and what's a first order approximation of $n-H(n)$ for large $n$?

If $F$ was a random function, we'd have $n-H(n)\approx0.8272\dots$ starting with moderate $n$ according to my analysis there. But I fail to rigorously derive that for the much narrower class of $F$ in the question.

All functions (including permutations) mapping a finite field $\mathbb{F}_q$ to itself can be uniquely represented by polynomials (via Lagrange Interpolation, possibly followed by reduction modulo $x^{q}-x.$ When $q=2^n,$ the linear permutations $F(x)=x+a,$ for $a\neq 0,$are exactly the type of polynomial that give zero entropy in your formulation since $F(x)+x=a$ a constant.

Focusing only on $q=2^n$ due to crypto applications, we don't know explicit representation of many other permutations but some include certain monomials $F(x)=x^{e}$ with special conditions on exponent $e,$ as well as families such as Dickson's polynomials, which don't have an $x$ term in their polynomial and won't suffer the weakness of zero entropy for $F(x)+x$. As for computing what fraction of overall permutation polynomials have an $x$ in their polynomial expression, it's likely to be a difficult problem.

Edit: The below is redundant, due to your comment, the above is still relevant but I can take it to a comment if requested, it's a bit long.

If we model the map $F(x)=P(x)+x$ by a random mapping instead of a random permutation from $A=\{0,1\}^n$ to itself, then the number of points $y$ in $A$ that have no preimages, i.e., there is no $x\in A$ with $f(x)=y,$ is on average equal to $e^{-1}\#A=\frac{2^n}{e}.$

This would mean that the expected size of the range of $F$ is $$\mathbb{E}[F(A)]=(1-e^{-1}) 2^n\approx 0.6321 \cdot 2^n$$ yielding $$H(n)\approx n+\log_2(0.6321)= n-0.66172,$$
so as you predicted the  $\lim_{n\rightarrow \infty}H(n)/n=1.$

References for this type of argument include Sedgewick and Flajolet's book An Introduction to the Analysis of Algorithms, and the paper "Random Mapping Statistics" by Flajolet and Odlyzko in Eurocrypt'89, but a very readable account is in Chapter 5 of Riordan's classic book An Introduction to Combinatorial Analysis, from 1958.


Is it ever OK to to sign RSA messages with padding random bytes? If a message is padded with cryptographically secure random bytes, is there any reason why this would be less secure than the standard signature padding schemes (PKCS1 v1.5 and PSS)? To give context to the meaning of the word "secure," I would note that my only intention is to prevent others from being able to forge the message signature.

The correctness of the padding should be verifiable from the hash of the message - that is, given the hash of the message, the same padding should be reproducible. Otherwise, "existential forgery" would be possible.
So what is "existential forgery"?
Basically, you just produce a random string of bytes as your signature. When it's interpreted as an integer and raised to e'th power mod n, the lower 256/384/512 bits will be as valid a hash value as any other, so even though we don't know what message produces such hash value, we've found one that exists, hence "existential forgery".
To actually make the attack work requires some extra effort, including but not limited to:

mounting collision attack on the hash function against the verification exponent with many random messages.

for small modulus, GNFS may yield results with part of lower-order bits matching the candidate message digests.

As noted by @fgrieu in the comment, the question asks a hypothetical situation that cannot be universally applied, thereby making it a false proposition.


Why have Nonce and why encrypt everything in step 2 for Needham-Schroeder? Here is the protocol outline I am looking at (source: Foundations of Computer Security, Lecture 60: The Needham-Schroeder Protocol)

  $$
\begin{array}{ccl}
   1.& A \to S \colon& A,B,N_a
\\ 2.& S \to A \colon&
              \left\{ N_a,B,K_{ab},\{K_{ab},A\}_{K_{bs}} \right\}_{K_{as}}
\\ 3.& A \to B \colon&
              \{K_{ab},A\}_{K_{bs}}
\\ 4.& B \to A \colon&
              \{N_{b}\}_{K_{ab}}
\\ 5.& A \to B \colon&
              \{N_{b}-1\}_{K_{ab}}
\end{array}
$$
  Where $N_a,N_b$ are nonces.

My questions are:

Why do we need nonce $N_a$ in step 1?
Why do we encrypt everything in step 2? Surely $S$ could instead send message to $A$ like $K_{as}\{K_{ab}\} || K_{bs}\{K_{ab}\}$?
Why $S$ can't send $K_{ab}$ to $B$?

As Marcin already said, nonces are for replay protection. Imagine an attacker records message 2 and later on manages to comprimise the old key. He could then impersonate $ S $ and make $ A$ and $ B $ reuse the old key by sending the recorded message to $ A $.
To prevent this, the nonce is included. $ A $ remembers previously received nonces and does not accept messages if an already known nonce is included. If the attacker now tries to resend the old message again, he would fail.

Regarding the second point, I guess you want to ask if double encryption is necessary? If so, you forgot to include the IDs and the nonce :) Kerberos v4 used the same aporoach and was often critized for double encrypting the ticket to $ B $. In v5 they changed that and did your approach, so yes it is possible.
Without the IDs it is not possible though, $ A $ wouldn' t know to whom the ticket has to be delivered.

Regarding the last point, of course the key has to be encrypted. If we assume $ S$ has a shared key with  $ B $ too, this wouldn't be a problem however.
The main reason why $ S $ forwards the ticket to Alice and not to Bob is scalability I guess. $ S $ is a central component and thus reducing the number of message exchanges it has to initiate is probably a good thing.


RSA padding confusion attacks Server A produces signed messages on request.  You can tell server A what type of RSA padding to use in the signature (either RSASSA-PKCS1v1_5 or RSASSA-PSS).  Either way, the message will be signed using the same private key.  The signed message is a JSON object where you can supply some of the fields, but the server supplies the others.

Server B accepts these signed messages and verifies the signature using server A's public key.  You have the ability to select which padding scheme that server B should use to perform the verification (again, either RSASSA-PKCS1v1_5 or RSASSA-PSS).

Is it possible to abuse the ability to switch between padding schemes in order to tamper with the message?  Is it possible to cause server B to misread fields in the JSON object that were supposed to be supplied by server A?

The security proof of RSASSA-PSS assumes that the private key is used only for RSASSA-PSS purposes, that hypothesis is violated, thus the security proof does not hold (but as long as RSASSA-PKCS1v1_5 remains usable, you do not have a security proof anyway).

Similarly, the wide consensus that RSASSA-PKCS1v1_5 is secure in practice was formulated without taking into account the use of the same key for another purpose, so you are left without a wide consensus.

That said, some deployed systems use the same RSA key for different purposes, and I know no example of ensuing disaster as long as the padding schemes are very different, and each is secure (an example is the European Digital Tachograph, which uses the same RSA key for RSASSA-PKCS1v1_5 signature, and a custom authentication and key agreement protocol using ISO/IEC 9796-2 (scheme 1) signature padding; it was rubber-stamped to ITSEC level E3, and no attack emerged). The situation is similar to using the same key for HMAC-MD5 and HMAC-SHA1: that's theoretically undesirable, but the only clear consequence is that the weaker of the two systems caps the security.

I find improbable that a feasible cryptographic attack exists based only on the option to tell A and B to use RSASSA-PKCS1v1_5 or RSASSA-PSS, because these padding schemes are different enough. What I find much more probable is that an exploitable bug creeps in the specification or implementation, and the increased complexity due to the option increases that risk.


Stream cipher with Diffie-Hellman and Cryptographic Hash Function? I know: Never do your own crypto. But this question is just theoretical.

Assume you do a Diffie-Hellman Key Exchange with a server to produce a shared secret $x$. Then use a cryptographic hash function like SHA3 to generate a pseudorandom bitstream like this:

$$p_i = \operatorname{SHA3}(x||p_{i-1}).$$

To encrypt $i$th packet of data, labelled $m_i$, compute

$$c_i = m_i \oplus p_i.$$

I realize that the key stream for a OTP must be completely random to ensure perfect secrecy, but would this scheme at least be as hard to break as the underlying hash function or Diffie-Hellman?

In my opinion, it should be, but I'm new to cryptography.

Since the shared secret is only used for one session, assuming the hash function is a random oracle, no keystream is ever used twice. By including $x$ in every $p_i$ an attacker has to break (not only find a collision) the first sent packet in order to decrypt the rest of the session, breaking any other packet will most likely be a collision and not give away the needed $x$, only the content of this packet. Also, breaking any packet requires at least plaintext knowledge but it gives you only this particular hash, not the previous/next hashes.

Since the shared secret is only used for one session, assuming the hash function is a random oracle, no keystream is ever used twice.

This construction, like all stream ciphers, will cycle and produce the same key stream.

All that has to happen is $p_i$ has to equal any of the previously observed output blocks and we'll have a cycle.

If the hash is $n$-bits wide then we can expect this to occur after approximately $2^{n/2}$ blocks by the birthday paradox. The precise size of the cycle will vary from key to key.

This is kind of a problem. Some keys could have much smaller cycles than others. At its extreme, SHA-3 could have a fixed point where by SHA-3(x) = x. The cycle length would thus be one if we were unlucky enough to hit upon this value. Note that fixed points like this can absolutely occur under the random oracle model, although it is rather unlikely.

You can fix this by introducing a counter in to your state update function. Each input to the hash would be unique.

Under the random oracle model, the oracle would choose an $n$-bit hash output uniformly at random for each iteration of the state update function. This is because it never sees the same input message twice; the oracle never gets the chance to return a previously seen state.

In theory, you'd now be back to perfect secrecy. The oracle is now flipping fair coins for each bit of the message, which is analogous to the set-up we see the in the OTP.

This is just an academic point though. Obviously, in reality no hash is a random oracle. The security just reduces to the security of the underlying hash.


Significance of parameter q in NTRU lattice attack In NTRU (N,p,q,d), N is usually chosen to be prime and q be a power of 2. Why is it that if I increase the parameter q, the probability of finding a key or spurious key that can decrypt the message is much higher?
For example, N=127, q=256 will give me an unsuccessful lattice attack but N=127, q=2^16 will give me a successful lattice attack

Basically, the norm of the secret key does not depend on $q$, while the norm of the second minimum of the lattice does, so, when you increase $q$, you increase the gap between the first and the second minima of the lattice, which makes the problem easier.
For instance, if the secret key is composed by two degree-$(N-1)$ polynomials $f$ and $g$ with coefficients in $\{-1, 0, 1\}$, then we have $||(f, g)|| < 2N$.
One basis of the lattice $L$ that we use in attack is
$$
\begin{pmatrix}
I_N & H \\
0   & q\cdot I_N
\end{pmatrix}
\in \mathbb{Z}^{2N\times 2N}
$$
So, it is clear that $\det(L) = q^N$ and $\dim(L) = 2N$.
Then, by the Gaussian Heuristic, we expect the short vectors of $L$ to have norm close to
$\sqrt{N}(\det(L))^{1/\dim(L)} = \sqrt{Nq}$.
Because $(f, g) \in L$ and $||(f, g)||$ is smaller than the value predicted by the Gaussian Heuristic, there is a "gap" in $L$, that is, we expect that
$\lambda_1(L) = ||(f, g)||$ and
$\lambda_2(L) \approx \sqrt{Nq}$.
Now, roughly speaking, if the vector that we recovered is shorter than the second shortest vector, then it has to be the first shortest vector.
So, when we run a lattice basis reduction, if we recover a vector smaller than
$\sqrt{Nq}$, it will already be (a short multiple of) $(f, g)$ and we win.


Why $n=pq$ with $p=2p'+1$ and $q=2q'+1$ instead of just $n=p'q'$ for RSA crypto? For RSA cryptography, we know that the modulo $n$ is a product of two big prime numbers(say $p$ and $q$). However, in some documents I see an extension of $p=2p'+1$ and $q=2q'+1$ with $q'$ and $p'$ being huge prime numbers.

Why is it necessary to have $n=pq$ with $p=2p'+1$ and $q=2q'+1$ instead of just $n=p'q'$ when we know that $p'$ and $q'$ are already prime numbers?

Could you please also provide any documents/resources, if available?

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that:

any small odd $e>2$ (including the common $e=3$ and $e=65537$) is a usable public exponent (because then, $e$ does not divide $p-1$ or $q-1$);
Pollard's $p−1$ factoring algorithm will be ineffective, because it depends on the integer $n$ being factored having a factor $p$ with $p-1$ a smooth integer.

In RSA as usually practiced, it is generally enough to use huge random primes for $p$ and $q$. However, for relatively small modulus it is customary to require that $p-1$, $q-1$, $p+1$, and $q+1$ have one big prime factor, in order to ensure that Pollard's $p−1$ and William's $p+1$ factoring algorithms are less efficient than ECM; that precaution was mandated by ANSI X9.31, and is still in FIPS 186-4 for all $1024$ bit modulus and some prime generation methods; I believe (against the advice of many) that it remains useful when one considers an adversary content with factoring one public modulus among many.

As pointed by DrLecter, RSA-like cryptosystems or protocols using a key similar to RSA may have additional requirements; see his answer.


How to calculate CPA attack complexity in bits manipulation The following Forward Errors Correcting FEC is used in our daily devices. But I added a potential security measure.
In one of FEC systems the input is $K$ bits and the output code is $M$ bits where $M=3K$. The legitimate user at the other end uses FEC decoder to get the correct $K$ bits.
The proposed security is that if only $N$ out of $M$ bits are selected for transmission in the same order of $M$ in a way the receiver still can decode successfully. The number of $N$ bits and there positions in $M$ are generated by pseudorandom number generator with nonlinear structure driven by a key that changes every block of $K$.
The FEC decoder is able to decode only if $N$ and the positions are known so the unselected positions at the sender are filled by $M-N$ bit $0$ before decoding. The attacker does not know the key so $N$ so he won't know $M$ and $K$. In this system $K>500$ bits and the length of PRNG $n=100$.
How we calculate the number of CPA attack possibilities here?

The answer would depend on the entropy of the set of bits $M$. Let's say $M$ is a set of all-zero bits; in that case there would be only $1$ possible set of bits you could choose - every bit in every position is zero. If, however, you had a random set of bits for $M$ you'd approach ideal security; ideal security meaning $m\, P\, (n-(n/2))$ possible keys to brute-force.
How we calculate ideal security:
We know why we use the permutation function, but why use $n-(n/2)$? Let's imagine we have a random set of bytes, each unique; we have less than 256 bytes in our set so we can avoid repeats. The possible unique states would become $\infty$ meaning $m\, P\, (n-(n/\infty))=m\, P\, n$. But if we get each byte twice we end up with half the possible unique sets of choices - for every byte I select I could just as well select another byte and get the same result. As such, for $n$ bits the repeats will be defined by $n / 2$ since there are $2$ unique possible states for each bit. For sets of bytes it would be defined by $n/256$ meaning the complexity would me $m\, P\, (n-(n/256))$. This is because the frequency of repeats is based on the number of possible non-repeating states.
Therefore, if you want the scheme to be secure you should make $M$ as random as possible. A nonrandom value $M$, or a value specifically chosen to be weak would cripple the entire system; if $M$ is all-zeroes that's effectively a base-1 system which means each (bit-like-thing-with-only-one-state) has only $1$ possible state, giving me $m\, P\, (n-(n/1))=m\, P\, 0=1$ possible key.
CPA attack possibilities:
If the attacker can find the value $N$ for 1 block, they now know the position of $n$ bits within $M$. If they repeat this for multiple blocks, they will eventually get enough bits to brute-force the rest; so the difficulty of a CPA comes down to whether the value $N$ can be figured out from the plaintext-ciphertext relationship, which is dependent on the specifics of your FEC. This applies in the same way to known-plaintext attacks. Thus, your system would be secure from chosen-plaintext attacks iff (if and only if) it is secure against known-plaintext attacks.
Update:
I noticed an error where I forget to account for the fact that the repeating bits can themselves be permutated. This lowers the number of possible states significantly. I have updated the formulas accordingly, and the information should be correct now.


Simple protocol for 1-out-of-2 oblivious transfer I'm trying to explain the concept of 1-out-of-2 oblivious transfer to folks who haven't seen this idea before.  I can explain what properties it provides, but it's also helpful if I can show a simple protocol for 1-out-of-2 OT, to give people a feeling that this is achievable.

What's a simple protocol for 1-out-of-2 OT that doesn't need much explanation or advanced cryptography to understand?

I don't need something you'd actually want to use in practice.  It doesn't need to be the most efficient, the most practical, or have a clean security proof: just something that gives the basic idea.  I'm asking only for pedagogical purposes, not to build a real system.  Assume the audience is familiar with basic concepts of cryptography (including things like RSA, Diffie-Hellman, etc.) but may not be familiar with advanced concepts (e.g., zero-knowledge proofs, secure multiparty computation).

There are two that I know of that are pretty simple.

I'll first start with one that requires a "Trusted Initializer" where we assume that there is a party Ted which is trusted by both Alice and Bob and only needs to be present for the initialization stage. This is an extension of a quantum protocol and was proposed by Rivest in Section 7.

Alice holds $m_0,m_1\in\{0,1\}^k$, Bob holds $c\in\{0,1\}$ and wants $m_c$
Ted privately gives Alice $r_0,r_1\in\{0,1\}^k$, chosen at random
Ted generates a private bit $d\in\{0,1\}$ and privately sends $d,r_d$ to Bob
Bob sends $e=c\oplus d$ to Alice
Alice sends $f_0=m_0\oplus r_e$ and $f_1=m_1\oplus r_{1-e}$ to Bob
Bob computes $m_c=f_c\oplus r_d$. About $m_{1-c}$ Bob learns nothing.

The second comes from Wikipedia where it is instantiated with RSA (so exponentiations are done in the RSA group parameterized by the public key).

Alice holds $m_0,m_1$, and an RSA key pair $(e,d,N)$. Bob holds the public key $(e,N)$ of Alice, $c\in\{0,1\}$ and wants $m_c$
Alice generates random $x_0,x_1$ and sends them to Bob
Bob chooses a random $k$, computes $v=x_c + k^e$ and sends $v$ to Alice.
Alice computes $k_0=(v-x_0)^d$ and $k_1=(v-x_1)^d$ and sends $m_0'=m_0+k_0$ and $m_1'=m_1+k_1$ to Bob
Bob computes $m_c=m'_c-k$ and learns nothing about $m_{1-c}$

You'll notice that the two protocols are somewhat similar which is kind of cool if you wanted to present both. The 2nd removes the assumption of a trusted initializer and replaces it with a public key pair for Alice.


Paillier addition with plain text $A$ sends $B$ the encryption $E_{pkA}(m)$.
$B$ computes $R=xE_{pkA}(m) + y$ and sends $R$ back to $A$, but tells him nothing about the parameters $x$ and $y$.
$A$ performs $D_{pkA}(R)$ and recovers the value $xm+y$.

Is this protocol possible using the Paillier cryptosystem?

Yes (assuming $A$ knows the Paillier private key and $B$ knows the Paillier public key and the values of $x$ and $y$)

With Pallier, someone with the public key can:

Homomorpically multiply a ciphertext by a known value; that is, given $x$ and $E_{pkA}(m)$ compute $E_{pkA}(xm)$
Encrypt a known value; that is, given $y$, compute $E_{pkA}(y)$
Homomorphically add two encrypted values; that is, given $E_{pkA}(xm)$ and $E_{pkA}(y)$, compute $R = E_{pkA}(xm + y)$

The resulting $R$ value can be decrypted by $A$; $A$ cannot deduce anything other than the value $xm + y$


R-LWE instantiation with non-power of 2 polynomial In almost all RLWE papers, the polynomials are chosen from a ring $\mathbb{Z}[x]/f(x)$ where $f(x)$ is a polynomial of the form $f(x)=x^{2^n}+1$. That leaves us the choice of polynomials like $x^{256}+1$, $x^{512}+1$ or $x^{1024}+1$ etc. Apart from irreducibility, I understand that using this polynomial has few other advantages like fast polynomial multiplication. One disadvantage of this is that it makes the sizes of keys or ciphertexts or signatures bigger. Just for example in the NewHope key-exchange scheme, their proposed parameter uses a polynomial of degree $1024$ which provides much more than $128$ bit security, whereas the less secure version (JARJAR) uses a polynomial of degree $512$ but provides security less than $128$ bits. Evidently, the former version sends much more data over the wire than the latter one.  But, what if I want to use a polynomial of degree that is between the above two, for example, $768$, it will provide sufficient security and will use a lesser amount of data.

Now my questions are

Can I use cyclotomic polynomial $\phi_{3*768}= x^{768} - x^{384} + 1$ as a modulus?
If yes, does the error distribution change? By what degree? (I understand there are some issues described in this paper (How (Not) to Instantiate Ring-LWE) but it is little difficult for me)

Thank you for your help.

On the IACR eprint archive there is a paper entitled "Even More Practical Key Exchanges for the Internet using Lattice Cryptography" by Singh and Chopra that discusses using other cyclotomic fields which provide the same security guarantees as the power of 2 cyclotomic case.

One reason why these other cyclotomics are not as popular is that the speed of the Nunber Theoretic Transform in these other cyclotomics is not as computationally efficient.  Nevertheless as you point out there is a legitimate tradeoff between parameter sizes and computation.


PBKDF2-SHA256+SHA256 for password storage I recently came across an interesting paper detailing the use of hardened session cookies. Each cookie includes a preimage of the password hash, and the preimage is hashed once more and compared to the stored password hash as part of the cookie authentication process.

In order for this to work, we must be able to quickly compute the password hash from the preimage on each web request. This is not easily possible using plain PBKDF2-SHA256 to store the passwords. However, if we store the passwords as:

$SHA256(PBKDF2(password, salt, iterations=10000))$

we can quickly move from the preimage, $PBKDF2(password,salt,iterations=10000)$, to the stored hash by computing $SHA256(preimage)$.

What are the relative weaknesses here, compared with just storing the PBKDF2-SHA256 digest?

Thanks to @Stephen Touset for the solution.

In order to avoid tying the session cookie to the user's password (and avoid using PBKDF2-SHA256+SHA256), we can simply create a random $key$ for the user upon login. $SHA256(key)$ is then stored in the db, along with a session ID that ties the session to a specific user.

$key$ is then used as the preimage in the session cookie. Upon each request, we calculate $SHA256(key)$, and compare it to the value stored in the db.


CBC first block malleability Let $m_1 = \underbrace{ \{0,1\}^n  \times \cdots \times \{0,1\}^n }_{L\text{ times}}$ be a message of space $\mathcal{M}^L$, where  $\mathcal{M} = \{0,1\}^n$.

Let $c_1$ be the encryption of $m_1$ using CBC mode.

Let $x \in \mathcal{K}$ be some binary string.

Finally, let $m_2$ be another message such that:

$m_2[1] = m_1[1] \oplus x$
$m_2[i] = m_1[i]$ for $i = 2, ... ,n$

How can I modify $c_1$ to be a $c_2$ that is the encryption of $m_2$ ?

I didn't figure out how to modify $c_1$ directly, I could only think about something like $\oplus$ing the Initialization Vector with $x$, so $c_2$ would somehow have both $m[1]$ and $x$ used in its computed first block.

Yes, you can modify the initialization vector to accomplish your goal (as mentioned in the comments, the initialization vector is the first block of the cipher text). So, by computing a new initialization vector, $IV_2 = IV_1 \oplus x$, the cipertext/IV pair $(c_1, IV_2)$ is a valid encryption of $m_2$ with CBC mode. This is because $m_2[1] = m_1[1] \oplus x$, so
$$m_2[1] \oplus IV_2 = (m_1[1] \oplus x) \oplus (IV_1 \oplus x) = m_1[1] \oplus IV_1$$ This way, the first blocks of input to the blockcipher are the same for both messages ($\oplus$'d with their respective IVs), and the encrypted outputs are valid for both messages.


Does it matter if IV is used as the first block of data before the encryption and then some fixed value is used for the actual IV? Usually the IV for the crypto operations is chosen randomly and is sent together with the encrypted data [at the first block]. For decryption, the IV is first extracted from data and set separately in the crypto components (functions or HW peripherals) and then feed the crypto operation with data.

The other case is to set the IV always to fixed value but the first block of data is chosen randomly. In this case after decryption the first block will be just ignored!

In terms of result, I understand that the encrypted text are different but in terms of security does anybody know if it matters or not?

Actually, that turns out that it's sometimes a useful way of implementing CBC mode (at least, with the understanding that you don't send the value you have labeled 'Initialization Vector', but instead the first cipherblock you generate will be sent to the decryptor as the CBC mode IV, and the rest of the cipherblocks will be sent to the ciphertext.

It is easy to see that if the decryptor uses the standard CBC decryption process with the provided IV and ciphertext, he'll get the plaintext.

So, why is this useful?  Well, one requirement for CBC mode is that the IV be unpredictable (specifically, unpredictable to someone who doesn't know the key; if they know the key, they don't need to predict IVs to verify potential plaintext blocks).  With the standard CBC mode implementation, you are given the responsibility of generating unpredictable values, which is not especially cheap.

However, with your construction, it turns out that we no longer require that the first block (that is, the one you labeled 'Initialization Vector') be unpredictable; it is sufficient that it just be unique - after it passes through the AES function, it'll become unpredictable.  Hence, it is sufficient that it can be a counter, which is a lot cheaper than an unpredictable value.

However, you'll say, you perform another CBC mode block (which involves another AES block operation); doesn't that increase the cost?  Well, sometimes, it doesn't - specifically, if you have some encryption hardware that performs a CBC mode encryption as a primitive, then the cost for encryption one additional block is usually fairly minimal (and certainly a lot cheaper than a side operation to generate an unpredictable value).

So, if you are in this specific scenario, yes, it can be a nice optimization.


Any concrete examples of the use of NIST Special Publication 800-90B? This question relates   to NIST Special Publication 800-90B, Recommendation for the Entropy Sources used for Random Bit Generation. A copy is available here.

Can anyone supply a pointer to any publication that has used the entropy assessment techniques of sections 5 and 6?  These relate to the characterisation and entropy measurement of non independently & identically distributed data generated by the entropy source of a true random number generator.

By publication I mean some work that is associated with a real TRNG, either DIY, commercial or experimental.  I'm not looking for theoretical papers on theoretical TRNGs.  The TRNG has to be made of wires and capacitors, not just formulae. I hope that the publication will contain a numerical entropy measurement, most probably << 8 bits per byte or sample.

What is the purpose of NIST SP 800-90B?
I think you are misunderstanding what NIST SP 800-90B is for. It is not a document explaining how to estimate the quality of a hardware noise source, but rather is meant for validation of a noise source. This means that you will not see it used to return a number of bits per byte. Instead, it will return pass or fail, depending on the quality of the randomness. A source that passes the test will be able to proclaim that it is 800-90B compliant and will be one step closer to being fully FIPS compliant. See section 3 in that paper for more information on that validation process.
To put it simply, there are two steps. The first is a test done in an accredited lab environment where the raw noise source is subject to tests, and the second involves an online test that actively runs as the noise is being collected, prior to conditioning or whitening. The first tests are extensive and are used to check whether or not the noise source lives up to the IID claims made by the manufacturers. The second test is an online test which is constantly run. The online test is part of the implementation and is designed to detect transient failure of the RNG. FIPS requires it shut itself down and refuse to output anything if the test ever fails. The online tests are much simpler than the initial tests as they are run constantly, making performance an issue.
You can run these tests yourself on any raw noise source you have. Post-processing using a simple algorithm is permitted if the source is biased but IID. Only three algorithms are permitted: Von Neuman debiasing, linear filtering, and run length counting. After that, you are free to condition the output using a cryptographic whitener, such as those specified in 800-90A.
A simple overview on one of the drafts for this document is available here.
Who is compliant with 800-90B?
Almost every single product listed on Wikipedia's Comparison of HWRNGs is either directly 800-90B compliant, or is compliant by extension of being FIPS 140-2 compliant. Others are compliant to similar standards such as STS or AIS 31 (which both specify a battery of statistical entropy tests run on pre-whitened, raw hardware noise sources). Some of these have open designs, meaning everything, including the noise source, is public. Others keep that as a trade secret, but publish detailed whitepapers and patents. Perhaps you should look at them.
It is a standard and necessary for FIPS 140-2 compliance, so many TRNGs will be using it. If you have something with a hardware noise source that needs to be FIPS certified, you will see a use of NIST SP 800-90B. At this point, the question becomes Are there any examples of FIPS-certified implementations in which case the answer is yes, many. Microsoft, Intel, Atmel, and even Western Digital have products that are FIPS 140-2 compliant, and thus also NIST SP 800-90B compliant.
If you are looking for a research publication, there are various academic papers that discuss improvements and critiques of the various entropy testing techniques used. For an actual publication going down to the silicon itself, you will probably be out of luck. Those things tend to be considered trade secrets and the most you will see is various whitepapers. In these cases, what you want to look for is whether or not their datasheet or whitepaper claims compliance.
While it is not an academic research paper, here is one concrete example, the TRNG-IP-76:

Another example may be the ATAES132A, an encrypted EEPROM chip with its own FIPS-certified RNG. Other examples would be the main microcontroller for any number of Opal-certified storage devices, TCG-certified TPMs, various smart cards, or even your CPU itself.


80-bit vs 128-bit security in today's world In today's world of applications, I see a lot of the time a 256-bit encryption key is used, but what about an 80 or 128? What makes 256 the one to use. Is a 80 or 128 easily decrypted?
Are comp ciphers better than others with the encryption of these keys?

80-bit
First, note that the Bitcoin miner's hash rate reached $> 2^{93}$ SHA-256 hashes per year in February 2021. This makes the 80-bit security absolute for known entities. They even passed that years ago (that is around 2012 per year). And even around 2011, it was absolute and NIST increased security strength from 80 to 122 for Federal Government in 2014. So there is no place for 80-bit in today's security.
128-bit
For 128-bit the question a bit more interesting, while yet there cannot be a group that can reach $2^{128}$ complexity ($2^{35}$-year is needed for a power like the Bitcoin Miners). There are

multi-target attack
In short; The expected cost of finding a key from $t$ targets is $2^{128}/t$. If you have a billion targets that you will be able to find the first key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$.

quantum-based attacks due to Grover's quadratic speed algorithm on symmetric ciphers. If ever build and if we omit other costs, 128-bit has 64-bit symmetric security on quantum computers.

Or see what can be done to AES-128
256-bit
To mitigate all just use AES-256 (or any 256-bit secure cipher like ChaCha20) and that is already the golden standard by the industry. Brute-force is impossible, multi-target has no meaning, and Grovers's algorithm can just reduce the security to 128-bit. Now we are safe as long as there no breakthrough either in breaking the algorithms or find a new scientific advancement.
112-bit
For lightweight cryptography NIST required at least 112-bit security from the 128-bit key size.


plaintext distribution ,perfect secrecy cryptosystem I have been trying to solve the next problem:
let pi be a perfect secrecy cryptosystem with specific plaintext probability distribution.
How to prove pi will have perfect secrecy for all other possible plaintext probability distributions?

Perfect scheme \Pi defined such that for every distribution over M and every $c\in C$ it holds that:  $Pr[C=c|M=m]=Pr[C=c]$ which means that probability to get a cipher text $c$ is independent of the message been encrypted, thus independent of the distribution over the message space M.


Is it generally possible to employ brute force methods when the encryption scheme is not known? Why or why not? Lets say you are presented with an encrypted string of bits or text, and no other information. What would be necessary before you could apply brute force methods to decrypting the string? How would a cryptanalyst approach such a case? (lets assume the conditions are such that the encryption can be brute forced in a reasonable time frame).

This is called ciphertext-only cryptanalysis*, and it's pretty difficult unless the cipher is quite weak.  Therefore, the first priority for a cryptanalyst in such a situation is usually to try to find more information about the algorithm.  Fortunately (for the cryptanalyst), as Kerckhoffs' principle suggests, there are often ways to find out how the algorithm works.  For example:

If the string was encrypted (or meant to be decrypted) by a computer program, one could try to obtain a copy of the program and inspect it in a debugger to determine the algorithm.
Similarly, if the encryption and/or decryption was done by a hardware device, one could try to obtain such a device and reverse engineer it.
One might also try to obtain a copy of a manual explaining how the cipher is used, or design documents explaining how it works, or even look for hints in public articles written about it.  Or one could even try to capture someone who knows how the cipher works and interrogate them.

That said, there are some things that can be done even without knowing the algorithm in advance, particularly if the cipher is a simple one:

One can look at the character frequencies in the cipher, or more generally at $n$-gram frequencies or at correlations between characters $n$ positions apart.  Many simple classical ciphers can reveal characteristic patterns under such an examination, allowing the algorithm and perhaps eventually the key to be guessed.
More generally, one can look for patterns that may reveal information about the algorithm.  For example, modern ciphers usually operate on bytes, or blocks of bytes, while classical ciphers typically use a smaller alphabet of letters and maybe a few symbols.  Some modern operating modes may reveal the block size of the cipher; also, comparing the length of the ciphertext with that of the plaintext, if known, may reveal the presence (or absence) of an IV and/or a MAC.  And sometimes, e.g. when used in ECB mode, even the output of a modern block cipher may have patterns that can reveal information about the plaintext, and, incidentally, the cipher and mode used.
Finally, one can simply try known algorithms and variants of them and see if they work.  This works particularly well if one has already narrowed the choices down somehow, and/or has additional information available (such as knowing the key but not the algorithm).

For an interesting historical example, see the cryptanalysis of the Enigma (and of the other WWII axis ciphers), which provides examples of several of these methods and their combinations.

* The term "ciphertext-only cryptanalysis" is also used for the broader situation where the algorithm is known but no information about the key or the plaintext is available.  Even that can be quite challenging, although obviously easier than if even the algorithm used is uncertain.


Extracting key bits from linear cryptanalysis equation for SDES From the linear cryptanalysis of SDES, we get a linear equation consisting the K[1, 3] of the round key 1 and 2. From this how will I retrieve the key bit?

How do we solve the linear equation we get from the linear cryptanalysis to predict the key bits?

The 1 and 3 bits of the round key 1 and 2 are present in the final relation. Form this we apply the algorithm 1, as stated in the paper by Matsui on linear cryptanalysis(The second image)

But from this how do we predict the bits of the actual/original key?

The attack, as stated in sections 6.2 & 6.3, actually can only recover the quantity
$K_1[1,3]\oplus K_2[1,3]$.

What you would hope to do is, to use a similar approach via another high probability linear relation [usually there is more than one] and recover more relations between subkey bits. Eventually, the goal is recovering all the original key bits. Assuming enough relations between pairs of key bits are recovered, then you can use take one variable in each relation as an unknown, and use more plaintext/ciphertext pairs, by brute forcing over those values, and select the values that give the highest bias. This is quite tiresome for DES.

I suggest reading Howard Heys' tutorial on linear and differential cryptanalysis [google it], which now appears as part of Stinson's Crypto book (3rd ed.) as well, where a more clear examples of targeting subkey bits is given, for both linear and differential cryptanalysis.


Is it safe to use a timestamp to build a nonce? I'm writing an application, which can be used on multiple clients, and share data on a server. To make sure the data never leaves the clients unencrypted, the application should offer encryption with AES-GCM and ChaCha20-Poly1305. Both of them need a nonce of 96bits, and it is recommended to use a counter, to make sure the nonce never repeats for this key.

Since I cannot think of a reliable system to guarantee the uniqueness/state of this nonce (the server is passive and only offers storage), I thought about using a timestamp to build the nonce:

Nonce-96-bit = Timestamp-Milliseconds-64bit combined_with CsRandom-Number-32bit

Is this a correct way to solve the problem? I'm aware of XChaCha20-Poly1305 which solves the problem with a bigger nonce so a random number can be used, but at the moment I'm working with the BouncyCastle library which offers the necessary .Net cross-platform support.

This isn't a very good idea - your chances of collision are not that low (depending on the number of clients you have). At best, your chances are $2^{-32}$ for 2 active clients. You would be better of just using a secure random 96 bit nonce as recommended by the NIST guidelines for AES-GCM (note though that you must not send more than $2^{32}$ messages with the same key when using this construction so that the chance of IV colliding doesn't exceed $2^{-32}$)


Why do SignTool/Authenticode Message Digests not match the direct hash of the file? I'm attempting to validate an Authenticode signature (generated by signtool /fd SHA256 /f <code signing PFX> /p <PFX password> test.exe), and I've run into an issue that I've narrowed down to a single point of confusion.

For the command above, if I hash test.exe before running the signing operation, for example using Get-FileHash test.exe in Powershell, I get a SHA256 hash of the file. But after signing the file, inspecting the signature in windows (Properties -> Digital Signatures -> Details -> Advanced) shows a "Message Digest" value which is entirely different from the hash of test.exe as calculated before signing.

Windows reports this signature as valid, so there is clearly a consistent understanding of "Message Digest" that isn't the one I have in my head (hash of the raw file contents, excluding signature). Can somebody please explain to me what Message Digest means in this context, and how it differs from a regular hashing operation?

You are expecting that the hash that is produced is always over the complete file. This is not correct. Authenticode uses the Cryptographic Message Syntax - a container format - to embed the content and the signature. This ensures that the Authenticode signature is using the hash of the original data (+ other signed attributes). The Authenticode format is specified here.

To quote:

  A PKCS#7 SignedDatastructure contains the PE file's hash value, a signature created by the software publisher’s private key, and the X.509 v3 certificates that bind the software publisher’s signing key to a legal entity. A PKCS#7 SignedDatastructure can optionally contain:

  A description of the software publisher.
  The software publisher's URL.
  An Authenticode timestamp.

Note that Microsoft keeps interchanging the name of the standard with the name of the structure that it defines: PKCS#7 is the standard that defines the Cryptographic Message Syntax.

Unfortunately, going through all the steps of "Calculating the PE Image Hash" is a bit too much for this answer; if you plan to do this programmatically you could ask questions about it on StackOverflow.


Deduplication: Encrypting the SHA-256 hash of a file chunk I'm designing a data storage system that should be both able to deduplicate data that share the same encryption key, and be reasonably secure.

I know that this kind of encryption quality can be achieved by using AES in CTR mode with a synthetic IV derived from the HMAC of the file chunk - so that the contents are deterministic and still not leak information about the similarity of chunks.

While thinking about this problem, however, it seems to me that a good way to allow data deduplication is to encrypt the SHA-256 of the unencrypted file, and use that as a key to determine if the contents are the same.

This seems simpler for a variety of reasons - the first being that it's cheaper to check if a file chunk already exists on the server; The other is that while the encryption of the SHA-256 hash should still be deterministic, the actual chunk contents' encryption don't have to be. This also allows me to perform other non-deterministic filters - like compressing the file contents before sending it.

Are there any down sides or known attacks for this cryptographic approach?

==== EDIT: More info ====

A file will be divided into chunks; Each chunk will have its plain-text SHA-256 hash calculated (this may be lowered to SHA-1 though for storage space reasons); This hash will be encrypted with a deterministic encryption - probably AES-256 (but suggestions are very welcome). This encrypted hash will represent the file chunk into the abstract file storage system.
At this point, the encrypted hash will be checked against the storage system, and checked if it exists already. If it doesn't, the chunk will be compressed, encrypted (I still haven't decided what encryption will be used for this), and sent to the storage. The file storage system will be "dumb" - meaning that it won't make any check.

The chunk is not of fixed size - instead, it should implement a bup-like hashplitting, so deduplication can work better. I'm studying the possibility of having bigger chunks, but right now in bup's implementation, each chunk has about 8k of data.

Information leakage in systems that do data deduplication typically involves timing hints that the data is already stored and related leverage of that information.  See the comments in https://security.stackexchange.com/questions/7142/online-backup-how-could-encryption-and-de-duplication-be-compatible/7146#7146 for insights there. Suggest you consider your attacker's profile and see of any of those issues apply as a confidentiality threat.

Efficient deduplication needs to maximize the capture of identical data and thus is typically done at the file level or some subset that will always produce the same chunks in the same file.  If your chunk boundaries plan addresses that you are good otherwise consider it.

Finally, encrypting a hash with a method that always produces the same output would appear to add very little protection if any.  The hash is by definition not reversible so the only potential value is in protecting against someone who can recreate the hash and wants to know if they are correct about the guessed plain text or binary.  That attack assumes the attacker can see the resulting hash.  If that is the case then seeing the predictably encrypted result adds very little to the attackers task as he only needs to see that the data is not moved to storage but rather already exists in the system (see first point about information leakage).


How strong is XooDoo vs AES? What is Gimli, and how does XooDoo compare to symmetric ciphers such as AES or ChaCha?

I am looking at this library, called charm.

Interesting paper here.

I also note the paper on XooDoo here.

There were no questions on XooDoo on this site, so I'm really interested to have peoples thoughts.

How do these 'permutation' based ciphers compare with standard symmetric ciphers?

Gimli is an unkeyed permutation, mapping a 384-bit input to a 384-bit output, $\{0,1\}^{384} \rightarrow \{0,1\}^{384}$. It is not a cipher by itself as you can reverse the output if you have it in its entirety, so it is not sufficient for security by itself. Instead, it is used to create a secure construction, e.g. using the sponge function. This function gets its security by keeping a portion of the permutation's output a secret, making it impossible to reverse without guessing the unknown (too large to brute force) portion of the output.

XooDoo appears to be another unkeyed permutation, with a slightly different design. There's very little we can say about its security right now, however, because it is relatively new. It often takes many years of analysis for the cryptographic community to feel comfortable about a new design. I will say, though, that it was made by reputable cryptographers, including one of the designers of Keccak-f, a heavily-analyzed and secure unkeyed permutation which is used in SHA-3, a NIST-endorsed hash function.

You can't compare an unkeyed permutation to a keyed permutation like AES because they have different purposes. Although you could build a regular block cipher out of it, that's not typically done. A keyed permutation like AES can be thought as a function which selects a permutation at random based on a key. Without knowing the key, you don't know the permutation and cannot reverse the output even if you have it in its entirety. And ChaCha is even harder to compare it with, as it is a stream cipher.

So, is a keyed permutation (block cipher) or an unkeyed permutation better? Typically, a block cipher has been considered a universal cryptographic primitive. Numerous constructions have been built around a block cipher to create things like hashes (for example, using the Davies–Meyer compression function). Recently, unkeyed permutations like Keccak-f and Gimli have gotten significant attention as potentially superior universal primitives because not only are they easier to analyze, but the sponge construction that they are useful to build can be easily adapted for a stream cipher, hash, or authentication function.

Simply put, block ciphers are older and more research has been done into utilizing them, but unkeyed permutations are more flexible and easier to analyze, and are starting to gain serious traction. XooDoo is a result of this trend towards unkeyed permutations. The Gimli paper mentions that there's no reason to doubt the "new conventional wisdom" that a permutation is a better unified primitive than a block cipher.


Why is "semantically secure" important for cryptosystems? The first question: what is the exact definition of semantically secure?
Basically, a cryptosystem is semantically secure if given the public key and the ciphertext, an adversary cannot learn any partial information of the plaintext.

However, the above statement is quite vague to me. For example, what does it mean by "partial information"? And how to prove that a cryptosystem is semantically secure by showing that no partial information can be learned?

I came across some security definitions (such as IND-CPA) that imply semantic security. Then how to show that the above notion of security (e.g. IND-CPA) implies semantic security?

Then the second question: why is semantic security important?

I came across many cryptosystems ( mostly homomorphic encryption schemes) requiring semantic security. So, why is it important?

A counter example is RSA, which is not semantically secure. But it is so widely used.

Let me try to answer your second question, and hopefully shed some light on the first one in doing so.

When we encrypt a message, it's because we want to keep something about that message secret.  But what is it that we actually want to protect?

Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON THE 20TH.  Is the secret that we wish to protect the name of the agent, or the number of units, or their destination, or their time of departure?  All of those?  Something else?

When designing a general-purpose encryption scheme, we really cannot know which aspects of the message being encrypted are sensitive.  Perhaps the user of the encryption scheme wants to pass off the message above as a routine weather report, and even just allowing the adversary to detect that it's probably not a weather report would count as an unacceptable security failure.  We can't know.

What we really want to do is to prevent an adversary (who does not know the key) from learning anything about the message.  That is, seeing the ciphertext should not allow the adversary to guess any property of the message with a better chance of success than if they had not seen the ciphertext.*

In other words, what we really want is perfect secrecy.  Unfortunately, as Shannon famously proved, perfect secrecy against an arbitrarily capable adversary is impossible to achieve unless the number of possible keys is at least as large as the number of possible (sequences of) messages encrypted with a single key.  In practice, this makes true perfect secrecy all but impossible; in particular, as it requires the key to be as long as all the encrypted messages combined, securely distributing the key becomes (almost) as hard as securely distributing the messages would've been in the first place.**  This is true for a simple reason: if there are $N$ possible keys, and $M > N$ possible messages, then the attacker can simply try to decrypt the ciphertext with each key, and thereby rule out those (at least) $M - N$ messages that are not the result of decrypting the ciphertext with any key.

However, in practice, even with the most powerful computers available today, no conceivable attacker can test more than, say, 1,000,000,000,000,000,000,000,000 keys, give or take a few factors of 1,000.  So if we just make the keyspace reasonably large (and it's not very hard — a random ten-byte key has more possible values than the huge number given above, and we can always add a few more random bytes for good measure), we can hope to make an encryption scheme that, even if theoretically not perfectly secret, is just as good in practice.

Informally speaking, this notion of "practically perfect secrecy" is just what semantic security is.  Or, to quote Goldwasser & Micali (1984)***:

  "Whatever is efficiently computable about the cleartext given the cyphertext, is also efficiently computable without the cyphertext."

The tricky parts of the formal definition (which I'm not going to give here; look it up in your favorite crypto textbook), involving strange theoretical concepts like asymptotic complexity and probabilistic polynomial-time algorithms, comes from trying to formalize this notion in terms of computational complexity theory, without assuming any specific computer hardware or resources for the attacker.

Basically, the reason for doing this (besides just wanting to make use of the toolkit that complexity theory gives us) is that, in practice, we won't really know just how much computing power the attacker can spare to break our encryption.  But we do know that, if the only (or at least the biggest) weakness of our encryption is the limited size of the keyspace, then we can increase the number of possible keys exponentially just by making them a little bit longer, with (typically) little impact on encryption speed, whereas the attacker can only increase their computing power linearly by buying more computers (and in general, only polynomially even by switching to a more powerful model of computation).

Thus, if we can prove (at least, subject to some reasonably plausible assumptions) that the difficulty of breaking our encryption (i.e. learning anything about the message) increases faster than any polynomial function of the key size, then we can safely conclude that we can make the encryption practically unbreakable by any given (or conjectured) adversary just by modestly increasing the key length.

*) Note that there's a hidden "gotcha" in the standard definitions of both perfect secrecy and semantic security: the length of the message is assumed to be public knowledge, and thus not necessary to conceal.  The reason for this is simple: the only effective way to fully conceal the length of the message is to pad all messages up to the length of the longest possible message; and if the message length is potentially unbounded, even this is impossible.  But this "gotcha" is indeed a practical issue, and can easily translate into real, practical attacks, like the CRIME and BREACH attacks against HTTPS.

**) The one practical advantage of OTP-like schemes with perfect secrecy is that you can distribute the keys before you know what you want to encrypt.  Even so, secure key generation and distribution is still the hard part of any such scheme.

***) This paper also contains a nice, and in some sense the archetypical, proof of the (conditional) semantic security of the cryptosystem defined in it.  If you want to see an example of how such proofs are done, this is not a bad place to start.


Check the validity of a rsa key pair with only the public key? I am currently developing a messaging application that uses rsa end to end encryption. The client generates permanent rsa keys, and sends the public key to my server for account management. As it currently is, my program will take any keys, without validation. This is a big security risk, so I need to validate the keys in some way, without knowlege of the private keys. How would I go about doing this?

While there are some obvious checks you can do, you can't cover everything:

You can check that the modulus is a composite odd number of the appropriate size
If you want to put in the effort, you can do a quick check if the modulus has any small factors
You can check if the public exponent is an odd number > 1

However, you can't check beyond that; you can't check if the modulus might not be specially built to be easy to factor, and you can't check if the public exponent is actually relatively prime to $\phi(N)$.  What is likely more important to you, RSA doesn't provide a way to verify that the public key entered is the specific public key of the intended receiver.

BTW: you said that this is a big security risk; what is the scenario that you fear that an attacker might introduce a bogus key, and gain some advantage?  If it's the fear that someone might substitute their public key, well, since they're likely to substitute a valid key, a validity check on the key isn't likely to protect you.  Instead, you need some other mechanism to tie the public key with the identity.


What is so special about elliptic curves? There seems to be sources like this, this also, and some introductions that discuss elliptic curves in general and how they're used.  But what I'd like to know is why these particular curves are so important in cryptography as opposed to, let's say, any other polynomial degree $\gt$ 2 which you can then mod over some group.  It seems like once a modulus is applied then other function types should be acceptable as well.

It seems even less intuitive when just looking at the bubble vs curve as here:

Since there are other curves (let's say anything from a sin wave to the $x^3 + x$ or even just some unusually shaped contour) that could do the job.  It seems like they would provide much more surface area to get a larger space in $\mathbb{Z}_p$ or really just more possible combinations of connecting lines from some arbitrary $P$ and $Q$ to get $R$ as opposed to something as restrictive (on the graph) as beginning from some bubble (which would seem to unnecessarily reduce the possible combinations) and then use a modulus to implement the discrete logarithm problem.

Sorry if this seems a little naive of a question, I'm trying to write an implementation right now and just to understand it fully even if that means asking something that is taken for granted.  Perhaps just walking through a simple example (most of the ones I've searched are anything but), just a few sentences, would be rather helpful, from "A wants to talk to B" all the way up to "now E can't listen in between A and B".

EDIT:

So it seems like this is the version of elliptic curves over a finite field:

Yes that looks pretty random.  But I'm still not really seeing why they are the only equations that have cryptographic significance.  It's difficult to imagine that if you simply took some other higher degree equation and applied modulus (to place within a group), then it seems like it would make sense that you'd get something that's also comparatively random.

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others.

For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line that goes through the identity element. Here's a handy picture for one of the best known conics, the unit circle $x^2 + y^2 = 1$:

If you take the identity element to be $(1, 0)$, then you get the very simple addition formula (modulo your favorite prime)

$$ (x_3, y_3) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)$$

This is much faster than regular elliptic curve formulas, so why not use this? Well, the problem with conics is that the discrete logarithm in this group is no stronger than the discrete logarithm over the underlying field! So we would need very large keys, like prime-field discrete logarithms, without any advantage. That's not good.

So we move on to elliptic curves, which do not have reductions to the logarithm on the underlying field.

But wait, we can generalize elliptic curves to higher degrees. In fact,

$$ y^2 = x^{2g+1} + \ldots $$

when $g > 1$ and some restrictions are respected, is called a hyperelliptic curve, and we can work on it too. But for these curves there does not exist a nice geometric rule to add points, like in conics and elliptic curves. So we are forced to work in the Jacobian group of these curves, which is not the group of points anymore, but of divisors (which are kind of like polynomials of points, if that makes any sense). This group has size $\approx p^g$, when working modulo a prime $p$.

Hyperelliptic curves do have some advantages: since the group size is much larger than the prime, we can work modulo smaller primes for the same cryptographic strength. But ultimately, hyperelliptic curves fall prey to index calculus as well when $g$ starts to grow. In practice, only $g \in \{2,3\}$, i.e., polynomials of degree $5$ or $7$ offer similar security as elliptic curves. To add insult to injury, as Watson said, the addition formulas also get much more complicated as $g$ grows.

There are also further generalizations of hyperelliptic curves, like superelliptic curves, $C_{a,b}$ curves, and so on. But similar comments apply: they simply do not bring advantages in either speed or security over elliptic curves.


Use of shared secret "other" than key creation I have read and (believe) I understand the basics of key exchange / creation over a public channel of communication from this diagram Diffie–Hellman key exchange.

Now, a fair bit of the online documentation states what has been produced by this process is a "shared secret" not a "shared secret key", nor any references to keys. The documentation does indicate what has been produced can be used as a (shared private?) key. But is the "shared secret" ever used for anything other than a key - I can't think what, but that's why I am asking the question. It was just the term "shared secret" without reference to "key" that prompts this question.

Edit:

This has been answered (but I can't find a way to indicate that on this post), so see comments below and : How to encrypt a symmetric key with a shared secret?

Shared secrets can also be used for authentication. He who knows the shared secret, is trusted.
For instance, this is used in IoT scenarios, where nodes communicate via DTLS and use the secret as a PSK instead of a certificate and a keypair.

Of course, this only makes sense if the shared secret has been preshared or calculated via some algorithm. The result of an online key agreement like DH cannot be used for that.