Understanding Twist Security with respect to short Weierstrass curves I'm trying to understand the "Invalid-curve attacks against ladders" section of SafeCurves Twist Security page and I have difficulties to apply it to short Weierstrass curves.

That section claims that in order to thwart invalid curve attacks an efficient technique is to use a single coordinate ladder to compute the scalar multiplication.
Then the section goes on in describing twists and explicitly refers to Montgomery Curves, particularly when it says "The Montgomery ladder formulas for $By^2=x^3+Ax^2+x$ also compute scalar multiplication for the twisted curve $(B/u)y^2=x^3+Ax^2+x$".

Now, I understand this is a problem because during an ECDH, implemented with a single coordinate ladder on a Montgomery curve, I can provide a public key on the curve's twist and, if the twist's order is "weak", gain information on the other peer's private key.

But, does this apply to short Weierstrass curves ? If so, how ?

It is my understanding that a nontrivial quadratic twists on a Weierstrass curve has the form $y^2=x^3+c^2ax +c^3b$ where $c$ is a non-square in $F_p$. So the twist modifies both $a$ and $b$ parameter of the curves.
For the attack to work I would assume that it is required to have a scalar multiplication ladder that works on both curves (normal and twisted).
Is this assumption correct ?

Does such a ladder exists for short Weierstrass curves ?

As far as I know all $x$-coordinate only ladders for short Weierstrass make use of $a$ and $b$ in the computation, such as the one of Brier and Joye. How could this work on the twist which as different values for $a$ and $b$ ?

I'm asking this question because if such an algorithm doesn't exist, then I don't see how to apply the measure of twist security to short Weierstrass curves such as NIST P-224 and brainpoolP256t1 as djb did on that page.

The twist attack is best explained in Fouque et al's paper.

While the (quadratic) twist of the curve $E : y^2 = x^3 + ax + b \in \mathbb{F}_p$ is indeed of the form
$E^t : y^2 = x^3 + d^2ax + d^3b \in \mathbb{F}_{p}$ for nonsquare $d$, you can also think of the twist as the
set of points $(x, y)$ in $E^2 : y^2 = x^3 + ax + b \in \mathbb{F}_{p^2}$ where $x$ is exclusively in $\mathbb{F}_p$ but $y$ is either $0$ or only defined in $\mathbb{F}_{p^2}$ (plus the point at infinity, obviously). You can map such points from $E^2$ to $E^t$ as $(dx, d^{3/2}y)$. But you don't have to—you can simply solve the logarithm directly in $E^2$.

Here's a Sage example that demonstrates a twist attack on a Weierstrass curve over the integers modulo $2^{127}-1$:

# Setup fields
p  = 2^127-1
d  = -1 # non square in the field
K  = GF(p)
K2.<z> = GF(p^2)

# this curve has prime order, but a 2^44-smooth twist
a  = -3
b  = 2045
E  = EllipticCurve(K, [a, b])
Et = EllipticCurve(K, [d^2*a, d^3*b])
E2 = EllipticCurve(K2, [a, b])

# precompute orders
print E.order().factor();
print Et.order().factor();
print E2.order().factor();

# generate a discrete logarithm to solve
s  = randint(0, E.order())
P  = E([0, 26743016104147931148362869907315104519])
Q  = s * P

# query target with an invalid point
# of order 207464639
P_ = E2.lift_x(randint(0, p))
while P_.order() != Et.order():
  P_ = E2.lift_x(randint(0, p))

P_ *= Et.order() // 207464639

Q_ = s * P_ # query -- pretend this is done with an x-only ladder

# solve the log directly on E2
x1 = P_[0]
x2 = Q_[0]
s_ = E2.lift_x(x1).discrete_log(E2.lift_x(x2))

# map to Et (optional) and solve
x1  = d * P_[0]
x2  = d * Q_[0]
s__ = Et.lift_x(x1).discrete_log(Et.lift_x(x2))

print s % 207464639
print s_, -s_ % 207464639 # either one or the other
print s__, -s__ % 207464639 # either one or the other

So you can see that there is no manipulation of the $a$ and $b$ parameters of the curve: the only thing required in a twist attack is to send an $x$-coordinate for which $x^3 + ax + b$ is not a square in $\mathbb{F}_p$. Note that since both $x$, $a$, and $b$ are well-defined in $\mathbb{F}_p$, an $x$-only ladder for $E$ will also work for points of the twist defined in $E^2$. Perhaps an easier way to understand why it works is to rewrite $y^2 = x^3 + d^2x + d^3b$ as $dy^2 = x^3 + ax + b$.


Prove the branch of number of Advanced Encryption Standard In the Advanced Encryption Standard (AES) document: page 27 section 7.3.1, It defines branch number. It said

  " Let F be a linear transformation acting on byte vectors and let the
  byte weight of a vector be the number of nonzero bytes. The byte weight of a vector is denoted by $W(a)$.

  Definition: The branch number of a linear transformation $F$ is
    $$min_{a\neq0}(W(a) + W(F(a)))$$

  If the branch number is 5, a difference in 1 input (or output) byte propagates to all 4 output (or input) bytes, a 2-byte input (or output) difference to at least 3 output (or input) bytes. Moreover, a linear relation between input and output bits involves bits from at least 5 different bytes from input and output."

The AES chose polynomial $c(x)=03x^3+01x^2+01x+02$ to construct MixColumn operation , where the coefficients are hexadecimal representation of numbers in $GF_{256} $(e.g. $03_{hexadecimal}= 0000 0011_{binary} =\alpha+1_{polynomial\,representation}$) The MixColumn operation is done by multiplying $c(x)$ and mod $x^4+1$

However, the document doest not give a mathematical proof. My questions are

Prove the maximum branch number is $5$. Besides, AES MixColumn can achieve the maximum value as $5$.
given a branch number, how to construct the linear transforamtion
$F(\,)$ (in the case of AES, it is $5$) ?
Reversely, given $F$ (a matrix), how to estimate its branch number?
For example, how should I prove that if the linear transformation is
self-inverse
($\;(c(x))^2\equiv 1 \;mod\,x^4+1$ or $F^2=I$ ), then the
branch number is at most $4$?

I suppose these problems are related to matrix norm, but I do not know where to start to tackle these problems.

The dear user @kodlu has answered to the similar question with excellent discussion but I want to answer with linear algebra argument.

We have two definitions for MDS (Maximum Distance Separable) Matrix:

First definition: A matrix $M$ of order $n$ is an MDS matrix if and only if every sub-matrix of $M$ is non-singular.

Second definition: A matrix $M_{n\times n}$ is MDS if and only if

$$
Y_{n\times 1}=M_{n \times n}\, X_{n \times 1} \Longrightarrow \mathop{\rm min}_{X\neq 0}(W(Y)+W(X))=n+1
$$

where $X={[x_0,x_1,\cdots , x_{n-1}]}^T$ and $Y={[y_0,y_1,\cdots , y_{n-1}]}^T$ are vectors  in an arbitrary
 field and $W(X)$ is the number of non-zero elements of $X$.

Now, suppose that we use a MDS matrix( by first definition) of order $4$ and
we want to proof by second definition that it's branch number is 5. Consider our MDS matrix be as follows

$$
 M=\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
$$
the entries $m_{i,j}$ are non-zero because $M$ by first definition is MDS. Now consider the following equation
$$
MX=Y \Longrightarrow
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
 \left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ y_{{3}}\\ y_{{4}}\end {array}
 \right]
$$
 where $x_i$'s and $y_i$'s are elements of finite field. By second definition $X$ should be non-zero. For simplicity, consider $x_1\neq0$ and other $x_i$ can be zero or non-zero.

We should consider some cases to show that for every selection of $x_2$, $x_3$ and $x_4$, at least four elements of $x_2,x_3,x_4,y_1,y_2,y_3,y_4$ are non-zero.

The first case is $x_2=x_3=x_4=0$. in this case we have:

$$
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\0
\\ 0\\ 0\end {array}
 \right]=
 \left[ \begin {array}{c} x_1\,m_{1,1}\\ x_1\,m_{2,1}
\\ x_1\,m_{3,1}\\ x_1\,m_{4,1}\end {array}
 \right]=
\left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ y_{{3}}\\ y_{{4}}\end {array}
 \right]
$$
 because $m_{i,j}$'s and $x_1$ are nonzero then the elements $y_1,y_2,y_3,y_4$ are nonzero. The next case is that are there non-zero
 values for $x_2,x_3,x_4$ such that

$$
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
 \left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]
$$
due to the $M$ matrix is non-singular we can conclude that
$$
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]^{-1}\left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]=\left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]
$$
and it contradict to our assumption that $x_1,x_2,x_3,x_4\neq 0$ and so one of the $y_1,y_2,y_3,y_4$ should be non-zero.

The next case is that: are there for example $x_1\neq0, x_2\neq0 ,x_3=x_4=0$ that result
 $y_1\neq0, y_2\neq0 ,y_3=y_4=0$. Consider there was this case as follows

$$
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_2
\\ 0\\ 0\end {array}
 \right]=
\left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ 0\\ 0\end {array}
 \right]
$$
so we have
$$
 \left[ \begin {array}{cc} m_{{3,1}}&m_{{3,2}}\\ m_{
{4,1}}&m_{{4,2}}\end {array} \right]  \left[ \begin {array}{c} x_{{1}}\\ x_{{2}}
\end {array} \right]=
\left[ \begin {array}{c} 0\\ 0\end {array} \right]
$$
from the first definition all sub-matrix of $M$ has non-zero determinant and hence we can conclude from the above equation that the values of $x_1=x_2=0$ and it contradict to our assumption.

The other cases are similar to mentioned cases and use from this fact that all sub-matrix of $M$ have non-zero determinant.

I hope you find it useful.


PKCS#11: Which CKK_types are supported by CKM_PKCS5_PBKD2? On Solaris there's a function pkcs11_PasswdToKey() which is a wrapper of C_GenerateKey(). I made a simple test and it turned out that pkcs11_PasswdToKey() only supports following CKK_types:

CKK_AES
CKK_BLOWFISH
CKK_DES
CKK_DES2
CKK_DES3
CKK_RC4

From my understanding, other symmetric ciphers (like CKK_IDEA) should also be supported. Can anyone make some clarification?

I am not familiar with that specific Solaris library (is that a software token?).

However, what I can say is that PKCS#11 does not set any minimum requirement for the algorithms that a certain implementation should offer. CKK_IDEA could be supported, but only if the implementer chooses to. For instance, up to a few years ago, IDEA was patented and it was often not included in libraries and devices for legal reasons.

Besides, that is there any good reason not to use CKK_AES? That is the best choice in most cases.


Confusion about security of quantum key distribution In Quantum Key distribution, it is my understanding that when Eve tries to intercept photons being sent from Alice to Bob, she has a 50% chance of using the correct polarization filter, and so 50% chance of getting the correct bit information. Let's just say hypothetically that she somehow gets all the photons she intercepted using the correct filter (and hence correct bit information), and re emits them so that they're all exactly the same photons as Alice had intended them to be.

Doesn't this mean that during the error reconciliation between Alice and Bob, they'll detect no errors and hence conclude that the distribution of the key was secure, but in reality, Eve has perfect information about the "secret" key?
Doesn't this violate the proof that QKD is "provably secure"?

You are right and you are wrong. Indeed, in the scenario that you describe Eve would perfectly break the system (in a certain way). She would learn information about the secret key without being caught. Note, however, that this only has any chance of success for a small amount of bits. The chance of success when measuring $x$ qubits is $2^{-x}$ (in this idealized setting ignoring all the implementation attacks). That's why you cannot use the the plain exchanged bit string. Instead, you have to use privacy amplification. There are different methods for this. The main idea is that you use some function to turn a long bit string of which Eve possibly knows some bits into a short bit string about which Eve has no information as long as she did not know a lot of the input bits. Choosing parameters right, you can that way ensure that as long as Eve does not learn more than e.g. $128$ bits of the original bit string the output string (used as secret key later) has e.g. $128$ bits of entropy.


Why don't crypto-currencies use the Lamport signature scheme? The Lamport signature scheme is faster, less complex and considerably safer than ECDSA. It's only downside - being only usable once - isn't really a downside when signing transactions, since you could just include your next public key whenever signing it. Why isn't, thus, the Lamport signature scheme used in crypto currencies such as Bitcoin?

The major issue will be size difference. The size of ECDSA in bitcoin is much less than the Lamport Signature.

For ECDSA in bitcoin

The public key is only 33 Bytes (1 byte for prefix, and 32 bytes for 256-bit integer x)
Signature is at maximum 73 bytes

Whereas in Lamport Signature

The public key is 512 numbers of 256-bit (total of 16KB)
The Signature is 256 number of 256-bit (total of 8KB)

The size of Lamport public key and signature together is 231 times (106 bytes vs 24KB) more than the ECDSA public key and signature.

The public key and signature form part of each bitcoin transaction and are stored in block chain. So use of Lamport Signature will need 231 times more storage than ECDSA. As of 1 Oct 2017, the Blockchain size is approximately 135GB. Had it been the Lamport Signature, this would have been in TeraBytes. This would have resulted in higher storage and bandwidth requirement, less number of transactions in one block(which may create backlog, as one block is committed in 10 minutes) and more time in blockchain propagation to other nodes.

Moreover, In bitcoin each transaction is charged a network fee based upon transaction size(in terms of bytes, not in terms of amount). At the moment, the network fee rate is 178, 149, 120 satoshi / byte for high, medium and low priority respectively.


Is forward search attack is the same as dictionary attack? Currently, I started to learn about secure passwords in password file. The password file contains the hashed values for passwords. I know that the forward search attack for a password that if an intruder could have an access to password file in a system. Then he/she could hash the most common password and compare them to the ones in the password file looking for matching. While the dictionary attack the intruder compute the hash for the password and looks for them in a dictionary of common passwords.

For me, both of the definitions looks like the same. So is forward search attack is the same as dictionary attack?

In the context of passwords, a dictionary attack is a forward search attack improved by using a dictionary of likely passwords (best ordered from most to least frequent), rather than enumerating all possible passwords in a mechanical manner (like in lexicographic order).

In other words, the dictionary attack necessarily uses a dictionary, when a forward search attack can do without.


Is it possible to apply hill-climbing algorithm to Diffie–Hellman? If Eve intercepts all the values communicated between Alice and Bob in a Diffie–Hellman key exchange, and applies the hill-climbing algorithm to reverse the modulo function, how will the algorithm know whether it is following the right path?

NO, we can't apply an hill-climbing algorithm to Diffie–Hellman.

In order to break Diffie-Hellman key exchange, it is enough for Eve to reverse exponentiation modulo the public prime $p$; that is, given $g^x\bmod p$, find $x$. That's the Discrete Logarithm Problem.

We do not know that hill-climbing can help for that (or the slightly less general DH problem). One reason is that in the DLP, we have no known way to estimate if a guess of $x$ is close or far from the solution (contrary to what happens for the continuous logarithm problem). Hill-climbing is nice when it works; but in crypto, it tends to work only against weak/broken systems.


Does a practical collision attack on a cryptographic hash function also mean it fails “indistinguishable from random data”? It is knowns that SHA-1 has been broken in practice using collision attacks. Related to SHA-1 this mainly had a negative impact on the security of

Digital Certificate signatures
Email PGP/GPG signatures
Software vendor signatures
Software updates
ISO checksums
Backup systems
Deduplication systems
etc.

Thinking about a LUKS related Q&A at our site, I'm wondering if a collision attack also means that the broken hash like SHA-1 can – or maybe even should - also be considered “distinguishable from random data” (from a cryptographic point of view).

Does a practical collision attack on a cryptographic hash function also mean we can (or should) consider it to fail “indistinguishable from random data”? Or does a collision attack have no influence on that?

Does a practical collision attack on a cryptographic hash function also mean we can (or should) consider it to fail “indistinguishable from random data”? Or does a collision attack have no influence on that?

For a random oracle with output length $n$, it takes $2^{n/2}$ time to find a collision.  So if you have a hash function with output length $n$ as well but for which there's an attack that finds a collision in less than $2^{n/2}$ time, then the hash function doesn't behave like a random oracle, period.  The function has some property that a random oracle does not have.

Note that even before we ever found a collision, we already knew that Merkle-Damgård hash functions like MD5, SHA-1 and SHA-2 don't behave like random oracles, because they're vulnerable to length extension attacks: for any choice of message $m$, an adversary who knows the result of $\mathrm{hash}(m)$ and the message length $|m|$ can use this knowledge to "shortcut" the calculation of $\mathrm{hash}(m || \mathrm{pad}(|m|) || s)$ for any choice of $s$.  A random oracle doesn't have this property—knowing the hash for any message is of no help for predicting the hash of any extension of it.

This doesn't mean that it's impossible to find some construction that uses the hash function in a carefully restricted way such that its output is indistinguishable from random (and indeed, HMAC-SHA1 is claimed to be a pseudorandom function—a function such that if you pick a secret key at random, the adversary can't tell it apart from a random function).  It means that from the point of view of an adversary that has control over the input of the hash function, they can very easily tell that it doesn't behave like a random function would.

(Note that I have been careful to talk about random oracles and random functions instead of just the outputs of a function; the very stringent question we ask of a hash function is how it behaves from the point of view of an adversary who can choose what inputs to feed to it.  Again, this doesn't rule out the possibility that in a weaker attack model—one where the adversary has fewer powers—the adversary might not succeed.)


Calculating Multiplicative Inverse for Rijndael S-box using EEA I am currently learning, and I'm stuck on something that I thought is very simple. On many academic sources they suggest using Extended Euclidean Algorithm to calculate the multiplicative inverse for calculation of the S-Box, but I could not find a proper explanation how to do that. Every practical approach calculates log+antilog and uses that. But I'm stubborn and I want to use EEA!

I got my algorithm from here: https://www.youtube.com/watch?v=fq6SXByItUI

For my calculations I used values 0xCA and 0x53.
When I multiply them using the Rijndael finite-field multiplication I get 1. So I know that they are each others inverses. But when I put them inside EEA I get a different value :(

0x53 = 83
0xCA = 202
0x11B = 283 (Rijndael Plynomial)

283 = 3 * 83 + 43   |   34 = (1) * 283 + (-3) * 83
 83 = 2 * 43 + 15   |   15 = (-2) * 283 + (7) * 83
 34 = 2 * 15 + 4    |   4 = (5) * 283 + (-17) * 83
 15 = 3 * 4 + 3     |   3 = (-17) * 283 + (58) * 83
  4 = 1 * 3 + 1     |   1 = (22) * 283 + (-75) * 83

The final result is correct according to google calculator.

When I use modulo 283 on both sides I get:

1 = (-75) * 83 = (283 - 75) * 83 = 208 * 83

So I got 208 instead of 202!

My experimental implementation of this procedure is here.

public static int RijndaelInverse(int a)
{
    int old_s = 0; int s = 1; int new_s = 0;
    int old_t = 0; int t = 0; int new_t = 1;
    int old_r = 0x11B; int r = 0x11B; int new_r = a;

    while (new_r > 0)
    {
        int quotient = r / new_r;

        old_s = s;
        s = new_s;
        new_s = old_s - quotient * s;

        old_t = t;
        t = new_t;
        new_t = old_t - quotient * t;

        old_r = r;
        r = new_r;
        new_r = old_r - quotient * r;
    }

    if (r > 1) return 0;
    if (t < 0) t = t + 0x11B;

    return t;
}

I tried substituting the multiplication with RijndaelMultiply and subtraction with RijndaelSubtract but that broke the whole algorithm and gave me crazy values. I think it's because the algorithm requires negative values to work, and there is no easy way of dividing polynomials that I know of.

Does anyone know how to correctly use EEA with Rijndael finite-field?

[EDIT] Working implementation

public static uint RijndaelInverse(uint a)
{
    uint old_s = 0; uint s = 1; uint new_s = 0;
    uint old_t = 0; uint t = 0; uint new_t = 1;
    uint old_r = 0x11B; uint r = 0x11B; uint new_r = a;

    while (new_r > 0)
    {
        var r_msb = (int)Math.Log(r, 2.0);
        var new_r_msb = (int)Math.Log(new_r, 2.0);

        int quotient = r_msb - new_r_msb;

        if (quotient >= 0)
        {
            old_s = s;
            s = new_s;
            new_s = old_s ^ (s << quotient);

            old_t = t;
            t = new_t;
            new_t = old_t ^ (t << quotient);

            old_r = r;
            r = new_r;
            new_r = old_r ^ (r << quotient);
        }
        else
        {
            new_s = s ^ new_s;
            s = s ^ new_s;
            new_s = s ^ new_s;

            new_t = t ^ new_t;
            t = t ^ new_t;
            new_t = t ^ new_t;

            new_r = r ^ new_r;
            r = r ^ new_r;
            new_r = r ^ new_r;
        }
    }

    if (r > 1) return 0;

    if (t > 0xFF) t ^= 0x11B;

    return t;
}

To do EEA on a finite-field, you can't perform the operations using the operations in the ring of the integers (and they're not precisely the same operations in the field either, as you're working with bit vectors, not field elements).  In particular:

When you do "addition", you need to perform the addition as done in even characteristic fields (that is, you actually do an exclusive-or).
"Subtraction" is actually the same as "addition", so you use exclusive-or for that as well.  Yes; addition and subtraction are the same thing; we're not in Kansas anymore.
The "multiplication operation" is actually a bit shift, as so we would have something like:

new_r = old_r ^ (r << quotient);

What you want is to have (r << quotient) cancel out the msbit of old_r; To make this work, your 'divide' operation needs to effective compute how far the r needs to be shifted left so that the exclusive-or will cancel out the msbit (and hence reduce the size of r).
The test at the bottom (if t is out of range) looks differently.  It turns out (with the above changes) t will never be negative; it might be larger than 255

The Extended Euclidean algorithm can be made to work.  On the other hand, I'm having a hard time seeing a situation where it is a best algorithm for this job.  It's not nearly as fast as a simple table lookup, and it's not even slightly side channel resistant.


Is a bit string pseudorandom if it starts with predictable bits? Assume we have $k = n + m$ bits string $S$ where the first $n$ bits are predictable, and the last $m$ bits are pseudorandom (the HMAC of the first $n$ bits + IV). Can we say $S$ is a pseudorandom number?

What can we call S exactly?

No, first of all, you've defined it to be a bit string. A bit string is not a number although you can of course interpret it as a specific number.

Furthermore, it is not pseudo-random if we assume that the number is between 0 and the maximum value for S, as it clearly is either in a range, or it ends with a lower end bits set to a specific value.

Now if we assume big endian then you can however consider $S$ pseudo random in the range $\Big[N \cdot 2^m, (N + 1) \cdot 2^m \Big)$ where $N$ is the big endian value of the first $n$ bits of $S$.

I don't know what we can call $S$, it's a constructed bit string. With the HMAC it could be some kind of token, but that's speculating on a specific use case for it.


Elliptic curve cryptography related key attacks This question is an extension of Families of public/private keys in elliptic curve cryptography

As described above, bitcoin "type 2" deterministic wallets use a root private/public key pair, where subsequent keys take advantage of the fact that in elliptic curve cryptography the public key for a private key + a fixed number, happens to be another public key plus the same number times a point.

Symbolically, with root private key $a$, public key $A$, 'fixed number' $b$, hash function $H(\cdot)$, we could construct a new private key as:

$a' = a + H(b)$,

which gives the corresponding public key as:

$A' = A + H(b) \cdot G$, where $G$ is the generator of the elliptic curve group in question.

There was some discussion about the properties $H(i)$ should have, with the responder being unsure if $H(i)=i$, or any $H$ at all, results in a secure system. This issue has been discussed in the bitcoin community as well, with the consensus being that if $H$ is a pseudorandom function, the idea is secure. Theory aside, this is exactly how a number of production "type 2" deterministic wallets work, and they haven't been hacked yet.

Building on that sandy foundation, I'd like to extend the idea even farther. Specifically, I'm creating a wager service, where I'd like users to be able to submit their wagers by sending bitcoins to specially encoded addresses. My thought was to use $H(\mbox{bet details} | \mbox{return address})$ with $|$ representing concatenation and $H$ a pseudorandom function. Thus the final public key for the address becomes $A + H(\mbox{contents})\cdot G$ and the private key $a + H(\mbox{contents})$

If the bet details are restricted to a small search space, and the return addresses restricted to addresses seen on the bitcoin network in the last $n$ blocks, simple brute force checking of every transaction to see if it is part of the system is quite feasible.

Note that I do not care if someone can determine if a given public key is related to another; the system will be completely public and all public keys will be determinable by anyone. In fact, for this application this property is an advantage for reasons of transparency.

The problem is, this gives the attacker a lot of control over the value $H(\mbox{contents})$: they can set an arbitrary number of bits by exhaustive search, incrementing the return address as required. If the service then spends the payments it is forced to use related private keys chosen by the attacker. To me, this smells bad, but if ECC is genuinely secure against related keys, it's not a problem.

Now I will say, a countermeasure would be to include (in the contents of $H()$) the block hashes of $n$ consecutive bitcoin blocks seen after the receiving address was last in the block chain. This assumes that no attacker has the hashing power to choose the hashes of $n$ consecutive blocks; a particularly strong statement as even to generate one block you are heavily constrained by the requirement to create a partial collision; $n=1$ may be sufficiently secure. However this extension would complicate the user interface and slow down the wagers which I'd like to avoid if possible. The attacker  would still have control over the bet details as well.

Quite simply: Is my proposed scheme secure, and why?

The answer depends on your definition of security:

Anonymity: this scheme will produce key pairs, and hence also public addresses, that are indistinguishable from random to anyone who does not know the hash function contents, if the hash function is modeled as a random oracle.
Cryptoeconomic security: People will not try and game your scheme if you can ensure that the value of gaming your scheme is less than the cost of doing so. In your example, if you use the blockhash within the protocol, an adversary controlling the blockhash may withhold the block they have successfully mined, in order to give themselves a better than average chance at winning your game.
With this knowledge, you can find the lower bound on how motivated and powerful an adversary attacking your scheme must be by defining a security parameter $n$ such that:
$$ \mbox{value gained by winning your game} < n * \mbox{bitcoin block reward}.$$

For your question of whether creating signatures with 'related keys' is secure, this is something I'm currently working on formally proving. With the hash function modeled as a random oracle, I believe we have the result that one can produce: $$a' = a + H(S),$$ and hence spend funds associated with an account if and only if they know the $A$ such that:
$$ A' = A + H(S) \cdot G,$$
with $G$ the generator of the elliptic curve group in question. However, this is dependent on your opinion of hash functions as random oracles. $H(i) = i$ would definitely not be sufficient, and $S$ is assumed to be secret.

EDIT: If $H(S)$ is not secret, there will be a de-anonymising attack on all transactions associated with your account, but people will not be able to forge transactions from you, or spend the bitcoin from that account, as they will not have the root private key $a$ necessary to form the private key. They will simply be able to scan the blockchain and group the accounts associated with you. This is how view keys and spending keys in anonymous cryptocurrencies such as Monero work.


Unique GCM/CCM initial counters without recipient side message counters I am implementing the encryption layer for a communication protocol. The bulk encryption method used is either AES-CCM or AES-GCM. Due to implementation details, encryption of packets is usually, but not necessarily, performed by the sender in the same order the packets are sent over the network. This means two things:

Implicit packet counters can't be used to ensure that the initial counters are unique,
Explicit packet counters shouldn't be sent as plain text, due to implementation-specific side-channel attacks. (When packets are sent out of order, it is due to things happening sender side the attacker shouldn't be unnecessarily made aware of, and that would be significantly harder to spot using frequency analysis only.)

Packet counters are however sent encrypted and verified by the recipient using a sliding window technique.

Additionally, the following requirements should be met if possible:

No additional AES context should have to be maintained for each connection. i.e. if AES encryption is used in any way, it has to be done using the same key as for bulk encryption.
The size of the packets should be kept as small as possible. The overhead of the ciphertext should be equal to the 96-bit nonce, 128 bit MAC, plus optional padding that might be used to mask the length of the plain text.
I don't want to consider all possible security implications of letting the recipient simply try all possible implicit packet counter values in order (DOS-attacks, timing attacks, etc).

Thus, I am thinking a simple two-round unbalanced Luby-Rackoff cipher could be used for generating the nonces sender side, e.g.:

Let $T$ be the 32 bit encoding of the packet counter value.
Generate a 64 bit random bit string $S$.
Let $U = MSB_{32}(AES_k(0^{32}||S||0^{32})) \oplus T$
Let $V = MSB_{64}(AES_k(0^{32}||U||1^{64})) \oplus S$
If $MSB_{32}(V) = 0^{32}$ goto 2.
Let $Nonce = V||U$.

Since the transform is bijective, these nonces will be unique. Furthermore, the padding ensures that the plain text blocks passed to $AES_k$ do not collide with any counter values. Also, $AES_k$ is rekeyed at least once every $2^{32}$ packets, plus that the nonces aren't decrypted by the recipient since the packet counter value is also sent encrypted as part of the "regular" plain text.

The question is what the security level of the confidentiality of the packet counter values become?

Obviously, by the birthday paradox, there is a 0.5 probability that the same $S$ value will be generated at least twice before the cipher is rekeyed, and since the packets are sent in order most of the time, it should at least be easy to spot when such $S$ collisions do not happen, but is it possible to distinguish such occurrences caused by chance from those caused by $S$ collisions with non-negligible probability? Should a third-round be added?

Perhaps a workaround for this would be to instead use deterministic nonce generation with AES-GCM-SIV, which has been formally proposed in a paper by Shay Gueron and Yehuda Lindell. The core idea is to use the MAC over the plaintext as part of the initial counter for encryption and reuse that as a tag on decryption.

This can be bolted onto any AES and GCM implementation if you have the ability to call GHASH standalone.

This has several advantages:

The counter only needs to be kept for re-keying, but no longer needs to be sent over the network in any way.
You gain IV/nonce reuse resistance (though it still leaks whether two messages were identical), possibly allowing randomized nonces safely.
You're back on the “beaten path” so that you're back in an area where cryptanalysis exists, rather than homegrown cryptography.

But also disadvantages:

You need an initial extra AES call to derive the internal keys when initially setting up keys, plus an extra call with a separate context for every authentication tag.
The scheme is inherently dual-pass, once to derive the authentication tag and once for the encryption/decryption, so it may be unacceptably slow for your use case.

Technically, this meets your criteria:

  Implicit packet counters can't be used to ensure that the initial counters are unique,

Non-uniqueness no does not lead to a loss of confidentiality with AES-GCM-SIV. You can avoid using a counter and instead use a randomized nonce (or a fixed nonce if you know all messages will be unique, e.g. by making the counter part of the message body instead).

  Explicit packet counters shouldn't be sent as plain text, due to implementation-specific side-channel attacks. (When packets are sent out of order, it is due to things happening sender side the attacker shouldn't be unnecessarily made aware of, and that would be significantly harder to spot using frequency analysis only.)

The packet counter does not have to be sent in any way with AES-GCM-SIV.

  Additionally, the following requirements should be met if possible:

  No additional AES context should have to be maintained for each connection. i.e. if AES encryption is used in any way, it has to be done using the same key as for bulk encryption.

AES-GCM-SIV unfortunately requires a second AES context to encrypt the GHASH output with, but this requirement is only a “should”.

  The size of the packets should be kept as small as possible. The overhead of the ciphertext should be equal to the 96-bit nonce, 128 bit MAC, plus optional padding that might be used to mask the length of the plain text.

Depending on how exactly you implement this, the size of the packets will actually go down if you use a fixed nonce and unique message bodies.

  I don't want to consider all possible security implications of letting the recipient simply try all possible implicit packet counter values in order (DOS-attacks, timing attacks, etc).

There won't be any packet counter values to try because it's completely out of the attacker's hands.


How does the TLS Client Hello message choose the TLS version? Im looking at a Client Hello message in wireshark, the client supports 1.2 and 1.3, but Wireshark says the client used TLSv1.3 record layer when the server hasn't replied yet the choosen version.

How can this be explaned?
Also, why after that i see version 1.0 and version 1.2 if version 1.3 was used?

TLS 1.3 record layer is shown because the ClientHello contains TLS 1.3 as supported version. This can be seen at the bottom of the following image. See also TLS record layer and Handshake protocol at ask.wireshark.org.


How can AES be considered secure when encrypting large files? Why is AES considered to be secure when encrypting large files since the algorithm is a block cipher?

I mean, if the file is larger than the block size, the file will be broken down to fit the blocks. Then the same key is used to encrypt each block of the file. And as I know it, using the same key to encrypt multiple messages/blocks is not a good idea. Is not that how AES works?

Or do I have misunderstood something? :-)

Encrypting big amounts of data is no problem for block cipher - if you remember a few important things.

You can't encrypt plaintext which is bigger than the block size. You need to do some addition work. Most cipher operation modes first divide the plaintext into blocks of the size of the cipher. Now you can do different things: How about just encrypting each individual block, plain and simple? That's called ECB mode.

What happens if you encrypt the same block twice at different positions in a file? You get the same cipher text. If an attacker sees this, he can tell: "At this two positions there's the same plaintext." - The attacker could also swap two blocks without it being detectable (at least if the decrypted plaintext still makes sense).

Then there's the CBC mode. You first xor an Initialization vector (IV) with the first plaintext block. The IV should be randomly generated and has to be as big as the block size. Now you encrypt the resulting block. This is your first ciphertext block. As next step, you xor this first block with the next plaintext block. Block cipher algorithms create mostly random looking blocks after encryption and as a result, the xor of this and a plaintext block creates a new block to encrypt. This removes the two mentioned problems of the ECB mode: Swapping two blocks results in at least one garbage plaintext block. Also the same plaintext block will (in nearly every case) encrypt into different ciphertexts.

There are many more encryptions modes like the Counter mode (CTR). Also you should normally use some kind of Authenticated encryption. The use of a good cipher mode is not enough to avert most attacks. Things like a Message authentication code (MAC) are also important. A commonly used, but pretty complex way of combining both ways is the Galois/Counter Mode.


How secure is this block cipher? As an 17-year old highschool student with some interests into cryptography I developed following block cipher:

Let $H$ be an irreversible hash function with the block length $L$, which also is the block and key length.  (I used SHA-256 for my example implementation below).

$O$ is the original key while $K$ is the expanded (and mutated) key.

First, the key is expanded to the length of the plain text $P$ using following scheme:

$K_0=H(O)$

$K_n=H(H(K_0,n) \oplus O)$  ($K_0,n$ should be the n'th byte of $K_0$)

Next, the ciphertext $C$ is set to $P$ and following modification of the feistel round is being run 64 times, please note that $C_0$ are the first 64 bits of an block, $C_1$ the second 64 bit, etc.

$C_2 = C_2 \oplus ((C_3 \oplus K_3) \lll 41)$

$C_1 = C_1 \oplus ((C_2 \oplus K_2) \lll 29)$

$C_0 = C_0 \oplus ((C_1 \oplus K_1) \lll 13)$

$C_3 = C_3 \oplus ((C_0 \oplus K_0) \lll 5)$

After each round, the key mutates by $K_n = H(K_n \oplus O)$, this key mutation is not shown in the graph below.

To decrypt, you'll just have to calculate the round keys and apply the rules above in reversed order. Functional java code can be found here.

Sadly, I'm not able to perform an any "modern" cryptoanalysis due to lack of mathematical knowledge, but here are some thoughts on my cipher:

You shouldn't be able to get $O$ unless you are able to break $H$.
Since key expansion and mutation make use of $O$, you shouldn't be able to predict another round key given you already have one and don't know $O$.
An attack vector could be predicting $H$ outcome even without knowing it's input.

I hope you have more idea's when it comes to attacking this algorithm and / or are able to perform known cryptoanalysis.

Thanks in advance

// Edit: Updated algorithm and added graph

As pointed out in the comments, your encryption process is linear (mod 2). So this cipher is very weak, all you need is linear algebra.

See, for example, the question answered here


Pseudo-random generator explanation by Bruce Schneier I am reading about Pseudo-Random Sequences in Applied Cryptography book by Bruce Schneier. Description is provided below.

  A pseudo-random sequence is one that looks random. The sequence's
  period should be long enough so that finite sequence of reasonable
  length —that is, one that is actually used— is not periodic. If you
  need a billion random bits, don't choose a sequence generator that
  repeats after only sixteen thousand bits. These relatively short
  nonperiodic subsequences should be as indistinguishable as possible
  from random sequences. For example, they should  have about the same
  number of ones and zeros, about half the runs (sequences of the same
  bit) should be of length one, one quarter of length two, one eights of
  length three, and so on. They should not be compressible. The
  distribution of run lengths for zeros and ones should be the
  same [643,863,99,1357].

My questions on above text

What does statement "or example, they should  have about the same number of ones and zeros, about half the runs(sequences of the same bit) should be of length one, one quarter of length two, one eights of length three, and so on. " mean?
What does statement "Theere should not be compressible"?
What is number 643,863,99,1357?

Thanks for your time and help

This is a about properties of a random sequence in general.

  What does statement "or example, they should have about the same number of ones and zeros, about half the runs(sequences of the same bit) should be of length one, one quarter of length two, one eights of length three, and so on. " mean?

Consider a coin toss with a perfect coin (i.e. one that doesn't land on the side and lands on head or tail with 0.5 chance). Then about half of the time it will be a head or a tail. If you would toss it infinite times then you would have an equal amounts of heads and tails. However, if you toss it some other amount you'd expect about the same number of heads and tails.

If you would toss the coin an odd number of times you would certainly not have the same amount of ones and zeros, even with a perfect coin.

  What does statement "Theere should not be compressible"?

Probably this should read "they should not be compressible". Things are compressible when a pattern can be found (think .zip files). If a pattern can be found then the sequence is not random. Note that small patterns can exist by chance, so this requirement is a rather heuristic (unless there is a different definition of compressible around).

Then again, you should not be able to always compress the random number sequences generated.

  What is number 643,863,99,1357?

That looks like a set of references to me, nothing to do with the random numbers in itself :)


One time pad- XORing or substitution I have come across 2 versions of otp while reading it and want to confirm it.

they have taken a plain text consisting of alphabets where they are
shifted and replaced by alphabets itself.
XORing of binary I/P streams with binary key.

Are they both valid forms? When I/P is in alphabets, shouldn't we convert it into binary form and then perform XORing with key?

According to the definition on Wikipedia, both are valid uses of the term "one time pad" - "each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition." - that is: e=(d+p)%m, where e=encrypted data, d=decrypted data (input), p=pad, m is the number of possible values in e, d, and p (which must be the same). % is modulus - divide (d+p) by m, but take the remainder.

The most common implementation is the XOR method, which is the above calculation using m=2 (since 1 bit has two different possible values). A byte-by-byte solution would be equally valid, with m=256. letter by letter (m=26) is fine PROVIDED only encrypted data is sent - if you use this but send punctuation, capitals, newlines, and spaces unencrypted (or encrypted as a separate character set, then this is no longer secure (it will leak data - e.g. word lengths, and position and likely candidates for proper nouns, etc.).

Remember also, the pad needs to be really, really random, and of the same length (at least) as the message. It can never be reused. If the pad is English text, it is very insecure.


Security of DGHV Encryption In DGHV Security How to get reliable oracle for least significant bit and then uses binary GCD algorothm that uses reliable oracle to find secret key p.Also what is oracle. Is this a turing machine.How we get Least Significant Bit from it. Please giude. Thanks

You should read this article about Security of DGHV Encryption.

Oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.


Does order matter for RSA when used multiple times? I actually have no idea how RSA works, but I currently (think that I) know

Public and private keys are mathematically doing their opposites
Therefore, the order in which they are applied doesn't matter
The system is cyclic and applying one key repeated times will eventually lead to the starting number

Hoping I am OK till here, these made we wonder if you can apply the keys in any arbitrary order multiple times and come back to the starting number, as long as you use both keys the same number of times.

In textbook RSA, one can apply the public key function $x\to E(x) =x^e\bmod n$ and the private key function $x\to D(x)=x^d\bmod n$ in any arbitrary order multiple times and come back to the starting number, as long as one use both keys the same number of times, and the starting number was in the set $\{0,1,\dots,n-1\}$ (also known as $\mathbb Z_n$ ).

Proof follows from the fact that, assuming proper choice of RSA parameters, $E$ and $D$ are inverse permutations of some set. Using that sole fact, we can prove that applying $i$ times $D$ and $j$ times $E$ to any elements of the set, in any order, is equivalent to applying $i-j$ times $D$ if $i-j$ is positive, or $j-i$ times $E$ otherwise. Proof is by induction on $i+j$.

Fact 3 in the question (which is true for any permutation on a finite set) was not used.

As rightly pointed in comment: RSA as actually used for encryption and decryption adds extra operations like padding to textbook RSA, and that destroys the property discussed; in particular, because the encrypted message's space is larger than the message's space.


Who can create a MAC? Who can verify a MAC? I have read many answers but I cannot get the basic explanation. There's no need for full details. I just need some basic information about who can create a mac and verify it.

Anyone who holds the key can create a MAC. For any secure MAC it should be computationally infeasible to create a MAC without knowledge of the key.

By the correctness of a MAC, anyone who holds the key can verify it. In pretty much any practical MAC, the key is also needed to verify, but this is not something that's actually implied by the functionality or security definitions.


Pen-and-paper one-way function for externally-anonymous survey When conducting surveys, an Administrator might send an Enumerator to survey a Respondent. For "sensitive" questions (e.g. about embarrassing behavior), the Respondent may be fine with the truth being revealed to the Administrator but not to the Enumerator.

Is there a way to create a one-way function/process using simple (small and cheap) physical objects such as pen and paper that isn't too time-consuming or involves complex math? Inverting the function would be too hard for the Enumerator during, or just after the survey, but the Administrator could do it later. Assume that the Enumerator can do anything quickly to uncover the answer (e.g. "accidentally" open a sealed envelope or claim non-random data is random) so long as the Administrator gets the truthful answer in the end. Assume that this is the only interaction with the survey, so no secret information has been passed among the Administrator and the Respondent. FYI: Previous questions include ones about non-computer/manual full cryptosystems and ciphers, but answers to both involve a long time to execute.

There are techniques for doing online surveys on sensitive subjects.  They don't follow the approach you outlined, but here's a sketch of how they work.

Suppose we want to survey people to determine how many people have ever seriously considered suicide (say), but we suspect many people might be unwilling to answer honestly because of the stigma associated with answering yes.  Here's what we do.  We give the respondent an ordinary 6-sided die.  We ask the respondent to secretly roll the die (where the enumerator can't see it).  If the die comes up 1-4, we ask them to answer honestly; if it comes up 5 or 6, we ask them to reverse their answer (tell us the opposite of their true answer).

This provides plausible deniability for respondents.  If they answer "yes", it might be that they have seriously considered suicide; or it might just be that they got a 5 or 6.

It also gives us a way to estimate the fraction of people who have seriously considered suicide.  Suppose a fraction $q$ of respondents answer yes.  Then we can estimate that about $p=3q-1$ of the population of respondents have seriously considered suicide.  We can't identify any specific individual who did or didn't seriously consider suicide, because we only have a noisy view of the truth for any one individual, but we can still compute aggregate statistics.

(Do you see why the formula $p=3q-1$ works?  Suppose a fraction $p$ of the population has seriously considered suicide.  What fraction of people will answer yes, given this procedure?  Well, of the $p$ fraction who have seriously considered suicide, $4/6$ of them will answer yes; of the $1-p$ fraction who have not seriously considered suicide, $2/6$ of them will answer yes; so in total, $4p/6 + 2(1-p)/6$ of the population will answer yes.  A bit of simplification shows that this is equal to $(p+1)/3$.  Of course, we cannot observe $p$ directly, but we can observe this fraction; this fraction is exactly $q$.  So, setting $q=(p+1)/3$ and solving for $p$, we find that
$p=3q-1$.)


Are there some problems to use pseudo-random number generator in Smart Card? A Smart Card is a kind of secure device, with limited storage capacity and
computational resource.

If we use a Pseudo-Random Number Generator to generate random numbers in a Smart Card, then is there any problem?

All modern microprocessor Smart Card ICs contain a physical True RNG, generally followed by conditioning using a hardware de-biaser (such as Van Neumann's) or/and deterministic Pseudo-RNG of some kind that make the TRNG output more indistinguishable from random. Independently, a Smart Card could contain a (Cryptographically Secure) Pseudo-RNG. The later is what the question as worded is about, but I'll cover both.

Yes there are possible problems with these RNGs - and techniques to deal with them.

Defective RNGs happen. In a well-documented recent example, the TRNG used inside a Smart Card to generate its RSA public/private key pair was bad on a fraction of the production, making the RSA modulus factorisable with specialized techniques. This class of failure is a bad design or build of the physical randomness source. Here it was most likely accidental, but an adversary could try to induce similar fault (e.g. by varying the temperature of the IC, its power supply..) e.g. so that a random number generated as challenge by a Smart Card actually repeats with much higher probability than normal.

In order to guard against such failure in TRNGs, the reasonable thing to do is to include tests of the TRNG source at least before conditioning, and use well-thought post conditioning, perhaps including Cryptographically Secure for some usages. This is codified in the AIS31 scheme for common-criteria security evaluation of TRNG (index in German, linking to documents in English; see also how French authorities have been using AIS31 method, including some reservation in section 5).

Sometime, the state of a PRNG is held in non-volatile memory (if it was not, when we power-off the Smart Card, the state would be lost and, absent special precaution, the PRNG's output would be the same each time we power-up the Smart Card, which is a devastating issue). The adversary would like to recover that state, or alter it to a known state (e.g. by removing power while this state is being changed). Well-designed Smart Card hardware and software have layered protections against such attacks on their non-volatile memory, making memory examination extremely difficult, preventing data loss using temporary duplicates and flags, and using techniques for detection (perhaps correction) of errors.

Another issue for implementation of a PRNG in a Smart Card is side channel and fault injection attacks (slides), which try to guess the PRNG state while it normally changes, or alter how it changes (the aforementioned power removal is a fault injection). Again, Smart Cards have an arsenal of countermeasures against these.

Comments suggest comparing use cases of PRNG vs TRNG in a Smart Card.

Smart Cards need randomness, and a lot of it, as part of protection against side-channel attacks. That's starting right at power-up, which can be performed an unlimited number of times (I have seen contactless Smart Card readers doing a hundred power cycles per second). A pure PRNG just can't work: it is deterministic, and will either produce the same output on two card power-up, or require update of a non-volatile memory, which is slow, easily detectable by SPA, and doable only a limited number of times in the operational life of the device. Also, this state must be initialized at some point of the life of the Smart Card, with a random secret, an operational annoyance.

That's why all Smart Cards ICs provide at least one hardware TRNG, at least for their internal use. The only hardware PRNG that I ever met on these ICs was used as post-conditioning of a TRNG. This (conditioned) TRNG provides excellent randomness, of near-crytographic quality, in usably ample quantity, easily and quickly accessible to the low-level system programmer (after a check that the TRNG is actually working, which is a source of serious complications). It is common (and the recommendation of many competent persons beyond French authorities in the aforementioned section 5) to use this as seed to a CSPRNG implemented in software (often using hardware accelerators for a block cipher) for something requiring cryptographic characteristics.


Is there any implementation of threshold BGN homomorphic encryption? The BGN paper (Evaluating 2-DNF Formulas on Ciphertexts) used a threshold variant of BGN. I also want to use this cryptosystem, however, I cannot find any open-source implementation. Is there any such an implementation? If not, how could I implement it (the secret key can be easily shared, but I do not know how to decrypt a ciphertext by each share and then combine these shares to get the final plaintext)? Thank you.

Here are two implementations, I haven't used any of them though.

https://github.com/baonq-me/bgn
https://github.com/nasimmaleki/Cryptography


Why does OpenPGP encryption produce different ciphertexts from the same plain text? With the same plain text to be encrypted and the same public key, OpenPGP tends to produce a different ciphertext every time I run the encryption operation. Why is this?

OpenPGP is a hybrid cryptosystem. The actual message is encrypted applying a symmetric cipher like AES with a random session key. This session key again is encrypted using a public/private key cryptography algorithm like RSA. This is mostly because symmetric encryption is much faster than public/private key cryptography, especially for large messages. As the session key is generated randomly, the cryptotext is different each time you encrypt something.

Another reason is that OpenPGP includes timestamps in different packets.


Why is ECBC-MAC with one key insecure? For handling variable-length input and having the calculation of the MAC remain online, encrypting the output of CBC-MAC with a second key is recommended. I have not seen it said that a different key is required, but that that appears to be the implication. I don't see why a different key is necessary for encrypting the last block. Double encryption with the block cipher $E(K, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{X}}$ could be rewritten as $F_{1}(K, X) = E(K, X)$. Then, the entire MAC procedure can be reformulated as:

$m$ is the number of message blocks to be authenticated.
$M_{i} \in \{0, 1\}^{\ell_{X}}$ is the $i$th zero-based message block to be authenticated where $0 \leq i < m$.
$t_{0} = F_{1}(K, M_{0})$.
For $0 < i < m - 1$, $t_{i} = F_{1}(K, t_{i - 1} \oplus M_{i})$.
The MAC, T, is calculated from $F_{2}(K, t_{m- 2} \oplus M_{m - 1})$.

With two calls to the block cipher, $F_{2}$ is a different function than $F_{1}$, the same way $E(K_{0}, X)$ is a different function of $X$ than $E(K_{1}, X)$.

Note that re-encrypting the output of CBC-MAC with the same key as it was calculated with is equivalent to appending a single all-zero cipher block to the message:
$$E_K(\text{CBC-MAC}_K(m)) = E_K(\text{CBC-MAC}_K(m) \oplus 0^b) = \text{CBC-MAC}_K(m \,\|\, 0^b),$$
where $0^b$ represents a $b$-bit block of all zero bits and $b$ is the block size of the cipher.

Thus, the classic attack on unmodified CBC-MAC with variable-length messages can be easily adapted to your scheme.  Specifically, let $$\begin{aligned} t\phantom{'} &= E_K(\text{CBC-MAC}_K(m)), \\ t' &= E_K(\text{CBC-MAC}_K(m')), \end{aligned}$$ and construct the message $m'' = m \,\|\, 0^b \,\|\, (t \oplus m')$, where $t \oplus m'$ represents $m'$ modified by XORing its first block with $t$.  Then $$E_K(\text{CBC-MAC}_K(m'')) = E_K(\text{CBC-MAC}_K(m')) = t'.$$


Why does plain RSA not work with big messages ($m>n$)? From what I can remember, RSA is something like this:

Generate 2 distinct prime numbers $p$ and $q$ that have similar bit length.
Compute $n=pq$ and $\phi(n)=(p-1)(q-1)$
Compute $e$ such that $1<e<\phi(n)$ and $\gcd(\phi(n),e)=1$. It is optimal for $e$ to be prime
Compute $d$ such that $ed\equiv1\pmod{\phi(n)}$
To encrypt a message $m$ into cipher $c$, compute $c=m^e\pmod{n}$
To decrypt a cipher $c$ into message $m$, compute $m=c^d\pmod{n}$

But for large $m$ values, this does not necesssarily work.

Let me use an example to demonstrate what I mean:

Let $p=1999$, $q=2039$, and $e=65537$ (note, all of $p$, $q$ and $e$ are prime)
Compute $\displaystyle n=pq=1999\times2039=4075961$
Compute $\displaystyle \phi(n)=(p-1)(q-1)=1998\times2038=4071924$
Compute $d$ such that $65537d\equiv1\pmod{4071924}$  by solving the Linear Diophantine Equation $\displaystyle 65537x-4071924y=1$

Steps to solve (using a bad implementation of the Extended Euclidean Algorithm)

$\displaystyle 65537\times63-1\times4071924=56907$

$\displaystyle 1\times65537-1\times56907=8630$

$\displaystyle 1\times56907-6\times8630=5127$

$\displaystyle 1\times8630-1\times5127=3503$

$\displaystyle 1\times5127-1\times3503=1624$

$\displaystyle 1\times3503-2\times1624=255$

$\displaystyle 1\times1624-6\times255=94$

$\displaystyle 1\times255-2\times94=67$

$\displaystyle 1\times94-1\times67=27$

$\displaystyle 1\times67-2\times27=13$

$\displaystyle 1\times27-2\times13=1$

Therefore, these things can be substituted:

$\displaystyle 1\times27-2\times(1\times67-2\times27)=5\times27-2\times67=1$

$\displaystyle 5\times(1\times94-1\times67)-2\times67=5\times94-7\times67=1$

$\displaystyle 5\times94-7\times(1\times255-2\times94)=19\times94-7\times255=1$

$\displaystyle 19\times(1\times1624-6\times255)-7\times255=19\times1624-121\times255=1$

$\displaystyle 19\times1624-121\times(1\times3503-2\times1624)=261\times1624-121\times3503=1$

$\displaystyle 261\times(1\times5127-1\times3503)-121\times3503=261\times5127-382\times3503=1$

$\displaystyle 261\times5127-382\times(1\times8630-1\times5127)=643\times5127-382\times8630=1$

$\displaystyle 643\times(1\times56907-6\times8630)-382\times8630=643\times56907-4240\times8630=1$

$\displaystyle 643\times56907-4240\times(1\times65537-1\times56907)=4883\times56907-4240\times65537=1$

$\displaystyle 4883\times(63\times65537-1\times4071924)-4240\times65537=303389\times65537-4883\times4071924=1$

Through calculation, we conclude that $\displaystyle d=303389$ because $\displaystyle 65537\times303389\equiv1\pmod{4071924}$

Example 1

Encryption

Let $m=113$, then, $c\equiv(113^{65537})\pmod{4075961}=3345792$

Decryption

Let $c=3345792$, then, $m\equiv(3345792^{303389})\pmod{4075961}=113$

It works this time! Good!

Example 2:

Encryption

Let $m=33555553$, then, $m\equiv(33555553^{65537})\pmod{4075961}=2621940$

Decryption

Let $c=2621940$, then, $m\equiv(2621940^{303389})\pmod{4075961}=947865$

It does not work this time! What the ----?

Is this message too big to be encrypted? If so, how do we make it smaller?

The issue is that we use modular arithmetic. In modular arithmetic, you may view $m \bmod n$ as the remainder of $m$ when divided by $n$. So, for example, $7 \bmod 2 = 1$, also written as $7 \equiv 1 \pmod 2$, because $2(3) + 1 = 7$.

Now consider what you're guaranteed by $m \equiv c^d \pmod n$, the decryption formula for plain RSA. You're guaranteed that $c^d$ is equivalent to the message modulo $n$. You're not guaranteed that it is precisely equal. Now, if the message is smaller than the modulus — if $m < n$ — then by the way we program modular reduction, where we usually give the smallest positive integer modulo $n$ , you're going to get $m$ exactly when you compute $c^d \bmod n$. But if $m>n$, if the message is bigger, you're going to get a smaller integer that is equivalent modulo $n$.

And indeed this is the case with your example. Note that your example message $m = 33555553$ is larger than your example $n = 4075961$. So when you compute $c^d$, you're going to find an equivalent integer modulo $n$, but not exactly the one you wanted.

In this case, you got back $c^d \bmod n = 947865$. But note what happens if you reduce your original message modulo $n$: you get that your original message is equivalent to $c^d \bmod n$.

In summary: if your message is larger than your modulus, you won't get the exact message back when you decrypt. You'll get an equivalent message instead. To avoid this, you can instead encrypt a key used in a symmetric cryptosystem (or any cryptosystem that can handle messages of the length you're wanting). As Ricky Demer linked in his comment, this is sometimes called a hybrid cryptosystem. Once you've done this, you just use the other cryptosystem's key to do all of your encryption for you.


Theoretical decryption of RSA I am currently looking into RSA and have some questions. I am interested in theoretical answers, assuming there is infinite time for decryption.

Is it necessary to work out the private-key exponent for decryption? Are there no alternative options?
Can a message encrypted using RSA be decrypted using only the public key? If so, how? If not, why?

I am interested in theoretical answers, assuming there is infinite time for decryption.

We call such an attacker a 'computationally unbounded adversary'

  Is it necessary to work out the private-key exponent for decryption? Are there no alternative options?

One approach that a computationally unbounded adversary could is as go through all possible values $M$, and find one which has $M^e = C \bmod n$; such a message $M$ is the decryption of the ciphertext $C$.

This approach actually takes longer than the more traditional approaches that involve factoring $n$ (and from that, rederiving the decryption exponent); however a computationally unbounded attacker might not care.

  Can a message encrypted using RSA be decrypted using only the public key? If so, how? If not, why?

Actually, there are a number of different ways that RSA could be decrypted by a computationally unbounded attacker

They can brute force the message (as listed above)
They could factor the modulus, and rederive the decrypion exponent
As pointed out here, they could generate every possible public/private keypair, and pick out the public key that they actually see.  Any public key cryptosystem can be broken by this method.

So, if RSA can so easily be broken by a computationally unbounded adversary, why do we still use it?  Well, we don't believe that computationally unbounded adversaries exist, and so that's not considered a real world requirement on crypto systems.  Actually, if they do exist, we don't have that much in the crypto toolbox that they can't trivially break anyways.


Clarification questions about timestamp servers I am reading the bitcoin white paper, and I came across the concept of timestamp servers in it. Unfortunately the description of the usage of a timestamp server leaves me with more questions. And unfortunately googling has not helped much.
The paper has this:

The solution we propose begins with a timestamp server. A timestamp server works by taking a
hash of a block of items to be timestamped and widely publishing the hash, such as in a
newspaper or Usenet post [2-5]. The timestamp proves that the data must have existed at the
time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in
its hash, forming a chain, with each additional timestamp reinforcing the ones before it.

Okay I have questions:

What is the format of the artifacts published by a timestamp server? Is it like an hash? or signature? or something else? How is the date attached to such an artifacts?

Each timestamp includes the previous timestamp in its hash How is it possible to include a previous timestamp in another timestamp? Does timestamp have some form of verifiable identity? How does this look like?

Where does a timestamp server publishes to? A URI of some sort?

Anyone knows an example of a timestamp server? Preferably being used outside the context of bitcoin? I ask this so as to better get a feel of how timestamp server works and used.

In 1991, Stuart Haber and Scott Stornetta proposed a method for time stamping a digital document. In their method, when someone (Alice) wants to timestamp a document, she send the hash of her document to a Trusted Third Party (TTP). TTP (similar to figure 1) puts this hash in a Merkle tree and sends back to Alice a proof that her document is in the Merkle tree and then publishes this Merkle root [RH(i-1)] in a newspaper or Usenet post, just for time stamping, adding a specific time (publishing day) to RH(i-1).

Next day, TTP does a similar job with a difference: for calculating the Merkle root RH(i), he uses the previous day's Merkle root [RH(i-1)]. It is called linking and hash pointer and linked list made it possible. Hash pointer (figure 2) is a pointer to hash of some information that it will guarantee that the information hasn’t changed, because if someone wants to change a previous hash, he should change all next hashes and informations in the chain.

Bitcoin uses a hash pointer (figure 3) for creating the ledger of transactions (Tx), with a difference: for calculating hashes of the chain, it uses Hashcash. Hashcash added the proof of works to bitcoin. In hashcash, miners scanning for a value that when hashed, the hash begins with a specific number of zero bits. For finding this specific hash, miners changes Nonce parameter in the blocks of chain.

In bitcoin, with a peer to peer network, hashcash-based timestamp server and the ledger of transactions is distributed and all miners have a copy of it, so bitcoin doesn't need a Trusted Third Party (TTP).


Predictable, but private IV in CBC It is said that a predictable IV is dangerous, because you can do adaptive chosen plaintext attacks. But if the IV is never seen to the attacker, is it still dangerous? What I mean, is that the IV is predictable - it is incremented for every message, but never communicated - the attacker only knows it increases by one, but not the exact value. Can they still attack from that information alone?

Edit: I'm asking if it is ok to just increment the IV for every message given that the attacker doesn't know the initial IV

If a nonce $N_i$ is even, then the binary numeral for it its increment $N_{i+1} = N_i + 1$ differs from $N_i$ only in its least significant bit; and if $N_i$ is odd, its increment is even.  This means we can adapt chosen-plaintext attacks against CBC with counter nonces (e.g., from section 4 of this Rogaway paper) to target your scheme.  Given an block cipher $E_k$ with random secret key $k$ and block size $n$, a secret initial nonce $N_1$, and nonce generation rule $N_i = N_{i-1}+1 \mod 2^n$ known to the attacker:

Ask the oracle to encrypt $0^n$ (the one-block plaintext with all zero bits), getting back $C_1 = E_k(N_1 \oplus 0^n)$.
Ask the oracle to encrypt $0^{n-1}1$ (the one-block plaintext with all zero bits except for the least significant), getting back $C_2 = E_k(N_2 \oplus 0^{n-1}1)$.
Ask the oracle to encrypt $0^n$ again, getting back $C_3 = E_k(N_3 \oplus 0^n)$.
If either $C_1 = C_2$ or $C_2 = C_3$, the attacker knows with high probability they're talking to an encryption oracle. Otherwise the attacker knows they're talking to a random oracle.

Proof.  If $N_1$ is even, then its least sigificant bit is $0$, meaning that $N_2 = N_1 \oplus 0^{n-1}1$, and then, given that $C_2 = E_k(N_2 \oplus 0^{n-1}1)$:

$$
\begin{align}
C_2 &= E_k(N_1 \oplus 0^{n-1}1 \oplus 0^{n-1}1) \\
C_2 &= E_k(N_1) \\
C_2 &= E_k(N_1 \oplus 0^n) \\
C_2 &= C_1
\end{align}
$$

If $N_1$ is odd, its least sigificant bit is $1$, $N_2$'s is $0$, and $N_3$ differs from $N_2$ only in its LSB: $N_3 = N_2 \oplus 0^{n-1}1$.  So given that $C_3 = E_k(N_3 \oplus 0^n)$:

$$
\begin{align}
C_3 &= E_k(N_2 \oplus 0^{n-1}1 \oplus 0^n) \\
C_3 &= E_k(N_2 \oplus 0^{n-1}1) \\
C_3 &= C_2 \\
\end{align}
$$


SHA256 message bytes I have been reviewing the documentation for SHA256 and I believe the last two words (64 bits) for each chunk are not used in creating the message schedule.

From Wikipedia...

Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:

for i from 16 to 63
    s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
    s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
    w[i] := w[i-16] + s0 + w[i-7] + s1

Notice how w[i-1] and w[i] are not used?  These two words would be the length for a 1 chunk hash but for actual data that is longer then 512 bits the last 64 bits are ignored.  This would result in the same hash for two (or more) messages.  Am I missing something or am I correct?

I've figured it out.  The Message schedule is 64 words in length where as the chunk is only 16.  The schedule contains a copy of the chunk in the first 16 words then smears the original 16 words in the chunk to the remaining 48 words.


Can I obtain the hashing algorithm if I know both the input and the output? Suppose I have a string "Hello World".
And I pass it through an unknown function which gives output as "6Xbhkfo520/78".

So, using several input and output pairs, can I determine the algorithm of the hashing function?

It is weird to assume a hash function is private. This contradicts Kerckhoffs's principle. If you are talking about keyed hash functions, then I think the answer is no in theory. They are typically used to construct message authentication codes like HMAC, of which the keys cannot be derived from several hash inputs/outputs.


What exactly is a quantum key distribution network for? There are many diagrams out there explaining how quantum key distribution works on a physics /optics and mathematics level. I understand these explanations fairly well so I'm not asking about the underlying principles.  This is one of the few that actually features people on it (although they seem to be fairly incidental to the usage):-

As I understand it, the machines only transmit keys not actual business data.  I appreciate the exchange is done with one time pads, but is it like Diffie–Hellman key exchange otherwise, but only between fixed machines /servers?  Do they replace entering AES keys transmitted over the phone /fax? Since AES is hard to break, surely the keys don't need replacing every hour?  And do they then operate in pairs, because two is only a network from a marketing perspective.  They can't control the log in into my desktop computer can they? And wouldn't all the desktops have to be interconnected with fibre optics rather than Ethernet? The latter is probably a rather naive question.

This additional image clearly shows the transmission of secure encryption keys through a Toshiba quantum network:-

At a separation of 20Km, the devices are generating /exchanging keys at a rate of 10 kbits/s.  Why as that's 40 no. 256 bit AES keys each and every second?  What exactly does someone do with 140,000 unbreakable AES keys per hour? Even more ridiculously, that's a million new keys in a single business day.

I'd appreciate an answer from a operational perspective, although I realise that this is firstly a cryptography theory site.  So what's it for?

I looked at Quantum key exchange skepticism/confusion  and a simulated network, but both were unfruitful.

It seems that the initial diagram is correct.  A QKDN is exactly this:-

and it relies on two pieces of kit, a quantum key generator and an encryptor device. A 256 bit AES key is generated and shared between Alice and Bob via the BB84 protocol running over dedicated fibre optic cable. The key itself is created via a true random number generator (perhaps based on the phase interference of a laser beam).

The keys are then passed to the encryptor devices which operate AES between themselves over conventional channels. So actual business data flows only between the encryptor devices, over common networking technology and not the quantum machines. The thing that ensures the security of the transmitted data is that the AES keys only have a life span of one minute.  They're then replaced.  That's why all that quantum data is transmitted.  AES keys are constantly being replaced before anyone could even attempt to break them. Clearly some of the numbers here are dependant on individual networks and hardware.

And QKDNs are used in anger all over the world including government and commerce. The first was deployed in Switzerland to secure their frequent public votes /elections. And there are some interesting future developments that won't require fibre optics at all, and some that will ensure secure key exchange over infinite distances.

All of this is to be found on YouTube.  Don't laugh.  It's a presentation by Kelly Richdale, head of quantum randomness at ID Quantique, a market leader in QKDNs.   There is also an unbiased and fair summary of QKD from  the European Network and Information Security Agency (ENISA) here.  It's concise but rather dated (Nov 2009), so a lot of the open issues should have been resolved or are in the process of being so.


is it possible to extract a "hint hash" of some kind from another hash? I'm a web developer starting to dip into cryptography so please bare with me on this...

Let's say I have a collection of hashes that were generated from some common data i.e. changes to multiple records. Is there a way that I could generate a secondary hash from the main hash and compare it to the other hashes based on how the main hash was generated. For example...

plain text             | hash      | hint hash
----------------------------------------------
"USER:123:fName:Alice" | 92eb5ff.. | 3cd24
"USER:123:fName:alice!"| 1c77753.. | 3cd24
"USER:456:fName:Bob"   | fee6ae2.. | 7d28e
"USER:456:fName:bob!"  | 7775315.. | 7d28e
"USER:789:fName:Carl"  | fec3ad7.. | 75315

Notice how all hashes are unique but the hint hashes match up to the record IDs they are hashed from. So if I generated these hashes based on the plain text and some key i.e. genHash(plainText, keyText). If you only had the hashes, you could associate which hashes are related to each other by their hint hashes only. So if I only had the hashes, I could still find their associations with a couple getHintHash(hash) calls...

Table of hashes:

hash
---------
92eb5ff..
1c77753..
fee6ae2..
7775315..
fec3ad7..

Table of hashes with hint hashes:

hash      | hint hash
----------------------
92eb5ff.. | 3cd24
1c77753.. | 3cd24
fee6ae2.. | 7d28e
7775315.. | 7d28e
fec3ad7.. | 75315

Now I have the relationships between the unique hashes without exposing the plain text that generated them. Is this possible? Remember, the hashing function got the plaintext and a key that the "hint hash" could be based off of...

genHash("USER:123:fName:Alice", "USER:123") -> 92eb5ff..

Cryptographic hash functions are designed to have certain properties, which is collision resistance, preimage resistance and second preimage resistance. If those definitions are not clear, we could state informally:

If you only have hash values of some input data, then you can't do anything except check for equality. You can't compare the input data, you can't check if they have a common substring, and most importantly you can't get back the input from the hash. So imagine a hash function as a one-way street, where you can afterwards just check for equality. Any other structure is lost.

And this is the behavior, which is wanted from cryptographic hashes.

So if you consider your database, when you have access to the plain text, you could just use a hash function with only the user ID as input:

$h_1 = hash(FullPlaintext)$
$h_2 = hash(User ID)$
Save tuples $(h_1,h_2)$, e.g. in a table

If you want to add some keys to those inputs, you have to consider that using a different key means getting a different example, and there is no way to tell if just part of the input was equal or not. But with this table you could do your lookups. But it is impossible to get $h_2$ from $h_1$ or vice versa. In a cryptographic hash function, you simply can't go backwards.


Are timing attacks exploitable if each key is used only once? Suppose that one performs (for example) AES-GCM encryption and decryption using an algorithm that is vulnerable to timing attacks, but each key is used only once. Is it still possible to perform a successful timing attack?

Yes.

Let's a thought experiment and not limit this to AES-GCM.

A very trivial example:

$M = \{0, 1\}$ (a one bit message)

$K = \{0, 1\}$ (a one bit key)

$E(m, k) = m \oplus k$

Let's say with this implementation the computation takes 100x as long if $k = 1$. Running this function only one time will give you a pretty good idea what k is based on how long it takes.

Again, this is just a trivial example meant for a thought experiment as to why you wouldn't necessarily need the encryption process to go more than once.

Another case might be that the plaintext has a series of repeated texts. All of which will be computed against the same key. This can be (not always) similar to computing a single plain text several times.


Would a "Triple AES" (in the sense of how Triple Des works) serve for a dramatic increase in safety? The system requires to be as paranoid as possible regarding security. One of the few contemplated changes to the current design is to use multiple encryption. First proposal was to use Serpent on top of AES-256, but after looking into it, it seems like a triple AES could also serve the purpose.

So the options are:

Encrypted(Input) = AES256(key2, Serpent(key1, Input))

And

Encrypted(Input) = AES256Encrypt(key3, AES256Decrypt(key2, AES256Encrypt(key1, Input)))

Where all keys are independent and randomly generated.

In performance tests with input that is supposed to be representative of what I would find in production second option (a triple AES) outperforms using Serpent, being around 20% faster.

As far as I'm aware, even though DES is completely broken, Triple DES still sustains a moderately safe resistance, even though one can use theoretical meet-in-the-middle attacks. So, even though I haven't spent much time on this, even if AES was somehow broken within the next 15 years, this would still offer a significant protection to the data (I would be expecting around 512 bits). Is this a correct assumption?

I've normally just gone standard in the past (sha256 with salts for stored passwords, aes 256 with secure random keys and ivs, and 4k rsa when asymmetric encryption is possible), so I never explored more complex escenarios until the past few days, so I apologize for my probable incorrect conclusions.

It really depends on what sort of break AES would suffer. The primary issue with DES was that it's key length was too small (56-bits). Multiple encryption can help here because it increases the effective key length of the whole operation. The meet-in-the-middle attack on DES takes about 2^112 operations, which is infeasible to brute force anytime soon.

AES doesn't have an issue with keysize, so multiple encryption won't really help you that much in that sense. It really depends on what sort of attacks emerge on AES so it's hard to tell if multiple encryption will be better. It might be more secure, but it won't be a "huge" improvement and it's hard to judge.


Rapidly changing passwords? Suppose you need to authenticate yourself to a program with the password - but the program's source code is public, the program doesn't have access to any private information and all your communications with the program are public.  The only privacy you have is the information that you have but don't send.

No fixed password could work because the first time you used it, everyone would know it, and all subsequent runs of the program would be compromised.  One partial solution would be to have a different password every second.  But naive password generation wouldn't work, since both the source code of the program and any information it has access to are known.

Is there a (secure) way for the program to quickly generate password hashes, so that a trusted user with the right information could quickly generate passwords matching those hashes?  This would be difficult to attack iff it is hard to predict the next password given the next hash and all the previous passwords.  It is easy to make it so that nobody can come up with passwords (just randomly generate hashes), but making it actually possible for one person to generate passwords (quickly) given a little secret information seems much harder to me.

This is a case for public-key cryptography (in the form of digital signatures, or a key exchange algorithm).

In the simplest case, the program (Alice) would know (embedded in the source or in a configuration file) a public key, and the user (Bob) would have the corresponding private key.

Bob would then send the message which should be authenticated, and sign it using the private key. The program (as well as anyone who has the public key) can then verify that the message really came from you.

This authenticated message should include a timestamp and/or nonce, and the program should make sure not to accept the same timestamp/nonce twice (this will prevent a replay attack).

If you want something where the user actually uses a password, have a look at the secure remote password protocol (SRP). In this case, the server stores a password verifyer instead of the password itself, and the exchanged messages are a Diffie-Hellman-like key exchange, which don't give any clue about the password. You also get a shared secret between Bob and Alice, though I'm not sure how secure this is against man-in-the-middle attacks when Alice can't be authenticated due to missing secret.


CBC mode with same plaintext I'm working on a file encryption system where multiple versions of the same file might exist. The filenames are encrypted using AES in CBC mode with a random IV and stored in metadata. Since versions of the same file share the same filename, this information may be used by an adversary. Is there any additional information to be derived from multiple ciphertexts which are known to share the same plaintext, just with a different IV?

the key and plaintext is the same. The attacker knows this and the IVs used but doesn't know the plaintext. Is there anything to learn about the plaintext when multiple ciphertexts are available instead of only one?

No. Giving the attacker multiple encryptions of a single plaintext using a randomly chosen IV and a fixed key with AES-CBC does not leak any more information about the plaintext than does a single ciphertext.

In fact if the attacker didn't know whether or not they were the same plaintext (but had the same length), the attacker couldn't tell you whether or not they encrypted the same plaintext.


Can the McEliece cryptosystem be used as an additively homomorphic encryption scheme? Since the McEliece cryptosystem is linear, if matrix G is kept constant for different plaintexts, it can be used for linearly combining the corresponding ciphertexts. In that case, what are the advantages of McEliece over Paillier encryption?

In that case, what are the advantages of McEliece over Paillier encryption?

It's not that easy to think of any specific advantages; the public key will be huge (because you would need to expand the code to allow the relatively small initial error vectors to be secure), and those keys are already large enough to begin with.

About the only thing that springs to mind is the addition operation; for Pallier, the addition operation is addition modulo $\mathbb{Z}_n$, with the homomorphic McEliece, it would be addition in some field $GF(2^n)$, for some relatively large $n$, and perhaps some application would prefer that addition.

On the other hand, there are other cryptosystems (such as Goldwasser-Micali) which are homomorphic over addition in $GF(2)$, and running $n$ parallel copies would give you addition in $GF(2^n)$. It would appear likely that the homomorphic operation in McEliece is cheaper than the homomophic in $n$-ways parallel Goldwasser-Micali; however, to me, that sounds like a minor advantage (given the other disadvantages, such as Goldwasser-Micali has no bound on the number of homomorphic operations you can do before the ciphertext becomes undecryptable)


Do I need to worry about timing attacks in Base64 encoding/decoding of private keys? Do I need to worry about timing attacks in Base64 encoding/decoding of private keys?  This is a common operation (ex.  PEM keys) and is variable time in typical implementations.

Yes, kind of. The encoding does depend on the individual bits so there could very well be timing differences. Note that the differences would be pretty small; encoding a byte is likely much faster than e.g. modular exponentiation. But as even block ciphers are vulnerable it may very well be possible, especially since table lookup may be implemented.

The solution however is also very standard: before storing the keys you first wrap the keys with a symmetric cipher. The key can be derived from a strong passphrase. Most of the time when private keys are stored in PEM format (which is just the ASCII armor) they are encoded in PKCS#12. As the encoding after the wrapping and the decoding before, you should be secure against timing attacks against base 64. Obviously the block cipher is much more likely to be protected against timing attacks (but don't forget to verify that).

In principle PKCS#8 could also describe an encrypted private key, but that doesn't seem to be used much. PKCS#12 can be used to encrypt the private key and store the certificate (chain) for the public / private key pair.

If you directly store them in PKCS#1 or PKCS#8 format (without encryption) you should make sure the system itself is secure - especially with regards to file access.


Salt length for a single password So I've been reading about salt, and am confused about why the length is so critical. From my understanding salt is used for protection against pre-computed attacks.

Say I have a single password that is hash with salt length n. Suppose this hash and salt is accessible to the attacker. My questions are as follow:

If the n is too short, is the problem that a pre-computed rainbow table may already exist?
If n is long enough that a pre-computed rainbow table doesn't exist, what function does a longer salt serve? A brute force attack would simply add the n length salt to each hash it's generating. 50 bit n, 500 bit n. No difference, because the salt is known and simply added to all the brute force password values being hashed.

So to summarize, when trying to crack a single salted password hash, as long as n is long enough that a rainbow table doesn't exist, then the salt length n adds no security to the hashed password. Is this true?

You are correct that the function of using a distinct salt for each user is to thwart any batch advantage an adversary attacking one of many targets might have gotten out of precomputed tables.  If there are $2^n$ distinct salts and they're chosen uniformly at random for each user, it's only around $\sqrt{2^n} = 2^{n/2}$ users that a collision in the salts might happen so that the adversary might even get a chance to apply one precomputed table to many users.

Pick $n = 256$ bits and you won't ever have to worry about it.
Pick $n = 128$ bits and you probably won't ever have to worry about it even if everyone else uses the same hash function.
Pick $n = 64$ variable bits and an application-specific constant that nobody else uses and you're probably mostly OK because the precomputation of the table is expensive already, even if there are a handful of collisions in a few billion users.  But consider revisiting once you've hit a million users just to be safe.

No need for $n = 500$ bits or anything obscenely large like that.


Factors of RSA modulus In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any multiple of φ(n).

Imagine I know the public and the private key. But what I really want is the factors of n, the p and q but I cannot use any factorization algorithm in a large number of n.

In the Miller's article it is suppose to say how I can find the two factors, knowing the public and private key. But I cannot understand how exactly it is done. Does someone know? Or have a small example?

While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case.

What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd.  The special property that $\lambda$ has is that $(m^\lambda)^{2^k} \equiv 1 \pmod{n}$ for any $m$ relatively prime to $n$.

Here's how we use it; we pick a random $m$, and compute $m^\lambda \mod n$.  If it is 1 or $n-1$, we go back and select another $m$.

If it is not, we repeatedly square the value ($\mod n$), and check if the value becomes 1 or $n-1$ (and because of $\lambda$'s property, it'll turn into one of the two in at most $k$ squarings, unless we happened to pick an $m$ which wasn't relatively prime to $n$); if the value became $n-1$, we go back, and pick another $m$.  However, if it became 1, that means that the immediately previous value $z$ had the property $z^2 \bmod n = 1$, that means that $gcd(n,z-1)$ and $gcd(n,z+1)$ are the factors of $n$.

And, at least 1/2 of the possible $m$ values will result in a factorization, hence this method is practical.


Bits of security vs collision resistance? I have been doing some research on security, and I am confused on the bits of security vs collision resistance, and I was wondering if someone could clarify my understanding.
For instance, if you have an AES has a 128-bit block, being used with a 256-bit key, that provides 256 bits of security, because the key length determines the bits of security in this case.
But if you have SHA-256, that offers 256/2 = 128 bits of collision resistance. Does that mean that the bits of security of SHA256 is 128 bits? Or is bits of collision resistance just in a whole different category than bits of security?
I wrote down what I think captures bits of security based on the type of primitive being used:

Bits of security for a block cipher depends on the key length (so like the example above with AES 128 with a 256 bit key)
Bits of security for a MAC is min(key bits of security, hash bits of security)
Bits of security for a hash function is l/2 or l-bits?

My question is do we aim for bits of collision (when applicable) over bits of security?
Any help is appreciated!!! Thank you!

I am confused on the bits of security vs collision resistance

Well, here is what "bits of security" means; we say that a primitive offers $\ell$ bits of security if the best known attack against that primitive takes roughly $2^\ell$ operations.  Yes, that is somewhat imprecise (what is "roughly" and what is an operation?), but it is generally sufficient for discussions.

Bits of security for a block cipher depends on the key length (so like the example above with AES 128 with a 256 bit key)

Pretty much (assuming that the block cipher itself doesn't have any nongeneric attacks, and if we don't talk about birthday bound attacks or attacks against the ciphermode).
Nit: in general parlance, "AES 128" is AES with a 128 bit key; we'd call AES with a 256 bit key "AES 256"

Bits of security for a MAC is min(key bits of security, hash bits of security)

Well, here is where the general "bits of security" breaks down somewhat.  It is impractical to do any operation that does $2^{64}$ sequential steps (even if each step takes a nanosecond, we're talking about more than 500 years).  In most cases (e.g. doing a brute force attack against a key), this is not an issue; we can easily run things in parallel (e.g. rent a large number of cloud computers, or use a GPU farm), and so a large organization would have little issue in performing, say, $2^{64}$ operations in aggregate.  However, the generic attack against "size of the MAC" would be "generate the message we'd like, insert the guess of the MAC, and send that to the device under attack".  Since the device under attack would need to process each guess in succession, we cannot parallelize it (unless we have a large number of devices, all with the valid key; generally not the case), and so, in practice, attacks against the "hash length" (as you term it) are considerably harder than attacks against the key.

Bits of security for a hash function is l/2 or l-bits?

Depends on the attack you need to be strong against.  If it's a collision attack (that is, the attacker "wins" if he is able to find two messages that hash to the same value), it's at most l/2 (as there are generic attacks that work in $2^{l/2}$ time.  On the other hand, if you don't care about a collision attack, and care only about a preimage or a second preimage attack, it can be as much as l-bits (as the best generic attack takes $2^l$ time


openssl sha1 message digest not matching with NIST vector input? When I call openssl sha1 from the command line

 echo "00" | xxd -r -p | openssl dgst -sha1

the output I am receive is

(stdin)= 5ba93c9db0cff93f52b521d7420e43f6eda2784f

But the NIST Vector output is:

 MD = da39a3ee5e6b4b0d3255bfef95601890afd80709

Can anyone please explain this?

You read the testvector incorrectly.

I assume you are referring to the following part of the file SHA1ShortMsg.rsp of the FIPS 180-4 vectors:

[L = 20]

Len = 0
Msg = 00
MD = da39a3ee5e6b4b0d3255bfef95601890afd80709

This test vector has length 0, so the specified hash is for an empty message and not for a single zero byte. This openssl command shows the correct result.

  $ echo -n ""|openssl dgst -sha1
  (stdin)= da39a3ee5e6b4b0d3255bfef95601890afd80709