Can e = 2 be used in unpadded RSA? I am wondering whether $e = 2$ can be used in unpadded RSA...
It seems like it is not possible to use it: the value of e needs to be coprime with $tot(n)$. $tot(n) = (p - 1)(q - 1)$ where $p$ and $q$ are prime numbers.

The way I see it, there are two scenarios.

1) Neither $p$ nor $q$ are equal to $2$. This means they are odd. The product of $(p - 1)(q - 1)$ would be even i.e. not coprime with $2$.

2) Let's say $p = 2$ and $q$ is any prime greater than $2$. This would give $tot(n) = 1(q - 1)$ and since we know that $q$ is odd, the result will be even anyway.

Is there something I am overlooking here or is my reasoning correct?

Adding some more information to fkraiem's answer:

The encryption in the Rabin cryptsystem is basically textbook RSA with an exponent of $2$.

  1) Neither p nor q are equal to 2. This means they are odd. The product of (p−1)(q−1) would be even i.e. not coprime with 2.

Well, yes. That is one of the basic problems in Rabin's cryptosystem. If we want that
$$c=m^e$$
is a bijection, $e$ has to be coprime to the order of the multiplicative group. In your scenarios you realized, for normal RSA-moduli this is not true for $e=2$(and $N=2\cdot p$, with $p$ prime, is quite useless cryptographically).

Soo... why are there 4 square roots then? Let's look at the square roots of $1$ for simplicity. Now we could have the following solutions:

$$x_1 = 1 \mod p; x_1=1 \mod q$$
$$x_2 = 1 \mod p; x_2=-1 \mod q$$
$$x_3 = -1 \mod p; x_3=1 \mod q$$
$$x_4 = -1 \mod p; x_4=-1 \mod q$$

With the help of the Chinese Remainder Theorem we can calculate those four solutions mod $N=pq$. For arbitrary elements, this works pretty much the same: Calculate the roots in both $\mod p$ and $\mod q$, then combine the result. And this is the decryption in Rabin.

So with $e=2$ we get 4 possible roots. But the choice which root was the correct one has to be done outside the encryption scheme.

As a final note, there is a crucial difference between RSA and Rabin, when it comes to security property:

If you have a decryption oracle, then the result of the Rabin decryption (even if it just outputs one of the roots every time), reveal the integer factorization. How to do this: Pick a random number, square it and give it to the oracle. The oracle can't know which of the roots you started with and will return a random root. In 1/2 of the cases this reveals the factorization.
This means, that breaking Rabin is actually equivalent to factorization (unknown for RSA). Thus making it "stronger".
On the other hand, a decryption oracle for RSA does not reveal the factorization (as far as we know yet).
For IND-CPA security, Rabin as well as plain RSA are insecure. However, with a proper padding scheme RSA can be made IND-CPA. For Rabin we can apply adaptions (e.g. redundancy or error detection codes), but so far it is unknown if those are CPA secure.

As a final note for RSA: Knowing both $e$ and $d$ is deterministic polynomial to factorization. What is unknown: Can a decryption oracle (with $d$ fixed) help you find $d$ in polynomial time (or equivalent information, e.g. a nontrivial root of $1$, a zero divisor, etc.)


Binary format of encrypted PGP private key? Short Version of the Question:
I would like to remove any predictable information from an encrypted private keys binary representation. Does anyone have a hint where the binary format for encrypted GnuPG private keys (.gpg) is documented?

Longer Explanatory Version of the Question:
Hey guys,
 basically I'm trying to write a program which hides the encrypted private key in a random user-selectable medium (e.g. JPEG image) using steganography.

I'm assuming the attacker knows the kind of medium, but not the specific file, it would be rather useless if the private key doesn't appear completely random.

Basically, I would like to remove any predictable information for example on the type of encryption (maybe AES-128-CBC) used, and reconstruct the key after retrieval from the medium. A wrongly chosen medium should deliver a seemingly valid private key. So the attacker would have to brute-force all possible passphrases for all possible storage mediums.

Is that generally a stupid and futile endeavor?

From the encrypted keys I looked at and the information I collected I would guess that the key is concatenated like "SALT + EncryptedByteStream + InformationOnEncryptionAlgorithm". Does anyone have a hint where to find that? I'm a little tired from digging haphazardly through source code right now.

PGP key formats are defined in RFC 4880. Specifically, section 5.5.

The private key format includes the public key and quite a bit of other information in unencrypted form. It might be easier to add another layer of encryption on top of that before you use steganography.


Different keys for clients but 1 key on server Is it possible to have different keys on alot of (embedded) devices and just have 1 key on a server (to witch all these devices connect)? The main point here being when 1 device is compromised this does not mean the traffic between other devices and the server is compromised (even if the server does not know that 1 device is compromised).

Background:
All the devices will have a key pre-installed during the assembly of the device but must be changeable over internet.
Currently all devices in 1 system (a customer can have multiple systems) have the same key. But I am trying to create it in such a way that they all have different keys, hence the question.

What I think I know:
1. I believe DVD's and dvd-players use a similar scheme (ccr?) but this is broken.
2. There are Key Derivation Functions which could be used for this scenario.

For point 2 I am not quite sure how to use this i can (when assembling the device) make a salt and use it with (for example) PBKDF2 and a master key (which the server will have) than store the PBKDF2 generated key and the salt on the device and send over the salt to the server when the device is connecting so the server can create the key again. though after this i should set up a session key as well. and worst of all the salt will be vulnerable.

So this to me does not seem like a solution.

How should I do this properly, or am I looking at this the wrong way and should i do something different?

Simple solution (with symmetric encryption):

Assign each device an ID (probably already present)
Store a master key on the server
Use a KDF on the master key and the device ID to generate the key for the device. Then you only need the device ID on the device, and the server can re-create that key as required with the master key and the device ID. Of course the device ID has to be transmitting at the connection phase.
If you want to change keys for the devices, you will also need some random input to the KDF, which also has to be stored for each device ID.

That way each device has its own key, and the server can reconstruct all keys just from his one master key. However, this way the devices have no shared keys and cannot communicate with each other. For that you would either need some sort of public key infrastructure, or you could apply an IBE scheme to your devices, where the server holds the master key. However, public key encryption is quite a bit less efficient than symmetric encryption and hashing, so that you have to check the limitations of your devices.


Confusion regarding computing Multiplicative Inverse Modulo P? May be a silly doubt, please rectify my confusion regarding below problem:

For concreteness assume $g=2, p=11, a=6$ and $x=9$

$$A = g^a \bmod p = 2^6 \bmod 11 = 9$$

$$X = g^x \bmod p = 2^9 \bmod 11 = 6$$

$$C = A^x \bmod p = 9^9 \bmod 11 = 5$$

To find $X$ (i.e. $g^x$) using $C$ and $a$ only is:
$X' = C^{a^{-1}} \bmod p = 5^{6^{-1}} \bmod 11 = 5^2 \bmod 11 = 3$

The answer should be $X = X'$ but it is $X \neq X'$
Why this problem, where is my mistake?

Indeed, theoretically $$X'\equiv C^{a^{-1}}\equiv A^{x*a^{-1}}\equiv g^{x}=X\pmod p$$

should hold, given $gcd(a,p-1)=1$.

However there are two reasons why you won't get this equation to hold.

You calculated $a^{-1}$ using the wrong modulus. As it is in the exponent you need to calculate $a^{-1}\bmod q$ with $q$ being the group's order instead of $a^{-1}\bmod p$. In your example $q=p-1=10$.
The value you have for $a$ makes it impossible to invert. For $a^{-1}\bmod q$ to exist $gcd(a,q)=1$ must hold, but $gcd(6,10)=2\neq1$ so there's no $a^{-1}\bmod q$ for your specific choices of $a$ and $q$.


Information-theoretic security From Wikipedia:

  Information-theoretic security is a cryptosystem whose security derives purely from information theory. In other words, it cannot be broken even if the adversary had unlimited computing power. The adversary simply does not have enough information to break the encryption and so the cryptosystems are considered cryptanalytically-unbreakable.

List of unbreakable encryption-methods:

Secret sharing
Private information retrieval with multiple databases
Reduction between cryptographic primitives or tasks
Symmetric encryption with high entropic security
Quantum Cryptography

Why quantum cryptography isn't commercially used:

  GCN Article: “There are limitations to QKD (= Quantum key distribution),” Hayford said. Photons can only be sent about 60 miles, and it is a point-to-point protocol, meaning that complete system hardware is needed at each location. Expanding a system beyond a campus or a small number of local facilities “starts to be a little impractical.” And: "There also are challenges with existing hardware, particularly in the generation and measurement of individual photons. “That is a complicated physics problem,” which NIST and other research facilities have been working on for years, he said. Ideally the photon source would generate a single photon on demand. “We can’t do that right now.”

  The problem for a broad execution of QKD is, that the two parties have to know each other before communicating. And there needs to be a physical established line of communication, either from point to point or in nodes.

One-time pad
Pedersen commitments against the opener
ElGamal encryption used as commitment, against the committer

My questions are:

Are there more known unbreakable encryptions? If so, please provide a link & I will extend the list.
Why aren't these schemes commercially used? Please provide an explanation (and link if possible) and I will edit the list as well.

Information-theoretic security is a cryptosystem

Nitpick: information-theoretic security is a property that a cryptosystem can have against a particular attack model. AES is a cryptosystem, but doesn't have this property against any of the usual models; the one-time pad is a cryptosystem that does against passive attackers (but not active ones).

Other systems that have information-theoretic security, off the top of my head:

The one-time pad, against passive attackers.
Pedersen commitments, against the opener (but not against the committer).
ElGamal encryption used as a commitment, against the committer (but not the opener).
A bunch of OT systems of the Chu-Tzeng style, against either the sender or the recevier (against both at once is impossible - same goes for commitments).

Some of the above schemes are very much commercially used.

QKD is a very specific form of quantum cryptography, the two terms are not equivalent.


An efficient PACE protocol with curve25519 The PACE protocol is a password authenticated key agreement which is widely used. For instance, in the electronic ICAO passports as the so called SAC protocol. PACE is standardised in ICAO DOC9303 Part 11.
PACE is rather complicated. For instance, it needs 2 Diffie-Hellman exchanges and a specific $G' = s*G+H$ mapping function. The complexity stems form the fact that PACE needs a function, which hashes a random value into a curve point. The function must also be timing invariant and may not lead to offline dictionary attacks.

Now I think with Curve25519 and Montgomery arithmetic we can remove all those difficulties and make a very simple PACE variant. The main reason for simplicity is that mapping a random value in the curve is easy on Curve25519. First, one can simply using that random value as the x-coordinate, because one does not have to find an x-coordinate lying on the curve.  Second, Curve25519 uses the x-coordinate only. So, one does not have to calculate a corresponding y-coordinate. And finally, Curve25519 arithmetic is timing invariant.

Now let's construct the simple PACE protocol:

Let $Enc_k(x)$ be an encryption function (e.g. AES) , where k is somehow derived form a password. The same for $Dec_k(x)$ as decryption function.

\begin{array}{lcr}
Terminal & & Passport \\
& & s \xleftarrow{$} \{0,1\}^{128} \\
s \leftarrow Dec_k(s')  & \xleftarrow{\hspace{1cm}  s' \hspace{1cm}    } & s' \leftarrow Enc_k(s) \\
x \xleftarrow{$} \{0,1\}^{256} & & y \xleftarrow{$} \{0,1\}^{256}\\
h_x = s^x & \xrightarrow{h_x} &  h_y = s^y \\
z \leftarrow h_y^x & \xleftarrow{h_y}  & z \leftarrow h_x^y  \\
\end{array}

Looks too good to be true!
So, do you see any problem here?

P.S.  As Poncho made clear, this doesn’t work.
But maybe someone sees an advantage of using curve22519 for PACE or any other related PAKE protocol (e.g. SPEKE).

Sorry, but this doesn't quite work; it allows the adversary with a dictionary of possible passwords to eliminate large parts of his dictionary efficiently.

Here's how a terminal who doesn't know the $k$ can eliminate half of the possible values in his dictionary per exchange:

The terminal receives $Enc_k(s)$; he remembers it
The terminal sends a random $h_x$ value; doesn't matter what it is
The terminal receives $h_y = s^x$; he determines whether $h_y$ is on the curve or on the twist.

Then, for every $k'$ that is in his dictionary, he computes $Dec_{k'}(Enc_k(s))$, and determines if that is on curve or on the twist.

If $k' = k$, then $y_h$ and $Dec_{k'}(Enc_k(s))$ will both be either on the curve, or on the twist; hence if one is on the curve, and the other is on the twist, he knows that wasn't the correct value of $k$.

This logic will allow him to eliminate about half of his values in the dictionary; going through this process 20 times will reduce a 1 million entry dictionary to the 1 correct entry (and perhaps 1 false hit).

Now, this sort of thing could be made to work over a MODP group; we just pick a Sophie-Germain prime (that is, one where $(p-1)/2$ is also prime) that's just under (say) $2^{2048}$; there we have an efficient mapping between random bit strings to members of the subgroup of quadratic residues (and so testing which subgroup $h_x, h_y$ are in doesn't yield any information...)


MuSig/Schnorr key aggregation: How get the combined private key Given all parties' private keys in MuSig, is it possible to get a combined private key corresponding to the combined public key? I know it's possible to sign a message, but how to get the combined private key?

Yes, it's possible if you eventually know all the parties' secret keys! However, note, that in most realistic application scenarios, where there is at least one honest party whose secret key is not known, it is computationally infeasible to recover the aggregated secret key, under the  Discrete–Logarithm assumption,  given the secret keys of the corrupted parties. In the following let me use the notations introduced in the MuSig paper by Maxwell et al.

Let $L$ be a multiset (the same public key can appear multiple times in $L$) of signers' public keys: $$L=\{X_1=g^{x_1},\dots,X_n=g^{x_n} \}. $$ The message to be signed is denoted as $m$, $H$ denotes a hash function and $R=\prod_{i=1}^n R_i=\prod_{i=1}^n g^{r_i},$ where $r_i$ is a share generated by $i$th participant. Challenges are computed as: $c_i=H_{agg}(L,X_i)\cdot H_{sig}(\tilde{X},R,m),$ where we define $a_i= H_{agg}(L,X_i)$ and the aggregated public key is defined as $\tilde{X}=\prod_{i=1}^n X_i^{a_i}.$

Since $\tilde{X}=\prod_{i=1}^n X_i^{a_i}=g^{\sum_{i=1}^n a_i x_i}$ Therefore it is easy to see that the aggregated secret key is $\sum_{i=1}^n a_i x_i.$ The verification equation for an $(R,s)$ aggregated signature on message $m$ is: $$g^s=R\tilde{X}^c, $$ where $c=H_{sig}(\tilde{X},R,m)$.
Although note that the aggregated secret key has no role in verifying aggregated signatures and does not play any role in the MuSig scheme.


Why are some x-coordinates unsuitable for an ECDSA generator point? For Bitcoin's ECDSA curve (secp256k1, where $a=0$, $b=7$), why can't the generator point's first coordinate be $x=0$?
That is, the point on the curve would be $(0,y)$ where $y$ satisfies $y^2 = 0^3 + 7=7$.

Are there any elements other than $0$ which can't be used as a generator point's $x$ coordinate?

Here is a plot of secp256k1 over the reals. That I'll use for illustration purposes.

What happens at $x=-3$, well, we get $y^2 = (-3)^3+7$ which reduces to $y^2=-20$. Solving for $y$ we get $y=\sqrt{-20}$, which is not in the reals, so, we cannot have a point on that curve for $x=-3$.

This is what is happening. In the case of the real secp256k1 used in bitcoin, we are using a finite field instead of the reals. In the reals, the equation $y^2=x^3+7$ is not defined for the entire domain. Similarly, over the finite field, the equation is not defined over the entire field.

In other words, in order for there to be a point (actually 2 points) on the curve at $x$, we must be able to take the square root of $x^3+7$ in the field. As to the number of valid $x$ values, see this question on Math.SE.


Is there a cumulative commitment scheme? For a certain application I need a commitment scheme where each user could make a commitment, and a single verification operation could verify all the commitments simultaneously, faster than single verifications. It's like a batch verification of signatures but we are able to build each commitment based on the previous one (that's not the usual case for batch verification of signatures)

Formally:
Each user i, makes a commitment $C(i)$ to a value $x(i)$, as $C(i):=Commit(C(i-1),x(i),open(i))$, with $open(i)$ the randomness used for computing the commitment, or nothing if the scheme is deterministic. $C(0)$ is an initial value.

Then $CheckReveal(C(n),x(1) .. x(n),open(1) .. open(n))\ $ verifies the commitment equations very fast (e.g. $O(\log(n))$ modexps or $O(1)$ modexps).

Obviously the simple scheme $C(i)=C(i-1)^{x(i)} \mod p\ $ does not work, because two parties $i$ and $j$ (in collusion) can now change their commitments setting $x'(i) = x(i) · k$  and $x'(j) = x(j) · \frac{1}{k}$.

It sounds like you are thinking about this the wrong way.  Verifying a commitment is very fast, if you choose the commitment scheme properly.

In particular, I recommend that you use a hash-function-based commitment scheme: C(i) = Hash(x(i) || open(i)).  Then verifying an opened commitment requires just one hash evaluation, which is very fast.  Based on my measurements with openssl speed sha1, you should be able to verify several million commitments per second, if you use a SHA1-based commitment.

The question talks about modexps.  That suggests that you are considering the wrong kind of commitment scheme.  Modexps are much slower than hash evaluations.  If you are choosing a modexp-based commitment scheme, you are going to end up with something significantly slower than the best possible.  Rather than trying to make up for the suboptimal choice of commitment scheme by looking for fancy batching tricks, I recommend you simply move straight to a fast commitment scheme (based on a cryptographic hash), and then you won't need anything fancy.  My guess is that straightforward use of a hash-based commitment is going to be faster than any modexp-based commitment scheme, even with batching.


Difference between RFC-5869 (HKDF) and SP800-108 (Nist's HMAC-based KDF spec)? I'm trying to find the difference between the two aforementioned algorithms. It seems that one is either a subset of the other. Could someone explain the similarities/differences?

RFC-5869 is about the "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)", while NIST SP-800-108 gives "Recommendation for Key Derivation
Using Pseudorandom Functions". The main difference between Extract-and-Expand KDFs and KDFs based on PRFs are the requirements on the input keying material.

A PRF requires a uniform random key, which implies that the key must have a high entropy. So, in case of the NIST SP-800-108 versions of HMAC based KDFs it is assumed that you provide a random key at the beginning.

The HKDF scheme from RFC-5869 (and also NIST SP-800-56c) was originally proposed by Hugo Krawczyk in [1] as extract-then-expand KDF. As the name suggests, the function works in two steps. First, a key for key-derivation is extracted from the input keying material and a salt. The next step is essentially what SP-800-108 defines: use an HMAC (i.e. PRF based) KDF to derive further keys. The difference between SP-800-108 and RFC-5869 is the randomness extraction. With an extract-then-expand KDF you can use for example a shared secret to derive cryptographic keys and you must not provide a random key as input.

[1]. Hugo Krawczyk, "Cryptographic Extraction and Key Derivation:
The HKDF Scheme", 2010, https://eprint.iacr.org/2010/264


How secure is ECDH if the public keys are never changed? I have a scenario where I'd like to use Diffie Hellman keys where the public keys are exchanged once and then never changed.

So server generates a key pair (secp256k1 or secp256r1) and sends its public key to client and the client does the same. From that point onward, all the communication is secured by using the derived symmetric key. But these key pairs are never changed.

My question is how secured is how easy would it be for someone to figure out the symmetric key now that the same key is used for encryption/decryption?

How secure is ECDH if the public keys are never changed?

The following notation of $Gba$ is the $\operatorname{diffie-hellman(Gb, a)}$ or ${g^b}^a$ where we assume Alice' perspective where Alice knows $a$ and $Gb$, not $b$. Bob computes the equivilent $Gab$.

I advise against using straight static-dh where $a$ and $b$ are static and $k$ is unique per pair of users.

$$k = \operatorname{kdf}(Gba)$$

If either key is compromised then a passive adversary who records transactions may recover all messages. Worse, an active adversary may silently MiTM all sessions in real-time.

The full MiTM requires impersonating both sides, which KCI (key compromise impersonation) enables. I.e. If Mallory knows $a$, she can pretend to be Alice to Bob and pretend to be Bob to Alice.

One popular alternative is 3DH, as used in Signal and similar protocols.

$$k = \operatorname{kdf}(Gda \| Gbc \| Gdc)$$

Where $c$ is Alice' ephemeral key and $d$ is Bob's ephemeral key. Notice $Gab$ is not used because it is static and does not introduce additional security as the ephemerals are paired with the static keys providing KCI-resistant mutual authentication and paired together for forward secrecy.

If both of Alice and Bob's keys are compromised. A passive adversary is still unable to recover messages. However, an active adversary may substitute the ephemerals and do the full MiTM again.

If the client is anonymous, you may use 2DH by omitting $a$ and computing instead:

$$k = \operatorname{kdf}(Gbc \| Gdc)$$

  My question is how secured is how easy would it be for someone to figure out the symmetric key now that the same key is used for encryption/decryption?

You must always respect the security contract of any function you use. I.e. Never reuse a $k$ with a single-use AE. Never reuse a $(k,n)$ tuple with an nAE.

If you're using the symmetric key correctly or not is irrelevant to how the key was derived.

Edit: If you're asking if it is safe to shake hands with with many people? Then yes, so long that the construction is safely guarding against bad-keyshare attacks, the result should not reveal anything to an adversary, even if you shake hands directly with them.


Would it be better to split a file and then encrypt, or vice versa? Assuming that you are paranoid before storing your file (distributed across a shared location), which will be the best case scenario: splitting the file first and then encrypting or encrypting first and then splitting?

Either could be implemented securely, but if you encrypt first and split afterwards, you can use standard tools and get everything right more easily. If you used the opposite order, you would have several pitfalls to deal with:

With password-based encryption you would either have to derive the key many times (spending resources that would be better used on additional hashing) or have a separate key derivation step and then use the key on all the parts.
If you had a single key used multiple times, you would have to make sure IVs are unique, when with a single-use key you can forgo it completely.
To fully authenticate the encrypted file you would need to add some metadata or a whole-file MAC, instead of simply using authenticated encryption on each part. Otherwise an attacker could be able to drop or reorder the parts.
As a practical issue, if you are splitting to a certain target size, you would have to take into account the expansion caused by encryption IVs and authentication tags.


What is it known about the hardness of the factorization search problem in non-commutative crypto? The factorization search is an interesting problem in non-commutative crypto that can be defined as:

Given an element $c$ of a group $G$, two subgroups $A,B \leqslant G$. Find two elements $a\in A$ and $b \in B$ such that $c=ab$.

In the case of $A=B$ we can see that any element $a'\in A$ will give us $b' \in B$, since $b'= a'^{-1}c$, because the resulting element is in the same subgroup.

If $A$ and $B$ commute element-wise then pick $b'\in B$ and compute the commutator $[c,b'] = [ab, b'] = b^{-1}a^{-1}b'^{-1}abb'$. Since $[a^{-1}, b'^{-1}] = 1$ then $[ab,b'] = (b'^{-1})^b b'$. Finally multiply by the inverse of $b'$ to obtain $(b'^{-1})^b$. This is a reduction to the conjugacy search problem (CSP).

Q: What is the situation about the factorization search problem?

Q: What reductions exist to known problems on Group Theory, if any?

Q: Is there any protocol based on this problem?

Q: What reductions exist to known problems on Group Theory, if any?

I would consider the factorization search problem to be a known problem in group theory. After all, the LU-decomposition and QR-decompositions of matrices are special cases of the factorization search problem. In group based cryptography, the decomposition problem is usually stated in the following equivalent but seemingly more general form:

Suppose that $G$ is a group and $A,B$ are subgroups of $G$. Suppose that $x,y\in G$. Then find $a\in A,b\in B$ where $axb=y$.

  Q: Is there any protocol based on this problem?

The Ko-Lee et al key exchange, one of the first two non-commutative group based public key cryptosystems, is the cryptosystem which is most closely related to the factorization search problem.

$\textbf{Ko-Lee key exchange classical formulation:}$ Suppose that $G$ is a group $c\in G$, and $A_{L},B_{L},A_{R},B_{R}$ are subgroups of $G$ such that $ab=ba$ whenever $a\in A_{L},b\in B_{L}$ or $a\in A_{R},b\in B_{R}$.

Alice selects $a_{L}\in A_{L},a_{R}\in A_{R}$ and sends
$r=a_{L}ca_{R}$ to Bob.
Bob selects $b_{L}\in B_{L},b_{R}\in B_{R}$ and sends $s=b_{L}cb_{R}$ to Alice.

The common key is $K=a_{L}b_{L}ca_{R}b_{R}.$

Alice computes $K_{A}=a_{L}sa_{R}$.
Bob computes $K_{B}=b_{L}rb_{R}$.

Note: Sometimes, in the Ko-Lee key exchange, one sets $A_{L}=A_{R},B_{L}=B_{R}$ and $a_{L}=a_{R}^{-1},b_{L}=b_{R}^{-1}$ so that the Ko-Lee key exchange is based upon the conjugator search problem.

$\textbf{Ko-Lee key exchange alternate formulation:}$ Suppose $G$ is a group and $A'_{L},B'_{L},A'_{R},B'_{R}$ are subgroups of $G$ such that $ab=ba$ whenever $a\in A'_{L},b\in B'_{L}$.

Alice selects $a'_{L}\in A'_{L},a'_{R}\in A'_{R}$ and sends
$r'=a'_{L}a'_{R}$ to Bob.
Bob selects $b_{L}'\in B'_{L},b'_{R}\in B'_{R}$ and sends $s'=b'_{L}b'_{R}$ to Alice.

The common key is $K'=a'_{L}b'_{L}a'_{R}b'_{R}.$

Alice computes $K'_{A}=a'_{L}s'a'_{R}$.
Bob computes $K_{B}'=b_{L}'r'b'_{R}$.

The alternate formulation of the Ko-Lee key exchange is a special case of the classical formulation of the Ko-Lee key exchange. To formulate the classical formulation of the Ko-Lee key exchange in terms of the alternate formulation of the Ko-Lee key exchange, one sets $A_{L}'=A_{L},B_{L}'=B_{L}$, $A_{R}'=cA_{R}c^{-1},B_{R}'=cB_{R}c^{-1}$ and $a_{L}'=a_{L},b_{L}'=b_{L}$ and
$a_{R}'=ca_{R}c^{-1},b_{R}'=cb_{R}c^{-1}$ and $K'=Kc^{-1}$.

  Q: What is the situation about the factorization search problem?

The decomposition problem on the braid groups has been attacked for example using length based attacks. Such an attack can be found in this paper. In general, one could more or less use length based attacks to attack any cryptosystem based upon the factorization problem in non-commutative cryptography. For example, length based attacks have successfully broken the Ko-Lee key exchange with Thompson's group as the platform (see this paper).


Cryptanalysis of Nonlinear Table Lookup I am trying to derive a symmetric key based on a master key, combined with a simple string. Based on my limited knowledge, it seems that something like PBKDF2 would do that for me in a well-defined way:

DK = PBKDF2(PRF, Password, Salt, c, 256)

Password = master key
Salt = simple string
c = number of iterations
DK is the 256 bit derived key

However, I am working in a very constrained embedded environment, so a high number for 'c' is not an option. Now for my question:

Would I improve security if I used a low value for 'c', but I did some kind of table lookup as a final step, such that

DK_final = table[F(DK,i) MOD size]

Assume DK is twice is large as DF_final, so 256 bits and 128 bits respectively
table = a large table of randomly chosen bytes (more than 4000 elements)
F(DK,i) = a simple function that takes the i'th 2 byte pair from the string DK
size = the number of elements in the table
DK_final = the final derived key, 128 bits in this example

I could not find any published material on such a method, besides a vague reference here. However, no indication of cryptanalysis was given.

Any help on such a scheme would be appreciated, if only to warn against it: It seems that the general rule of thumb is never invent you own clever idea with it comes to cryptography.

If the master key is strong (e.g. random 256-bit key), $c=1$ is fine, or you can use HKDF. A high number of iterations is only needed when you derive the key from a password or other low entropy string.
If you can store a 4000 element table securely, you could just use random keys instead of derived ones.
If you need the derived key to depend on a low entropy master key, you could use a randomly generated salt you keep secure. In that case leaking the salt will allow a brute force or dictionary attack on the master key, but without knowing the salt an attacker cannot attack it.

Optimally, your situation is 1. and you don't need to do anything special. 2. is also a secure alternative, but requires you to store more keys. You should only use 3. if you have no other options, and in that case you should use as high a $c$ as you can.

Now the actual question, is such a table secure?

If you have a large enough table that is only used for one key, it will not hurt the quality of the derived key. However, if that isn't the case, it may, since the keys will share the nonuniform probability distribution defined by the table.

An attacker who has the table could of course derive the key just as easily as when no table was used, so it is no better than using a random secret salt like I suggested in 3. above. So I wouldn't recommend using it.


Number of Sbox in a Cipher Camellia has 4 SBOX and so does the TwoFish(key dependent 4 Sboxes). Where as AES uses only one. Would it have made AES more secure if AES had 4 or more SBOX too? Does using more Sbox with similar Properties (Non Linearity, Differential Probability, Linear Probability, Strict Avalanche Criteria etc) increase the security as compared using just one for all possible byte positions? What security impact it will gain if 16 Different SBOX are used?

Coincidentally I had the Twofish and Camellia design papers open on my computer when you asked this question.

S-boxes in the ciphers

Both are Feistel ciphers, and the way the s-boxes are used is quite different when compared to AES. The s-boxes are used almost identically in Twofish and Camellia, but key mixing and post s-box diffusion are quite different. I assume you know the general structure of the ciphers so I will not go over that here.

Camellia uses each s-box twice per round, and runs the entire 64-bit input through those s-boxes in parallel, then mixes them together. Key material is added to the input prior to the s-boxes. Twofish uses each s-box twice per round in parallel, then mixes each 32-bit half, then mixes those halves together, followed by addition of key material.

AES of course uses the same s-box on all 16 input bytes prior to mixing, followed by diffusion and key mixing.

S-box design

The way the s-boxes in these ciphers are generated is also different. AES uses its single s-box generated from finite field inversion followed by affine transformation and addition of a constant.

Camellia uses 4 AES-like s-boxes (finite field inversion), S2 S3 and S4 are generated from S1, which has a base design optimized for minimum hardware resources. A time-memory tradeoff can be made in implementations where only the table of S1 is in memory, and the permutation to the other s-boxes is done at runtime, which is composed of fixed rotations. Minimal hardware resources and a Feistel design (same decrypt hardware, less data processed per round) can make Camellia more efficient than AES in dedicated hardware. The key schedule is more complex than AES, and it reuses the round function to generate key material.

Twofish s-boxes are made from 2 different permutations and key material. The permutations themselves are made from 4 fixed 4-bit s-boxes each. A time-memory -storage tradeoff can be made in implementations where only the tables of 4-bit s-boxes are stored in code, and the permutations are generated and stored in memory during key scheduling, where the s-boxes are generated. Twofish has a much more complex and expensive key schedule by design.

S-boxes and security

When it comes to the question of security, Camellia is a more modern cipher than AES, with a complex key schedule more resistant to related key attacks, but a more simple round structure which requires more rounds to meet its required security bound. Twofish has a very complex key schedule along with a complex round structure which requires 32-bit addition, limiting performance on platforms with only simple logical operations. Twofish was considered to be more secure than AES but lost out due to its slow key schedule and implementation issues due to 32-bit addition on non 32-bit platforms.

Because Twofish and Camellia are a completely different structure than AES, the way the s-boxes contribute to security is different. Round counts in all ciphers are chosen to keep known security properties within the margin defined by the key size. At this time, out of the 3 only AES is known to have a security level under any condition lower than the key size, and only in a related key model, and it is not a practical attack.

It is certainly possible than the use of additional s-boxes could have eliminated such an attack, but at the expense of an additional s-box, possibly making storage requirements on constrained platforms such as 8-bit microprocessors and smartcards substantially larger, which is quite small for AES when compared to other ciphers of similar security and performance on a variety of platforms.

There are multiple ways additional s-boxes could have been added to AES. You could have 2 s-boxes, one for odd rounds and one for even rounds. A different s-box could be used in the key schedule. You could have multiple s-boxes in each round like Camellia and Twofish. You could have a combination of these using 4 s-boxes, like 1 and 3 on odd rounds, then 2 and 4 on even rounds. If the s-boxes have similar or identical properties to the original, the full cipher would have similar or identical security against some attacks, and most likely superior security against some others.

The other problem with adding more s-boxes is that security proofs and analysis gets more complicated, using a single highly nonlinear s-box allowed initial analysis on Rijndael to use very simple and easy to analyze descriptions, which gave confidence in the algorithm under intense scrutiny. This same simple description is also one reason why people are looking for alternatives. S-boxes based on finite field inversion are also under scrutiny due to CCZ-equivalence, which may be exploited to reduce the complexity of attacks.

With 15 years since AES was chosen to replace DES, much of block cipher design has been focused on smaller faster designs as opposed to more secure designs, and on designs immune to side channel attacks, which have been the bane of many AES implementations. S-box table lookups are a problem for cache timing consistency, they can reveal plaintext or key material. Multiple s-boxes can make it more difficult to mount such an attack, but s-box free designs can eliminate them. Since the AES s-box is already as nonlinear as you can get with an 8x8 s-box, adding more s-boxes will not improve overall linear properties, only a larger s-box will do that, or addition of more nonlinear steps to the round function.

Conclusion

This question is similar to "If I add more pistons to an engine, will the car go faster?" My 6cyl car is much faster than my old V8, but its also turbo charged, and direct injected and the V8 was not, so there is more to a car than just the piston count of the engine. There is also more to a car than just speed, just as there is more to a cipher than just security.

Adding more s-boxes to an AES derivative will probably increase security, but since AES is still considered secure for use, even for top secret US government use, that is not a good use of resources. An improved key schedule will improve resistance to many attacks at the expense of performance, with less hardware and software resources required when compared to an additional s-box, and way less when compared to multiple s-boxes, unless it was done in the way the Camellia s-boxes are created, which are permuted from a single s-box.

Using maybe 2 or 4 different types of s-boxes and increasing the round count by 1 or 2 rounds would most likely result in the the best balance of security, performance, and implementation resources based on adding s-boxes alone. By different types I mean those with a more complex algebraic description or those without CCZ-equivalence, like the Skipjack s-box for example.


Re-encrypting a message and proving that the message has not changed Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each?

More specifically: if I have a message $m$, and I encrypt it with an asymmetric key scheme $E_1: c_1 = E_1(m)$ and then re-encrypt it with a new key pair $E_2: c_2 = E_2(m),$

is there a way for an observer (possibly using a ZKP or homomorphic encryption) who only has access to $c_1, c_2$ and the public keys of $E_1$ and $E_2$ to prove that $m$ is the same plain text used to generate $C_1$ and $C_2$?

I  think this is not compatible with semantic security (IND-CPA). If such a proof exists,  an adversary that chooses $(m_0,m_1)$ and receives $c_b=E_1(m_b)$ may compute $E_2(m_0)$ and try to prove that $m_b=m_0$. If the proof is correct, then he guesses that $b=0$, else $b=1$. But may be there exist weaker security models that allow to test the equality of two plaintexts.
Your problem seems similar to plaintext checkable encryptions.


What is an advantage of MDS matrices in block ciphers? I saw the several articles about MDS matrices. They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks. My question is:

For example in the case of linear attack, is constructing the bias table of MDS matrices behavior impossible? Or the values of biases are such a way that linear attack is not applicable and its complexity is higher that brute force attack?

They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks.

That would probably depend on the cipher, but in generally, pretty accurate.

  is constructing the bias table of MDS matrices behavior impossible?

Actually, it's trivial; MDS matrices are completely linear, and so they have probability 1 linear and differential trails.

So then, if MDS matrices, in themselves, offer no protections against linear and differential cryptanalysis, why are they said to help greatly?

Well, it's because they help other components within the cipher work a lot more effectively, as it forces any linear/differential characteristic to go through most of the cipher.

Consider this simple design:

     |       |      |      |
   sbox    sbox   sbox   sbox
     |       |      |      |
    ------ MDS Matrix ------
     |       |      |      |
   sbox    sbox   sbox   sbox
     |       |      |      |

Then, for any linear characteristic, that characteristic must go through at least 5 of the sboxes; that's because for any nonzero change, the MDS matrix ensures that the number of input lines changed plus the number of output lines changed is at least 5.  So, if the sbox have a best linear characteristic of $\epsilon$, then the best path here is at most $\epsilon^5$.

If we scale this toy example up into something realistic (e.g. AES), then any path must go through a huge number of sboxes, and so any path is effectively dampened out.


What signature schemes allow recovering the public key from a signature? It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone.

This seems like an interesting property; as far as I know, RSA doesn't share it.

Depending on the application, this can both be an advantage (shorter messages, as the public key or a key id doesn't have to be attached) and a disadvantage (if confidentiality is required, the signature has to be encrypted).

Which other cryptographic signature schemes have that property? I'm especially interested in RSA, Ed25519 and (non-elliptic) DSA.

Well, lets go through the issues:

  It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone

Nope, not quite.  You also need the message being signed. And, with that, it doesn't give you the unique public key; it does allow you to narrow it down to two possibilities (assuming you're using a curve with a cofactor of 1; almost always the case nowadays), however from a single signature, you don't know which of the two possiblities it is.

  In some circumstances, the private key can be recovered as well

I should certainly hope not.  If you can recover the private key with a signature and the message being signed (and you can throw in the public key if you want), then the signature scheme is "broken"; I rather doubt that Mr. Brown claims that ECDSA is broken.

  this can be an advantage (shorter messages, as the public key or a key id doesn't have to be attached)

Well, it's not that much of an advantage; not only does the verifier need to know what the public key is, he also needs to know that it's the correct public key; that is, it is the public key whose private key is held by the person you think is signing the message.  There are a number of ways a verifier can ascertain that; however he must do so; just passing a public key somehow (either explicitly or implicitly) doesn't cut it.

  this can be a disadvantage (if confidentiality is required, the signature has to be encrypted)

Not so much; if confidentiality (rather, anonymity) is required (specifically, you don't want an evesdropper to be able to verify who signed the message), then you need to hide the signature anyways.  If you don't, then the evesdropper does get a copy of Alice's public key, and has a guess for the message can simple check if the message is from Alice by running the signature verification method using his copy of Alice's public key.  This doesn't require any special properties of the signature method.

  Which other cryptographic signature schemes have that property?

I'll go through the ones you listed:

RSA; if the public exponent isn't large, and you use a deterministic padding method, then you can recover the RSA public key from two signatures (of two different messages)
Ed25519; I don't believe that you can recover the public key.  The verification process involves a hash of data including the public key; there's no way to quickly check which public key would make the hash come out correctly.
DSA: I don't believe that you can recover the public key.  The distinction between DSA and ECDSA is that the DSA verification process involves an outer "mod q" operation; that operation discards information that would be needed to recover the public key.


Chance to find HMAC key/salt when having knowledge of the hashed data? I'm not sure how to word this... I'm working with a HMAC (I think of it being a "salted hash"). I know the entire string being hashed, I do NOT know the salt. I also know the first 8 characters of the resulting hash. I can also, repeatedly, generate new hashes by changing the input string, and retrieve new first-8 characters.

Does that in any way make it even remotely possible to find the salt? Even via brute forcing, would that decrease the entropy at all, if I were able to modify the hashing algo (much like how bitcoin is mined by pre-computing most of the hash and only updating the nonce at the end, removing many many steps from the hashing itself)?

From all I've learned, I'm leaning towards a "no", that its no help whatsoever. That being said, I've never worked with a HMAC/salted hash before, so I'm not sure if that works any differently. Is finding the salt any easier because of how a HMAC is computed?

Assuming you mean a normal HMAC with a strong unknown key, no amount of MAC values for known, or even chosen messages would help you find the key. That would mean a failure of HMAC's forgery resistance, which is expected of MAC algorithms.

(It would be a very bad case of forgery attack, since it would allow forging MACs for any messages. Even much lesser attacks, like being able to forge a single valid MAC for another message, would be considered significant breaks.)


Using RSA encryption to encrypt large files The following post discusses the use of RSA for file encryption:

https://medium.com/@ismailakkila/black-hat-python-encrypt-and-decrypt-with-rsa-cryptography-bd6df84d65bc

The file encrypted is a JPEG image. My question is: what if we were to encrypt larger files say, 10 MB, in a similar manner and are able to reach acceptable encryption speed with a modern i7 processor?

Is the resulting ciphertext practically decryptable in anyway without the private key?
What factors affect the speed of encryption in this case? The RSA key size? The block size? The padding type?

Note: I do realize that RSA is not meant for file encryption in this manner and that a hybrid encryption scheme is more suitable (encrypt data with a session key, then encrypt session key with the RSA key). Please do bear with me and assume that we must encrypt a large file with RSA. I'm merely trying to understand the practical impacts and limits in doing so and I realize that hybrid encryption is more appropriate here.

Is the resulting ciphertext practically decryptable in anyway without the private key?

No, you would need the private key. There is no practical limit on the amount of times that you can encrypt with a public key. I would make sure that the randomness within the padding is at least 128 bits though. Also note that decrypting many times with a private key makes the algorithm more vulnerable against side channel attacks (which often rely on statistics). Furthermore, it disallows you to protect the private key with a PIN or password for each decryption.

  What factors affect the speed of encryption in this case? The RSA key size? The block size? The padding type?

Yes, yes and yes.

The RSA key size is of utmost importance because larger key sizes will affect performance hugely. Furthermore, RSA key sizes grow very fast if you require more key strength. RSA-3072 is providing about 128 bit security, but you need to go over 16Kbit of key size to reach 256 bits. And those kind of operations are certainly very slow, specifically when it comes to private key operations.

The block size used for the plaintext differs from the one for the ciphertext (i.e. the input is always smaller than the output) due to the padding requirements. The block size for the plaintext is generally 11 smaller than the key size for the less secure PKCS#1 v1.5 padding and differs by the hash value for OAEP. The block size of the ciphertext is identical to the size of the modulus in bytes.

The padding type is generally not much of a problem when it comes to encryption speed. RSA private key operations are rather slow, and the unpadding won't take much time compared to them. The generation of the padding however relies on a secure random number generator. Random number generation can be fast, but it might also block or slow down the system by other means.

Note that performance is only one reason why direct encryption with RSA should be shunned. The expansion of the ciphertext compared to the plaintext is another big reason. And as indicated, requiring the private key to be available for batch operations may well put it at risk.


AES (or otherwise): can you decrypt concatenated encrypted messages as one? Say I have 20 distinct encrypted messages.
Using AES, I am only getting the correct output if I decrypt each of the 20 messages individually.
Is it possible using AES or another method to call my decrypt function on the concatenated 20 messages as one message and get the concatenated decrypted results?
It seems inefficient processing time to call decrypt 20 times.
(Note: I am doing this with raw audio, and interestingly when I decrypt 20 together it sounds like the original but with some clinky noise)-- I want without the clinky noise.

Stating "AES" is not enough to specify some encryption. AES is a block cipher, not a cipher. It's used per some operating mode. Among these

ECB without padding has the desired property that one can concatenate ciphertext fragments without decompression artifact, but is unsafe, and works only if the plaintext is an exact multiple of the AES block size (16 bytes).
CBC and CFB with IV prepended as ciphertext (which is usual) would do precisely what's reported: "when I decrypt 20 (concatenated ciphertext fragments) together it sounds like the original but with some clinky noise" because the IV (and perhaps some padding in the previous fragment) is misinterpreted as data, and inserts an error;
CTR or OFB would not recover from the error, and thus only the first 1/20 of the audio would be intelligible.
GCM or other authenticated mode would not output anything.

Is it possible using AES or another method to call my decrypt function on the concatenated 20 messages as one message and get the concatenated decrypted results?

Yes. One needs to take come precautions w.r.t. padding, but if the existing encryption procedure splits the data on some multiple of 16 bytes, there's nothing to change on encryption. Just remove from the output the extra data that corresponds to the inserted IV, and perhaps padding. That's merely 19 memory copy, over 19/20 of the data. It might save time, or not, depending on off-topic considerations.
For padding, the plaintext fragments should be aligned on multiples of 16 bytes (except for the last).
Encryption can be with padding (as most libraries do), but then one should either

Remove the last 16 bytes of each ciphertext fragment except the last before joining the ciphertext fragments; and remove the 16 bytes of IV at each of the 19 fragment frontiers in the output of decryption.
Remove the 16 bytes of data the padding generated (thus removing 32 bytes at each of the 19 fragment frontiers: 16 for padding of the previous fragment, and 16 for IV of the next one).

Alternatively, one can encrypt without padding, and manually pad the last plaintext fragment with zeroes, which for most compressed audio gets removed by the player, and for some uncompressed audio is silence.


Is there a standard method to compare hardware-implemented ciphers? I have been reviewing literature and I am trying to determine the best method to compare ciphers in hardware.  The two methods that seem to be somewhat de facto standard the literature are looking at throughput for a 100kHz clock, and looking at area in GE (gate equivalents).  I take issue with these methods because for the clock method, the initial state is not given, ie: I do not know if this is measured from a loaded state.  The second method I have an issue with because GE is the area of a NAND gate, and if you use a huge NAND, you look like your implementation is relatively better.

Is there a standardized method to compare ciphers on a hardware level that is not this seemingly de facto method?

Furthermore, is there a standard method to compare Feistel ciphers against a substitution-permutation network?

If someone could point me to a document that outlines a method to compare ciphers from the implementation standpoint, it would be helpful.

Because of how many ways there are to implement a hardware design there is not a specific comparison protocol that I am aware of. The main comparison points are power, area, and throughput, and comparisons are generally done on the same process, 32nm GF SOI for example. With a given process, area can be measured in GE or mm$^2$.

The algorithm itself will usually be the limiting factor when it comes to clock speed, and this may not be an issue if the throughput is still good. Unrolling loops uses more area but can increase throughput dramatically. Constants like those in SHA2 use a large amount of area, wheras those in SHA-3 use very little.

An implementation can be tuned to be better at a specific trait, such as power usage or speed, or tuned to have a good combination of two of them at the expense of another. Throughput/area or throughput/watt then become the usual target for a given implementation.

    Area          Power         Throughput
A   1mm^2         10mw          1.00Mb/s
B   1mm^2         30mw          2.45Mb/s

C   3mm^2         10mw          2.45Mb/s
D   3mm^2         30mw          6.00Mb/s
E   3mm^2         90mw          14.7Mb/s

F   6mm^2         90mw          44.1Mb/s

Each implementation has an advantage and a cost. D has a 100% increase in throughput/area and throughput/watt over A, but at triple the area. B and C have the same throughput, but one uses less area and the other less power. For a given area, triple the power budget gives a 2.45X increase in throughput. Because the 3mm area implementation is able to radiate more heat thanks to increased surface area, it can be pushed beyond the power limits of the 1mm area implementation. Despite using 1/3 the area and 1/9 the power, A is only 14.7 times slower than E. F is 3X faster than E at the same power, with only double the area used.

So how do you compare them? Which one is the best? The high area implementation obviously has the best throughput, and the best throughput/watt, but you may not have the area to spare, or the power. Would one consider A more efficient than E or the other way around? E has 63% better throughput/watt than A, but at the same wattage A has 22% better throughput/area.

In the end the a good comparison can only be made by keeping the process a constant, then deciding which implementation is better or more efficient based on the requirements of the final product.


CP-ABE for threshold cryptography I would like to know if there is any research work using CP-ABE for threshold cryptography?

I want to know also if applying CP-ABE for threshold cryptography would overcome other techniques.

Many ABE schemes support Threshold Cryptography in the sense that the policy that is used to share a random secret supports threshold gates. This is also not limited to Ciphertext-Policy ABE. Key-Policy ABE schemes also support threshold policies.

The threshold policy is usually written with the of operator such as

  2 of (attribute1, attribute2, attribute3, attribute4)

or more complex examples such as

  2 of (a1, a2, a3, (a4 and a5 and (a6 or a7 or a8)))

The paper you linked to (BSW07) describes a high-level view of the threshold policy in section 4.1 and a more detailed view in the Encrypt and Decrypt paragraphs of section 4.2. The functionality is very similar to Shamir Secret Sharing executed for each gate in the policy.

Access trees are not the only access structures that are used for policies in ABE schemes. LSSS matrices are also very popular. Liu et al. have published an algorithm in "Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees" (2010) to transform boolean threshold formulas into threshold LSSS access structures.


Will reading "Elementary Number Theory" by David M. Burton be useful for Cryptography? I am a Computer Science student and interested to learn Cryptography to be a researcher in this field. I heard that Number Theory is useful for Cryptography since there are some Crypto systems based on it. I really like Number Theory and have started reading Elementary Number Theory by Burton. So far I have been reading the theorems and trying to prove them myself. Will my approach be useful for Cryptography?

It's better to study cryptography and refer to number theory (and other fields) when it's needed.

Nevertheless, Math is very important, if you want to be something better than 'press any key' cryptographer. Mostly, you will need Group Theory, Linear Algebra, Graph Theory, Automata Theory, Complexity, Number Theory, some bits of Functional/Mathematical analysis, a bit of Complex analysis, some knowledge about polynomials, and of course, Probability Theory.

Before obtaining a degree in Security I got Masters in Math and, looking back, it helped me a lot, compared to other students. And yes, your approach will be useful.


Which compression functions are PRFs? In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs.

The Wikipedia article on cryptographic hash functions mentions that

  In practice, collision resistance is insufficient for many practical
  uses. In addition to collision resistance, it should be impossible for
  an adversary to find two messages with substantially similar digests;
  or to infer any useful information about the data, given only its
  digest. In particular, should behave as much as possible like a random
  function (often called a random oracle in proofs of security) while
  still being deterministic and efficiently computable.

It seems to me that in practice hash functions are usually considered to be PRFs. Is this valid and are commonly used compression functions all PRFs?

Note: The Bellare paper states

  (There are to date no attacks that compromise the pseudorandomness of
  the compression functions of MD5 or SHA-1.)

Has this changed since then?

An interesting related paper by Kim et al., also from 2006, gives distinguishers for HMAC based on SHA-0 and HAVAL to distinguish it from HMAC with a random function. Which at least hints that it might be hard to determine if a compression function is a PRF.

(There are to date no attacks that compromise the pseudorandomness of the compression functions of MD5 or SHA-1.)

  Has this changed since then?

Not as far as I know.

  It seems to me that in practice hash functions are usually considered to be PRFs. Is this valid and are commonly used compression functions all PRFs?

Note that there are two ways to define the PRFness of a hash function. A compression function is a function $f(x_1, x_2)$, where $x_1$ is the state input (either the IV or the previous block output) and $x_2$ is the current data block. You can take either $g_k(x) = f(k, x)$ of $g'_k(x) = f(x, k)$ when you consider whether it is PRF.

For SHA-1 and SHA-2 $f(x, k)$ is relied on when using the SHACAL ciphers. (Or actually, SHACAL relies on them being pseudorandom permutations, PRP.) However, for HMAC the opposite, $f(k, x)$, matters (as well, see comments).

E.g. since there are no known attacks on full SHACAL-2, you could assume that SHA-256 is PRF up to around $2^{128}$ calls (birthday bound for distinguishing PRP from PRF). However, that would not necessarily apply to the way it is used in HMAC... but there is no known attack on that either.

SHA-3 has more explicit security claims regarding its pseudorandomness, but it does not use a compression function in the normal sense, but a sponge function instead.

TL;DR: the compression function of the currently secure hash functions, like SHA-256, seems likely to be PRF, though it is not a property that the designers claimed. The compression function of the weak MD5 or SHA-1 might still be PRF, but I would not rely on it if I did not have to, since their use is deprecated. And if you want something with security claims regarding this, you could look into SHA-3 instead.


Cracking truncated DES Let's say we have a scheme in which 40 bits M are padded with 24 zeroes, encrypted using a secret DES key K, and the result truncated to the first 24 bits, C. If I wanted to determine a key that behaved identically to K, i.e. for each (or at least the majority of) M produced the same C, how many pairs of M/C would I require to find such a key with reasonable chance?

In symmetric cryptography, for fully known ciphertext, one is expected to need slightly more known plaintext bits than usefull key bits in order to reliably recover the key by pure brute force. That rule also works if we reverse plaintext and ciphertext, and that's what we want here.

The key is 56 bits. Each pair (M, C) with distinct M chosen at random gives 24 bits of ciphertext. Two pairs give 2⋅24 = 48 bits, 56-48 = 8 bits are missing, and about 28 = 256 keys would match. Three pairs give 3⋅24 = 72 bits and that is enough for brute force key search to pinpoint a single key with excellent probability (in the order of 256-72 < 1/50000 ). Most likely the first key found (after an expected 255 keys have been tested, and marginally more trial encryptions) will "behave like K" for any other (M, C) pair, because it is the actual K used to build the pairs (M, C).

It is feasible to intentionally exhibit three pairs (M, C) (perhaps more) with distinct M such that at least two keys are possible; but again this is unlikely to happen by chance.

It is asked the math. Let $(M_i,C_i)$ be the given plaintext/ciphertext pairs (40+24 bits each), with distinct $M_i$, corresponding to an unknown actual key $K_A$. Let $C_{(K,i)}$ be the result of expanding $M_i$, enciphering under key $K$, and truncating to 24-bit. By that definition, $C_{(K_A,i)}=C_i$.

Because the $2^{56}$ DES keys only cover a small fraction of the $2^{64}!$ permutations of the DES block, and in that application at least one bit in the input is fixed (thus making irrelevant the DES complementation property that $E(\overline K,\overline P)=\overline{E(K,P)}$ ), and we'll have few plaintexts (or/and can observe only a small fraction of the bits of an output block), we can model the $C_{(K,i)}$ for each $(K,i)$ as uniformly random and independent 24-bit bitstrings. That's true including for $K=K_A$, under the assumption that the $M_i$ have been chosen independently of $K_A$.

Under that model, a key $K\ne K_A$ is such that $C_{(K,i)}=C_i$ for $n$ plaintext/ciphertext pairs with probability $2^{-24n}$ (that probability is halved for each ciphertext bit). It follows that with $n$ pairs, each $K$ can be eliminated with probability $1-2^{-24n}$. After testing all $2^{56}$ keys, $K_A$ remains the only possible key with probability $p_n=(1-2^{-24n})^{(2^{56}-1)}$ and there remains more than one possible key with probability $\overline{p_n}=1-(1-2^{-24n})^{(2^{56}-1)}$.

For $n\ge3$, we use that $1<c\ll1/|\epsilon|\implies1-(1-\epsilon)^c\approx\epsilon\cdot c$ to get $\overline{p_n}\approx2^{56-24\cdot n}$. Thus $\overline{p_3}\approx2^{-16}$, which is very small (meaning 3 pairs will do with excellent odds).

For $n\le2$, we use that $\log p_n=(2^{56}-1)\log(1-2^{-24n})$, and $|\epsilon|\ll1\implies\log(1+\epsilon)\approx\epsilon$ to get that $p_n\approx e^{(-2^{56-24n})}=2^{-(56-24n)/\log2}$. Thus $p_2<2^{-369}$ which is ludicrously small (meaning 2 pairs won't do). The most probable is that many keys will remain possible (in the order of $2^{56-24n}$).


lcm versus phi in RSA In textbook RSA, the Euler $\varphi$ function
$$\varphi(pq) = (p-1)(q-1)$$
is used to define the private exponent $d$. On the other hand, real-world cryptographic specifications require the Carmichael lcm function
$$\lambda(pq) = \operatorname{lcm}(p-1,q-1)$$
to define $d´$.
It is clear that the $d´$ divides $d$, and therefore using $d´$ may be more efficient than using $d$.
My question is: Are there any further reasons, e.g. regarding security, why one should not use $d$?

I'll use these common definitions and notations:

$a\equiv b\pmod c$ means that $c>0$ and $c$ divides $b-a$
$a\equiv b^{-1}\pmod{c}$ means that $a\cdot b\equiv 1\pmod{c}$
$a=b\bmod c$ means that $a\equiv b\pmod{c}$ and $0\le a<c$
$a=b^{-1}\bmod c$ means that $a\equiv b^{-1}\pmod c$ and $0\le a<c$
$\varphi$ is the Euler totient function (also noted $\phi$)
$\lambda$ is the Carmichael function

I restrict to $N$ product of distinct primes; for two such primes, $\varphi(N)=(p-1)\cdot(q-1)$, $\lambda(N)=\operatorname{lcm}(p-1,q-1)$, and $\varphi(N)=\lambda(N)\cdot\gcd(p-1,q-1)$.

The cryptographic standard PKCS#1 requires that the private exponent $d$ is an integer with $0<d<N$ and $e\cdot d \equiv1\pmod{\lambda(N)}$. The later condition is used because it is precisely the necessary and sufficient condition on $d$ so that textbook RSA works, that is:
$$\forall x\in\{0,\dots,n-1\}, y=x^e\bmod N\implies x=y^d\bmod N$$

Notice that $e\cdot d \equiv1\pmod{\lambda(N)}$, or equivalently $d\equiv e^{-1}\pmod{\lambda(N)}$, does not uniquely define $d$. If $d$ is a valid private exponent, then from a mathematical standpoint $k\cdot\lambda(N)+d$ is also a valid private exponent $\forall k\in\mathbb Z$, and is valid from a PKCS#1 standpoint when $0<d<N$.

It is PKCS#1-conformant to use $d=e^{-1}\bmod\varphi(N)$; that uniquely defines a value of $d$, with $0<d<N$ since $\varphi(N)\le N$, and $d\equiv e^{-1}\pmod{\lambda(N)}$ since $\lambda(N)$ divides $\varphi(N)$. This common choice of $d$ will lead to exactly the same results as using any other valid $d$ when exponentiating to the $d$th power modulo $N$. As far as we know, it is not less safe than using $d=e^{-1}\bmod\lambda(N)$, even when side channel attacks are taken into consideration.

Using $d=e^{-1}\bmod\lambda(N)$ rather than $d\equiv e^{-1}\pmod{\varphi(N)}$ is not a good speed optimization: if one is interested in speed, one does not use $d$ at all! Rather, one implements RSA using the Chinese Remainder Theorem (CRT), where exponentiation is performed modulo each prime $p$ dividing $N$, using an exponent which can be computed as $d_p=e^{-1}\bmod{(p-1)}$ irrespective of which $d$ is chosen.

Update: as pointed in comment, the FIPS 186-4 standard requires $2^{\lceil\log_2(N)\rceil/2}<d<\lambda(N)$. Use of $\lambda(N)$ rather than $\varphi(N)$  restricts to a single private exponent, easing Known Answer Tests used for certification; does that in the most mathematically satisfying way; and happens to simplify the requirement $2^{\lceil\log_2(N)\rceil/2}<d$, intended to repel some dangerous ideas of using $p$, $q$ and/or $e$ crafted for low $d$, which otherwise would need to be expressed as the cumbersome $2^{\lceil\log_2(N)\rceil/2}<\big(d\bmod\lambda(N)\big)$.


In what paper was OCB2 introduced? I've been working through "Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality" 1 from earlier this year. My knowledge of OCB2 is pretty shallow though, and so I'm keen to study the scheme in depth before I continue.
From citations and searching around, it seems like OCB2 was introduced in a 2004 paper by Rogaway titled "Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC" 2.
There aren't any explicit mentions of OCB2 in this paper though. Section 10 is titled "The OCB1 Authenticated-Encryption Scheme" and includes a description of "OCB1 with an ideal tweakable blockcipher". The scheme described in that section matches what I have read about OCB2.
I suppose the scheme only started being called OCB2 after the publication of the paper? Is that correct? If not, where can I find a description of OCB2?

You are correct: OCB2 was only named so after the fact. Confusingly, it was named OCB1 in the original 2004 paper.
You can find the OCB2 naming on the paper that introduces OCB3, The Software Performance of Authenticated-Encryption Modes:

Integrated AE schemes were invented to improve performance of composed
ones, but it has not been clear if they do. In the only comparative
study to date [31], McGrew and Viega found that their composed scheme,
GCM, was about as fast as, and sometimes faster than, the integrated
scheme OCB [35] (hereinafter OCB1, to distinguish it from a subsequent
variant we’ll call OCB2 [34]).

Another instance of the name transitioning is in two papers of Minematsu. The first one, Improved Security Analysis of XEX and LRW Modes at SAC 2006, refers to the mode as the original OCB1; a later paper written in 2008, Generalization and Extension of XEX* Mode, already refers to it as OCB 2.0.
Finally, a patent filed by Rogaway in 2005 refers to the mode as OCB 2.0, which is presumably where the name change happened first.


Is there an algorithm to check if an elliptic curve is secure? As I understand it elliptic curves are of the form $y^2 = x^3 + ax + b$
Where $a$ and $b$ are the curve parameters. However not all parameters will give a curve suitable for crypto purposes. Is there a known algorithm that can evaluate a pair of numbers $(a,b)$ and return YES if they are valid ECC parameters. Is this algorithm deterministic or probabilistic ?

Let's suppose that you work in field $\mathbb{F}_p$ for a prime $p$; i.e. the $x$, $y$, $a$ and $b$ values are integers modulo $p$. The curve order $n$ is the number of points on the curve. By Hasse's theorem we know that $n$ is relatively close to $p$; namely, the theorem states that:
$$|n-(p+1)| \leq 2\sqrt{p}$$
So you get a range of possible values for $n$. The exact value depends on $a$ and $b$.

For cryptography, you normally need $n$ to be the multiple of a big enough prime. "Big enough" means $2b$ bits if you are after a "security level" of $b$ bits (i.e. resistance to attacks for a work factor of at least $2^b$). In practice, to make things simpler, you will want $n$ (the complete curve order) to be prime. So the algorithm you seek is roughly:

Compute the curve order. This uses Schoof's algorithm or a variant thereof. This yields $n$.
Check that $n$ is prime. If not, try again with new values for $a$ and/or $b$.
Do some extra checks.

The "extra checks" are about the MOV and FR attacks, which use pairings. This is a complex matter; to make the story short, there is a value called the embedding degree which is the smallest integer $k \geq 1$ such that $n$ divides $p^k-1$. Your curve will be safe if $k$ is high enough; it suffices that $k\geq 100$ (and that's with a wide error margin). In practice, with random $a$ and $b$, $k$ will be very high with overwhelming probability; however, testing all values $k$ from $1$ to $100$ is easy enough, so testing it is not a big issue. ANSI X9.62 recommends that test.

Schoof's algorithm (step 1) is deterministic. There are deterministic algorithms for primality, but usually we use Miller-Rabin, which is probabilistic but much more efficient. In any case, difference between deterministic and probabilistic has little practical relevance, because there is no computer which is really 100.0% reliable; a stray cosmic ray can still flip a transistor at the right time (or the wrong time, depending on your point of view). If you use Miller-Rabin with 50 iterations, you will get as much certainty of primality as you could ever get in the Physical World.

All of the above assumes that $a$ and $b$ are chosen randomly. Actually, $a$ can be fixed to some value (many standard curves use $a = p-3$, which yields a slight computational advantage in some implementations of point addition). If $a$ and $b$ are not chosen randomly, but with specific features, then you could obtain a weak(er) curve. Or you could loop forever; for instance, if you choose $a$ and $b$ such that the curve is a Montgomery curve, then $n$ is always a multiple of $4$, hence never a prime.

(See the Handbook of Elliptic and Hyperelliptic Curve Cryptography for details. The Guide to Elliptic Curve Cryptography is also a nice book; less complete but still full of information, and possibly clearer in its practical aspects.)


Make AES CBC more secure by destroying each block? Assume AES in CBC mode is used to encrypt an arbitrary file. The key and the IV are generated out of secure random data and are both different for each file and of proper length and strength. Then the key the IV are encrypted with RSA. Now the AES encrypted file will be transmitted via an insecure transport from the sender to the recipient. The RSA encrypted key and iv are also transmitted via an insecure transport. The recipient now decrypt the IV and key via it RSA private key and then decrypt the file with the key and IV. So far so good and pretty common. Assume further that authentication is not necessary and GCM mode is out of scope here.

The question is now: Does it add "more security" (or will it even be "less secure") to "destroy" the encrypted AES file by flipping a bit (or two) of each AES block and store information about the flips alongside with the key and IV in the RSA encrypted part (so that the recipient can decrypt properly)?

Background of the question is the idea that an attacker, who "sees" the AES encrypted file, needs maybe more time and computing power to run a brute force attack because even when he has the right key and IV the decryption would fail because the blocks are all invalid?

Or is this "security by obscurity", useless, even dangerous or just another kind of "self invented encryption" (which is typically a bad idea)?

Does it add "more security" [...] flipping a bit (or two) of each AES block and store information about the flips alongside with the key and IV in the RSA encrypted part (so that the recipient can decrypt properly)?

This would essentially be a stream cipher applied to the ciphertext, as a stream cipher encrypts by unpredictably deciding for each bit whether it should be flipped or not.

So this additional scheme can be seen as a custom stream cipher and will most likely add very little security beyond the existing encryption.

  Background of the question is the idea that an attacker, who "sees" the AES encrypted file, needs maybe more time and computing power to run a brute force attack because even when he has the right key and IV the decryption would fail because the blocks are all invalid?

CBC has no notion of "invalid decryption" (beyond padding errors) and so the adversary would have to decide based on the "deciphered" contents whether the decryption was ok or not.


Solve the congruence using Pohlig-Hellman algorithm Use the Pohlig-Hellman algorithm to compute a solution to:
$3^x\equiv 2 \pmod {65537}$

My attempt:

$p-1 = 65537-1 = 65536= 2^{16}$

$x= 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$
For $x_0$:
$2^{65536/2}=3^{(65536/2)x_0}$
$1 \pmod {65537} \equiv (-1)^{x_0} \pmod{65537}$
So $x_0 = 0$

Is this right? Because for all other steps after that, I get $0$'s for all $x_i$'s where $i=1,2,3,...,15$

Any help would be appreciated!

You are correct in the procedure.
You need to express $x$ as $x = 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$
Where the $x_i$ are in $GF(2)$

First compute:
$3^{(0*(p-1)/2)} \pmod p \equiv 1$
$3^{(1*(p-1)/2)} \pmod p \equiv 65536$

So that when you'll compute
$2^{65536/2^{i+1}} \pmod p$ you'll get either 1 (corresponding to $x_{i} = 0$) or 65536 (corresponding to $x_{i} = 1$)

For the first values of $i$ you will get only $x_i=0$, but then for $i=11$: $2^{65536/2^{12}} \pmod p\equiv 65536$ which corresponds to $x_{11}=1$

Then you need to proceed... but I just wanted to show that you don't get 0 for all $x_i$


How do you prevent the risk of damage to the security of Fully Homomorphic Encryption? In this paper on pg. 1248 in the "preprocessing phase" section the authors say:

  In the preprocessing phase, the parties run a (standard) MPC to
  collectively generate a key pair (pk,sk) for the FHE scheme, and to
  secret share sk in such a way that (a) learning the shares of
  corrupted parties, and leakage on each remaining share, does not
  damage the security of the FHE, but (b) collectively, the shares can
  be used to evaluate the decryption circuit in a leaky environment

Part (a) above makes me believe there is a risk with FHE security being damaged.  Is it possible to use another encryption scheme where this risk is mitigated ?

Part (a) above makes me believe there is a risk with FHE security being damaged. Is it possible to use another encryption scheme where this risk is mitigated ?

I'm not sure what you mean by that. In what way is security damaged? All ciphers risk security being damaged by leakage. For example if the key leaks, security is damaged.

I think what they are saying is, they distribute shares of the secret key to all parties. This needs to be done in such a way that even if all corrupted parties get together and reveal their shares to each other. And additionally reveal any leaked information they have gleaned during the protocol execution, the original secret key $sk$ cannot be reconstructed.

As a more concrete example, say we are using additive secret sharing. Assume some number of parties is corrupt (say $n/2$). Thus we assume the adversary knows all of those $n/2$ shares. But there are $n/2$ shares held by uncorrupt parties that are not known to the adversary. Assume, however, that some information about those shares is leaked (not sure what that info is, perhaps they say in the paper). They are saying that even given that information, the security of the FHE should not be damaged.


Most secure but feasible encryption running on WWII technology Imagine you are transported back to ~1940. What is the best (i.e. most secure, but technologically feasible) encryption you can think of for widespread (i.e. military) use? How would you implement it?

It depends on what you mean by widespread (military) use.  The Russian VIC cipher, which used a lagged Fibonacci generator, classified as a "straddling bipartite monoalphabetic substitution superenciphered by modified double transposition," as identified by the FBI in 1953, could have been applied to widespread military intelligence use, especially for HUMINT. After all, it was not broken until 1957--with the aid of a defector. It was used in World War II, and it clearly worked.

But for moving armies that use radio communications, a one-time-pad system that actually worked in practice would have been an excellent idea.  The German one-time pad GEE system was considered unbreakable, and had been in use for quite a while prior to its initial interception in 1934--used for diplomatic traffic from 1925--and continued to be heavily used in 1943, according to this declassified NSA document, but it suffered from weak key generation, according to this declassified NSA technical report. Its additive generator of wheels and switches had weaknesses which were brilliantly exploited by American analysts: the phases, cycles, potential overlaps, and limits of the keys became clear after exhaustive analysis of captured GEE one-time pads. So, the GEE system with a good TRNG, responsible cryptographic clerks, and cautious leaders, would have done the trick.

The other solution would have been to fix the weaknesses in Enigma, especially in its rotors and settings, modernize it-- see this paper by Ross Anderson-- and to improve the training of its operators, change key settings frequently, reduce predictable formatting, and not regard Enigma as an unbreakable magic box.  Weaknesses in how the settings were shared over the radio were pivotal to Enigma's downfall. Or we could continue with the Rasterschlüssel 44 (RS44), a grid-based, broken double transposition that was better, in practice, than Enigma. Even so, we could tweak the RS44 and make some improvements.

Implementation is very important, as your question suggests. Procedures such as message formatting need to be emphasized.  Again, weaknesses in the training of cryptographic clerks helped speed the exploitation and downfall of both GEE and Enigma--as did overconfidence, even hubris, among the leadership.

Perhaps even more important was a failure to understand some of the underlying principles of information security, the work that would soon be done by Claude Shannon.

One could implement everything according to the principles of information theory that we now know.

Edit:  We should also include the Schlüsselgerät 41 (SG41), which was a rotor cipher machine similar to the Enigma--but better.  It had six rotors that could move irregularly--forwards and backwards--and it was intended to replace the Enigma.

Traffic from the SG41 was almost never broken by Bletchley Park.  But due to its weight (about 30 lbs; see one here) from a lack of light metal building materials, relatively few were made and then put into service (about 1500 were created in total).  From the viewpoint of the frontline soldier, heavy is bad.

Both the Germans (SG41) and the Allies (SIGABA) had rotor-based encryption that worked well when used properly.  Some of that equipment could have been improved for service--it was definitely good enough for the time.


How should I store passwords that need to be available in plain text? Suppose I need to store login information for a third-party website for a few users, how would I go about doing it?

Since I am logging into a third party website, I need the password in plain-text, not hashed. And no, the website in question does not provide any API.

In addition, the server I am using is accessible to people whose credentials are stored on it, so they will be able to get at least one plaintext/ciphertext pair, namely their own.

Given these two conditions, is there any way of storing user credentials on the server, or should I just ask for them each time the user logs in?

You could encrypt them using some key derived from the user's password (to your site).

Of course, this assumes that you get your user's passwords in plain text (or in any form which is always the same) - thus you need to have an encrypted connection to your user. Do not allow any non-SSL login.

You can use some key derivation function like PBKDF or bcrypt to derive the encryption key from the password (if this uses a salt, make sure the salt is not the same as you are using for your password checking). You could additionally use some server-secret here, but if your say that some potential attackers have (read-)access to the server anyway, this will not really increase security.

Then encrypt/decrypt the stored login information for the third party website using a standard symmetrical encryption algorithm like AES.

Of course, you also should use an encrypted connection to this third-party website.


breaking fully homomorphic encryption schemes Fully homomorphic encryption schemes allow one to evaluate any arbitrary computation over encrypted data. Intuitively this seems to be too weak, irrespective of how we achieve this.

An adversary who has access to the cipher text only could do variety of operations. For example, duplicates in the cipher text could be found easily. No separate trapdoors are required apart from Public Key. Variety of further operations could be performed on the given corpus of cipher text, so identifying prefixes, suffixes etc. among the cipher words by simply running their respective circuits.

Also with additional information like if an adversary could guess if the column in the encrypted database is an integer. He can do operations like $<$ or $>$ among the encrypted values to further deduce interesting information.

Is this true with homomorphic schemes ? or am i missing some thing ?

Even though all the operations you described can be performed homomorphically, the result remains encrypted, i.e., the attacker cannot "see" it.  So homomorphic computation is not useful (on its own) as an attack, because the results remain unknown to the attacker.

For example, given two ciphertexts $c, c'$, an attacker can homomorphically compute whether they encrypt the same message.  The result is a ciphertext $c''$ that is an encryption of either 1 ("same message") or 0 ("different messages").  But the attacker cannot decrypt $c''$, so the 0/1 answer remains hidden to him.


Large Volumes of Asymmetric Encryption First of all, I apologize in advance if I use any incorrect terminology. I am just getting my feet wet when it comes to cryptography and there is a lot to learn.

For the past 12 months, we have been developing an application infrastructure for a Cloud and Mobile Application (iOS/Android). As part of the infrastructure, we require the ability to encrypt $\text{SHA-}256$ hashes using asymmetric encryption and in some cases, encrypt multiple hashes at one time. A non-decryptable digital signature is not sufficient for our requirements. The simple explanation for this is, the digital signatures we have been using thus far, allows anyone with a corresponding public key, to review the contents to ensure they align with corresponding data in the database row. Ownership of the row of data cannot be transferred or duplicate rows created, without the correct signature. Rows have a signature and an owner and two digital signatures validating the product serial number is valid and that the declared owner, does, in fact, own the serial number.

We have built a working prototype that was built on top of our existing framework, which uses PostgreSQL and PHP and preliminary testing using $\text{SHA-}256$ and RSA 2048 has yielded the results of being able to encrypt and insert/update 10,000 unique rows of data every 40 seconds. When inserting 10,000 rows of data, there are 10,000 unique digital signatures that have to be created. The bulk of the work is in creating these digital signatures.

We are wondering what the best way to speed this up is? Ultimately, we need to be able to drastically reduce this time and it would be ideal if we could get 10,000 rows signed and inserted in under 5 seconds.

Is there a faster solution for signing digital signatures with a private key? We have discussed writing this component in C#. We are also wondering if Bitcoin mining hardware (ASIC) could be used for asymmetric encryption? If not mining hardware, would GPU based processing be better? Acquiring specialized hardware, should improve the processing time, which is not a problem.

We eventually need to generate in excess of 1 billion digital signatures per month. Any guidance or help would be greatly appreciated.

EDIT: I forgot to mention we are using OpenSSL with our current prototype.

I would explore the GPU option before spending money on specialized hardware.

I have done something similar using CUDA where I was doing many ECC operations in parallel. The GPU was about 30x - 50x faster than the CPU.

You could probably hash the data on the CPU and then use the GPU for the RSA exponentiation.


Security of a signature scheme based on both factoring and discrete logarithms I have seen this paper: A New Signature Scheme Based on Multiple Hard Number Theoretic Problems by Ismail and Tahat:

  In this paper, we propose a new signature scheme based on two hard number theoretic problems, factoring and discrete logarithms.

It seems that it is a dramatically more secure signature scheme.
Looking for thoughts/insights as to how useful/safe it actually is.

Although I can't see any immediate weaknesses, I also don't see how it adds significant value over DSA (while being significantly slower).

It claims to be based on two hard problems, discrete log and factoring. However, it doesn't give any particular proof that if you could forge signatures, you can solve both problems.  It also doesn't look particularly likely; if you can solve the problem of finding a value $K$ where $K^K = x \bmod p$ (for a fixed $x$), you can forge (by selecting a random $\nu$, computing $x = g^{\nu^e}y^{h(M)^2}$ and then solving for $K$), and it would appear unlikely that this problem would be reducible to the discrete log or the factorization problem.

In addition, while it is true that discrete log and factoring are different problems, they are related.  The paper claims that "it is very unlikely that factoring and discrete logarithms can be efficiently solved simultaneously", however it is not actually that implausible that an advance would solve both.  For example, a dramatic speedup of the Number Field Sieve may solve both (as that algorithm can be modified to work against both problems).  Alternatively, if someone builds a Quantum Computer, well, both problems are then solved.

In addition, their algorithm doesn't appear to run nearly as quickly as DSA (which is not a particularly efficient signature algorithm).  Here's why: their algorithm can be viewed as a DSA variant, except that they work in a composite subgroup (rather than the prime subgroup that DSA works in).  Here's the rub: their subgroup must necessarily be large (as it must be hard to factor their subgroup; otherwise one of the problems they're relying on is easy).  So, instead of having a 256 bit subgroup (which we may work with DSA), they need to work in a 2048 bit subgroup.  Because the time taken to compute, say, $K^K$ is proportional to the size of the subgroup, their scheme would take 8 times longer than DSA.

Also, at points their algorithm description is a bit goofy.  Take their signature generation algorithm; it would appear that the three steps they have listed could be summarized as $\nu = (Kr - xh(M)^2)^d$.  This alternative formulation would better than halve the time (as you don't have to compute a modular square root, and we do one modular exponentiation step; they do it twice); and you don't have to worry what to do if $Kr$ happens not to be a quadratic residue.  The only reason I can think of to use their formulation would be to add some sort of side channel resistance; however if you're concerned with that, well, there's got to be a cheaper way.


Understanding Diffie-Hellman - Choosing a bad g I am taking a class on Cryptology, and I'm having a hard time understanding the potential pitfalls of Diffie-Hellman. Specifically, the professor gave the following problem:

  Alice and Bob want to use Diffie-Hellman for key agreement and choose
  p = 982734982635928741927391824619283719654192837198273923771,
  however, they do not know how to calculate a relative prime, and hire
  Evan (Eve in disguise) to generate one for them. Evan gives them g =
  584451952932889263219289637911613296416146180021897568955.

  Explain what Evan did, and how this makes it easy for him to find the
  secret key that Alice and Bob agreed to, and find that secret key.

I understand that the value of choosing a g that has a large sub group of possible keys (i.e. you wouldn't want to choose g = 1, because then all keys would be = 1, no matter the other numbers) but I'm not understanding how that would impact this case with such a large g. Could anybody explain how I'd go about this question?

There are two tricks that Evan could have played in selecting the $g$:

She could have selected a $g$ that has a small order; that is, $g^x$ could take on a small number of possible values.
She could have selected a $g$ that has a large but smooth order; that is, $g^x$ could take on a number of possible values, but that total number is a product of small primes.

Here's why Evan could take advantage of this second point: if the order $g$ has a prime factor $r$, then given $g^x$, it's possible to determine $x \bmod r$ in $O(\sqrt{r})$ time.  Hence, if the order of $g$ consists only of small factors, then Eve can compute $x \bmod r$ for all the small prime factors, and from that, reconstruct $x$.

In either case, the question is: what's the order of the value $g$ that Evan picked?  Well, one important thing that helps us determine that value; the order is always a factor of $p-1$.  So, the very first step is factoring $p-1$.  Then, you can go through all the prime factors of $p-1$, and use this fact: if $r$ is a factor of $p-1$, the order of $g$ is a multiple of $r$ if $g^{(p-1)/r} \ne 1$.  That should let you determine the order of $g$ without a huge amount of pain.


What are the consequences if someone finds the accessible 1600-bit block $X$ and $R$-bit block $V$ such that $\text{Keccak-}f[1600](X \oplus V) = X$? Let $H$ denote any hash function based on the sponge construction. Let $F$ denote its underlying function that transforms the $L$-bit state (for SHA-3, $F = \text{Keccak-}f[1600]$ ). Let $R$ denote the bitrate.

Note that the padded message $M$ has the following form:

$$\text{pad}(M) = B_1 \mathbin\Vert B_2 \mathbin\Vert \ldots \mathbin\Vert B_{N-1} \mathbin\Vert B_N,$$

where $B_i$ denote $R$-bit blocks.

Consider the possibility that there exists some $L$-bit block $X$ and $R$-bit block $V$ such that $F(X \oplus V) = X$ (obviously, assuming that the xoring takes place in the same position where the padded message blocks are xored into the state). Moreover, there exists some sequence of $R$-bit blocks $$S = B_1 \mathbin\Vert B_2 \mathbin\Vert \ldots B_{Y-1} \mathbin\Vert B_Y$$ that lead to the state $X$. Doesn’t this mean that if someone knows $S$ and $V$, it would be very easy to choose any suitable sequence of $nR$ bits (where $n$ is any natural number greater than 0), denote it by $T$ and generate arbitrarily many different messages such that
$$\begin{array}{l}
{\text{pad}(M_1)} = S\mathbin\Vert T,\\
{\text{pad}(M_2)} = S \mathbin\Vert V \mathbin\Vert T,\\
{\text{pad}(M_3)} = S \mathbin\Vert V \mathbin\Vert V \mathbin\Vert T,\\
{\text{pad}(M_4)} = S \mathbin\Vert V \mathbin\Vert V \mathbin\Vert V \mathbin\Vert T,\\
\ldots?
\end{array}$$

But this means that $H(\text{pad}(M_i))$ is always the same for any $i$. What are practical consequences for $H$ if someone manages to find such a combination of $S$ and $V$, and then publishes it immediately (so that this combination is in open access for everyone)? That is, what practical applications (use cases) of $H$ will be impacted?

Then you've found a collision in SHA-3, and you get a prize.

There is a choice of prizes:

You could get your name on a virtual piece of paper that makes a lot of people excited and causes exceptionally insufferably tedious debates on Hacker News.
You could get a large number of unmarked bills in small denominations and possibly an unwanted piece of lead in your head by selling the collision on the black market.
You could get the fruit of exploiting the collision in real-world applications, with a lot more effort, and who has time for that kind of effort anyway?


Would a non-envelop, prefix only, SHA2 built MAC be susceptible to key recovery attacks? When aiming to build a MAC, classic literature discusses the use of Envelopes or key "Sandwich" to build MACs. These were proved to be as secure as HMAC in “Sandwich” Is Indeed Secure: How to Authenticate a Message with Just One Hashing by Yasuda. In these Envelopes, a key (K) is prepended to the padded message (M) and then another key is appended afterward (K). We can describe the MAC construction as $\operatorname{MAC}=H(K\mathbin\|M\mathbin\|K)$.

As Yasuda explains, the key after the message is added in order to avoid length extension attacks on the MAC. It is also important to keep the appended key in its own hash block in order to avoid attacks such as the one described in On the security of two MAC Algorithms by Preneel and Oorschot.

Now, what I haven't found in recent papers is any security analysis on the security (or lack of) of MAC algorithms such as the ones described by Yasuda in his paper as "prefix". In other words, I'm trying to find how secure MAC=H(K||M) nowadays is and which are the tradeoffs of using such algorithms beyond the danger posed by length extension attacks.

More explicitly, I'm currently trying to find out if a "prefix" MAC building algorithm that would use SHA2 as its hashing algorithm would be susceptible to key recovery attacks. Let's suppose that this algorithm makes use of SHA2-256 and generates a MAC over 2 blocks containing a key, data, and padding. The blocks would look like this:

Block1 (Secret key 32 bytes || 32 bytes of message data that can be influenced by an attacker))

Block2 (64 bytes of message data & padding).

As far as I can see attacks such as the one discovered by Preneel & Oorschot will only work for keys whose value lies between two hashing blocks, so I'm trying to find other methods of key recovery attack that would be relevant for "prefix" MAC building algorithms.
I'm assuming that any number of MACs and message data can be gathered by an attacker but considering that the key can only be recovered through cryptoanalysis.

None of these constructions will lead to key recovery unless the underlying hash function is spectacularly broken in the sense of preimage resistance, which pretty much none of them are (archived).

But key recovery is not usually what's directly relevant to your application.  If you're using one of these constructions as a MAC, for example, what's relevant to your application is forgery—and while key recovery is one path to forgery, it's not the only path to forgery.  In MAC applications, length extension is fatal: it is trivial to forge MACs under $m \mapsto \operatorname{SHA256}(k \mathbin\| m)$.

These days, it's all an academic concern, because:

the world has settled on using HMAC to get a PRF out of SHA-256 so it's ubiquitous and ready at hand essentially everywhere,
there are much cheaper MACs like GHASH and Poly1305 built into authenticated ciphers like AES-GCM and crypto_secretbox_xsalsa20, and
SHA-3 and BLAKE2 natively provide keyed variants anyway with PRF security so you don't need to construct your own—and making the prefix construction secure was an explicit design criterion for the SHA-3 competition if you really still want to use it.