How to correctly evaluate the security of DH in TLS I'm trying to understand and evaluate the security impact of DH in TLS.

As far as I can tell, there are four major different implementations of DH in TLS.

DH
DHE
ECDH
ECDHE

With the ephemeral DH's, forward secrecy is possible, which I consider a huge bonus to security.

What I'm not too sure about is the elliptic curve part. With elliptic curves, the public certificate (?), used for DH, can be smaller than without elliptic curves and still be considered secure.

I have something in my mind like, non-elliptic-curve DH should have at least 2048 bit, to be considered secure.

Is my information correct?

How can I determine the key length (or public certificate size, I'm not sure what exactly I'm looking for here), of my server?

Can I use the information from the .pem file, used for DH (see comment below)?

openssl dhparam -inform PEM -in ./file.pem -check -text
DH Parameters: (4096 bit)
        prime:
             [...]
        generator: 2 (0x2)
DH parameters appear to be ok.
-----BEGIN DH PARAMETERS-----
[...]
-----END DH PARAMETERS-----

So in this case the DH key length/public certificate size would be 4096, correct?

With elliptic curves, the public certificate (?), used for DH, can be
  smaller than without elliptic curves and still be considered secure.

Yes, you can achieve the same level of security with shorter keys and thus shorter certificates with EC-based crypto and as an additional bonus: we tend to encode the full field (ie order, prime, generator) for standard DH but only a name (an OID to be precise) for elliptic curves.

  I have something in my mind like, non-elliptic-curve DH should have at
  least 2048 bit, to be considered secure.

  Is my information correct?

Yes, standard key size considerations (based on the GNFS) apply to finite-field DH.

  So in this case the DH key length/public certificate size would be
  4096, correct?

Yes, the size of the public key / the field prime is 4096 bit, the size of an actual DH certificate would be quite a bit larger though, due to the additional encoding of owner information, issuing CA information, field information, ...

Chances are that you are actually looking at your server's DH parameters that are used for the ephemeral key exchange.


Why Stream Ciphers can be slower in software than Block Ciphers I made some tests on virtual environment (Virtual Box) using StrongSwan, a VPN based on IPSec. I had latency results using ping command saying that Chacha20 (stream cipher) had poor performance comparing with AES and BLowfish (Block ciphers).

How is this possible since stream ciphers should be faster than block ciphers?

Almost everything depends on the hardware platform the algorithm is implemented for and specifics of the implementation.
So really one cannot say "algorithm x is faster than y" without referring to the specific hardware platform.
For example, this page https://bearssl.org/speed.html contains a couple of benchmarks. Taking amd64 as the platform, if we have no AES-NI acceleration, Chacha20 beats AES-128-CTR. However, if we do have AES-NI, the situation reverses and AES-128-CTR is a couple of times faster than Chacha20.

If you want to test various algorithm implementations on your machine, you can play e.g. with openssl benchmarking tool

openssl speed -evp aes-128-ctr
openssl speed -evp chacha20-poly1305


What does Modification Detection Code (MDC) in OpenPGP do? The authentication is often done by an HMAC in modern cryptosystems. What does MDC do exactly in OpenPGP and is it a software hack or an algorithmic authentication?

Also, how to force GnuPG to stop on error when the MDC is not checked? Right now it issues a warning and decryptes. That was a basis for a recent attack.

What does MDC do exactly in OpenPGP ?

MDC stands for Modification Detection Code. It's a field of cryptograms aiming at detecting that an encrypted message has been partially tampered with.

Why partially? Because that's the best achievable goal in asymmetric encryption, where it is always possible that an adversary changes a message in its entirety (since encryption requires no secret, only the recipient's public key).

So why does it matter to detect partial tampering if we can't detect total tampering? As illustration, if an adversary knew that a message will be like

connect with password nebulaergpaaelia to the website https://acme.com

and could change it to

connect with password nebulaergpaaelia to the website https://acne.com

then the adversary having registered the domain acne.com stands a chance to intercept the password thru what the recipient will do. Hence the need of an MDC.

OpenPGP has (for most ciphers and all recent ones) a provision for an effective MDC. Problems are:

There are legacy encryption modes without MDC. Thus if a decryption tool allows these legacy ciphers, it must accept to work without MDC.
OpenPGP encryption modes with MDC (that I know) detect message alteration only at the end of the message¹. But decryption tools often can be used as a pipe, spitting the deciphered message before the MDC check. That is per the common Unix design pattern of piping, and is useful for efficiency.
Often a piece of code using OpenPGP acts on the deciphered message irrespective of the later MDC check made later. For example, when the ciphertext is html with embedded URLs, the mere tentative to display it can trigger actions that an adversary can observe, and this allows attacks.

How the MDC is implemented (or not) in OpenPGP depends on the algorithm. None is mentioned in the question, thus I won't dive into the specifics.

  how to force GnuPG to stop on error when the MDC is not checked?

Modern versions (2.2.8 and higher, according to the source code) fail by default. It should suppress file output if the MDC check fails (but can't if output goes thru stdout). All that should be necessary for safety when using GPG thru a command line or thru a well-designed GUI is to

refrain from explicitly disabling MDC check (beware that --ignore-mdc-error can be made a permanent options in a variety of files set up manually or by GUI).
and make decryption output to a named file (rather than using > outputfile or piping) OR avoid using the deciphered output before ensuring that the tool's return code is 0.

¹ Conceivably, an encryption mode could split large messages into blocks of some maximum size each with an MDC, so that a decrypting program using bounded intermediary storage could release a deciphered block only after checking an MDC demonstrating that this block has not been altered and is in proper sequence. That would be safer, but more complex, and would increase ciphertext size to some degree. I do not know that it is used in OpenPGP.


Create a CR hash function where truncating one bit leads to collisions I was reading Boneh and Shoups's A Graduate Course in Applied Cryptography, when I stumbled upon the following exercise (I have changed the array indices to start at 1 instead of 0):

  8.1 (Truncating a CRHF is dangerous). Let $H$ be a collision resistant hash function defined over $(\mathcal M,\{0,1\}^n )$. Use $H$ to construct a hash function $H'$ over $(\mathcal M,\{0,1\}^n )$ that is also collision resistant, but if one truncates the output of $H'$ by one bit then $H'$ is no longer collision resistant. That is, $H'$ is collision resistant, but $H''(x) := H' (x)[1 \ldots n - 1]$ is not.

I've tried many different approaches, but I have not been able to come up with an $H'$ that satisfies both requirements, namely that (1) $H'$ is a CRHF over its full range, and (2) is insecure over its truncated range (by one bit).

Note that if $H'$ was instead defined over $(\mathcal M , \{0,1\}^{n+1})$, then solving the exercise would be easy. Simply define:

$$
H'(x) = H(x[1 \ldots m - 1]) || x[m] \tag 1
$$

It is easy to see that this $H'$ is a CRHF over its full range $\{0,1\}^{n+1}$ by a reduction to $H$, while insecure if we truncate its last bit.

However, if we try to adapt this idea to the range $\{0,1\}^n$, for example as follows

$$
H'(x) = H(x[1 \ldots m - 1])[1 \ldots n-1] || x[m] \tag 2,
$$

then the reduction to $H$ doesn't work anymore. Specifically, suppose we found a collision $H'(x) = H'(y)$, where $x = \tilde x || b_x \neq y = \tilde y || b_y$.
Since this is a collision for $H'$, we must have $b_x = b_y$, so $\tilde x \neq \tilde y$. But notice that $\tilde x$ and $\tilde y$ is not necessarily a collision for $H$. Rather, it is a near-collision in the first $n-1$ output bits, i.e., $H(\tilde x)[1 \ldots n -1] = H(\tilde y)[1 \ldots n -1]$. But that doesn't imply $H(\tilde x) = H(\tilde y)$.

  Thus my question: how do you actually solve this exercise as stated?

Note that one could try other constructions similar to (2). For instance $H'(x) = H(\tilde x) \oplus b_x$,  where we take the full output of $H$ on the substring $\tilde x$ and XOR the last bit of that hash with the last bit of $x$. But again, one can at most show that this leads to a near-collision for $H$, but not a full collision.

The only reference I could find in the literature regarding this problem, is the following statement from Boneh and Boyen:

  Kelsey [13] observed that truncating a collision resistant hash function need
  not be collision resistant.

And Kelsey [13] is this (.mov video) 2005 Crypto Rump session presentation by Kelsey, using more or less the same slides as in this presentation: https://csrc.nist.gov/CSRC/media/Events/First-Cryptographic-Hash-Workshop/documents/Kelsey_Truncation.pdf.
However, what he shows is that truncating can lead to problems if your hash has near-collisions. But he doesn't actually exhibit an explicit collision resistant hash function  with near-collisions --- which is essentially what this exercise is asking us to provide!

Assume there exists a collision-resistant $H$ from $\mathcal M$ to $\{0,1\}^n$; that $\mathcal M$ has at least two distinct elements $x_0$ and $x_1$, which we can exhibit (otherwise, any function from $\mathcal M$ to any set is collision-resistant); and $n>0$ (otherwise we can't define $H''$).

Proposition: there exists a collision-resistant function $H'$ from $\mathcal M$ to $\{0,1\}^n$ such that $H''$ from $\mathcal M$ to $\{0,1\}^{n-1}$ with $H''(x)\;=\;H'(x)[1\ldots n -1]$ is not collision-resistant.

Proof: Define function $G$ from $\mathcal M$ to $\{0,1\}^{n-1}$ by $G(x)\;=\;H(x)[1 \ldots n -1]$.

Define function $\hat H$ from $\mathcal M$ to $\{0,1\}^n$ by
$\hat H(x)\;=\;\begin{cases}
1\|G(x_0)&\text{if }x=x_1\\
0\|G(x)&\text{otherwise}
\end{cases}$

If $G$ is not collision-resistant, define $H'=H$, from which it follows that $H''$ is $G$. Function $H'$ is collision-resistant, because it is $H$, which is collision-resistant; but $H''$ is not collision-resistant, since a colliding message pair for $G$ can be found, and is a colliding message pair for $H''$.

Otherwise (that is, if $G$ is collision-resistant), define $H'=\hat H$, from which it follows that $H''(x)\;=\;\begin{cases}
G(x_0)&\text{if }x=x_1\\
G(x)&\text{otherwise}
\end{cases}$. Function $H'$ is collision-resistant, because any colliding message pair for $H'$ would be one for $G$, which is collision-resistant; but $H''$ is not collision-resistant, because $(x_0,x_1)$ is a colliding message pair.


Interpreting Figure 1 in the "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography" I'm reading "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography" by O. Regev.

I'm having trouble with understanding graphs in Figure 1.

By the definition of $\overline{\psi}_{\alpha}$, its support is $[0,1)$.

However, graphs in Figure 1 use support as $[-1,1] \times [-1,1]$.

Can anyone explain me about this?

The points of $\mathbb Z/q\mathbb Z$ are mapped to $\mathbb R/\mathbb Z$ and plotted in a circle.  The plot shows
\begin{align*}
  x &= \sin (2\pi i/q), \\
  y &= \cos (2\pi i/q), \\
  p &= \Psi_\alpha(i/q).
\end{align*}
for each $i$ in the least nonnegative residues modulo $q$.

The following gnuplot script gives a similar graph, for $q = 31$:

set parametric
set samples 31
psi(alpha, r) = exp(-pi*(r/alpha)**2) + exp(-pi*((r - 1)/alpha)**2)
splot [i=0:30] sin(2*pi*i/31), cos(2*pi*i/31), psi(0.1, i/31) with points


How can I change the length of PRF output? Say if I have a Pseudo Random Function PRF E: {0,1}^k x {0,1}^l -> {0,1}^l.

Hence it takes a key of length k and outputs text of length l bits. Is it possible to use this PRF E to construct another PRF H (with same inputs)
that outputs t bits instead l bits, where t < l.

Also, is it possible to construct a different PRF G (using E) such that on inputs: (k-bit key and (l-n) bit plain text) G outputs t-bit string such that t = 2 x l

I can't seem to figure out how to construct H so that it outputs a string that has less bits than the input string's length. Because to my understanding, it is impossible to do this yet maintain the one-to-one function property.

As for G, I was thinking of taking the output from E and feed it back to E again as an input, then concatenate everything together. Basically the output will be E{input} + E{E{input}}. But is this Pseudo Random and secure?

I don't understand why you are talking about a 1-1 property; a pseudorandom function is not 1-1. As such, you can always just truncate in order to reduce the output size, and you can just truncate by taking the first $t$ bits that you want (you don't need to apply any other function). In order to extend, if $\ell$ is long enough to be the length of a seed in a pseudorandom generator, then you can apply the PRG to the output of the PRF to get a longer output.

If you really are talking about a 1-1 function, then you want to change the output length of a pseudorandom permutation. This is much more difficult, and can be done. A place to look is at the whole body of work on "format preserving encryption", which is problematic in name (it's deterministic so not secure encryption). However, what they really do is construct permutations over domains of arbitrary size.


Theoretical Hashing Question I am testing a theoretical hash function, $f()$, which produces n-bits of output.

By the pigeon hole principle, if I run $f(x)$ over a search space of $1+2^n$ values, I will get at least one collision. According to the birthday problem I should get many more collisions than that.

Is there a similar principle that I can determine how many values of $x$ will be needed to ensure with high probability  that I have produced all possible $2^n$ values of $f(x)$?

I'm relatively certain that there is no 100% guarantee of obtaining all values, but at least an approximation within a degree of confidence should be possible. Are these approximations only practical when considering specific hashing algorithms?

If $f()$ can be modeled as a random function (that is, if each output for a distinct input is independent of all other outputs), then this is a well studied problem in probability theory, known as the Coupon Collector's Problem.

The link I gave you gives more details; the bottom line is that you start getting good probability of seeing all possible sequences after around $C n 2^n$, for a constant $C$ not too far from 1 (and whose actual value depends on what "good probability" actually is).

Of course, if your theoretical hash function doesn't act randomly (for example, there are pairs of inputs $A \ne B$ where we're guarranteed that $f(A) \ne f(B)$), this analysis does not apply.


The dth root unity in the Pollard Rho Algorithm In the original paper of Pollard's Monte Carlo Methods for Index Computation (mod p):

When the epact is reached, i.e. $$x_i = x_{2i}.$$ then the following equation is formed
 $$q^m \equiv r^n \pmod p,$$ where where $m=a_e- a_{2e} \pmod{p - 1}$ and $n = b_{2e} - b_e \pmod{p - 1}$.

with ext-GCD, the Bézout's identity calculated  $d = \lambda m + \mu (p - 1).$ Raising the above eqution to the $\lambda$ power gives
$$q^d \equiv r^{\lambda n} \pmod{p}$$

After this, it is claimed that $\lambda n$ is of the form $dk$ and then

$$q \equiv r^k \theta^i
 \pmod p,$$ where $\theta \equiv r^{(p-1)/2}$ is a $d$ root of unity, and $i (0 \leq u \leq d-1)$ remains to be determined.

Questions:

Why $\lambda n$ is of the form $dk$
In Wikipedia's sample code for Pollard's Rho algorithm, there is no such determination of $i$ (note that the $i$ in the article is not the counter of the code). Why is this so?

1) Because $r$ is a primitive root, there exists a $k$ such that $r^k = q$, so $r^{dk} = q^d$.

2) The sample code (lifted from section 3.6.3 of the Handbook of Applied Cryptography http://cacr.uwaterloo.ca/hac/about/chap3.pdf) assumes that the group has prime order. Pollard doesn't make this assumption.


Is key size the only barrier to the adoption of the McEliece cryptosystem, or is it considered broken/potentially vulnerable? A recent paper showed that the McEliece cryptosystem is not, unlike RSA and other cryptosystems, weakened as drastically by quantum computing because strong Fourier sampling cannot solve the hidden subgroup problem.

However, in 2008, new parameters were proposed after the old ones were found to be vulnerable.

So my question – as someone who hasn't much knowledge on this particular cryptosystem – is: Why isn't it in greater usage?

It would seem that if the promise of quantum computing is fulfilled, we may soon have need for cryptosystems not vulnerable to it. So, is the requirement for a large matrix (and therefore a large key) the only barrier, or are there other concerns/potential weaknesses? Or is there a better candidate for a post-quantum public key system?

The huge key is definitely an issue. Another is the lack of standardization or recommendations. Should you use OAEP with McEliece, or some other padding? What parameters are actually secure? And so on.

Part of the problem is that, while it has been around since the 70s, it was not considered particularly interesting until quite recently—so it probably hasn't had that many research years spent on its security properties. And so far as I know, it's never been deployed in the real world.

Other potential candidates for post-quantum crypto include NTRU and HFEv-, which are fast and have small keys. Unfortunately, both are patented. If you're interested in post-quantum cryptography, I would highly recommend picking up Post-Quantum Cryptography by Bernstein, et al, which is a good survey text.


Why are they called "commitment", "challenge", and "response"? I'm reading Proof Systems for General Statements about Discrete Logarithms, and I think I'll have a better understanding of the process if I can understand where the terms come from. They give a basic example which I'll just post a snapshot of below:

Can someone explain the logic behind the naming of these terms?

This is because:

For the commitment $t$, it comes first and uses the difficulty of the discrete logarithm problem to protect the value $v$. Once you've published the value $t=g^v \bmod q$, if someones knows the value $v$, then they can easily verify that the value $t$ corresponds to the value $g^v \bmod q$, but on the other hand it is really difficult to find the value $v$ knowing only the value $t$. Hence, you commit to the knowledge of the value $v$ by giving out the value $t$.
For the challenge $c$, you can see this value as being a "challenge": anybody able to give you a value $r$ such that $g^ry^c=g^v=t \bmod q$ must be knowing the value $x$, otherwise they wouldn't have been able to compute $r$ such that the $y^c=g^{xc}$ cancels out with the $g^r$ value. So you challenge them to provide you with a correct $r$ value.
And for the response $r$, it is an answer to the question of finding a value $r$ such that $g^ry^c=g^v$. If you know $x$ and $v$ then you can compute the value $r$ in such a way that the challenge would not be hard, but if you do not know those values, your chances to find a correct value $r$ are negligible. So you're responding to the challenge using that value $r$.

This is possible in the end because $g^ry^c=g^rg^{xc}=g^{v-xc}g^{xc}=g^v=t$ by definition of $y$ and $r$.

I'm speaking $\bmod q$ for all of it to hold, obviously.


Proof of a key agreement protocol based on bilinear pairings I'm currently trying to understand a proof of a protocol of the paper of Liqun Chen and Caroline Kudla entitled "Identity Based Authenticated Key
Agreement Protocols from Pairings". You can find a copy here.

In particular, it is a key agreement protocol which makes use of the bilinear maps. The protocol is the one described in the page 6 of the paper. The protocol is not very complex. It considers two users Alice, and Bob. Both choose at random their ephemeral private keys $a,b\in \mathbb{Z}_n^*$. Then both interchange the ephemeral keys $W_A=aQ_A$ and $W_B=bQ_B$ where $Q_A=H(ID_A)$ and $Q_B=H(ID_B)$. Then the established key can be computed by using a bilinear map as $K_{AB}=\hat{e}(S_A, W_A+aQ_B)$ and $K_{BA}=\hat{e}(W_A+bQ_A, S_B)$, where $S_A=sQ_A$ and $S_B=sQ_B$ (generated by the KGC).

The protocol is proven secure under the Bellare and Rogaway model. However there is a particular step that I don not understand which is associated with Theorem 1 of the paper. In particular, when they say (at top page 7):

Now call $A_k$ the event that $H_2$ has been queried on $\hat{e}(Q_I, Q_J)^{s(i + j)}$  by $E$ or some oracle other than $\Pi_{IJ}^n$ or $\Pi_{J,I}^t$. Then

Following, they say:

$Pr[E\text{ succeeds}] = Pr[E\text{ succeeds}|A_k]Pr[A_k] + Pr[E\text{ succeeds}|Ā_k]Pr[Ā_k]$.

Are they considering the case $Pr[E\text{ success} \cap A_k]$ and $Pr[E\text{ success} \cap Ā_k]$ for the first and second part of the previous expression?

Later, they assume $Pr[E\text{ succeeds}|Ā_k] = \frac{1}{2}$ which I understand. However, later they consider:

$\frac{1}{2}+ η(k) ≤ Pr[E\text{ succeeds}|A_k]Pr[A_k] + \frac{1}{2}$

and say "Thus $Pr[A_k] ≥ η(k)$". How they conclude this last expression from the previous one? I can understand that:

$η(k) ≤ Pr[E\text{ succeeds}|A_k]Pr[A_k]$

however... I can't see how they deduce $Pr[A_k] ≥ η(k)$ from the last expression.

I guess that it is something related with probabilities, but I suppose that I'm missing something...

Thank you in advance

however... I can't see how they deduce $Pr[A_k] ≥ η(k)$ from the last expression.

They use the upper bound $Pr[E\text{ succeeds}|A_k]Pr[A_k]\leq Pr[A_k]$, which follows from the fact that $Pr[E\text{ succeeds}|A_k]\leq 1$.


How to optimise Euclidean Algorithm for large numbers? -RSA I am using the standard version of the Euclidian Algorithm (i.e. GCD(270, 192) = GCD(192, [270 % 192]) =  ...repeat until 0) to determine if two numbers are coprime. I run the algorithm, check if the GCD is 1 and use that to determine if they are.

The problem is that I'm doing this for RSA and when I test the algorithm with 5 or 6 digit numbers it takes about 4 seconds, so I need a way to optimise the algorithm to work with hundreds of digits. I found references to the Extended Euclidean Algorithm online, but to my understanding that is used for checking the modular inverses that you create.

Can anyone confirm that the Extended Euclidean Algorithm should be used for this purpose, or suggest another algorithm that can be used to calculate the GCD of 300 - 600 digit numbers?

This answer covers use and implementation of the Euclidean algorithm in RSA, first straight for computing the Greatest Common Divisor of two integers; then (half-)extended for the computation of modular inverses.

The (straight) Euclidean algorithm is often used at one step in RSA: when it comes to choose odd $e>1$ and distinct primes $p$ and $q$ such that $\gcd(p-1,e)=1=\gcd(q-1,e)$. It has very little cost compared to other computations involved in that choice, in particular the test that $p$ and $q$ are prime (which is not performed using the Euclidean Algorithm). $e$ is usually small, thus only the first step of the algorithm needs to be carried with large numbers. Further, often $e$ is prime (including when $e=F_k=2^{(2^k)}+1$ with $0\le k\le 4$, the 5 Fermat primes); hence $\gcd(p-1,e)=1$ holds precisely when $p\bmod e\not=1$, and this simple test sidesteps explicit GCD computation.

Another possible use of the (straight) Euclidean algorithm in RSA is when computing $\lambda(N)=(p-1)(q-1)/\gcd(p-1,q-1)$ , if that's desired.

One possible efficient form of the Euclidean algorithm to compute $\gcd(a,b)$ for positive integers $a$ and $b$ repeats (until the algorithm stops):

$a\gets a\bmod b$ .
That is, replace $a$ with $a'$ matching $0\le a'<b$ and $b$ divides $a-a'$ .
Or equivalently, $q\gets\lfloor a/b\rfloor$ followed by $a\gets a-q\,b$ .
If $a=0$, then output $b$ and stop.
Exchange $a$ and $b$ .

Practical implementations often replace the exchange with a copy of the other steps with permutation of $a$ and $b$ .

The average number of steps is significantly reduced in this optimized version, but each step is slightly more complex:

$q\gets\lfloor(a+b/2)/b\rfloor$ (that is $a/b$ rounded to nearest, sometime noted $\lfloor a/b\rceil$ )
$a\gets|a-q\,b|$ .
If $a=0$, then output $b$ and stop.
Exchange $a$ and $b$ .

In RSA, the extended Euclidean algorithm is often used to compute one or more of the following modular inverses:

$d=e^{-1}\bmod\varphi(N)\;$ with $\varphi(N)=(p-1)(q-1)$ .
$d=e^{-1}\bmod\lambda(N)\;$ with $\lambda(N)=(p-1)(q-1)/\gcd(p-1,q-1)$ .
$d_p=e^{-1}\bmod(p-1)$ .
$d_q=e^{-1}\bmod(q-1)$ .
$q_\text{inv}=q^{-1}\bmod p$ .

The last three are used by optimized implementations using the Chinese Remainder Theorem. One of the first two is customary in introductory material on RSA, and useful in practice when $d$ is required (for archival/interchange, or because the CRT optimization is not used).

In all cases, the half-extended Euclidean algorithm can be used to efficiently compute $a^{-1}\bmod b$ for non-negative integer $a$ and positive integer $b$ , manipulating non-negative integers only:

$x\gets0$ and $y\gets1$ and $m\gets b$ .Note: $ax+by=m$ will keep holding, with $m$ the original modulus.
if $a=1$, then output "the desired inverse is $y$" and stop.
If $a=0$, then output "the desired inverse does not exists" and stop.
$q\gets\lfloor b/a\rfloor$ .
$b\gets b-aq$ and $x\gets x+qy$ .
if $b=1$, then output "the desired inverse is $m-x$" and stop.
If $b=0$, then output "the desired inverse does not exists" and stop.
$q\gets\lfloor a/b\rfloor$ .
$a\gets a-bq$ and $y\gets y+qx$ .
Continue at 2.

Note: $a$ and $b$ evolve as in the straight Euclidean algorithm; $x$ and $y$ are the (half) extension. The (full) extended Euclidean algorithm keeps two more variables, in order to fully solve the Bezout identity.

Various optimizations apply to the Euclidean algorithm and its (half)-extended variant:

The quotient $q$ needs not be computed exactly. If it is too small, the penalty is that the next $q$ will be 0. If $q$ is too large, numbers can get negative (and that can be either dealt with, or corrected). We can thus get away with a rough estimation of $q$ (and it pays to round to nearest if we can deal with that).
Usually, $q$ is small. When the numbers handled use multiple limbs/digits, it pays to optimize the case when $q$ fits a single limb. It may even pay to special-case $q=1$ and $q=2$.
Large $q$ need to be handled (otherwise worst case execution time becomes linear with the inputs), but is infrequent thus not critical. We can round large $q$ down to a power of two. In fact, restricting to $q$ a power of two is not disastrous, and has the advantage of replacing multiplication with shifts.
Usually, it is possible to predict the next few values of the (small) $q$ from the high-order bits of $a$ and $b$. That allows to group several transformations of $a$, $b$, $x$, $y$ into linear transformations with moderate multipliers computed from the predicted values of the $q$.

Off-topic since strictly speaking that's no longer the Euclidean algorithm: there is a binary GCD algorithm that performs only subtraction, additions, and divisions by 2. It also has an extended version fully solving the Bezout identity (see the Handbook or Applied Cryptography, algorithm 14.61), and a half-extended version specialized towards computing the modular inverse (see the first section of this answer). It can be competitive with the Euclidean algorithm when multiplication is expensive; and the two can be blended.


Validating successful decryption in AES I have a program which uses AES-256 in CBC mode to encrypt and decrypt files. As I have quickly realized, AES will even use an incorrect passphrase to decrypt data, which leaves me with no way to validate whether the passphrase was correct or not and, in turn, whether I'm decrypting things successfully.

One idea which was suggested before was to embed a known value in beginning of the encrypted data to validate whether decryption produced an expected result. Essentially, since the IV is a known value, I thought of simply hashing it and embedding it as the first 32 bytes in the file. If, after the first block is decrypted,  the first 32 bytes equal the hash of the IV, we can know that decryption succeeded. If not, we can know that it failed.

Does this in any way compromise my encrypted files?

That would work and almost certainly wouldn't have any negative impact on security, but it would be cleaner just to have a string of 16 0x00 bytes at the start of a message, instead. Not only does this save you the trouble of hashing, but you stay within the standard threat model for CBC which assumes the IV is independent of the message blocks. (One can come up with pathological yet technically still secure hash functions that would cause your approach to become insecure.)

And a quick note: the block size is 16 bytes, not 32 bytes. The 256 in AES-256 refers to the length of the key, not the block.

You should look into using a message authentication code, such as HMAC. Doing so will not only validate a correct passphrase, but will also ensure the ciphertext has not been tampered with. (CBC will prevent someone from learning information about the plaintext, but will not stop someone who already knows it from tampering with the ciphertext so that parts of it decrypt to strings of his choosing.)

Edit: A couple warnings, if you decide to go with a MAC (and I think you should): (1) Use different keys for CBC and the MAC; (2) MAC the ciphertext, not the plaintext; (3) Concatenate the IV to the ciphertext before using the MAC.


How to generate a permutation of n numbers using secret sharing scheme? Consider $n$ parties having their private inputs $s_1,\cdots,s_n$. How can they compute a public function $f(s_1,\cdots,s_n)= \pi$, where $\pi$ is a permutation of numbers between $1,\cdots,n$, using secret sharing scheme?

If you are just lacking a function from some random number to permutations, this is easy:

Consider the set of all permutations of $\{1,\dots,n\}$, put them in lexicographical order and assign natural numbers. There are $n!$ permutations, so let's say $x$ is some random number from $\mathbb{Z}_{n!}$, and here's an algorithm how to get the matching permutation:

Generate list $L = [1,\dots,n]$ and empty list $O = [\;]$
$a = (|L| - 1)!$
$b = \lfloor x / a\rfloor $
Remove $L[b]$ from $L$ and append it to $O$
$x = x \mod a$
if $L$ is not empty: GOTO 2.
output $O$

List indices are starting from $0$ as usual.

It wasn't stated in the question from which set the private inputs were taken, and ideally this would be from $\mathbb{Z}_{n!}$ (or alternatively $\{a, a+1, \dots ,a + n! - 1\}$). Then all you need is to use MPC to calculate the sum $x = s_1 + \dots + s_n \mod n!$, and use above algorithm to calculate the matching permutation. If the entropy of the inputs is not enough, use can use a PRG to expand this input and use $s'_i = PRG(s_i)$ instead (for party $P_i$).


Nomenclature of Certificate Authorities and Certificates in PKI In PKI there are different terms to identify certificate authorities in the chains. All terms I know of are as follow:

Root
Subordinate
Super
Intermediate

I see all terms used interchangeably in the combination with “certificate authority (CA)” and “certificate”. I read a lot of web pages as well as books and my personal understanding from all of this is as follow:

A CA is called a root if it’s certificate has no super certificate.
A CA is called a subordinate if it’s intermediate certificate has a super certificate of another subordinate or root CA.

What is the actual meaning of the four terms and their relation to each other?

  How is this question of a practical matter to cryptography?

I‘m not entirely sure if this question fits this StackExchange or if it should go somewhere else. However, I consider this question to be directly related to cryptography since it is about PKI and the nomenclature is specific to the world of cryptography and PKI.

The practical matter comes into play during communication – especially in documentation – regarding PKI, CAs, and certificates.

A CA certificate is a certificate which is used to sign other certificates. This is indicated by the Basic Constraints extension
A root certificate is a certificate which is self signed i.e. not signed by another CA cert
An intermediate certificate is any (CA) certificate in a certificate chain between the root and the leaf. Those are also sometimes called Sub CA. Usually, there is one such in a chain.
Super and subordinate means exactly what it says. Remember that you are working with a certificate chain.


What is the most secure ECC Curve? I have for a while used Koblitz curve (sect571k1), in ECDH and ECDSA. But I have started wonder if it is the most secure. I prefer security over efficiency. So the curve doesn't have to be the most efficiency curve.

I'm not looking for a curve that is only secure today, and the next few years. The compute power increases rapidly today, and I'm looking for a curve that is secure as far as possible in the future. So if someone is able to steal my encrypted data today, they should not be able to crack it in next 20 years, hopefully longer.

There is no such thing as the most secure curve. For one you can always come up with a larger curve if you need one. For another there are many measures of security and not all curves are directly comparable.

If you wanted the curve for which the current best known attack is the slowest, then by that measure sect571k1 is actually the most secure out of the curves that are in use.

However, that is not necessarily a very useful requirement, because any curve for which the best known attack is slower than ~128-bit strength equivalent will never be broken without either advances in attacks or the arrival of practical quantum computers. Those advances need not apply equally to all curves, while quantum computers would break all curves regardless of strength.

Binary field curves like the one in question are sometimes considered more risky because better attacks are known than for prime field curves of similar size, so it is thought that new attacks are more likely. That is a judgement call.

Likewise there are other measures of security that do not apply to all curves. Perhaps the most talked about is the potential for some kind of backdoor in the parameters, which makes some distrust NIST curves in particular and any curves without a good explanation for the parameters in general. Also things like ease of secure implementation may matter in practice.


What is the correct value for "certainty" in RSA key pair generation? I'm creating an RSA key pair in Bouncy Castle and need to specify an int value for certainty.  This Stack Overflow answer says it is a relative test for how prime the values are.

There is another answer that says this value should be adjusted relative to the key length.

Question

What are the correct values for certainty relative to key length (how did you determine this?)
What does it mean to say "certainty of x bits" of a number?  (If it's possible to sub-divide a number and certify bits, which bits are being certified?)

Certainty of $x$ bits means that the probability that something (in this case $p$ being prime) not being true is smaller than $2^{-x}$. This is the same probability as guessing a random $x$-bit value correctly on the first try, hence the name.

How to select $x$? We want the probability of $p$ (and $q$) not being prime to be small enough that a failure probability in this point is not larger than other ways the system could be broken - like guessing a symmetric key, factoring the modulus etc.

So here a correspondence table of symmetric and asymmetric key sizes should help. Pick the same prime certainty as you would pick an symmetric key size accompanying your public key usage.


Interactive Homomorphic Encryption Let's say that I have a plain computational process that consists of several divisions and I do not want to do it with non-interactive homomorphic encryption.

I would like to ask how can I call this process: Until a division, I do the computations non-interactively. When I face with division operation, here comes interactivity. I should send encrypted numerator and denominator to a party and get the division result back. This second party should not learn the contents of numerator and denominator.

Since I cannot call the process, I cannot find papers to read. I want to use this kind of solution, but I am new to homomorphic encryption. I have experience with non-interactive homomorphic encryption. But I would like to get experience on this interactive one.

I have no idea which scheme I can use and how to implement this. Do I need garbled circuits for this?

This can be seen as a particular case of secure two-party computation, where one party has the (encrypted) inputs, and the other has the decryption key. There is no specific name for the functionality you are looking for, as it is just a particular functionality that one can want to realize in the framework of two-party computation.

So, I think you're looking for a two-party computation protocol realizing the following functionality:

Alice has input $E(a),E(b)$, where $E$ is some encryption scheme (I guess that in the scenario you have in mind, it's an FHE), and Bob has the decryption key of this FHE scheme. You want to realize the functionality that returns $E(a/b)$ to Alice, and nothing to Bob.

(note that even a perfectly secure realization of this functionality will at least leak whether $b = 0$, so you have to make sure this is not an issue for you in the larger protocol you want to use this subprotocol in).

As for how to implement it: if you're using an FHE scheme and just want to avoid doing the expensive division, it's super easy. Just let Alice homomorphically multiply $b$ by some $r$, and randomize the ciphertext: she gets $E(rb)$ and sends that to Bob. Bob decrypts, gets $rb$, computes $(rb)^{-1}$, encrypts, sends back. Alice gets $E((rb)^{-1})$, and homomorphically multiplies with $r$ and $E(a)$ to get $E(a\cdot b^{-1})$.

I suspect from your comments, however, that you are interested in approximate division of floats, and not just computation of $E(a\cdot b^{-1})$. Is it the case? If so, you will likely need a much more complex and interactive protocol.


Securely derive AES and ED25519 keys from a ED25519 seed Go's ed25519 package exposes a function which allows creating a private key from a 32 byte seed.

See: https://godoc.org/golang.org/x/crypto/ed25519#NewKeyFromSeed

The reason I want to use this is because this is only 32 bytes, hence easy to copy and pass around.

I assume if I use a cryptograpically secure source of random for the seed, I should be ok in terms of security for the ed25519 key.

(Ideally I'd go even smaller if I could, without compromising on security).

Now I'd like to derive an AES key for encryption from those 32 bytes I already have (or the pub/priv key generated by the seed).

I would like anyone with the seed (or the private key) to be able to do the same.

Now there might be three types of clients:

Clients that have the seed/private key, who are able to derive the AES key, encrypt and sign the encrypted data. (needs 32 bytes for privkey or seed)
Clients that have the public key, and are able to verify the data has not been tampered with, but not be able to decrypt the data. (needs 32 bytes for pubkey)
Clients that have the public key and AES key, who area able to verify and decrypt data, but not able to sign it themselves (needs 64 bytes, 32 for pubkey, 32 for aes key)

How could I derive an AES key securely for this matter?

My gut says to use pbkdf2 on the private part of the ed25519 key to generate a AES key, but I am not sure if it somehow weakens the security.

Using pbkdf2 on the seed feels like it would compromise the security even more?

You should pick a key-based key derivation function, such as HKDF-SHA256.  Then:

Generate a master key $k$ uniformly at random.
Derive an Ed25519 seed $k_0$ from it by $$k_0 = \operatorname{HKDF-Expand}_k(\text{info=‘Ed25519 signing key’},\, \text{size=32 bytes}).$$
Derive an AES key $k_1$ from it by $$k_1 = \operatorname{HKDF-Expand}_k(\text{info=‘AES encryption key’},\, \text{size=32 bytes}).$$
Derive any other keys you want for any other purposes—perhaps even other Ed25519 or AES keys, just for different purposes—using HKDF-Extract with the same master key and a distinct info parameter for each distinct purpose.

You can organize the tree as you see fit to distribute subtrees with partial authority, like the authority to sign (give out $k_0$ but not $k$ or $k_1$) or the authority to encrypt/decrypt (give out $k_1$ but not $k$ or $k_0$).

Any other reasonable keyed XOF, such as KMAC128 from SHA-3 or keyed BLAKE2x, will serve too.  Functions with fixed-length outputs like HMAC-SHA256 or keyed BLAKE2s are a little finickier in case you need, e.g., a 64-byte key for some reason instead of just a 32-byte key; HKDF is a generic way to turn these into a variable-length output.  HKDF also includes an optional initial step, HKDF-Extract, to turn a nonuniform but high-entropy seed—such as a computer-generated BIP39 passphrase—into an effectively uniform random master key.

There is no need for a password-based key derivation function (or just ‘password hash’) such as PBKDF2 because the input—your 32-byte master key—is already a uniform random bit string.  All that you really need is derived subkeys—$k_0$, $k_1$, etc.—that are apparently independent.


Signature using RSA (as described in Cryptography engineering) In the book "Cryptography engineering" (2010, Ferguson), I found, page 209/210, these 3 functions: MsgToRSANumber, SignWithRSA, VerifyRSASignature (see below).

I can't understand how the last function VerifyRSASignature works. It seems that it checks if "the given signature $\sigma$ raised to exponent $e$ mod $n$" (this part is ok) is equal to $s$, which is the result of MsgToRSANumber, i.e. the result of a random choice!

How can this work? Isn't there a mistake here?

The pseudocode shown is correct.

It works because  is a function in the mathematical sense; and in particular, always returns the same result for the same arguments $(n,m)$. This is possible because it internally uses a Pseudo Random Number Generator (PRNG), rather than a True RNG (wich indeed would make the signature verification fail).

The rationale for using a (P)RNG to transform the message $m$ into the message representative $s$ is that the (conjecturally hard) RSA problem is to invert the public key function $s\to s^e\bmod n$ for a random $s$ in interval $[0,n)$. If we used $s=m$, or a simple transformations (e.g. $s\ =\ (a\;m+b)\bmod n$ for some public constants $a$, $b$ ), an attack would often be tractable. The signature system proposed has some level of reducibility to the RSA problem.

RSASSA-PSS of PKCS#1v2, and RSA per ISO/IEC 9796-2 scheme 2, are signature systems which combine a PRNG and a TRNG in preparing the message representative $s$. The TRNG insures that an adversary can not predict or choose which $s$ the legitimate signer will use, even if given the opportunity to choose the messages signed. This allows stronger/simpler security reduction.


Man-in-the-middle attack on text-book RSA PKE I am attempting to solve the following problem:

I know the following:
3 messages are being sent between Alice and Bob, all messages are encrypted with the known public key $(d,N)$:

Alice sends Bob: $m_1=E(R_1);$ $R_1$ is a 28-bit number.
Bob sends Alice: $m_2=E(R_2,R_1);$ $R_2$ is a 28-bit number and $R_1$ follows (i.e,
$p_2 = (2^{28} * R_2 + R_1)$ if i am not mistaken)
Alice sends Bob: $m_3=E(R_2,R_1,R_3);$ $R_3$ is a 156-bit number known in advance.

The goal is to alter $R_3$'s value which is about to be sent to Bob to a new value (first 7 bits only).

The best I could come up with is to precompute all possible 28-bit number encryptions which will allow me to know $R_1$'s value when sent by Alice -> then easily figure out $R_2$'s value -> send my desired $R_3$ value to Bob.

Is there a neater (and more feasible) way to do so?

I see four ways how to attack this scheme

1) RSA malleability
Suggested in comments

2) If $e=3$ then
Trivial attack exists. Hint: What is the minimal possible size of $N$?

3) If the attack is active(MiTM)
Cheaper attack exists. Hint: Treat the task as a set of Oracles:

$Oracle0: n \mapsto E(n)$ - If you know $(e,N)$, you can encrypt any $n$.
$Oracle1: \epsilon \mapsto E(R_1)$
$Oracle2: E(n) \mapsto E(R_2*2^{28}+n)$
$Oracle3: E(n) \mapsto E(n*2^{156}+R_3)$ - Are you sure?

4) You treat it as a blackbox
Your solution


Does adding a random number to my data make it secure? Say I have some real valued data that i want to keep secure. Now I have to pass on some modified version of the data to a second party for some computation, but i do not wish to reveal my data to the other party. If I add a value generated by a pseudo-random generating function to my data and then pass it on, does my data stay secure?

Yes, adding a secret random value $r$ to secret data $s$ and publishing the result $t=r+s$ can leave $s$ confidential; not perfectly so, but arbitrarily close to perfectly.

How much information leaks about $s$ from revealing $t$ depends on the assumed distribution of $r$ and $s$. For example, if $s$ is assumed to be chosen in $\{0,1\}$, and we chose $r$ uniformly randomly in $\{0,\;1,\dots,\;2^{128}-3,\;2^{128}-2\}$, then $t$ fits a 128-bit bitstring. It $t$ is $0$ or $2^{128}-1$, then the adversary has learned $s$ with certainty, but that's unlikely: probability about (just above) $2^{-127}$ for any distribution of $s$, or about $2^{-128}$ if $s$ is chosen by fair coin toss. And in other cases, the adversary has learned nothing about $s$.

More generally, if $s$ is an $m$-bit integer and $r$ is a uniformly random $n$-bit integer, then probability that the adversary learns anything about $s$ from $t$ is at worst about $2^{n-m-1}$ when that's small.

Other distributions of $r$ allow $t$ to use much less bits, without increasing the probability that an adversary learns $s$ with sizable probability, but trade this against more often revealing a little about $s$.

The question mentions that it should still be possible to perform some computation about $s$ from the masked $t$. That holds for addition at least. For example we can perform $t_i=s_i+r_i$ for several secret $s_i$, and the $r_i$ generated pseudo-randomly from a key $K$ and $i$ (using some PRF such as HMAC). $\sum t_i$ then allows to find $\sum s_i$ for one knowing $K$.


Differential Privacy of the Laplace mechanism with non-deterministic function This question is about the proof of the differential privacy of the laplace mechanism.

All more detailled explanations I found of the proof, that the laplace mechanism is $\epsilon$-differentially private, use deterministic functions as the query f that is made on the database (e.g. counting queries).

But is the statement actually only valid for deterministic f?

Seems to me, that adding Laplace noise is a popular easy way to make any kind of query differentially private. Imagine having a random query, but its randomness is weird and you just say: Eh, skip finding out, if the mechanism is private on its own. Just add additional noise (in this case laplace noise) and it will be fine. Judging from the idea behind adding noise to improve privacy this should be possible - I thought.

If the laplace mechanism works for non-deterministic functions as well - where in the proof of the differential privacy is the influence of the function's randomness taken into account?
If the standard proof as shown below (from "The algorithmic foundations of differential privacy" by Dwork/Roth) doesn't work for random f - is there a way to prove it in another way? How?

Thank you in advance for any help.

The Laplace mechanism only works for deterministic $f$, because the notion of "sensitivity" (the $\Delta f$ in the formulas above) isn't well-defined for random functions. $\Delta f$ is the maximum difference between $f(x)$ and $f(y)$, for neighboring $x$ and $f$. If $f$ is a random function, then that notion of "difference" becomes much more complicated to capture, so in general, you simply assume that $f$ is deterministic.
To extend this to the case where $f$ is random, you could define $\Delta f$ to be the maximum difference between a possible output of $f(x)$ and a possible output of $f(y)$, for all possible values of the random bits used by $f$. That would still allow you to say $\frac{||f(x)-f(y)||}{\Delta f}\le1$. But that doesn't work if that value is unbounded (for example, if $f$ implicitly adds Gaussian noise to the result of the computation), and that's a loose approximation in general; so it's pretty much never done.


Quantum algorithm for elliptic curve's private keys Is there a quantum algorithm to find private keys generated using elliptic curves ?

Shor's algorithm, which runs only on quantum computers, solves all discrete-logarithm problem instances over all groups.

This obviously includes the elliptic curve discrete logarithm problem at the heart of ECDH, ECDSA and ECIES. For a more detailed discussion of the details, see this recent paper.

However, there are things we can do with elliptic curves that are believed to which we don't know better quantum algorithms, like elliptic curve supersingular isogeny-based key exchanges.


Is choosing $1$ as a public exponent valid in RSA? I know it will not encrypt anything. But is $1$ valid as a public exponent in an RSA public key?

TL;DR: it is a matter of conventions and context that $e=1$ is allowed or not.
Definitions of RSA vary:

The original RSA article asks to first choose the private exponent $d$ as « a large, random integer which is relatively prime to $(p−1)\cdot(q−1)$ », then to compute $e$ as « the “multiplicative inverse” of $d$, modulo $(p−1)\cdot(q−1)$ ». This makes it extremely improbable that $e=1$, but allows it. Later descriptions of RSA tend to choose $e$ first.
PKCS#1 v1.5 / RFC 2313 asks to « select a positive integer $e$ as its public exponent ». That allows $e=1$.
PKCS#1 v2.0 / RFC 2437 states « the public exponent $e$ is an integer between $3$ and $n-1$ satisfying $\gcd(e,\lambda(n))=1$, where $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ ». That does not allow $e=1$, but still allows $e=\lambda(n)+1$ and $e=(p−1)\cdot(q−1)+1$, and perhaps a few other values of $e$ that are such that $x\mapsto x^e\bmod n$ is the identity function over $[0,n)$ just as it is for $e=1$. PKCS#1 v2.2  has the same prescription for $e$.
FIPS 186-4 states « the exponent $e$ shall be an odd positive integer such that $2^{16}<e<2^{256}$ », and that forbids $e=1$. Combined with $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$ and a minimum for $d$, that makes it impossible $x\mapsto x^e\bmod n$ is the identity function.

For computer implementations, that depends on if an explicit test against $e=1$ is present or not. Both exist.
Sometime, public keys with $e=1$ or $e=\lambda(n)+1$ (which is more rarely disallowed by software) are used in test keys, or in reverse-engineering, in order to allow easy analysis of padding. Of course, such keys must not be used for encryption or signature of valuable data.


Reseeding a PRNG with the generated PRN Would reseeding a PRNG with the PRN from the previous generation have any effects whatsoever on the quality of the generated numbers; if so, does this depend on the PRNG used, or are the effects generally applicable to any algorithm?

Perhaps I'll enhance the question with some pseudo-code:

firstSeed := get_seed_from_entropy_pool()
seed(firstSeed)
firstPrn := rand()
seed(firstPrn)
nextPrn := rand()

Is nextPrn already of inferior quality? Would quality decrease if repeated?

In most PRNGs, this leads to a total disaster, in particular when the generator's state is bigger than the result returned as pseudo-random (call to rand()).

If you take Mersenne Twister with its big period guaranteed and apply the construction you expose, as it returns 32-bit integers, eventually you will get a repeated value that was used to seed previously, so it turns into a loop. You'll get an about $2^{16}$ repeating sequence of pseudo randoms, according to the birthday probability, and not the guaranteed generator's period length. This same issue applies to all other generators if it's seeding is deterministic and guarantees that a given seed always generates the same sequence of pseudo randoms.

On the other hand, if you do some steps of autoseeding first and then you use the PRNG without seeding it anymore then it shouldn't affect its properties.


A lower bound on the insecurity of CipherCloud? CipherCloud claims to support , among other things, searchable encryption. A bunch of speculation seems to suggest they did this via some breathtakingly  incompetent means( unfortunately such speculation "appears" to be copyrighted)
Regardless of their actual methodology, if we assume their encrypted data is searchable by the cloud providers they work with without changes to the providers(e.g. salesforce), then doesn't this result for order preserving encryption constitute a lower bound on how insecure their system  could be(and a pretty poor one at that)?
The result deals with the security of the ideal functionality of an order preserving encryption (OPE) scheme.  This is the ideal model of a  scheme where you can sort  $c=enc_k(m)$ by numerical comparison of $c$. Any scheme where you search encrypted cipher texts with existing queries in a database must meet this requirement. This appears to suggest that the absolute best case for CipherCloud is that their encryption leaks roughly the $1/2m$ high-order bits of a given message* . This seems drastically unsafe for low entropy messages such as social security numbers, credit card numbers, earnings reports, and most other data you might want to search on in say a sales application.
*Per the paper, where M is the size of the message space(i.e. $M=2^l$ for $l$ length messages) "Intuitively, Theorem 4.2 implies that for $r\approx b \sqrt{M}$, where b is a large enough constant (say $b \ge 8$),there exists an adversary $A$ whose r-window one-wayness is very close to 1."

That paper refers to the numerical ordering, while what would be relevant for searchable encryption without changes to the providers is the substring ordering. $\:$ (Thus, their bound does not apply.)

What do you mean by "existing queries in a database"?

If your assumption holds, then
{
Encryption must be deterministic (given the key), since different encryptions of the

same message (with the same key) must be substrings of each other (and thus equal).

There must be a noticable $\big($though not necessarily $\theta\hspace{.01 in}(1)\big)$ chance of breaking authenticity via a

single ciphertext only (by submitting a random substring of it). $\:$ The scheme must be malleable by

almost the same amount, again with just a single ciphertext only and for basically the same reason.
}

"without changes to the providers" is a rather stiff assumption. $\:$ For example, one could easily shut

down active attacks by splitting the ciphertexts into two columns and having the cloud just search the

left column, while the right column has message authentication codes which are only relevant to the user.


Dual system encryption:New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts In the paper New Techniques for Dual System Encryption and
Fully Secure HIBE with Short Ciphertexts from Waters and Lewko, how can the elements $R_3$ and $R'_3$ be eliminated in the decryption algorithm?

It uses an artifact of pairings over groups of composite order.

Specifically, if the order of $G$ is $p_1$ and the order of $H$ is $p_3$ and $p_1, p_3$ are relatively prime, then $e(G, H) = 1$.

This can be easily seen by considering the order of $e(G, H)$; we know that $e(G, H)^{p_1} = e(G^{p_1}, H) = e(1, H) = 1$, hence the order of $e(G, H)$ must be a divisor of $p_1$.  Similar logic shows us that the order must also be a divisor of $p_3$.  Because $p_1, p_3$ are relatively prime, the only common divisor they have is 1; hence the order of $e(G, H)$ must be 1.

Section 2.2 of the paper gives a different derivation of the same result.

Once we have that, we can see that $e(K_1, C_1) = e(g^r R_3, (u^{id}h)^s) = e(g_r, (u^{id}h)^s) \cdot e(R_3, (u^{id}h)^s)$.  Since the order of $R_3$ (which $p_3$) and the order of $(u^{id}h)^s$ (which is $p_1$) are relatively prime, the second half is a constant factor 1, and so this reduces to $e(g_r, (u^{id}h)^s)$ (and thus $R_3$ disappears).  Similar logic gets rid of $R'_3$ as well...


Why isn't E' secure if it's built over a secure cipher? Let $E$ be a semantically secure cipher.

Let $E'(k,m) = E(k,E(k,m))$.

How would one prove that $E'$ is not necessarily secure even if $E$ is?

It doesn't make sense to me. If you consider the advantage of an attacker $\mathcal{A}$ over a semantically secure cipher $E$, you have $SSadv[\mathcal{A},E] = \epsilon$, where $\epsilon$ is negligible.

If you call for $E(k,E(k,m))$, you should have $E(k,E(k,m)) = E(k,c)$, where $c$ is $\epsilon$-distant of being random, so you give an advantage of $\epsilon$ to the attacker.

When you compute $E(k,c)$, analogously you give another advantage of $\epsilon$ to the attacker, so you give an overall advantage of $(\epsilon + \epsilon)$, and such a sum would be negligible as well.

Summarizing the answer from the comments:

what happens if E is a stream cipher? ~ Richie Frame
What if you use exclusive-or to combine the key stream instead of addition? ~ Ella Rose
So $c_i=m_i\oplus k_i\oplus k_i=m_i$, and it would be trivially broken. Thanks! I wouldn't come up with the idea of using a stream cipher nor modifying the one-time pad like this. ~ Daniel


Why can't we find $d$ if we know $e$ and $n$ in RSA? Say, we have RSA public key $(n,e)=(221,7)$,

and the encryption of the message $m=12$ is $$c=m^e \bmod n= 12^7 \bmod (221) = 194 \bmod (221)$$

Can we find the $d$ by solving the equation;

$$194^d \bmod(221)=12$$

I get that the numbers I used are way smaller than they are in real life, but this should be easier then just guessing $p$ and $q$ from $n$ right?

There are "hidden unknowns" in the notation. Suppose that $n$ is the modulus, $e$ the public exponent, $d$ the private exponent. Given a message $m$, its encrypted value is $c = m^e \bmod n$ (I am ignoring padding here), and you can certainly choose a message $m$ and compute $c$ given the public elements $e$ and $n$ (that's how RSA encryption works). Now, you might want to find $d$ by solving the following equation:
$$ c^d = m \bmod n $$
with only $d$ being unknown.

When working with real numbers, an equation of the form:
$$ a^x = b $$
for given values $a$ and $b$, is solved as:
$$ x = \frac{\ln b}{\ln b} $$
and you could imagine that "solving RSA" is just a matter of computing logarithm with the required precision.

However, this would neglect an important part, which is somewhat hidden in the notation. When we work "modulo $n$", we are actually having the following:
$$ c^d = m + kn $$
for the known ciphertext $c$, message $m$ and modulus $n$, unknown private exponent $d$, and unknown integer $k$. At that point, you have a single equation with two unknowns, and the usual tools of analysis with real numbers (e.g. logarithms) won't help at all.

In all generality, RSA is expressed in algebraic things such as rings of integers modulo $n$, and all equation solving activities in such things have their own rules, quite distinct from what you may have learned with real numbers. Obtaining $d$ from $e$ can be done relatively easily when $n$ is prime, but, of course, the crux of RSA is that $n$ is not prime.

We do not have any proof that factoring $n$ into its factors is really required to recover an unknown plaintext from the ciphertext. We do know that recovering the private exponent $d$ is equivalent to factoring $n$ (i.e. if you factor $n$ you can easily obtain $d$ from $e$, and if you somehow obtained $d$ and $e$ you can easily factor $n$); but there could be a method by which a ciphertext can be decrypted without revealing the private exponent itself. Right now, factoring $n$ is the best attack we know of; and factoring big integers is a problem that has been studied for quite some time (more than 2500 years, in fact), and the only sure thing we know is that there is no obviously easy solution. There might be an efficient factoring method, but it is definitely not obvious.


Robust cryptosystem for files/chunks protection? I'm not a cryptographic expert by far but I do understand that when it comes to cryptography it's best to stick with established standards.

I have to ensure confidentiality and integrity of a bunch of files (chunks of these files actually).

Getting inspiration from "serious" people, AES-GCM with distinct IVs and keys for each chunk seems the way to go since it provides both confidentiality and integrity, and is good performance-wise.
It also seems a good practice to encrypt each chunk key with a Key Encryption Key that has to be renewed on a regular basis.

Here are my questions:

Did I get it right up to this point?
Are there specific ciphers for encrypting each chunk key with the KEK? Does it require to use an IV since there shouldn't be two identical chunk keys?
What are the good practice/standards to protect the KEK on a server without dedicated hardware such as an HSM?

PS: I'd be glad to take a look at any ressource available and accessible to non-experts on that topic.

I'm looking at a very similar thing, where I need to encrypt data at rest, and the existing file structure that I'm trying to add encryption to is randomly accessed chunks / blocks of binary records.

The file IO I'm working with is performance sensitive, and the binary structure caters for allocating and freeing record space within these chunks.  It is in an embedded environment, so the desktop storage encryption solutions can't be applied.

I looked at AES-GCM after seeing many recommendations for it.  But the NIST guidelines for its use, which require unique IVs for a given key, make it challenging for storage encryption.  Somewhere I read that AES-GCM is better suited to transport encryption.

I'm currently heading down the path of AES-CBC + AES-CMAC, due to less stringent requirements around key and IV re-use.  Having a file key and chunk IVs from a CRNG seems to be acceptable.  Again, I'm new to this as well, so I'm happy to be told otherwise.  I'm just on here researching the process of deriving keys for encryption vs MAC generation from a common key.

I was tempted by OpenSSL's EVP_aes_256_cbc_hmac_sha256, but then the docs have a warning that it was only intended to be used internally by OpenSSL's SSL/TLS.  It would be nice to find the "shrink wrapped" answer to take care of all this.

Key storage without an HSM can be challenging, especially if there is no user involved.  In a desktop environment, a key derived from a passphrase (KDF) is the traditional solution.  A "logon secured" encryption scheme can also be used (e.g. Microsoft's DSAPI). Without that, I think it becomes a chain of "where to keep the key that encrypts the key...", which I haven't yet seen a good answer for.

Securing keys with another layer of encryption is called key wrapping.  I've seen code that uses AES to encrypt one key with another as a simplified version of this.


Ciphertext length in TLS 1.3 additional data RFC8846 says:
..and the additional data input is the record header.

   I.e.,

      additional_data = TLSCiphertext.opaque_type ||
                        TLSCiphertext.legacy_record_version ||
                        TLSCiphertext.length

But the length of the encrypted text (which is the length field in the record header) is not known until the encryption is done. It looks to me like a chicken and egg situation.
Question is, what I am missing here ?
Thanks.

the length of the encrypted text (which is the length field in the record header) is not known until the encryption is done

The length of the ciphertext is known as soon as the length of the plaintext is known. This is true for any non-broken encryption mechanism. An adversary can easily observe the length of the ciphertext, and if that allows the adversary to deduce anything about the plaintext other than its length, it's a weakness in the encryption.
All the standard AEAD mechanisms for TLS 1.3 (CCM, GCM, ChaCha20+Poly1305) are constructed in such a way that the ciphertext is the application of a stream cipher to the plaintext, followed by a one-time MAC (the authentication tag). Thus the length of the ciphertext is the length of the plaintext plus the tag length of the mechanism (16 for GCM, CCM and ChaCha20+Poly1305; 8 for CCM_8). RFC 8846 is worded in a more general way that would allow AEAD mechanisms with a more complex construction. But whatever the mechanism is, there is a way to calculate the ciphertext length from the plaintext length, although it could be harder than adding a constant.


Poly1305 Key for MAC generation I just went through https://tools.ietf.org/html/rfc7539#section-2.6 (sections 2.5 and 2.6). There it is described how to generate one-time Poly1305 keys using the ChaCha20 block function (for this a 96-bit nonce is required).

I am asking myself how this is "better" or "more secure" in comparison to just use the key that is used for the ChaCha20 block function.

You wrote in the comments:

  no, I am only interested in the MAC generation using Poly1305 with a key that is always been freshly generated for each execution of the MAC function. The key is derived using an HKDF with a shared DH key and a random value for each execution (e.g. a nonce).

In the same RFC that you mention it is written (quoting Bernstein's paper):

  The original article ([Poly1305]) is titled "The Poly1305-AES
     message-authentication code", and the MAC function there requires a
     128-bit AES key, a 128-bit "additional key", and a 128-bit (non-
     secret) nonce.  AES is used there for encrypting the nonce, so as to
     get a unique (and secret) 128-bit string, but as the paper states,
     "There is nothing special about AES here.  One can replace AES with
     an arbitrary keyed function from an arbitrary set of nonces to
     16-byte strings."

Now you've got HKDF, which is a keyed function, a nonce and an output which can be made 16 bytes. I say: go for it, but don't use the key for anything else, including ChaCha20 encryption or worse, calculating another authentication tag.

Just for reassurance: do please use SHA-256 or better for HKDF. Then it should be just as secure.

Do remember that you're now in unchartered territory. That means using libraries to implement this kind of functionality will be harder, compared - for instance - to just using the AAD of a ChaCha20/Poly1305 cipher to calculate a MAC.


Must root certificates be self signed? Root certificates are normally self-signed.
What is the reason behind that convention?
I mean, one must trust the root certificate in a non cryptographic way anyhow.

Among the reason why root public keys are often expressed as a self-signed certificate are:

It cryptographically protects against a deliberate alteration of an attribute of the public key (e.g. extension of validity period, or of what the key can be used for).
It strongly protects against accidental alteration of the public key value.
It is a reasonably effective countermeasure against some deliberate alterations of public key value or attributes, e.g. fault-injection attack.
It makes it easier to have all public keys share a single common format, complete with attributes.
Public keys are usually generated by an entity distinct from the entity or entities that will certify it, and thus if we want to leverage the above benefits must be self-signed at some point. Now if there is no authority to certify that key (as is the case for a root CA key in a system with a single and independent root CA), it will just stay that way.

However, not all implicitly trusted or root public keys exist as a self-signed certificate, much less exist only in this form. For example, the public key of the European Root Certification Authority of the Digital Tachograph system is not available as a self-signed certificate (which could be made), for good reasons:

the relevant legal text does not provide that the key could be used to certify itself:

  [CSM_007] At European level, a single European key pair (EUR.SK and EUR.PK) shall be generated. The European private key shall be used to certify the Member States public keys. Records of all certified keys shall be kept. These tasks shall be handled by a European certification authority, under the authority and responsibility of the European Commission.

there would be a chicken-and-egg problem accessing the content of an hypothetical self-signed certificate of that key, for Digital Tachograph certificates use a signature scheme with message recovery (as many Card Verificable Certificates do), and part of the public key is in the recoverable part of the signed message.


Encrypt hash using hash of hash? I wonder what is wrong with this scheme for authentication.

Server sends random challenge, C
Client returns (C, B(P)) encrypted in H(B(P)) where B(P) is high work factor salted hash of the user passphrase (e.g., bcrypt), and H() is a low work factor hash
Server has K = H(B(P)) in database, and can use it to decrypt (C,B(P)) and verify that H(B(P)) = K and that C is equal to the challenge

I wonder is B(P) adequately protected by encryption in key = H(B(P)) when sent over the network?  Or, other problems?

EDIT:  Let me clarify based on comments.  I obscured the main question by splitting the password hash function into 2 stages.  I think the answer to my question is the same if there is no B(P) and H() has high work factor.  So, client is submitting (C,passphrase) encrypted in H(passphrase).  Server knows H(passphrase), as in typical password authentication, so can decrypt.  Then can compute H(passphrase) to verify client knows passphrase.  It is like classic bcrypt based authentication, but using H(passphrase), rather than SSL, to secure the transport.  My concern is how to safely do encryption when the key is derived from the data being encrypted.

The reason for the 2 stage H(B(P)) in my original question is to minimize load on the server, which is the main aim of the protocol, to allow run of the mill hardware to separate wheat from chaff in face of gbps DoS attacks.

EDIT2:  Also, I left out how the server proves to the client that it also knows K, which is necessary to prevent active man in the middle.  In step 2 the client includes a random session key encrypted in K, which is used to compute a message authentication code on all subsequent messages, including the server return.

So your idea is that the client does the work in calculating the slow hash $B(P)$, and proves that to the server by using a hash as an encryption key. It is definitely not a standard way to do things, and has some problems.

In particular, any eavesdropped can trivially launch an offline dictionary attack on the password, so it is like your normal password database was constantly compromised (which should normally lead to "change your password" emails being sent). That means any passwords that are simple enough to be attacked are completely unprotected.

Instead, I would second the suggestion of using TLS. Even if you can come up with a strong password authentication system that works in the clear, you need authenticated encryption to prevent eavesdroppers from reading the authenticated content etc.

If TLS is simply out of the question, you could use SRP. It, too lets you offload all the hard work of using e.g. bcrypt to the client, by using as B(P) as the SRP password: the server only uses the verifier, meaning it does not need to do the calculation. Unlike your protocol, it prevents both passive attacks on the authentication (as well as MITM). However, you should use the agreed key to authenticate and encrypt the rest of the session, or an attacker can just jump in at that point, so complexity is not that much less than TLS.

(You mention patent concerns. IANAL, but Stanford has a royalty free patent grant for implementing RFC 2945, and anyway the patent may already have expired.)


Does AES-GCM without security tag turn into regular CTR Mode? We are looking to implement a simple password based key agreement scheme. Part of this is deriving a symmetric key from a common passphrase known to both parties involved.

This symmetric key is then used to encrypt an ephemeral public key A and the resulting ciphertext is then sent to the other communication partner who does the same with his public key (B). Both sides then calculate the common secret using a regular Diffie-Hellman approach (both sides also include two additional static keys)

Both sides then complete a key confirmation step in which they assert that the common secret is indeed common and no man in the middle is between them.

Since the public keys A and B are randomized, an attacker should not be able to run a brute force attack on the password used to derive the symmetric key since an attacker should not be able to determine whether he has succesfully guessed the correct password as the output of the decryption function should also be random no matter what key is used to decrypt the random public keys.

Is this a safe assumption to make?

Now to the question stated in the subject line:

There is already an implementation of an AES-GCM mode as authenticated encryption scheme in existence to ensure integrity and confidentiality of exchanged ciphertexts. As stated in the previous paragraph this mode of operation would allow an attacker to have access to a sort of oracle to start an offline attack on the password used during the encryption process of the public keys and is therefore not suitable for that specific task.

The question therefore is:

If we use the implemented AES-GCM mode but without security tag (TAG_SIZE 0 bit) does this make the cipher behave like regular CTR mode as to the attacker can no longer start guessing passwords and knowing whether he has guessed the correct one and thereby losing this potential oracle?

/edit: To clarify: We plan to implement EAP-EKE as key exchange protocol (https://tools.ietf.org/html/rfc6124) I thought this to be not essential to the question in the title. In my understanding the protocol relies on the described behaviour (not being able to distinguish a correct password guess from an incorrect one) to guard against dictionary attacks on the password.

I'll keep to the final question as security evaluating the entire scheme would be off topic:

  If we use the implemented AES-GCM mode but without security tag (TAG_SIZE 0 bit) does this make the cipher behave like regular CTR mode as to the attacker can no longer start guessing passwords and knowing whether he has guessed the correct one and thereby losing this potential oracle?

Yes, GCM would then just get you CTR mode, but with a specific way of calculating the initial counter: $n << 32 + 2$ where $n$ is the encoded nonce, shifted left 32 bits (multiplied with $2^{32}$), and then added the value 2 in the zeroed, least significant bits. The proof is in the implementation.

Notes:

The implementation I pointed at uses a (GCM default) nonce of 12 bytes; if you do not do that then calculating the initial counter will get more complex.
Not all libraries will allow a tag size of zero as that obviously falls outside the acceptable range for the size of the authentication tag $t$.

Off topic, some remarks on using GCM in your protocol:

As others have commented, creating (or in this case hacking) your own protocol is probably not the safest thing to do; there are already schemes out there that will do this for you. And just using CTR instead of GCM should be preferred if you go with this scheme.

Beware that the decryption will always succeed, but that parsing / handling the plaintext may still result in an oracle. E.g. if you encode a number and send it then decoding could possibly fail, resulting in an oracle.


Deviation from CCM specification - security impact? The following question is about a specific protocol that uses a modified version of the CCM mode. Since I'm not a cryptographer, the protocol specification provides no reasoning for this change to CCM or proof of security, I'd like to know if this might have any practical or theoretical implication for the security of the encryption and authentication.

In NIST 800-38C and RFC 3610 the CCM mode creates the $S_0, ..., S_m$ by encrypting the counter blocks in the following way:

For $j=0$ to $m$, do $S_j=CIPH_K(Ctr_j)$

Then the $S_1$ to $S_m$ are concatenated to form $S$. Note this doesn't use $S_0$:

$S = S_1 || S_2 || ... || S_m$.

The encryption of the plaintext $P$ is done by xoring it with the $Plen$ most significant bits of $S$ and the MAC $T$ is xored with the $Tlen$ most significant bits of $S_0$:

$C = (P \oplus MSB_{Plen}(S)) || (T \oplus MSB_{Tlen}(S_0))$

The step where the protocol in question deviates from the standard CCM is in the construction of $S$. It includes $S_0len - Tlen$ of the least significant bits of $S_0$ into $S$.

$S = LSB_{S_0len - Tlen}(S_0) || S_1 || S_2 || ... || S_m$

The ciphertext is still created through:

$C = (P \oplus MSB_{Plen}(S)) || (T \oplus MSB_{Tlen}(S_0))$

It is ensured that the $MSB_{Tlen}(S_0)$ and $LSB_{S_0len - Tlen}(S_0)$ never overlap.

In my layman's eyes it seems like a strange change. However, since the $Ctr_0$ is constructed in the same fashion as the other counter blocks and the particular bytes used for xoring aren't that same between the encryption and authentication, it might not degrade security? Is there any obvious reason why someone would want to include parts of $S_0$ into the encryption?

The reason why $S_0$ is not used by the encryption is because it is already used by the final calculation of the authentication tag:

  The authentication value U is computed by encrypting T with the key
     stream block S_0 and truncating it to the desired length.

 U := T XOR first-M-bytes( S_0 )

So yeah, the protocol simply uses the leftover bits of the first block of the key stream. These should be unpredictable to the adversary, so I don't see any issue using them.

It obviously is slightly more efficient when it comes to the amount of block operations for some messages. This makes most sense for small messages on limited machines where the block operation takes more time than all the rest of the calculations and 16 byte alignment doesn't matter. If the messages are all of a specific size then it might remove one block operation for each message.

All in all, using bits from the keystream that are otherwise not used is fine. For me, I would wonder if it is worth deviating from a standard for it, but that isn't a question of security but of interoperability. You'd have to start by writing or adjusting an algorithm, so that in itself may be enough reason to discard it.

It of course also assumes that the tag size is smaller than 128 bits, and undercutting the tag size in itself is dangerous as well (although it doesn't have the same security implications as for e.g. GCM). If the tag size is 128 bits then the entire block is used and the scheme is just normal CCM again.


How often to reseed the NIST CTR_DRBG with AES256_CTR Even at a high consumption rate of 100,000 generations per second, it would take decades to exhaust the NIST recommended reseed interval of 2**48 invocations of DRBG _generate(). Should one even care to reseed?
(REF: NIST SP 800-90A, Rev 1.0)

As usual, the answer is: it depends.

It mainly depends on two factors:

Do you have a source of entropy and how good is it?
What's your environment and your threat model?

The benefit of re-seeding your DRBG should be clear: If the state of your DRBG gets compromised at any point, an attacker can re-compute all the outputs of the DRBG following up until the last reseed which limits the damage in case of an successful attack.

Now for the question you may have: Can a re-seed hurt security? No, it can't because information from the last DRBG state is included, transferring initial entropy into the new state and adding new entropy.

So for the first point: Assume you have a good RNG, then re-seeding as often as possible is a good idea that highly limits the risk associated with a state-compromise. If you however have a bad RNG or none at all, you could still try to re-seed, but then it's also a question of the effort involved in doing the re-seed and whether this effort is worth the minimal gain.

Now for the second point: The threat model. This really is your answer to the question: "what access to my device(s) does the attacker have?". If you have secure hardware for the DRBG and an attacker can at most get software-level access or only have a remote view, chances are that a state-compromise won't happen. If the attacker however can get hands-on with the device and try all their best in extracting the state (as you'd be able to with a stolen smart card for example), then advanced attacks like DPA need consideration. If you're sure that such advanced attacks aren't realistic (because breaking the RNG wouldn't outweigh the cost of developing and deploying these attacks), then you can go without a re-seed. If an attacker has a motivation to try really hard to get into the device they'll probably try all those attacks and depending on how good the secured hardware is, chances are they'll succeed.


Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? Linear Feedback Shift Registers (LFSRs) can be excellent (efficient, fast, and with good statistial properties) pseudo-random generators. Many stream ciphers are based on LFSRs and one of the possible designs of such stream ciphers is combining outputs of $m$ LFSRs as input of a boolean function $f:GF(2)^m\rightarrow GF(2)$. This last function has to be carefully selected.

My question is a rather elementary one. I understand that using one LFSR to produce the keystream is not appropriate as one can create the whole keystream by knowing a tiny fraction of it: if the tap positions of a length $n$ LFSR are known, one needs $n$ bits to determine the entire keystrem sequence, and if they are not known, one needs $2n$ bits (by using the Berlekamp-Massey algorithm to find out the tap positions). However, why do we need a non-linear combination of LFSRs (among all sorts of other requirements)? What would be the problem of getting a number of LFSRs with appropriate lengths and tap positions and XOR together their output to produce the keystream?

The Berlekamp-Massey algorithm is an iterative method for finding the shortest LFSR that can generate
a given sequence of bits. The given sequence might or might not be generated by
an LFSR: the Berlekamp-Massey algorithm does not care. It just finds the shortest
LFSR that can generate the given sequence, and if the sequence has been generated
by an LFSR of length $n$, then the Berlekamp-Massey algorithm is guaranteed to find
this LFSR after examining no more than $2n$ bits of the sequence.  A simplistic
description of what happens is as follows.
After the algorithm has found the shortest LFSR that generates the first $k$ bits of the sequence, it examines the $(k+1)$-th bit of the
sequence. If this $(k+1)$-th bit of the
sequence matches the $(k+1)$-th bit of the output of the current LFSR, the
LFSR is accepted as the one that generates the first $k+1$ bits. If not, the LFSR is
updated so that the new, typically longer, LFSR generates the first $k+1$ bits.
As stated earlier, if
the sequence in question was in fact generated by an LFSR of length $n$, then
the Berlekamp-Massey algorithm is guaranteed to find this LFSR  by the time
it has examined $2n$ bits of the sequence.  How does the algorithm know that it
is done? Well, it doesn't, but after the correct LFSR has been found, the $(2n+1)$-th,
the $(2n+2)$-th, the $(2n+3)$-th, $\ldots$ bits of the given sequence match the
corresponding outputs of the LFSR and so the Berlekamp-Massey algorithm does
not update the $n$-bit LFSR it has found.

What does all this have to do with the question asked?  Well, the
(bit-by-bit XOR) sum of the
outputs of the various LFSRs is a sequence that is generated
by a longer LFSR (typically, the length of the longer LFSR is the sum of
the lengths of the LFSRs whose outputs were summed). So, the cryptographic
security is not significantly larger. What is needed is some way of
combining the constituent LFSR outputs so that the resulting sequence
has linear complexity much larger that the sum of the LFSR lengths.
The linear complexity of a sequence is defined as the length of the
shortest LFSR that can generate the sequence.
What we want is a sequence that has high linear complexity
but which can be generated easily
as a nonlinear function of the outputs of short LFSRs. The
legitimate users of the system can encipher and decipher
easily, but a cryptanalyst attempting to break the system
via a known plaintext attack has to either figure out
the nonlinear function (and the constituent LFSRs) which is
not easy to do or
attempt a Berlekamp-Massey algorithm attack which may fail
because not enough bits of the sequence can be determined
via a known plaintext attack to
find the shortest LFSR that generates the sequence.


How to customize a standard encryption algorithm? I want to modify and customize AES encryption algorithm and develop a variant of it. What factors should I consider so that it does not become weaker? What skill sets would be required to undertake this task? How complicated can it get?

The comments on the question are very good. That said, I'll try to address the question(s).

  What factors should I consider so that it does not become weaker?

This is a very important concern that I am glad you have. One of the big strengths that standard ciphers have is that lots of really smart people have looked at them and have not been able to break them. See Schneier's Law -- "Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break."

So normally the answer to this question would be to publish the details of the modification so that other cryptographers can analyze them and determine whether or not security has been weakened due to your modifications. Based on your comments, however, it sounds like that might violate other design constraints (BTW, I agree with the other commenters that keeping your algorithm secret is a poor choice). So, instead, I'd recommend hiring a group of experts to review the design and point out any fatal flaws. Actually, what I'd really recommend is that you use standard ciphers and just keep the key secret.

  What skill sets would be required to undertake this task?

Years of experience breaking ciphers. There are lots of ways to gain this expertise, but no shortcuts. It will take years of experience. That said, what modifications you make will have a great impact on what experience you need. For example, could the changes possibly create side-channel attacks? If so, you need that experience. The less you change the better and the easier it will be to do the analysis, but at the same time, the less you change, the more I have to wonder why you are changing anything at all. Make sense?

  How complicated can it get?

Depends on what you do. It could get very, very complicated. To the point that you are really not changing things and really creating a new cipher.

For a recent example of an "updated" cipher, I suggest you look at the Spritz cipher. It is an "update" to RC4. Maintains similar structure to the RC4 cipher but has very significant modifications. Also, take a look at this paper which claims statistical weaknesses in Spritz. See, even seasoned pros can potentially get things wrong when updating/modifying a standard cipher. This also is a good example of why publishing your cipher is a good thing.


How to choose keys for a block cipher? AES and DES are block ciphers. Mathematically, its the mapping from plaintext space to ciphertext space using the keys i.e. $\{{0,1}\}^k$ x $\{{0,1}\}^l \longrightarrow \{{0,1}\}^l$

I know that these keys are random. What I want to know is how these are calculated in real world and is there any way to change these keys meaning that is it possible for me to use my own keys in these block ciphers?

In contrast to asymmetric schemes (notably RSA and El Gamal) which require some sort of computation to generate the key, the only constraint one has when selecting a key for DES or AES (or 3DES) is to make it look indistinguishible from a random stream. That said both El Gamal and RSA require some randomness in key generation, but that phase does not depend just on that.

You could however use any byte stream of sufficient length as a key, irrespective or randomness, at your peril. That's because the security of these schemes (of all schemes really) depends on the inability of some adversary to compute or guess the key in some practical timeframe. It's worth mentioning here that DES keys can be (and have been) efficiently brute-forced because they are short in length. Search this site for randomness test or take a look at the randomness tag to get a better idea.

In practice it's possible to derive a key from a password, passphrase or a random stream of smaller length by using a key derivation function. You may also use any CSPRNG to generate a long enough stream, which you can use as a key.


ASCII input to HMAC weaker than raw bytes? In various cryptographic programs I've written (most have been toy problems, but this current one is not) I have taken a slothful approach to performing a message digest (hash) of numerical input. I have been casting the numbers to strings, concatenating them, and then performing the hash. (Actually, this is a keyed hash, or HMAC, as described in RFC_2104.)

Example:

# I desire to hash a single bit with a sequence number.
# bit is either 0 or 1
# sequence_number is some 64-bit number.
# key is some 32-bit number/value used to create an HMAC.
make_HMAC(key, str(bit) + str(sequence_number))

# make_HMAC works on longs as well, but would become ambiguous because:
# make_HMAC(key, 0 + sequence_number) == make_HMAC(key, 1 + (sequence_number - 1))

I've been avoiding ambiguity, but I worry that I've weakened the strength of my hashing functionality in a subtle way.

Does casting these values to a string cause the HMAC to become less secure in any way?

If it matters, I'm using python 2.7 and the pycrypto library.

In one sense, no, encoding should not have an impact on security of HMAC.

On the other hand, it could have an application dependent impact.

Consider the following. '26' and 26 have the same HMAC. Now, assume your code receives a message, M, and an HMAC, MAC, and then does something like this

if HMAC(M, private_key) == MAC:
  if isinstance(M, basestring):
    grant_admin_privileges()
  else:
    grant_non_admin_privileges()
else:
  raise Exception('Bad HMAC')

Well, now obviously you are in trouble.


Encryption and decryption with Diffie-Hellman I don't understand how it works. I only found explanations about the key exchange, but what about the actual encryption and decryption?
Do you use the session key $K$ with a symmetric algorithm?
Do you use something similar to RSA like $m^d \bmod n$?

The purpose of Diffie-Hellman is solely to establish a shared key, $K$.  Taken from Wikipedia:

  Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical means, such as paper key lists transported by a trusted courier. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

I bolded the segments above to point out two things that I think are worth calling out here:

$K$ is being created over a public, insecure channel.  That is really the core benefit of a Diffie-Hellman key exchange.
There is no requirement that you use the shared key for anything in particular.  $K$ could be used to encrypt further communication, but could also be used as a seed to a pseudorandom number generator, or in any other case where establishing a shared piece of secret data might be useful (and, again, where it is beneficial to do so effectively in public).

So while Diffie-Hellman is often used to permit encryption and decryption of data, the actual use of $K$ is left to the two parties involved to decide.

Additionally, as pointed out by @fgrieu in a comment, it is often wise to pass $K$ through a key derivation function in order to limit any weakness caused by the mathematical nature of the shared secret, or to expand the shared secret to a desired length (e.g. so it can be split it into several keys to be used for different purposes).  So even where $K$ is used to facilitate encryption, it is often not used directly as a symmetric key.

As pointed out by @ComFreek, Diffie-Hellman does not inherently provide authentication of the other party, opening it up to the possibility of man-in-the-middle attacks.  If the keys involved are previously known or able to be verified through a PKI system, Diffie-Hellman is sufficient.  But if you are not able to directly verify the authenticity of the public key, the rest of your protocol should include some form of authentication that the other party is the who you believe it to be.


Does failure of indistinguishability of encryptions imply lack of CPA-security? Suppose we have an encryption scheme that fails the indistinguishability of encryptions test. That is, given messages $m_0, m_1$ and a ciphertext $c_b = Enc_k(m_b)$, where $b \in \{0, 1\}$, the distinguisher $D$ can extrapolate which message was encrypted. Here $D$ has the advantage of knowledge of what the messages are.

In CPA test however, after observing a set of (plaintext, ciphertext) pairs we are presented with a previously unobserved ciphertext. Our task here is not to distinguish (there is nothing to distinguish from...) but rather to decipher.

My question is, does failure of indistinguishability of encryptions imply lack of CPA-security?

Faliure of indistinguishablity of encryptions under a eavesdropper does imply faliure of indistinguishablity of encryptions under a chosen-plaintext attack. But the converse is not necessarily true (ex. OTP)
The aim of CPA-secure is not to decrypt previously unobserved ciphertext but to pass the distinguishability test after a set of (plaintext, ciphertext) observations.


What happens if you multiply a point with its order on complete Edwards curves? I was recently working with some ECC crypto and stumbled across the following phrase on the SafeCurves page:

  The rational points of a complete Edwards curve are the pairs (x,y) of
  elements of F_p satisfying the equation; there is no extra "point at
  infinity".

Normally, if you have a point $G$ on a curve $E$ with order (of the point) $q$, multiplying $qG=0G=\mathcal O$ results in the point at infinity.

But apparently complete Edwards curves don't have said extra point.

So what happens in this case?

Actually multiplying an elliptic curve point $G$ by its order $q$ gets you to the neutral element of the group, i.e., the point $O$ such that $P+O=P$ for any point P.

In a generic elliptic curves this point is the point at infinity $O$. However on Edwards curves, this point is $(0,1)$, i.e., it can be represented by affine coordinates. This is also stated on wikipedia.

Therefore, multiplying a point by its order, on an Edwards curve, gets you the point $(0,1)$

This means that on Edwards curves: $P+(0,1)=P$ for any point $P$.