What is a "constant time" work around when dealing with the point at infinity for prime curves? I've been working for some time, on designing a constant time solution for dealing with the "point at infinity" for prime curves. So, far I'm using the Standard Projective Coordinates for doing fast, Point Addition and Doubling operations, and my implementation uses a "window" approach to do scalar multiplication.
But, I do not know, how to implement addition with the point at infinity in such a way, that it takes the same amount of time, as any other point.
void PointAdd(POINT * R, POINT *P, POINT *Q ) // has many more args
   like curve etc.
{
     if(zero(P->z)) {
         copy(R, Q);
         return;
     }
     if(zero(Q->z)){
         copy(R, P);
         return;
     }
     /*Do other calculations*/
}

Since the z coordinate is an important entity in the Elliptic curve point addition formulas for projective coordinates, it being zero, makes the equations result in a wrong answer, if we plug such a point for PointAdd function unless both $P=Q=O$. I believe, that this if ... else  like checking will crush my implementation's purpose, of being side-channel resistant.
Is there a constant time solution to circumvent this, in a side-channel resistant way, or are there coordinate systems/addition-doubling formulas, that intrinsically, support the operations with the point at infinity $(0:k:0)$, where $k$ is an element of $F_{p}$?

Introduction
Dealing with the neutral element $\mathcal{O}$ of an elliptic curve in Weierstrass form is a major problem in implementations. This is due to the fact that this point has no affine representation on this form of elliptic curve and is called the infinity point.
This point can still be written using projective coordinates. Noting $x=X/Z$ and $y=Y/Z$, the equation of the elliptic curve defined by $y^2 = x^3 + ax + b$ becomes:
$$
Y^2Z = X^3 + aXZ^2 + bZ^3.
$$
An affine point $(x,y)$ has the representation $(X:Y:Z)$ where $Z \neq 0$ (and can have as many representation as there are possible values for $Z$). When $Z=0$, then $X=0$, so the point $(0:k:0)$ with $k \neq 0$ is the only point at infinity and is the neutral element $\mathcal{O}$.
Then it might be tempting to use this representation of $\mathcal{O}$ in the formulas. Unfortunately for most of them it doesn't work.
To make an implementation constant-time relatively to the infinity point, I see two general methods:

Manage the point addition in constant-time;
Use an algorithm that avoids the infinity point.

Solution 1: dummy point addition
The basic idea is to compute a point addition and ignore its result when the infinity point is one of the inputs.
This is what the double-and-add-always algorithm does, but can be extended to other regular algorithms.
This can be implemented using booleans based on the coordinates $Z$ of the points, then applying the point addition normally. Then the computation is ignored if one of the boolean indicates that one of the points is $\mathcal{O} by replacing the computed values by the other input point.
For example, this is exactly how it is done for several curves in OpenSSL with a conditional copy that erases the calculated values:
copy_conditional(x_out, x2, z1_is_zero);
copy_conditional(x_out, x1, z2_is_zero);
copy_conditional(y_out, y2, z1_is_zero);
copy_conditional(y_out, y1, z2_is_zero);
copy_conditional(z_out, z2, z1_is_zero);
copy_conditional(z_out, z1, z2_is_zero);

Source
Advantage:

can be used for any algorithm (double-and-add-always, fixed window based algorithms).

Drawbacks:

Useless computation;
Vulnerable to C safe-error attacks (an attacker inject a fault during the point addition and if no effect are observed on the output of the scalar multiplication, then the attacker knows the infinity point is involved and may decude information on the scalar).

Solution 2: Complete point addition
On the Edwards form of elliptic curves, the neutral element is an affine point, so it is possible have point addition formulas that are complete as was shown in this paper.
The authors of this paper proposed formulas for prime order elliptic curves that are complete using projective coordinates.
Advantage:

Unified and complete point addition (works for any inputs including the infinity point).

Drawbacks:

A little more costly than other formulas;
Still vulnerable to C safe-error attacks: if $P = (X_1:Y_1:Z_1)$ is the infinity point, then line 10 of algorithm 1 in the paper becomes a dummy operation, so a fault on this operation with no effects means that the entry $P$ is $\mathcal{O}$ (I didn't check the other algorithms on the paper).

Solution 3: Montgomery ladder with XZ formulas
Montgomery ladder is an algorithm where the point addition always occurs between a point $P_1$ and $P_2$ that satisfy the invariant $P_1 - P_2 = P$ where $P$ is the input of the scalar multiplication.
The formulas presented below are taken from the page XZ coordinates for short Weierstrass curves (given by the equation $y^2 = x^3 + ax + b$) in the Explicit-Formulas Database.
There are two types of mixed differential addition. Those do not make use of the protective coordinate $Y$ of the points.
I present the one from mdadd-2002-it-4 and make the assumption that the input $P$ of the scalar multiplication is a point of odd prime order $q$.
An affine point $(x,y)$ is represented as projective coordinates $(X:Z)$ that satisfy $x = X/Z$, and the infinity point $\mathcal{O}$ by $(1:0)$.
Differential addition
The inputs are $P_1$ and $P_2$ given by their XZ representation $(X_1:Z_1)$ and $(X_2:Z_2)$, and $x$ is the affine $x$-coordinate of $P_1 - P_2$. The computation of the addition is given by
$$
\left\{\begin{array}{rcl}
X_3 & = & 2(X_1Z_2 + X_2Z_1)(X_1X_2 + aZ_1Z_2) + 4bZ_1^2Z_2^2 - x(X_1Z_2 - X_2Z_1)^2 \\
Z_3 & = & (X_1Z_2 - X_2Z_1)^2
\end{array}\right.
$$
Now we need to look at the possible exceptions with these formulas:
Case 1: $P_1 = P_2$.
This case means that $P = P_1 - P_2 = \mathcal{O}$, but we assume that $P$ is not the infinity point so it is impossible.
Case 2: $P_1 = -P_2$ and $P_1\neq P_2$.
Then $P_1 + P_2 = \mathcal{O}$. We have $Z_3=0$ and
$$
\frac{X_3}{Z_1^2Z_2^2} = 4\left(\left(\frac{X_1}{Z_1}\right)^3 + a\frac{X_1}{Z_1} + b\right) \neq 0
$$
because $P_1$ is not a point of order $2$. So $P_1+P_2$ is correctly computed as a valid representation of the infinity point.
Case 3: $P_1 \neq \mathcal{O}$ and $P_2 = \mathcal{O}$.
We have $Z_1 \neq 0$, $X_2\neq 0$ and $Z_2=0$.
Then $X_3 = 2X_1Z_1X_2^2 - xX_2^2Z_1^2$, $Z_3 = X_2^2Z_1^2 \neq 0$ and
$$
\frac{X_3}{Z_3} = \frac{2X_1Z_1X_2^2}{X_2^2Z_1^2} - x\frac{X_2^2Z_1^2}{X_2^2Z_1^2} = 2x-x = x,
$$
so $(X_3:Z_3)$ is a correct representation of $P_1+P_2 = P_1 + \mathcal{O} = P_1$.
Other cases:
$Z_3\neq 0$ and $X_3/Z_3$ corresponds to the correct $x$-coordinate of $P_1 + P_2$.
Doubling
The input is $P_1$ given by its XZ representation $(X_1:Z_1)$.
Then $2P_1$ is given by the formulas
$$
\left\{\begin{array}{rcl}
X_3 & = & (X_1^2 - aZ_1^2)^2 - 8bX_1Z_1^3 \\
Z_3 & = & 4Z_1(X_1^3 + aX_1Z_1^2 + bZ_1^3)
\end{array}\right.
$$
Case 1:
$P_1 = \mathcal{O}$. We have $X_1\neq 0$ and $Z_1 = 0$.
Then $X_3 = X_1^4 \neq 0$ and $Z_3 = 0$, which gives a correct representation of the infinity point.
Other cases:
We have $Z_3 \neq 0$ and $X_3/Z_3$ corresponds to the correct $x$-coordinate of $2P_1$.
Recovery of coordinate $y$
At the end of the scalar multiplication, we can reconstruct the complete affine coordinates of the output thanks to the following formulas.
Given $P=(x,y)$, and $(X_1:Z_1)$ and $(X_2:Z_2)$ the XZ representations of $P_1$ and $P_2$ such that $P_2 - P_1 = P$, then the following formulas gives a complete representation of $P_1 = (X'_1 : Y'_1 : Z'_1)$:
$$
\left\{\begin{array}{rcl}
X'_1 & = & 2yX_1Z_1Z_2 \\
Y'_1 & = & 2bZ_1^2Z_2 + Z_2(AZ_1 + xX_1)(xZ_1 + X_1) - X_2(xZ_1 - X_1)^2 \\
Z'_1 & = & 2yZ_1^2Z_2
\end{array}\right.
$$
Case 1: $P_1 = \mathcal{O}$.
We have $X'_1 = Y'_1 = Z'_1 = 0$ which gives an incorrect representation of the infinity point. However, in the case of Montgomery ladder it means the scalar is a multiple of the order of the input so it has no cryptographic impact.
Case 2: $P_2 = \mathcal{O}$.
This case means that $P_1 = -P$.
We have $X'_1 = Y'_1 = Z'_1 = 0$ which does not correspond to $P_1$.
Case 3: $y=0$.
It means $P$ has order $2$, so it cannot happen.
Other cases:
We have $Z'_1 \neq 0$ and $(X'_1 : Y'_1 : Z'_1)$ is a correct representation of $P_1$.
Wrap-up
The only cases to manage are:

The input $P$ of the scalar multiplication is the infinity point;
The input scalar is a multiple of the order: the coordinate $Z$ at the end is $0$ then the output is $\mathcal{O}$;
The input scalar is a multiple of $q-1$: only a problem for the recovery of the missing coordinate.

Solution 4: Algorithms that avoid the infinity point
One possibility is to recode the scalar $k$ such that the point additions always occur between two points that can never be the infinity point.
A classic fixed window-based algorithm separate the scalar $k$ in windows of width $w$:
$$
k = \underbrace{k_0  + k_1 2 + \cdots + k_{w-1}2^{w-1}}_{K_0} + \underbrace{k_w 2^w + \cdots + k_{2w-1}2^{2w-1}}_{2^w K_1} + k_{2w}2^{2w} + \cdots
$$
so the scalar can be rewritten as
$$
k = K_0 + K_1 2^w + \ldots + K_{d-1}2^{dw-1}.
$$
where $d$ is the number of windows to cover the whole scalar.
Every $w$ doublings, a point addition with the precomputed point $[K_i]P$ is done. When the window $K_i$ is null, it means it is the infinity point.
To avoid that, several papers proposed to recode the scalar such that the windows are always nonzero. To cite a few:

https://eprint.iacr.org/2004/342
http://www.bmoeller.de/pdf/ecc-sca-isc2001.pdf
https://link.springer.com/chapter/10.1007/3-540-36563-X_23

Personnally, I like the way it is implemented in Mbed TLS. It is a variant of the technique proposed in the first paper above where the windows are in fact combs (the bits of the scalar in a comb are not taken consecutively but separated by a fixed distance).
Advantage:

No need to manage the infinity point in the point addition.

Drawbacks:

The scalar must be recoded, so it is a little bit more complicated;
While the infinity point is managed, does the case $P_1 = P_2$ can appear during the scalar multiplication? (The answer is maybe and depends on the method and other parameters.)


Standard hash function of Linux So I went through my /etc/shadow file in Linux and discovered that my passwords were stored in SHA-512-based crypt ('sha512crypt') mode, so SHA-512. But why? I mean SHA-512 is not even a secure password hashing function. Why not bcrypt or Argon2 or scrypt ....
And how much iteration does this hash even have?

PS: Does $2$ "Blowfish" mean bcrypt ? And if yes, then why do they use the name of the block cipher?

Though not my normal recommendation, the SHA-512-based password hash as implemented in Linux is a fine password hashing algorithm.  It is based on a well-understood cryptographically secure hash (SHA-512). It has a significant size salt and configurable number of rounds (default 5000). I would not feel insecure with such a hashing algorithm.

$2$ is indeed bcrypt, but note there are several variants around sometimes marked 2a or 2b and sometimes not marked. So, though bcrypt is considered very secure if you need a standard password hashing function, you need to be careful when choosing bcrypt.


What does ChopMD refer to in the default Go ECDSA package? If one navigates to the ECDSA Go package page, he can observe that:

  This implementation derives the nonce from an AES-CTR CSPRNG keyed by ChopMD(256, SHA2-512(priv.D || entropy || hash))

While I am familiar with AES in CTR mode and SHA2-512, I am not familiar with what ChopMD refers to and I haven't been able to find any definite answer.

The only reference to ChopMD I have found is this PDF, showcasing how to improve ChopMD but never really going into detail as to who conceived it, why etc. MD commonly stands for Message Digest in the hashing functions but within the paper, MD refers to the Merkle-Damgaard construct, which is internally used by MD-5, SHA-2 and SHA-1.

If someone could clear up what ChopMD refers to I would appreciate it.

Let $n$ be the digest length of a hash function $\operatorname{MD}^f:\{0,1\}^*\to\{0,1\}^n$. Now quoting the paper you linked:

  chopMD. For $0\leq s<n$ we define $\operatorname{chop}_s(x)=x_R$ where
  $x=x_L\parallel x_R$ and $\left|x_L\right|=s$. In this paper we fix
  $0<s<n$ and define
  $\operatorname{chopMD}^f(M)=\operatorname{chop}_s(\operatorname{MD}^f(M))$.

So the idea is basically "take the value, run it through the specified hash function and discard ("chop off") the first $s$ bits", which is a pretty intuitive and standard ways to get a small-domain hash function from a large-domain hash function.

So TL;DR: It appears the package runs the given data fields through SHA-512 and then only returns the last 256 bit of the resulting hash.


80-bit security and attack time Many designer claimed that their cryptography scheme has 80-bit security. So how to calculate the time of attcking this 80-bit security cryptography scheme, such as 80-bit security RSA using a kind of CPU?

The question largely boils down to:

  What does $n$-bit security means in practice for a given value of $n$?

TL;DR: as secure as a good symmetric cipher with an $n$-bit key.

There's not a single more precise definition, even if we restrict to attackers using classical computers (rather than quantum computers), as this answer does.

One generally accepted meaning is that the number of "steps" to break the system is believed to be $2^n$; or more precisely that the probability to break the system with $s$ "steps" is not known to be more than $s\,2^{-n}$ by any method for any $s$. However "steps" and "break" are not precisely defined.

In theory of symmetric encryption,"step" is typically taken as one execution of the cipher with a new key. This way, an ideal cipher with a key of $n$ bits has $n$-bit security, under brute force key search. When we move to practice, attackers are not bound to brute force key search, and the definition of a "step" has to become a number of sub-steps comparable in number and computational cost to the sub-steps required for one execution of the cipher with a new key for a plaintext the size of the key. With this definition, a practical cipher with a key of $n$ bits has at most $n$-bit security, and aims at that ideal.

When we move to hashes, the definition of a step could become a number of sub-steps comparable in number and computational cost to the sub-steps required for hashing a new message the size of the hash output.

One of many problems with the above is that there is no agreement about if we should count or not the cost of memory and memory accesses in the computational cost. The safe thing from a user's perspective is not to count it, but that can be be of paramount importance for an attacker.

The definition of "steps" becomes even more murky when it comes to asymmetric cryptography like RSA. In theory, "steps" might be one computation in the algebraic structure used for the cryptosystem; like, for RSA, one evaluation of modular multiplication $(a,b)\mapsto a\,b\bmod N$ for arbitrary integer $a$ and $b$ in $[0,N)$, where $N$ is the public modulus. But there are problems moving this to practice, in particular for RSA: the best known attack is to factor the public modulus $N$ using the GNFS algorithm, which computational cost is dominated by operations having little similarity with modular multiplication, and of practical cost dominated by memory and accesses to memory. Which puts use back to the vague definition in the TL;DR.

  how to calculate the time of attacking this 80-bit security cryptography scheme, such as 80-bit security RSA using a kind of CPU?

"80-bit security RSA" is not to be understood as RSA with a 80-bit public modulus $N$, which is terminally insecure. If we had the size of $N$, we could estimate the difficulty based on that and previous experience (see this and its links). But we do not, and there is no consensus on the size of $N$ for RSA with 80-bit security: 1024-bit is often cited, but depending on hypothesis, and who you ask, that's grossly too much or too little. Thus the best is to ignore that we are talking about RSA, and get back to: as much time as needed to break a good symmetric cipher with a 80-bit key.

Which brings us to:
$$\text{Time}=\frac{2^n\times k\times p}{\text{Frequency}\times\text{Number-of-CPUs}}$$
where $n$ is the security level in bits, $k$ is an estimation of the number of CPU cycles to evaluate a good cipher using an ultra-optimized algorithm, and $p$ is the residual probability of success of an adversary. Depending on perspective we might take $k=1$ (which saves examining the particulars), $k=32$ (because that's still less than in the best attacks against good ciphers using a general-purpose computer), or much more. Depending on perspective, we can take $p=1$ (most prudent from a legitimate user's perspective), $p=1/2$ (yielding the expected time in the case of a block cipher), or a smaller $p$ if we want a security margin¹.

For example, with $n=80$, $k=1$, $p=1/1000\approx2^{-10}$, $\text{Frequency}=4\text{GHz}\approx2^{32}\text{s}^{-1}$, $\text{Number-of-CPUs}=1000\approx2^{10}$, we get $\text{Time}\approx2^{80-10-32-10}\text{s}=2^{28}\text{s}$, that is about 8 years. In other words, our 1000 CPUs have only a very small probability of success against 80-bit symmetric crypto, until they become technically obsolete.

On the other hand, 1000 CPUs is a tiny fraction of worldwide CPUs, and bitcoin mining conclusively shows that 80-bit crypto is no longer enough against adversaries with the capabilities to design ASICs, build them in massive quantities, and sustain the energy costs for their operation; see this.

¹ The $p$ term in the formula is the most prudent from a legitimate user's perspective, but it causes $\text{Time}$ to be underestimated in many attack scenario. For example, in collision search, the correct term would be more like $\sqrt p$.


Hashing or encrypting twice to increase security? Over on the bitcoin forums I asked why the bitcoin client computes SHA-256(SHA-256(x)) as its cryptographic hash for a variety of purposes. The leading theory--since the bitcoin author has disappeared--seems to be that from a security standpoint it could be sort-of analogous to upping the number of rounds in SHA-256 from 64 to 128, thereby providing a margin of safety as it is probable that the first preimage attack against SHA-256 (if such a thing exists) wouldn't work against SHA-256(SHA-256(x)), giving time to transition to a new hash function.

First of all, is that true? Would hashing twice make it any more difficult to mount a preimage attack, at least for certain types of attacks?

If the answer is yes, my related question is: is there a mode for encrypting twice to provide a similar increase in security? How would one feed the result of the 1st round of encryption into the setup of the 2nd (or 3rd)? Would you use the same key twice? Would you derive the 2nd key from (a hash of) the ciphertext of the first round (and the 3rd round from the 2nd, etc.)? Would you need an odd number of rounds and alternate Encrypt(Decrypt(Encrypt())) like Triple-DES does to prevent a meet-in-the-middle attack? How would this interact with the various modes of symmetric key encryption? Anything else I'm not thinking of that I would have to know about this if I were to implement it in a real product?

SHA-256(SHA-256(x)) was proposed by Ferguson and Schneier in their excellent book "Practical Cryptography" (later updated by Ferguson, Schneier, and Kohno and renamed "Cryptography Engineering") as a way to make SHA-256 invulnerable to "length-extension" attack. They called it "SHA-256d". We started using SHA-256d for everything when we launched the Tahoe-LAFS project in 2006, on the principle that it is hardly less efficient than SHA-256, and that it frees us from having to reason about whether length-extension attacks are dangerous every place that we use a hash function. I wouldn't be surprised if the inventors of Bitcoin used it for similar reasons. Why not use SHA-256d instead of SHA-256?

Note that the SHA-3 project required all candidates to have some method of preventing length-extension attacks. Some of them use a method that is rather like SHA-256d, i.e. they do an extra "finalization" hash of their state at the end, before emitting a result.


Is SHA-256 a bijective function? I suppose this question addresses surjectivity and injectivity. We talk about collisions but did we prove yet rigidly that this function is not reversible?
EDIT: Accepting the answer based on Dirichlet Box Principle (if domain is bigger than codomain innevitably there will be collisions). I agree that for mappings
$h:\{0,1\}^*\rightarrow \{0,1\}^{256}$ the function is not injective and therefore not bijective

Background

Terminology

Injective : one-to-one
Surjective : onto
Bijective : one-to-one and onto.

Pigeonhole-Principle
The pigeonhole principle goes back to 1624. We can state it as; if there are $m$ pigeons and $n$ holes with $m>n$ then when the pigeons are placed into the holes, there is at least one box that has more than one pigeon.
We can look at the traditional example; 101 pigeons and 100 holes. Place each hole one pigeon, and you will get 1 pigeon not placed into a hole so one must put this pigeon into a hole that has already one pigeon. Therefore there is one hole more than one pigeon.
The pigeonhole principle doesn't state that each hole must be filled. It is possible that 101 pigeons are places into one hole (a big one). This still applies to the pigeonhole principle.
With a small note: although the pigeonhole principle is a very simple argument it forms the basis of the combinatorics.

Cryptographic Hash Functions (CHF): CHF maps arbitrary data into a small fixed hash space $$H:\{0,1\}^*\to \{0,1\}^\ell$$ where $\ell$ is the fixed output size and it is 256 for SHA256 and $\space{}^*$ is the kleene star and in short here it forms a set that includes empty string and all finite binary strings.
There are XOF hash functions (e.g. SHAKE of SHA3 series) that the output size is determined during the digest request. In any case, one can see that the input space is larger in practice!
There are 5 main properties we want from CHF's

Deterministic: the same message always results in the same hash value.
Effective: It must be quick to compute the hash value for any given message
Irreversible: it must be infeasible to find a message that produces the given hash value.
No easy collision:  finding two different messages with the same hash value must be it is infeasible.
Avalance: Any small change to a message should change the hash value randomly so that the new hash value appears uncorrelated with the old hash value.

The 3. and 4. have formal definitions that we consider on the security and the below definitions comes from Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton.

preimage-resistance — for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage $x$ such that $h(x') = y$ when given any $y$ for which a corresponding input is not known.
2nd-preimage resistance, weak-collision — it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given $x$, to find a 2nd-preimage $x' \neq x$ such that $h(x) = h(x')$.
collision resistance, strong-collision — it is computationally infeasible to find any two distinct inputs $x$, $x'$ which hash to the same output, i.e., such that $h(x) = h(x')$.

Collisions
With the pigeonhole principle there exist at least two input  $m_1$ and $m_2$, $m_1 \neq m_2$ such that $\operatorname{SHA256}(m_1) = \operatorname{SHA256}(m_2)$. This implies that collisions are inevitable!
The collision security is bounded by the birthday paradox and roughly for a hash function with $\ell$-bit output, it has $\mathcal{O}(2^{\ell/2})$ cost with 50% probability.
No Injective
Once you have a collision this implies that a function (SHA256 here) cannot be a bijective function, since is not injective. Therefore we cannot talk about an inverse.
Surjective?
Even we don't know that SHA256 is surjective. To see that SHA256 is surjective, one has to find or show that the $2^{256}$ outputs occur.
Finding out this is impossible, since, one at least must try $2^{256}$ distinct inputs and this is infeasible.
On the other hand, showing SHA256 is surjective is problematic since it will indicate that SHA256 is not secure!
If we model SHA256 as pseudo-random function as Meir Moar did and limit the input space equal to output space then a hash value doesn't occur with probability $(1-1/n)^n$ and that is $1/e$ when $n \to \infty$. This is also the portion of the output hash value is not occurs. For the modeled SHA256 this makes $~2^{254.56}$ has values empty.
However, the input space is not limited to 256-bit. In this case, the probability of being empty becomes smaller and smaller $(1/e)^\frac{input-space}{output-space}$. And for both cases, we are still don't know until we look for all values.
If reversible
Assume that SHA256 is reversible then this means that it doesn't have the pre-image security at all. Given the has value one can find the pre-image using the reversible. This is not simple news, you would have heard that immediately.
There is no proof that SHA256 has 256-bit preimage security, however, any attack that has less than 256-bit search will still require substantial work to achieve to break the pre-image resistance. All of the current attacks are on the reduced rounds.
A good example from history is this; MD5 has imminent collisions, however, it has still pre-image resistance ( the best non-brute-force pre-image attack is still slower than brute-force in practice). So, even any collision attack better than the generic collision attack ( the birthday attack), we don't expect that the pre-image resistance will be broken.

The cost of MD5 pre-image attack by 2009 by Yu Sasaki and Kazumaro Aoki.

This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5. The memory complexity of the attack is $2^{45} \cdot 11$ words.


If you had to implement the BGN Cryptosystem, how would you do it? If you had to implement BGN, how would you do it?

I'm looking for an implementation of the public-key cryptosystem due to Boneh, Goh, and Nissim (aka BGN), or at least some suggestions on implementing it myself. My goals are to explore/learn/play around with its structure, and, eventually, to produce some kind of timing data.

For those not familiar with BGN, it offers homomorphic addition of plaintexts (similar to Paillier and exp. Elgamal), but also a single homomorphic multiplication. So you can do things like homomorphically evaluate quadratic functions (with some bounds, mind you), or even do binary range proofs without a random oracle. Thus it seems like it would be incredibly useful in a range of cryptographic protocols, yet I can't seem to find an existing implementation, nor can I seem to account for why it hasn't been done already.

Nevertheless, it's not exactly something you can just whip up in Mathematica (with apologies to @PulpSpy).

Stanford's Pairing Based Crypto library (PBC) seems like a possible place to begin, but I don't know enough about the elliptic curves or pairings to modify their default curves to the one suggested in the paper. For example, the order of the default curve in PBC is based on a Solinas prime, whereas the order of the underlying curve in BGN is a prime that is functionally dependent on a large semiprime $n=q_1q_2$ such that the order of the bilinear group is $n$. The point is, it might take some doing to get PBC working for a BGN implementation.

Maybe CHARM would be a better option. Any thoughts?

Here's a paper showing how to realize the BGN cryptosystem with a prime order group.  You could implement the cryptosystem with PBC or one of the other paring libs.

"Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups"
David Mandell Freeman
Eurocrypt 2010

http://theory.stanford.edu/~dfreeman/papers/subgroups.pdf
http://theory.stanford.edu/~dfreeman/talks/eurocrypt10.pdf

Have a look at slide 13 of the talk — the BGN example looks fairly simple.  The following slide suggests that prime-order BGN will be more efficient at higher security levels too.

This is probably how I would implement it.


Are there any algorithms or alternatives to create short signatures? I am searching for a algorithm to verify that a short message (size of about 20-30 bytes) was created by a specific device/user. The device/user can be partially offline.

Signing the data using rsa with 1024 bit is not possible since the content of the message will get to big.
The size of the signature should not exceed ~100 bytes. Are there any algorithms or alternatives to create short signatures. The algorithm does not have neccessarily have to rely on public/private key. Both parties are ment to be secure and can use the same key if neccessary.

The purpose is to prevent other devices/users to create messages in the name of some else device/user.

Are there any algorithms or alternatives to create short signatures. The algorithm does not have neccessarily have to rely on public/private key. Both parties are ment to be secure and can use the same key if neccessary.

Absolutely; if you want a public key signature (which, when cryptographers use the term 'signature', that's what they mean), then you can consider ECDSA or EdDSA; those can have signatures of circa 64 bytes for "128 bit security" (that is, we expect that it would take circa $O(2^{128})$ operations to generate a forgery without the private key).

On the other hand, you said that you can have both sides share the same key; that means that you can use a Message Authentication Code (MAC), which are even smaller.  There are a number known (HMAC, KMAC, CMAC); those can have very long keys, and can have very short tags (what you call a 'signature'; again, cryptographers don't use that terminology to describe the output of a MAC).  The size of the MAC is essentially determined by how unlikely you want it to be that someone can just guess the correct tag for a message; if you are happy with making this probability $2^{-128}$ per attempt, you can use a 128 bit (16 byte) tag

My suggestion: if you are happy with both sides sharing the same key, a MAC makes a lot more sense.  It's a lot simpler (easier to get right); I would personally suggest HMAC-SHA256 (although there are a number of quite reasonable alternatives avaiable)


Need an introduction to SPKI (or "SPKI for dummies") I am familiar with concepts such as the following:

PKI and CAs
ID based cryptography
Certificateless cryptography
PGP web of trust
more or less anything in basic Crypto that is taught in a college course

I need to quickly understand the main ideas behind "SPKI" or (Simple public key infrastructure). The Wikipedia page, while not entirely disappointing, has not been very helpful either.

I would be grateful if someone could point me to a "for dummies" article on SPKI or explain it here. Basically, what I need to understand is:

What problem does it solve?
How is it different from tradational PKI or PGP web of trust?

Thanks in advance.

Short version: SPKI links not only names, but authorizations to keys. Also, it uses a better syntax (S-expressions) than X.509 certificates.

Long version:

What problem does it solve?

Both the traditional CA-based public-key infrastructure (PKI) and PGP's web of trust (and other similar systems) do mainly one thing: Linking names to public keys.

The idea behind SPKI is detailed in RFC 2692. It explains that, while this might be sufficient in the 1970's, when the relevant communities were small and one usually knew the person identified by a name before starting to use the key for communicating, it is not sufficient anymore for the Internet of the late 1990's (and even less later).

One reason is that names alone are not a globally unique identifier. (While my name seems to be quite unique in the WWW today, there are people which are less fortunate.)

More important, though, is what we are actually using the keys for: To access some resource (or to provide it).

Thus, we actually need certificates like these (examples from the RFC):

  I need a certificate to give me permission to write electronic
    checks.
  My bank would need a certificate, proving to others that it is
    a bank capable of cashing electronic checks and permitted to
    give permission to people to write electronic checks.

E.g. we need a certificate linking authorizations to keys. (I.e. a certificate that says the holder of the private key belonging to the public key X has the right Y - for example, "access this SSH server".)

SPKI does this. RFC 2693 - Theory of SPKI details the theory. The actual specification (i.e. the data formats) seem to have never reached the RFC state (there are some Internet drafts which expired in 1998).

What rights (authorizations) there are possible is left to the application (i.e. whoever actually has control over the resource). Its owner indicates an access control list, i.e. which keys are (with which authorizations) the roots of any certificate graph leading to the ones which actually have access.

Authorizations can be transferred between keys (if the delegate-bit is set on the first key) by issuing a certificate.

Any key holder can issue any certificate to any other key (or even to ones own key), i.e. we have a web of certificates between keys. But whoever evaluates the certificates will decide which certificates are acceptable for which use (depending on which other key holder signed these keys).

The traditional "name-key" linking certificates are still supported, this way the conventional PGP Web of Trust or the X.509 CA hierarchy can be a part of this infrastructure, and their certificates can be transformed into the same internal representation like SPKI certificates.

Syntax

To represent the keys, names and authorizations used in the certificates, SPKI uses S-expressions. (You might know these from Lisp - nested lists written in parenthesis, containing byte strings.) Here is an example of a name:

  (name (hash sha1 |TLCgPLFlGTzgUbcaYLW8kGTEnUk=|) jim therese)

For transmission and signing these are converted into a canonical form (length-prefixed literal strings).

These S-expressions are easier to parse than X.509 certificates.

Certificate revocation

A problem identified in the PKI was that is is not always totally deterministic whether a certificate would is revoked or not, depending on whether the evaluating client got the right CRL or not.

SPKI defines a way that makes this deterministic:

certificates contain references to CRLs which can revoke them
certificates contain the key that must be used to sign the CRLs (which must not necessarily be the same key that issued the certificate)
CRLs must have a validity date span (and these must be non-overlapping)


State level "Weak Diffie-Hellman" working for SRP too? I've read about the "Weak Diffie-Hellman" attack (paper, website), where a resourceful entity like a state can pre-compute values for known primes to aid solving the discrete logarithm problem for that particular prime.

I've also read that SRP is very similar to Diffie-Hellman, and has common groups (see RFC 5054). Can the attack be mounted on SRP as well?

In the introduction of the Logjam paper, it is stated that

  After a week-long precomputation for a specified 512-bit
  group, we can compute arbitrary discrete logs in that group
  in about a minute.

So it seems that what it actually does is attack the discrete logarithm problem, so any discrete-logarithm-based system which uses a common prime should be equally vulnerable. In particular, in Section 3.2 of RFC 5054, it is stated that

  An attacker who could calculate discrete logarithms % N could compromise user passwords, and could also compromise the confidentiality and integrity of TLS sessions. Clients MUST ensure that the received parameter N is large enough to make calculating discrete logarithms computationally infeasible.

Since RFC5054 specifies only one prime for each bit-length, it will indeed be vulnerable. Even though it does not specify a 512-bit prime, it does specify a 1024-bit one, which is considered vulnerable by the Logjam authors:

  We estimate that even in the 1024-bit case, the computations are plausible given nation-state resources

Using a prime of at least 1536 bits should be sufficient to thwart such attacks, since there is no known "downgrade" attack on SRP.


Altering file for to create partial matching MD5 Is it possible to produce a file(zip) where the first $n$ bits match a given value in optimal time?

Let us say we have a folder $f_1$ with hash $h_1$. After I change some contents in folder and the new folder this becomes $f_2$ with a rather different hash $h_2$.

Can I change (the) hidden contents in $f_2$ say $f_2'$ to get a hash $h_2'$ with where the first $n$ bits are identical to hash $h_1$?

If we can make such file can someone explain how?

note: hash is for zip of folder

Yes, you can, but the amount of bits (that get translated into characters if you'd use, say hexadecimal encoding) that will be identical to the original hash are of course limited.

Say a hidden file in the folder contains a large counter $c$. The total hash $h_2^c$ will have a pseudo-random value. The first bit of the hash will be identical to the first bit of hash $h_1$ with a probability of $1 \over 2$. That the next bit also matches has a probability of $1 \over 4$, which is ${1 \over 2} \times {1 \over 2}$ or $2^{-2}$. If you try enough counter values you will quickly find a hash where the first few bytes are identical.

Of course the chances of finding a full MD5 hash of 128 bits this way are very close to zero. 48 bits or so may be doable (your counter $c$ should be at least 48 bits but preferably larger, say 64 bits).

If the contents of the first folder $f_1$ can have a pre-calculated value inserted then you may be able to attack MD-5 and create a fully identical hash as MD5 is rather broken. But from your description this doesn't seem to be the case.

Furthermore, if $h_1$ is set then you cannot take advantage of the birthday problem, which halves the security of the hash. It's much easier to find two hashes $h_x$ and $h_y$ that match for $n$ bits than finding a single $h_x$ that matches a preset $h_1$.


Can sleeper agents in a public network find each other and avoid infiltration? Suppose a bunch of software entities are participating in a wide-area broadcast network (the network carries a lot of traffic, and the software entities also participate in those conversations, so their transmissions are likely to be seen by friend and foe alike).  How can they find each other efficiently and establish communications, without being infiltrated by enemy agents who (we will assume) can capture and inspect any particular entity?
For example, one entity could find another candidate entity by noticing a particular type of message error or checksum, and could send a decoy message that would contain a similar type of error.  But an enemy agent could do the same thing, or an enemy monitor could watch for entities engaging in this protocol.
What are the search keywords for learning about protocols that are useful in this area?
Edit to add:
My specific use case is within the BitTorrent network / ecosystem.  The main function of BT is to distribute data files among interested participants.  The data files are identified by a 160-byte hash (the infohash).  An auxiliary network, the Distribute Hash Table (DHT), helps clients find a node that is distributing the data file having a particular infohash.
DHT nodes are identified by a random 160-byte number, and their basic operation is to ask other nodes if they know a BT node that is distributing a particular infohash.  DHT nodes self-organize by their ID numbers, and searching is done by matching the hash from MSB to LSB.
If a DHT node is asked to find infohash abcdefghijklmnopqrs, then it will ask nodes it has already encountered, whose ID numbers start with abcd....  (The longer the matching prefix, the more likely that node will know the answer we're looking for.)  If those nodes don't know, they recursively ask the nodes they know about with longer matching prefixes.  Eventually, a node knows the exact answer, or does not know any other node closer to the exact answer, and that node's address is returned to the original querier.
So DHT nodes are continually asking each other where to find 160-bit hashes of one thing or another.
I would like my DHT nodes to be able to recognize each other by asking for particularly-formatted infohashes.  For example, infohashes where every prime bit is 0.  (I understand that some ordinary inquries may match this pattern as well, but that's OK -- one of my nodes might respond, but the ordinary querier wouldn't proceed with the protocol so my node will know that it's not one of my special nodes.)
The problem is, an adversary can reverse-engineer my code and determine what my special infohashes are, and can implement a node that pretends to be one of my special nodes, but which does not play nice -- it might feed me bogus data, instead of the data my nodes are actually trying to collect.
So, I would like to devise a way that my nodes can identify each other, and can detect and exclude nodes that pretend to be "on my team," but are in fact enemy nodes.  Obviously, I could hard-code the IP addresses of my nodes (or something similar), but I would like to be able to start an arbitrary number of nodes running at arbitrary places around the Internet, and have them find each other and start cooperating.

I'm looking for a way for one message recipient to distinguish steganographic (or other) messages from a friend client from similar messages from a foe client.

That's possible only if there's something friends know that foes don't. And if we talk crypto implemented by local-run software, that thing must be a key. If that key is not in the software itself, and that software is public, then it must be an input of the software available selectively to the "friend" instances. That does not seem to be the case here.
If we nevertheless assume such a key, we can think of using an authenticated encryption which cryptogram is indistinguishable from random for one without the key, which gives a method to hide the traffic in a context where there is legitimate reason to send arbitrary-looking data blobs like hashes. However:

If the software is public, the fact that it has provision allowing this can't be hidden. Only the use of that provision can perhaps be hidden.
That method rules out that one without the key can make a static analysis of a packet's content to tell if it contains a hidden payload (or which). But it can't rule out that such hidden payload gets indirectly detected by other means (like analysis of if there's any other reason a node could send a packet like this at that time; or the effect of that packet on the friend client software receiving it).


Given $g^a, Y$, is it hard to distinguish $e(g,g)^{ab}$ from a random value? where
$g$ is a group element in bilinear group $G$

$Y = M.e(g,g)^{ab}$

$M$ is a message

Does anyone know the answer or suggest some material for reference?

I'll assume that the attacker has the value $g$ as well.

If so, we can rewrite $M \cdot e(g, g)^{ab} = M \cdot e(g^a, g)^b = M \cdot h^b$ (where the attacker knows the value $h = e(g^a, g)$.

Assuming that $a$ is relatively prime to the size of the subgroup generated by $e(g, g)$, and that $M$ is a member of that subgroup,then, yes, it is indistinguishable; for any message $M'$ within that subgroup, there a $b'$ for which $Y = M' \cdot h^{b'}$


How to split up $GF(2^{128})$ into smaller fields? I've heard that it's possible to split up $GF(2^{128})$ into copies of several smaller fields like $GF(4)$ so as to make the math easier in some cases.  How do you do that?

I know how it works for groups modulo a composite number using regular arithmetic instead of carryless, such as when using the Chinese Remainder Theorem to speed up RSA.

I believe that this is called "field extension".

When you have a finite field $\mathbb{K}$ of cardinal $q$ (necessarily, $q = p^m$ for some prime $p$ and integer $m$), then a finite field $\mathbb{K}'$ of cardinal $q^k$ can be defined for any integer $k$, in the following way. You consider $\mathbb{K}[X]$, which is the ring of polynomials whose coefficients are in $\mathbb{K}$. Polynomials can be added and multiplied together, and you can defined an euclidian division on polynomials. Then, choose some polynomial $P \in \mathbb{K}[X]$ of degree $k$. You can then consider polynomials of $\mathbb{K}[X]$ modulo $P$: these are all polynomials of degree up to $k-1$, and when you multiply two of them together, you do a division by $P$ and keep only the remainder.

These polynomials taken modulo $P$ form a ring of cardinal $q^k$. If you chose $P$ to be irreducible (i.e. there is no polynomial $R$ of degree strictly more than $1$ and strictly less than $k$ that divides $P$ exactly), then the ring you got is actually a finite field: that's your $\mathbb{K}'$. This is called a field extension because the elements of $\mathbb{K}$ naturally map to the polynomials of degree $0$ of $\mathbb{K}[X]$, so $\mathbb{K}$ can be said to be a subfield of $\mathbb{K}'$.

It may help to think of this construction as the same thing as the construction of complex numbers $\mathbb{C}$ over the reals $\mathbb{R}$: in $\mathbb{R}$, the polynomial $X^2+1$ is irreducible (there is no real whose square is $-1$); so we define complex numbers as $a+bX$, and then $(a+bX)(c+dX) = ac + (ad+bc)X + bdX^2$, that you take modulo $X^2+1$, i.e. by considering that $X^2=-1$. You then get $(a+bX)(c+dX) = (ac-bd) + (ad+bc)X$. Traditionally, you call that $X$ "$i$", and there you go: you have the complex numbers. With finite fields, you can do the same, with some extra possibilities because you can find irreducible polynomials of any degree (with real numbers, irreducible polynomials cannot have degree more than $2$).

For example, to define $GF(2^{128})$, you can start from $GF(2)$ (the field with two elements) and use an irreducible polynomial of degree $128$. However, you could also start with $GF(4)$ and use an irreducible polynomial of degree $64$: you will also end up with a finite field of cardinal $2^{64}$.

Of course, the field you start with, and the polynomial you choose, will matter for the field you actually get: if your values are represented as sequences of bits, and you compute things with them, the bit sequences you obtain depend on these parameters. However, and that is the "magic" thing, it so happens that when two finite fields have the same cardinal, then they are isomorphic to each other. In that sense, there is only one field of cardinal $2^{128}$, and all concrete fields that you can build are just different representations of that mathematical structure. This is why you can talk of "the" field $GF(2^{128})$.

Computing the isomorphism, i.e. mapping from one representation of $GF(2^{128})$ to another (e.g. to a representation as an extension of $GF(4)$ of degree $64$) can be a bit cumbersome, but, ultimately, it is "just linear" and similar to a change of basis with matrices.

To get some extended information on these matters, go read this book.


Is it necessary to encrypt nonce in cryptographic communication? Server and client have a pre-shared key K. Assuming that that pre-shared key is safe, so nobody other than server/client can encrypt/decrypt.

Client sends a nonce N to server, server then sends back message M in encrypted form AES_CBC_Encrypt(M+N, K, IV) to client. So client can verify if there is a replay attack trying to send an expired message.

Is it necessary for client to send N in encrypted form AES_CBC_Encrypt(N, K, IV) or it is OK to just send N in clear.

M and N are 16-byte array, M+N means concatenation of M and N).

If your nonce is 16 bytes, and your message pre-nonce is a multiple of 16 bytes (i.e. no padding is needed), sending the nonce in the clear opens you up to replay-ish attacks. Specifically, if an attacker captures one exchange with nonce $N$ and response $R$ (with $b$ blocks $R_1$ through $R_b$), and then impersonates the server and the client sends them $N^\prime$ as nonce, they can create a new message with the correct nonce at the cost of scrambling the last block of $M$ (by XORing the second-last block of $R$ with $N\oplus N^\prime$). How this affects your system depends on the specific system, but this is generally not something you want to be possible.

The proper way to mitigate this isn't to send $N$ encrypted: it's to use authentication on the server's response. The client will already refuse a message that has a previously used nonce; it will also refuse a message that doesn't have the correct nonce value. That means that an attacker already can't do a straight replay attack, because a straight replay will be rejected. However, you should still worry about an attacker maliciously tweaking the message (that thing where if they know the contents of one block, they can change them at the cost of scrambling the previous one? That's true for all your blocks, and they can do it on the first block without scrambling any other blocks at all.) On the other hand, with a proper message authentication code, you can prevent any attacker who doesn't know the key from feasibly forging any message from the server; properly done authentication means that the only messages an attacker could send are exact replays, so if you can throw those out they can't do anything.

So the correct response is "use authentication, preferably with an AEAD mode like GCM, CCM, or EAX." (AEAD combines encryption and authentication in a secure way; it's fairly easy to screw up if trying it yourself). If you can't use AEAD, share a second key to use for a MAC algorithm and then use that MAC on the ciphertext to authenticate it (and do that before decrypting the ciphertext). Then you don't need to worry about encrypting $N$ or not, because the attacker can only pull off an exact replay and an exact replay is blocked by your challenge-response system.


Number of functions included in a keyed PRF I was reading Introduction to Modern Cryptography by Katz and Lindell and i found this:

  Coming back to our discussion of pseudorandom functions, recall that a
  pseudorandom function is a keyed function F such that $F_k$ (for $k\in2 \{0, 1\}^n$
  chosen uniformly at random) is indistinguishable from $f$ (for $f\in$ $Func_n$ chosen
  uniformly at random). The former is chosen from a distribution over (at most)
  $2^n$ distinct functions, whereas the latter is chosen from all $2^{n*2n}$
  functions in
  Funcn. Despite this, the “behavior” of these functions must look the same to
  any polynomial-time distinguisher.

How did he got into the conclusion that keyed function F is chosen over $2^n$ distinct functions?

Does he assume that there is a fixed function which maybe differentiated by the key k, so total of $2^n$ "functions"?

There are $2^n$ possible values for $k$, and for each one there is a function $F_k$, ergo, there are at most $2^n$ possible functions $F_k$. ("At most" is because it is possible that two different values of $k$ yield the same function $F_k$.)


What is the difference between perfoming Correlation Power Analysis (CPA) in the first AES round and doing it in the last round? I have a script that helps me to make to make a Correlation Power Analysis (CPA) attack. I am trying to attack the first round. As input, I put:

my traces
my plaintexts
my key

The steps to make the attack are:

Reading the data, which consists of the analog waveform (trace) and input text sent to the encryption core.
Making the power leakage model, where it takes a known input text along with a guess of the key byte.
Implementing the correlation equation, and then looping through all the traces.
Ranking the output of the correlation equation to determine the most likely key.

What must I change if I want to attack the last round please?

When you perform CPA against AES, you'll attack either the first or the last round depending on the data you've got at hand. Both attacks are of the same complexity, roughly.

If you know the plaintext $p$, then you'll exploit the very first AddRoundKey and attack the first SubBytes routine, which will allow you to recover directly the master key, by doing CPA on assumptions about the value of $k_0\oplus p$ as input to the operation SubBytes.

Now, if you know only the ciphertext, you'll want to attack the last SubBytes routine of the whole AES process, to recover the last round key through the last AddRoundKey operation, and once you have a round key, you can recover the master key since the key schedule is invertible.

In the last round the operations done by AES are:
SubBytes, ShiftRows, AddRoundKey.

So you will want to do CPA on the SubBytes operation, just like you did in the first round case, except that you'll have to deal with the ShiftRows operation, which is hopefully invertible.
You will have assumptions on the input value of your SubBytes method, which is $\mathtt{SubBytes}^{-1}[\mathtt{ShiftRows}^{-1}[k_{10}\oplus c]]$, for $c$ a known ciphertext. Those are all reversible operation, thus it is possible to compute the assumed input.

Thus the differences with the first round case are:

you are using a known ciphertext instead of a known plaintext,
you will end up with the last round key $k_{10}$ instead of the actual key $k_0$ ,
you'll have to deal with the ShiftRows operation.

Maybe you can read this, although it's not going really into the practical implementation steps.

You can also read this question and its answer to get why why want to target the SubBytes routine, as well as that one.


Are there any practical methods of steganography? There isn't a whole lot of information on steganography in the modern age, from what I can tell. A google search for steganography usually brings up a list of very impractical methods (e.g. tattooing a message on a guy's head then waiting for hair to grow over it). The only modern (and practical) method I've seen involves manipulating the least significant bits of an image. This method appears everywhere when you search for steganography. Are there any other practical methods of steganography?

The International Journal of Soft Computing and Engineering has published many articles on the subject.

If you want to move away from simple bit-twiddling in lossless images, take a look at spread-spectrum techniques for images and audio files.

There are plenty of tools available for hiding data in compressed images and audio (e.g., Steghide, JPHide and Outguess). However, it is often possible to detect when they have been used (e.g., using neural networks).


Break RSA when modulus is of the form $N = pq$ with $|q^2 - p|$ small I need some insight in how to break the following RSA problem:

  From an RSA encryption scheme you know that the algorithm that
  generated the RSA modulus $N$ always outputs moduli of the form $N = pq$ such that the difference between $q^2$ and $p$ is not bigger than $2^8$
  in absolute value.

My question is: Shall I try to factor $N$? Which method should I use if so?

Somewhat related is this question.

Edit:
Solving for $q$, I have that $q$ is between the square root of $p-2^8$ and the square root of $p+2^8$.

You can find the factor $q$ just by taking the cube root of $N$ and rounding to the nearest integer!

If $N = pq$ where $p = q^2 + \delta$, then: $$\sqrt[3]N = \sqrt[3]{q(q^2 + \delta)} = \sqrt[3]{q^3 \left( 1+\frac{\delta}{q^2}\right)} = q \cdot \sqrt[3]{1+\frac{\delta}{q^2}}.$$

Thus, as long as $2|\delta| < q$ then, given that $|1-x| \le |1-x^3|$ for all $x \ge 0$: $$\left|q - \sqrt[3]N\right| = q\left|1 - \sqrt[3]{1 + \tfrac{\delta}{q^2}}\right| \le q\left|1 - \left(1 + \tfrac{\delta}{q^2}\right)\right| = \tfrac{|\delta|}{q} < \tfrac12,$$ and so $\sqrt[3]N$ rounds to $q$.

(A more precise calculation, using the fact that $q \ge 2$ and that $|1-\sqrt[3]{1+x}| \le \frac{|x|}2$ for all $|x| \le \frac12$, shows that this actually works even up to $|\delta| < q$.)

More generally, even if $|\delta|$ could be several times as large as $q$, you could still solve the problem efficiently by starting with the approximate solution $\tilde q = \sqrt[3]N$ and testing nearby integers $q \approx \tilde q$ until you find one that evenly divides $N$.


Value of new symmetric key algorithm When I was in grad school, I invented (discovered?) a new PRNG algorithm.  This algorithm has an infinite period length (given infinite memory).  This in itself cannot be new, because all you need to do to accomplish this is simply take digits from an irrational number.  What does make this different, is that it is able to use any size of key.  1 bit, 1 GB, whatever.

The next logical step for me was to turn this into a symmetric key algorithm. simply by generating the bits based off of the seed, and XORing the source file bits with the resulting output.

I am in the middle of developing this into an Android app.  My problem is that 100% of my experience has been academic.  I know that this algorithm (Binary Lagged Fibonacci) is valuable academically, but does it have a practical value?  Does the flexible key size alone give it a benefit over, say, AES?

I have sent some emails out to a few companies, and I am trying to find out why no one has responded at all.  My best guess is that 1. they get 1000 crackpots emailing them every day.  Or 2. I sound like I have no idea what I am talking about.  The second one is definitely true.  I just learned the other day I need to be salting the seed when it gets passed.

Without a proof of security or proper cryptanalysis including an argument why it covers all currently known methods:
The value (in the context of cryptography) is zero.
This might sound harsh, but you brought up the main reason yourself: It is basically impossible to design a new secure cryptosystem without the proper knowledge of the field, but amateurs are convinced otherwise and keep on trying. The only solution here is to write a publication in some peer-reviewed context (e.g. crypto conferences). Regarding your experience, it is not clear from your question, because you wrote:

My problem is that 100% of my experience has been academic
Or 2. I sound like I have no idea what I am talking about. The second one is definitely true

Regarding your algorithm:
A lagged Fibonacci generator is a well known construction. It is an improvement over the linear congruential generator, and is related to similar concepts like LFSR, Mersenne Twister, etc.. But that doesn't say much: Those are not cryptographically secure random number generators, and they have no security at all (from today's point of view). So it's quite reasonable, this is also true for your algorithm.
Considering an infinite period: A large period is required for a proper CSPRNG, but it is not sufficient. A well-known counter example is linear-feedback shift registers, which have large periods and were used for stream ciphers in the past. But they are quite easy to break.
Also irrational numbers might offer an infinite period of numbers, but that doesn't mean they are unpredictable or you can't get the seed back from the sequence. I am not aware of any computationally hard problem regarding irrational numbers.


How to distributively compute a secret of that form $\mathsf{s=sk\cdot g^a}$? Is there a standard way to distributively compute secrets shares such that any $t+1$ combination out of $n$ of them constructs the secret $\mathsf{s=sk\cdot g^a}$, for a generator $\mathsf{g} \in \mathbb{Z}_p$ and $\mathsf{sk,a}$ chosen uniformly at random from $\mathbb{Z}_p$

I assume that your question relates to sharing a secret specifically of this form. Furthermore, you want to guarantee this even if the dealer is not trusted and may try to share a secret of a different form. Otherwise, you could just use any secret sharing (or verifiable secret sharing) scheme.

However, note that $s$ as you wrote actually does not have any special form. Specifically, since $a$ is uniformly random, $sk\cdot g^a$ is just a uniformly random element in $\mathbb{Z}_p$. Thus, as you have worded your question, you can use any secret sharing scheme for which the domain of the secret is $\mathbb{Z}_p$.


Why does Ed25519 scalar multiplication allow values larger than the subgroup order? The GeScalarMultBase function is documented like so. From the way it is documented we see that it expects a little-endian value and has a precondition that constrains the range it accepts.

// GeScalarMultBase computes h = a*B, where
//   a = a[0]+256*a[1]+...+256^31 a[31]
//   B is the Ed25519 base point (x,4/5) with x positive.
//
// Preconditions:
//   a[31] <= 127
func GeScalarMultBase(h *ExtendedGroupElement, a *[32]byte) {

My understanding of elliptic curves has me thinking that the range of accepted values for scalar point multiplication should be in [0, subgroup_order]. While it could accept larger values since $(n+x)G = xG \pmod n$ it would be wasteful computationally so I'd expect the function to constrain it to the subgroup order or always mod it before using it.

In Ed25519 the order constants are defined like so:

field_order 2**255 - 19
subgroup_order 2**252 + 27742317777372353535851937790883648493

Comparing these to what that method documentation says:

# hex in little-endian
field_order: 0xdefffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7
subgroup_order: 0xde3d5fc5a13621856dc97f2aed9fed4100000000000000000000000000000001
GeScalarMulBase states: a[31] <= 127 (0xf7)
field_order[31]: 0xf7 (127)
subgroup_order[31]: 0x01 (16)

Since we are working in little-endian, byte 31 is the most significant byte and we see from the documentation that the function enforces it is less than 127, which maps to the field order.

This seems to indicate it accepts values in the range of [0, curve_order] instead of my expectation of [0, subgroup_order].

Is my understanding of what's happening accurate? If so, is there a particular reason this allows values larger than the subgroup order?

My understanding of elliptic curves has me thinking that the range of accepted values for scalar point multiplication should be in [0, group_order].

Actually, that's not the case - the point multiplication $xG$ is well-defined for all integer values of $x$.

  While it could accept larger values since $(n+x)G=xG$, it would be wasteful computationally so I'd expect the function to constrain it to the group order or always mod it before using it.

Well, cryptographically that would be valid, however that would allow a further "optimization" that Dan wanted to avoid allowing to well-meaning implementors.

If someone were to implement the point multiplication $xG$ in the straight-forward manner (where $x$ is a number between $0$ and $n$), they might notice that, some of the time, $x$ was fewer than 252 bits - in that case, they might be tempted to skip those iterations of the point multiplication logic (and so speed things up slightly).  That might sound like a nice optimization, however that introduces a (small) timing leak (as the time taken depends on secret data), and Dan really wants to avoid any such leakage.

By ensuring that $x$ is a number between $2^{254}$ and $2^{254}+n$ (and thus is a fixed number of bits), any such optimization is far less straight-forward (and so far less likely to occur to our well-meaning implementator)


Numeric combination of passwords Pls I need explanation on How i can design a Cryptography that use multiple passwords or passphrase to open a safe(Lock). For example, if i need five people to unlock a secured device whereby all the five need to enter their individual password before the device can be opened.

Please how can this be done? I don't have much knowledge on this, hence i wouldn't expect all the answers right away. I would appreciate a link, or book or somewhere i can read details about it.
Thanks.

Start with “Shamir's Secret Sharing” concepts…

  Abstract. In this paper we show how to divide data D into n pieces in such a way that D is easily reconstructable from any k pieces, but even complete knowledge of k - 1 pieces reveals absolutely no information about D. This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.

source: http://dl.acm.org

In a nutshell:

I have a secret $S$. Let's say $S=10$ (or a password turned into the value $10$), and I want to share it between $N=2$ people. I create a polynomial of degree $d=N-1$ (because I care to have a secret for two people):
$$f(x) = ax + b$$

We set $b = S$, and let $a$ be a random value larger than $S$ and $N$. For example, let's say $a=13$.

Therefore:

$$    f(1) = 13*1+10 = 23
\\    f(2) = 13*2+10 = 36
$$
Now, send $f(1)$ to person $1$, and $f(2)$ to person $2$. In order to obtain the secret $S$ and to unlock the door, both person $1$'s value and person $2$'s value are needed.

Using polynomial approximation, we can get the resulting $f(x)$ from the people values:
$$ f(x) = \sum_{i=1}^N f(i) \cdot
             \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}
 = \sum_{i=1}^N f(i) \cdot
             \prod_{j\neq i} \frac{x-j}{i-j}
$$


How do you distribute secret shares without knowing who to first distribute them to? Figure 1 on page 1249 of the “Multiparty Computation Secure Against
Continual Memory Leakage” paper shows $m$ committees are elected in step 1 and then later in step 3 are each given a secret share.

But I was wondering if it is possible to pull out the election of $m$ committees from the pre-processing phase and do it in a different phase (like online phase)? The problem with the pre-processing phase is it is assumes no leakage so simplifying it is a step closer to completely getting rid of it.

I am essentially wondering if it is possible to distribute secret shares without knowing the committees (i.e. “don't run election protocol immediately, run it later”)?

As long as you know the reconstruction threshold a priori, I see no reason you can't generate a bunch of shares before knowing who you will distribute them to. Once you know who you are going to distribute them to, just send one share to each person.

On the other hand, if you don't know the reconstruction threshold, you wouldn't be able to construct, I don't see how you can do it. It would seem like an ill-posed problem at that point.


Examine whether a hash function is collision-resistant Assume a collision-resistant hash function $h$ which compresses sequences of length $2n$ to length $n$. It must be examined whether the hash function which compresses seqs. length $4n$ to $n$:
$$
h_1(x_1 || x_2 || x_3 || x_4) = h((x_1 \oplus h(x_2 || x_2)) || (h(x_3 || x_3) \oplus x_4))
$$
is collision-resistant or not. ($\oplus$ is XOR, $||$ is concatenation and $|x_i| = n$).
Attempt:
Assume we can easily find two distinct sequences $(y_1, y_2) = (x_1 || x_2 || x_3 || x_4, x_5 || x_6 || x_7 || x_8)$ such that $h_1(y_1) = h_1(y_2)$.
Then, we can easily find $(y_1, y_2)$ such that:
$$
h(g(y_1)) = h(g(y_2))
$$
where $g(y) = g(x_1||x_2||x_3||x_4) = (x_1 \oplus h(x_2 || x_2)) || (h(x_3 || x_3) \oplus x_4)$.
But then, if we can easily find such $(y_1,y_2)$, we can also easily find $(g(y_1), g(y_2))$ and thus $h$ is not collision-resistant.
In case the above argument isn't valid, another idea would be to state that $g(y_1), g(y_2)$ cannot be distinct (with non-negligible probability) since $h$ is collision-resistant and continue with solving $g(y_1) = g(y_2)$ etc until we get $y_1 = y_2$.
It'd be very helpful if someone pointed out to me which of the two (if any) is the correct proof.

Your proof starts with the correct approach, but $h_1$ is not collision-resistant (CR), and therefore your proof should give you a hint as to why it's not CR.
Edit: I have removed the counterexample, since it should be easy to figure out using the proof attempt below.
Attempt to prove
You want to prove that:
If $h$ is CR, then $h_1$ is CR.
We prove the contraposition of that statement:
If there exists an adversary $\mathcal{A}^{h_1}$ breaking $h_1$,
then there exists an adversary $\mathcal{A}^{h}$ breaking $h$.
We want to assume the existence of $\mathcal{A}^{h_1}$ and use it to
construct $\mathcal{A}^{h}$.
$\mathcal{A}^{h}$ is playing the CR game, and
is supposed to output a collision for $h$.
To achieve that, we let $\mathcal{A}^{h_1}$ run.
Since by assumption $\mathcal{A}^{h_1}$ has a non-negligible
probability of succeeding, it will output a collision of $h_1$ with non-neglibile probability, i.e. a $x^a \neq x^b$ such that $h_1(x^a) = h_1(x^b)$.
We now want to win the CR game against $h$ and construct a collision for $h$ from $x^a$, $x^b$.
We know that $h_1(x^a) = h_1(x^b)$, and $x^a \neq x^b$.
Therefore, using your $g(\cdot)$,
$h(g(x^a)) = h(g(x^b))$.
There are two cases here:
1. Either: $g(x^a) \neq g(x^b)$
then we immediately find a collision:
since $h(g(x^a)) = h(g(x^b))$
and $g(x^a) \neq g(x^b)$,
the pair $(g(x^a), g(x^b))$ is a collision for $h$.
2. Or not: $g(x^a) = g(x^b)$
then we have to look further for a collision.
by $g(x^a) = g(x^b)$ we know that
$\underbrace{(x^a_1 \oplus h(x^a_2 || x^a_2))}_\text{first part}\ ||\ (h(x^a_3 || x^a_3) \oplus x^a_4)
 = (x^b_1 \oplus h(x^b_2 || x^b_2))\ ||\ (h(x^b_3 || x^b_3) \oplus x^b_4)$.
By $x^a \neq x^b$ we know that at least one of these 4 cases must hold:
2.1. $x^a_1 \neq x^b_1$
By $g(x^a) = g(x^b)$,
the first part of the input of the outer $h$ must be equal:
$x^a_1 \oplus h(x^a_2 || x^a_2) = x^b_1 \oplus h(x^b_2 || x^b_2)$.
This is where the proof breaks down. You cannot construct a collision from this.
2.2. $x^a_2 \neq x^b_2$
2.3. $x^a_3 \neq x^b_3$
2.4. $x^a_4 \neq x^b_4$
Hope I could help!


Is it possible to perform a length-extension attack if only the last bit of the new message changes? Given a Merkle-Damgård hash function H, let's say SHA256, that computes a MAC as follows:

H(secret_key||timestamp), so that the attacker knows the result and the timestamp.

Is it possible to produce a valid MAC of H(secret_key||timestamp+1) with length-extension or other attack?

No, the length extension property does not allow to compute  $H(\text{secret_key}\mathbin\|\text{timestamp}+1)$ from $H(\text{secret_key}\mathbin\|\text{timestamp})$ and $\text{timestamp}$.

Two caveats:

That's for reasonable encoding of integers to bitstring for the $\text{timestamp}$ field, including anything fixed-size, ASN.1, Integer-to-Octet-String Conversion, and any conceivable variation. Argument: the length extension property computes the hash of a message larger than the original by the padding size (at least 65-bit for SHA-256), and further that much of the extension is heavily constrained.
What's considered is not an intended use of $H$, and we have no convincing argument of security from other attacks. The academically sound thing is to use a MAC, for example HMAC with $\text{secret_key}$ as the key and $\text{timestamp}$ as the message.


Does clustering the AES Sbox look up table to 32 bit entry per index, help reduce vulnerability to cache timing attacks? I've been searching for some, easy methods to help mitigate, a cache timing attack on software AES implementations.

Currently, my implementation uses, a usual 256 byte S-box

uint8_t sbox[256] = {0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30... /* and so on*/}

My goal as a developer, is to prevent/increase difficulty for an attacker to know the substitutions or the result of substitutions as a result of the AES SubBytes() operation.

This is a solution that I devised:
Rather than using a 256 entry Sbox table, I decided to cluster the Sbox table into a 32 bit per entry table, where four bytes are grouped to form an unsigned  integer, like this:

uint32_t sboxu32[64] = {0x637C777B, 0xF26B6FC5,  /* and so on */}

Now if I want to get the S-box substitution, for a byte x : I do ExtractByte(sboxu32[x>>2], x&3)
where, ExtractByte is  :

#define ExtractByte(x, n) (uint8_t)(((x) >> (24 - 8 * (n))) & 0xff)

Now, this is my reason for doing this, hoping that the above modifications will help protect my implementation from cache timing attack, without impacting my performance.

For every access to the entry of sboxu32, I'm accessing the index x>>2 which is the truncated  division of x by 4, Assuming that the attacker does not have any knowledge of x&3 , can the above modifications increase the difficulty for the attacker ?
If the attacker knows x >> 2 , then there are 4 possibilities for the exact x and hence x&3 , Since AES operates on 16 byte blocks, I'm guessing the attacker would have to guess $4^{16}$ for the correct sequence of bytes.

I realize that it is trivially brute forceable, but are there
    other    methods,  to, use this as a starting point, to build
    further    camouflage my access to the actual sbox substitutions,
    without impacting performance?

Are there better performance friendly methods to mitigate side channel attacks on my AES implementation ?

Every help will be greatly appreciated!

The answer to this sort of question would depend greatly on your hardware (both your CPU and cache architecture).

On the other hand, I don't see this adding any protection on common hardware.  When a program on (say) an Intel chip does a byte access, the CPU generally issues a read for a larger segment (often the cache line), and then extracts the desired byte from it.  From the CPU's and memory's viewpoint, reading the entire line is no more expensive than reading a single byte (the memory bus is designed to pull in an entire line at once), so it might as well access it all (and so fill in the entire cache line, just in case you access other parts of that same line in the future).

So, you're doing manually (via explicit instructions) what the CPU is likely able to do automatically (and cheaper; it already has the hardware in place, and so it doesn't spend extra cycles to do so); I would expect that this is a waste of time.


Device intercommunication with commands I want to create a smart house project, and in that I bought some simple
RF modules. Those modules don't support crypto out of the box  but I want to connect them to a device that I would program to use crypto (for example AES).

Now the question is since I would be sending a lot of same messages (digital I/O Pins) encrypted with the same password the output encrypted message would be the same. So if someone is sniffing the traffic he/she would be able to transmit that encrypted message and my C&C (command and control) device would think that the message is coming from the inside and do certain actions depending on that message. 4 Way handshake doesn't cut it since even without the knowledge what the message is it can be broadcast to achieve certain results.

Question: What is the best practice/crypto to use in this situation? Should I add a random string appended to my original message and on the other side parse that message and just pull out the info that I need?

Keep in mind that devices on all ends all low computing devices with low memory (some kind of Arduino if you will). So, I need a safe cryptographic solution where – even if the user can sniff the data – the user wouldn't be able to use it.

Among several aspects of the question, I'll cover only protection against replay of commands.

A common technique (among several) is to have commands tied to a nonce, that somewhat is accepted only once by the slave device receiving the command. The nonce is included in the input of a MAC or public-key signature algorithm that protects the integrity of the command.

When two-way communication is possible, a nonce can simply be a true random value wide-enough to most likely not repeat (say, 16-byte), generated by the slave device and sent to the master before it sends a command. The slave then receives the command, checks the MAC or signature included in the command (prepared on data including the nonce, as a prefix of the data in the actual command), and executes the command only if the MAC or signature checks. The slave then no longer accepts to execute another command until it has generated another nonce.

This is safe from the standpoint of pure replay. However an adversary may be content to defer execution of a command (rather than execute it a second time). Think of a garage door: an adversary waits for the home owner returning home and sending an open command; the adversary captures that command until the middle of the CRC at the end, and starting from that instant jams the radio channel. The command is ignored by the slave for wrong CRC, and does not get executed. Long after the attacker stops the jamming, then retransmits the command with recomputed CRC; abracadabra the door opens! Amazingly, some complex secure channel protocols put no time limit on how much an active adversary can delay a frame (perhaps inserting dummy requests for repetition to keep some link active), and are vulnerable to that attack. There's a simple countermeasure: we can put a time limit to the validity of a nonce, like seconds, enforced by the slave, counted from the sending of the nonce; and the nonce needs to be unpredictable (rather than only unique) to block some variants of the attack.

This is fine, but the nonce requires two extra frames (to the slave asking for the nonce; from the slave with the nonce). One option to reduce at least the number of overhead frames is to embed a fresh nonce in every frame sent, applicable to the next frame if received within delay; so that in a burst of commands, the overhead is two initial frames, plus the size of the nonces added to other frames. With great care, that later overhead can be eliminated using precise conventions on how the nonce evolves when there is authenticated activity.

Caution: the problem of making the nonce unpredictable, or even not repeating itself, is notoriously difficult if the adversary has access to the power supply of a slave device with no reliable TRNG (that was the situation in early Smart Cards). The solution of enciphering a counter held in EEPROM with a local secret key superficially seems to work (and even allow to use a nonce twice narrower with increased assurance against reuse); but there are the issues of making a counter that does not go backward on power loss during change; limited endurance of EEPROM to repeated writes to the same location; and the basic difficulty of keeping a secret key secret despite side-channels.


Could one construct a cipher that is secure for friendly parties to use but insecure for hostile parties? Consider the situation of a nation state (Blue) at war with another nation state (Red). Blue wants to deploy a secure cipher that blue currently can not break, but they are considered that Red could reverse engineer the cipher and use it to secure Red's communication (Red is unable to develop it's own secure cipher).

Questions:

How have governments in the past approached this problem?
How could one design such a cipher?

I have been working on an incomplete (maybe impossible) formulation of such a system. I know that asking is "my cipher secure" questions is frowned upon, but I hope my outline below is free of enough implementation details that it will not be seen in such a light. It is more of a "is my cipher possible" question.

Here is my formulation of a backdoor cipher.

Assume a function $g$, takes as input a integer $s_i$ and outputs a cipher $c_s$. That is, $g$ generates ciphers based on a seed $s$.

$$\text{Let }  g(s) =  c_s$$

The cipher $c_s$ has the property that if one knows $s$ one can decrypt all messages encrypted with $c_s$. Thus, the cipher is safe for Blue to use since Red doesn't know $s$ and can't learn $s$ from $c_s$, but if Red attempts to use $c_s$ Blue can decrypt all their communications.

One could build $c_s$ by appending an encrypted (using a public key derived from $s$) form of the key used by $c_s$ to the ciphertext. That is,

$$\text{Let } c_s.\text{encrypt}(key, plaintext) = ciphertext|publicKey_s(key)$$

While in principal this would work it would not satisfy our scenario above because the backdoor is so blatant and easy to remove. Red could just alter the cipher to not append the encrypted form, $publicKey_s(key)$, of the key.

Instead a more subtle approach would be to create a function $g'$, which still takes $s$ but produces both a cipher $c'_s$ and a function $v_s$.

$$\text{Let }  g'(s) = (c'_s, v_s)$$

The cipher $c'_s$ has the property that some of its keys are insecure and some of its keys are secure. The function $v_s$ produces only secure keys.

Blue can generate and distribute many secure keys using $v_s$.

Best case, Red doesn't realize that some keys are weak and some are strong and thus assumes that Blue would never use a cipher that Blue could break. Red trusting in this uses $c_s$ for secret communications.

Even if the vulnerability comes to light, Blue communication are still secure and Red still can't generate strong keys. Nor can Red use captured keys that were generated by Blue because Blue remembers generating them.

Question: Is this scheme is remotely possible, if so what math could be used to construct it?

EDIT:

I wrote this up as "Imagining a Secure Backdoor Cipher".

Mathematically, it can probably be done.  There has been research into trapdoor block ciphers.  See, e.g., A family of trapdoor ciphers by Rijmen and Preneel, and follow-up papers.

In practice, though, the problem statement is not realistic.  The assumptions are just not realistic.  Today, there's no reason why Red would be limited to using Blue's ciphers.  Instead, Red could just use any well-vetted cipher, like AES.  There's no reason why Blue should assume that Red will use Blue's ciphers; that's just not how adversaries are likely to behave given the current state of the public literature.  So while your problem statement might have been relevant and interesting to ponder 40 years ago, when there was no public literature on cryptography ... today, it is irrelevant.


How can I remove my personal data from my PGP public key? According to this Q&A-discussion it is possible to remove all personal data (name and mail address) that is attached to a public key.

What steps do I have to follow in order to remove all personal data?
Will that modified public key still allow me to decrypt data with my regular passphrase?

You cannot remove all UIDs, but you can create one which does not link to your identity and remove all others.

Backup your .gnupg folder (for unix systems, for Windows wherever your key is stored)!
Start editing your key:

$ gpg --edit-key 47AB515A

Create an anonymous UID:

gpg> adduid
Real name: Anonymous
Email address:
Comment:
You selected this USER-ID:
    "Anonymous"

Now we're ready to delete all others, but need to know which to remove:

gpg> list

pub  2048R/DEADBEEF  created: 2013-07-28  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
sub  2048R/DEADDA7A  created: 2013-07-28  expires: never       usage: E
[ultimate] (1)  Foo Bar <foo.bar@example.net>
[ unknown] (2). Anonymous

Every UID has a number (in parentheses).
Select all UIDs you want to remove (probably all but the newly created one):

gpg> uid 1

And repeat as needed. All selected UIDs will have a star in their record:

[ultimate] (1)* Foo Bar <foo.bar@example.net>

Delete all selected UIDs:

gpg> deluid

Save and exit:

gpg> save

This removes all personal information from your key - including all signatures (each is bound to an UID), so your "stripped down" key will lose all trust.

You will be able to use it like before; usually every OpenPGP encryption container contains your key ID which does not change, neither does your pass phrase.

If you did not publish your key yet, nobody will be able to find out who you are based on your OpenPGP key. As the key ID stays the same, an already published key can be looked up on the keyservers, they will not delete your UIDs but combine all they ever saw. You can never remove a published key or parts of it from the keyservers.

Caveat: The sender now must select which key to encrypt to as his client cannot automatically assign a key to your email address any more (well, you deleted it).


What constructions for data authentication are subject to the birthday paradox? $H(m\mathbin\Vert k)$ as an authentication algorithm, where $H: \{0, 1\}^* \rightarrow \{0, 1\}^{n}$, has at most a strength equivalent to $\frac{n}{2}$ bits. $H((k^\prime \oplus \mathrm{opad})\mathbin\Vert H((k^\prime \oplus \mathrm{ipad})\mathbin\Vert m))$, the definition of HMAC, has an upper strength of $n$. The security of block cipher modes and block ciphers providing authentication is less clear to me. What parts of a MAC algorithm construction determine if it has a strength of $n$ bits as opposed to half that number?

It turns out that the birthday paradox figures into both the suffix-MAC $H(m \mathbin\Vert k)$ and the HMAC $H((k \oplus \mathrm{opad}) \mathbin\Vert H((k \oplus \mathrm{ipad}) \mathbin\Vert m))$, but in different ways.  And, curiously, there is no theoretical formalism in the field of ‘provable security’ for the way that it figures into suffix-MAC, which is the one that, as you observed, is practically relevant.

The quick summary is that, for a $b$-bit hash function $H$, when $k$ is unknown to an attacker, for suffix-MAC $H(m \mathbin\Vert k)$, the attacker can spend $2^{b/2}$ work offline to find messages $m_a \ne m_b$ that collide under $H$, whereas for HMAC, the attacker must interact online with your system for $2^{b/2}$ messages before they're expected to stumble upon messages $m_a \ne m_b$ that collide under $\operatorname{HMAC-}\!H_k$.

Because $2^{b/2}$ offline work is sometimes feasible, e.g. if $b = 128$ as in MD5 (which also has nongeneric collision attacks that reduce the work to something negligible), whereas $2^{b/2}$ online interactions with a single application is nearly unthinkable, when summarizing MAC security we usually paper it over and say that suffix-MAC has $b/2$ bits of security while HMAC has $b$ bits of security—but you'll find the gory details in papers analyzing the ‘provable security’ of any MAC.

In a little more detail:

The suffix-MAC construction $H(m \mathbin\Vert k)$ for an iterated hash function $H$, i.e. roughly where $H(m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots \mathbin\Vert m_{n-1}) = f(\cdots(f(\mathit{IV}, m_0), m_1)\cdots, m_{n-1})$, is vulnerable to collisions in $f$: if you can find initial message blocks $m_a \ne m_b$ such that $f(\mathit{IV}, m_a) = f(\mathit{IV}, m_b) = h$, then the messages $m_a$ and $m_b$ always have the same authenticator $$H(m_a \mathbin\Vert k) = f(f(\mathit{IV}, m_a), k) = f(h, k) = f(f(\mathit{IV}, m_b), k) = H(m_b \mathbin\Vert k),$$ as do any pairs of messages that start with $m_a$ or $m_b$ and share a common prefix, $m_a \mathbin\Vert m'$ and $m_b \mathbin\Vert m'$.

An adversary who knows $f$ and $\mathit{IV}$—which are a public function and constant, respectively, in cases like SHA-256—can work offline to try to find such a collision.  Once they've found one, and they will know when they've found one because they can just test it, they may be able to break your application immediately with probability 1 and no prior interaction.

This is practically relevant: cryptosystems based on MD5 and SHA-1 were broken in practice by finding such collisions, and MD5 was even exploited to forge HTTPS certificates in a widely publicized incident of international industrial sabotage by the United States and Israel against Iran (although with RSASSA-PSS signatures, rather than with symmetric authenticators).

What's curious is that there's no theoretical formalism in the field of provable security about this.  Every fixed compression function like SHA-256 has collisions.  We just don't know any yet.  We can't say anything formal about an attacker's success probability after a certain amount of work for attacks on these constructions, because there is nothing randomized about them.  Either the attacker knows a collision (and one certainly exists) or they don't, and while we can informally conjecture about their expertise in cryptanalysis, no formalism in cryptography helps with quantifying probabilities about that knowledge.
$\operatorname{HMAC-}\!H_k$ is vulnerable to an internal collision in $H((k \oplus \mathrm{ipad}) \mathbin\Vert m)$: for every $k$, there are guaranteed to be many pairs of messages $m_a \ne m_b$ such that $$H((k \oplus \mathrm{ipad}) \mathbin\Vert m_a) = H((k \oplus \mathrm{ipad}) \mathbin\Vert m_b).$$  In that case, the two messages share a common authentication tag under the key $k$, and so if the sender provides an authentication tag for $m_a$, the attacker can replace the message by $m_b$ and leave the tag intact, and the receiver will be none the wiser.  (A collision may also happen in the outer $H$, of course.)

But the attacker can't try offline to test whether $m_a$ and $m_b$ collide under $\operatorname{HMAC-}\!H_k$, because they don't know $k$, in the formalism of provable security.  So, the attacker's best strategy (in the cases where we do have security reductions) is just to try substituting messages without changing their authentication tags, and the expected number of attempts at forgery before a collision will be about $2^{b/2}$.

The same applies to other constructions, like CMAC, and this is why, if you look closely at the security reductions for many of these constructions, you will find references to the birthday bound, and forgery probabilities in terms of numbers of queries $q$ as long as $q \lll 2^{b/2}$.  A notable exception to this is polynomial evaluation one-time MACs, which work differently, but that will have to be a bedtime story for another night.


OpenSSL aes-128-cfb does not produce expected size I try to implement aes-128-cfb myself for learning. To confirm whether my implementation is correct, I want to verify it with a well-known library such as OpenSSL. But then I noticed something strange when I try to use OpenSSL to encrypt.
I have file cleartext.txt with the following content:
This is cleartext that will be used to encrypt with OpenSSL.

Then I execute this command
openssl enc -aes-128-cfb -in cleartext.txt -K 48656c6c6f20576f726c642041455321 -iv 72616e646f6d20313662797465206976 -out output.txt

The strange thing is that the output file contains only 60 bytes. AES block is 16 bytes. The expected output size in byte should be multiple of 16. 60 is not multiple of 16.
Did I miss something important here?

Because CFB doesn't require padding similar to CTR and OFB mode of operation. These modes create cipher blocks and one uses the necessary amount from them.

In the case of openssl enc -K -iv the IV is not written to the output file output.txt. Therefore it has the same size as the plaintext in bytes; 61 bytes each for my file. In this case, you must handle the IV. Since you are also providing the IV, make sure that it is not used again. Otherwise, a crib-dragging can occur in the CTR mode or OTP's key re-use.

In the case of -k/-kfile/-pass, The IV and Key are derived from the key derivation method by using the user's password and the 8-byte random salt.
OpenSSL first writes file magic of Salted__ then 8-byte salt then the ciphertext into the file. Now the output size is your magic size + salt size + data-size. In my system, 8+8+61 = 77 bytes.

If ECB mode is used
openssl enc -aes-128-ecb -in cleartext.txt -k -pass -out output.txt

then the size is 80 bytes due to the padding. Of course, ECB doesn't use the IV and one should forget this mode!

CBC mode has similar results with ECB.

The derived IV size can change according to used encryption algoritm like 8-byte block cipher TDES and Blowfish requires 8-byte IV and 16-byte block ciphers like AES and Twofish requires 16-byte IV.

When using the password one might be careful about the entropy of the password and the used key derivation method. Using a Diceware password is recommended and at least PBKDF2 for the key derivation. OpenSSL provides various method for key derivation


Stream cipher vs OTP, with /dev/urandom and secure key exchange My application will work in an office setting where a user can directly and securely collect a long One Time Pad.  For example, it may be 16Gb on a USB drive.  This would fill me with joy except that the OTP will be generated from /dev/urandom and therefore is not 'truly random'.
I understand that /dev/urandom is acceptable for most cryptographic uses, but my OTP would no longer be information-theoretically secure.
In this circumstance, should I continue down the OTP path, or use a stream cipher instead?  Are there other factors to consider?  (Note: I believe the staff can store their OTP securely).

Are there other factors to consider? (Note: I believe the staff can store their OTP securely).

The obvious issues are authentication of data and storage of keys.  I will presume the data being encrypted is personal to each staff member, and is not to be transmitted between staff.
You note that staff can store their OTP securely, on USB drives.  What happens if they get lost?  If the storage used for keys cannot be lost and is secure, you could just store the data there.
I think you have to question how secure a physical piece of storage can actually be.  It's certainly never close to being secure against unlimited physical power in a manner analogous to information-theoretic security.
Data authentication would need to be carefully implemented in order to not affect the security of the scheme, and would require using pad data.  Per Wikipedia:

Universal hashing provides a way to authenticate messages up to an arbitrary security bound (i.e., for any $p > 0$, a large enough hash ensures that even a computationally unbounded attacker's likelihood of successful forgery is less than $p$)

Per the helpful user Poncho:

you can do data authentication with an OTP (and preserve the informational security properties); for example, using an epsilon almost-universal hash function (with OTP providing both the UH keys and xoring the hash output)

Not using data authentication would mean that the data could be tampered with so it seems unlikely that this would be the case.


What info should be signed with a digital signature to provide entity authenticaton for DH? $i \to r\colon\; g^x\bmod p$
$r \to i\colon\; g^y, \langle g^y,g^x\rangle_r$
$i \to r\colon\; \langle g^x,g^y\rangle_i$

Looking at run 2, I am trying to work out why it is necessary to include $g^x$ in the digital signature. Since $r$ is providing the digital signature to provide entity authentication for its public key, $i$'s public key should not need to be included in the digital signature.

Am I right in thinking the message that is being signed must be the same as the message that is being sent? Therefore run 2 should also send $i$'s public key if the digital signature is computed over both of them?

This must surely be adding redundancy and therefore inefficiency to the message.

Thoughts?

Typical signatures start by hashing the message. Thus including more data in a signature doesn't increase the size of the signature, if the recipient knows what you signed (in this case, remembered what they sent in step 1).

You need to hash more data if you include $g^x$, but the cost of hashing a public key is quite low.
If you didn't include some kind of challenge value in the signature a compromised session key would allow impersonation in future sessions, which is undesirable.
I recommend signing all the data exchanged so far (transcript hashing). This leaves much less room for an attacker to manipulate an exchange, which is important, especially for complex protocols like TLS.