Key space vs Cardinality of 1024-bit RSA I have been trying to figure out the encryption key space, and cardinality of 1024-bit RSA. From my understanding, the key generated from 1024-bit will be primes greater than $2^{1023}$ but less than $2^{1024}$. So, there are approximately $8\times10^{307}$ types of keys that can be used.

Is this the key space or the cardinality, and how do you distinguish the two from RSA ?

Definitions

In RSA, an encryption key is a pair of integers $(N,e)$ with $N$ the product of $m\ge2$ distinct odds secret primes $r_i$ (with $0<i\le m$), and $e$ is such that $\gcd(e,\lambda(N))=1$ where $\lambda(N)=\operatorname{lcm}(r_1-1,\dots,r_m-1)$ is the Carmichael function. It follows that $e$ is odd. Typically, other conditions are added, like $e\ge 3$ (because $e=1$ gives no security), or that each of the $r_i$ is large for some definition of that (because small $r_i$ can be easily found from $N$, and then are no longer secret). Other conditions are commonly added, and discussed later in this answer.

The most natural definition of encryption key space is the set of pairs $(N,e)$ matching the applicable conditions defined in a particular variant of RSA. The cardinality of the encryption key space is the number of elements in that set if it is finite, else the cardinality is $\aleph_0$ (the cardinality of $\mathbb N$ and all countable sets).

Strictly speaking, by the definition above, the cardinality of the encryption key space of 1024-bit RSA is $\aleph_0$, because we put no upper limit on $e$.

Counting classes of equivalent encryption keys

Different encryption keys $(N,e)$ and $(N',e')$ can be equivalent; that is encryption with $(N',e')$ (including with random padding, which is necessary to make RSA encryption secure) can always be reversed by using a decryption key $(N,d)$ corresponding to $(N,e)$. This occurs when one of the following holds:

$N=N'$ and $e\equiv e'\pmod{\lambda(N)}$;
for degenerate keys $e\equiv1\pmod{\lambda(N)}$, $e'\equiv1\pmod{\lambda(N')}$, and the bitsize of $N$ and $N'$ such that padding remains compatible; with the two common PKCS#1 paddings, that's when $\lceil\log_2(N)/8\rceil=\lceil\log_2(N')/8\rceil$.

We can thus use an alternate definition of encryption key space where we assimilate equivalent encryption keys (technically: by considering an element of the set as being an equivalence class of the equivalence relation among $(N,e)$ pairs that we just defined).

Now, for $k$-bit $N$

there are $2^{k-2}$ odd $k$-bit integers, thus no more possible $N$;
for each $N$ we have exactly $\varphi(\lambda(N))$ equivalence classes of encryption keys (where $\varphi$ is the Euler totient function), thus less than $N/4$.

There are thus less than $3\cdot2^{2k-6}$ equivalence classes of $k$-bit encryption keys, about $2^{2043.6}$. This bound could be slightly improved with a better estimate of $\varphi(\lambda(N))$, and removing those $N$ that are either prime or not square-free.

Conditions commonly added to RSA keys

$m=2$ (that is $N$ product of two primes, as in the original RSA paper); this is also mandated by FIPS 186-4. In that case, customarily, we note $p=r_1$ and $q=r_2$.
$\lceil\log_2N\rceil=k$ for $k$ in some limited set, that is $N$ has an exactly prescribed bit length (because that's good for interoperability); FIPS 186-4 mandates $k\in\{1024,2048,3072\}$, with $k=1024$ deprecated.
Bounds on individual primes $r_i$, such as $2^{(k-1)/m}<r_i<2^{k/m}$ (this insures condition 2 for any choice of the $r_i$; helps interoperability of private keys in CRT format; and gives protection against some factorization algorithms). FIPS 186-4 mandates that.
$e\ge e_\text{min}$. Typical values are:

$e_\text{min}=3$ (because that's the fastest secure value of $e$ for RSA using good padding); that's mandated by PKCS#1.
$e_\text{min}=2^{16}+1$ (because that's less insecure than $e=3$ when insecure padding is used, and other debatable reasons); FIPS 186-4 mandates that.

$e\le e_\text{max}$. Typical values are:

$e_\text{max}=e_\text{min}$, which fixes $e$, simplifying things.
$e_\text{max}=2^{16}+1$ (this is the most common $e$ around, and I know no reason to use a larger one).
$e_\text{max}=2^{2^l}-1$ with $l\in\{5,6,7,8\}$, because that puts an end to using ludicrously large $e$ that waste time, energy, and memory. FIPS 186-4 mandates it with $l=8$.
$e_\text{max}=N-1$; that's mandated by PKCS#1. Notice that with this definition, there are always equivalent keys.

Each $r_i-1$ and each $r_i+1$ is known to have a large prime factor, for some definition of large. The rationale is to render some simple factorization algorithms hopeless, and for moderate $\max(\log_2r_i)$ without such requirement it could make sense for an adversary to attempt using these algorithms on each one of a great many $N$, rather than using equivalent effort trying to factor a single $N$ using better algorithms. When $k=1024$, FIPS 186-4 mandates this, with large defined as $>2^{101}$; when $k=2048$ (resp. $k=3072$) this becomes an optional requirement, and large becomes $>2^{141}$ (resp. $>2^{171}$).
For $m=2$, it is common to require that $|p-q|>\Delta$. The only benefits are a simple counterargument to someone pretending that Fermat factorization can factor $N$, and catching a few of the many things that can go wrong in an implementation. FIPS 186-4 sets $\Delta=2^{k/2-100}$.
In addition to condition 6, there might be some upper bound on how large the largest (known) prime factors of $r_i-1$ and $r_i+1$ are. Refer to FIPS 186-4 which has several options in this regard.
In addition to the requirement that each $r_i-1$ has a large prime factor $u$, it has been recommended that $u-1$ has a large prime factor; see this question.
One of many particular key generation algorithm might be specified/used, which will put arbitrary constraints on the $r_i$. For example, algorithm B.3.4 of FIPS 186-4 specifies a deterministic algorithm to generate $N$ from a random seed of exactly $security\_strength$ bits, which (by reference to NIST SP 800-57) must be $80$ (resp. $112$, $128$) when $k=1024$ (resp. $2048$, $3072$).

Evaluating cardinality for a common set of requirements

As example I'll use $m=2$ (cond. 1), $k=1024$ (cond. 2), $a<p<b$ and $a<q<b$ with $a=2^{(k-1)/2}=2^{511.5}$ and $b=2^{k/2}=2^{512}$ (cond. 3), $e=3$ (cond. 4 and 5).

The density of primes near a large $x$ is about $1/\log(x)$, it varies little for $a<x<b$, thus the number of primes in range $]a\dots b[$ is about $t=(b-a)/\log({a+b\over2})\approx2^{501.8}$. Of these, a proportion of about $e-1\over e$ can be used given the requirement $\gcd(e,\lambda(N))=1$. Given that $p\cdot q=q\cdot p$, the cardinality is thus about $(t{e-1\over e})^2/2\approx2^{1001.3}$.

Different key generation requirements can yield vastly different cardinality. For example, the cardinality for 1024-bit RSA with fixed $e$ using algorithm B.3.4 of FIPS 186-4 (see req. 10) is at most $2^{80}$ (and close to that if the seed can take all possible values).


Why do all hash functions use big-endian data? I've looked at several hash function specifications, and they all emphasize the need for big-endian byte ordering. Is there a reason for this that has to do with security, or is it simply convention?

Probably you just looked at the SHA-family of cryptographic hash functions as others (like MD5 and the RIPEMD-family use little endian (see for example this table for the compression functions).

The emphasis on a certain byte ordering is purely functional and not relevant for security (see my 2nd comment to your question).


ElGamal proxy re-encryption I wrote an algorithm to implement a suggestion in a paper by Ivan and Dodis to convert a regular ElGamal encryption scheme into a proxy re-encryption one (it's at page 6, left column of this but I asked a question related to it on SO where you can see the maths quicker).

The part I'm referring to is this one.

$$\frac{mg^{xr}}{g^{rx_1}}=\frac{mg^{(x_1+x_2)r}}{g^{rx_1}}=\frac{mg^{(x_1)r}mg^{(x_2)r}}{g^{rx_1}}=mg^{(x_2)r}$$

The scheme works by splitting a private key $x$ into $x_1$ and $x_2$.

My question is: if I don't want to share my private key with someone, could I split it in $x_1$ and $x_2$, decrypt part of it using $x_1$, share that encrypted text with someone as well as $x_2$ (probably encrypted under their public key) and have them decrypt it? How easy would it be for them to figure out the whole private key given that information and how could that threat be diminished (if it could at all)?

Disclaimer: The use cases for proxy re-encryption are very specific. From your description it is not clear to me why you don't just encrypt the message with a different key for your someone.

Looking at the scheme it seems to me that someone only gets $x_2$ and cannot use that to learn anything about $x_1$. Even given multiple pairs $x = x_1^{(i)} + x_2^{(i)}$; if only the $x_2^{(i)}$ are known any $x'$ could be the correct key for $x_1^{(i)} = x' - x_2^{(i)}$.


Break El-Gamal Algorithm by knowing the value of the random k In El-Gamal Algorithm, the public key is $(p, g, A)$, and the secret key is $(a)$, in order to encrypt some data, the sender generate a random $k$, where:
$(C_1, C_2) = (m.A^{k} \pmod{p}, g^{k} \pmod{p})$
If a hacker know the value of $k$, should this break the algorithm security ?

Yes, this does break the security for that particular message.  If the attacker somehow recovers the value $k$, he can recover the message $m$ by computing $m = C_1 \cdot A^{-k} \pmod{p}$ (where $A^{-k}$ is the multiplicative inverse of $A^k$; one way it can be computed is by $A^{-k} = A^{p-1-k}$)


How to prevent Public Key from being replaced entirely? I am using RSA to sign my license file using Microsoft CNG API. I am signing the license file and sending the file with the public key to the end user.

Now I have a problem, what if someone's signs the license file content with entirely new set of private\public key pair. Then they can easily replace my public key with their own key and the license file with the one signed by new corresponding private key. Is their some guideline I am missing? Also Can it be prevented If I store the Public key in a certificate store?

Also Can it be prevented If I store the Public key in a certificate store?

Well, an adversary could probably just overwrite that entry and mount the same attack as before.

  Now I have a problem, what if someone's signs the license file content with entirely new set of private\public key pair.

What you have stumbled across is the "trust problem" of public key infrastructures (PKIs). Namely that you need a binding between a public key and an entity.

In this case you want a binding between your public key and your identity as the software vendor. The simplest solution would be "pin" the public key (eg the SHA256 hash of it) in the verifying program so that it only accepts the public key / signature pair if the hash matches.  Of course this could be patched out of the software by an adversary wanting to elide the license check, but so could be the check altogether (DRM is hard)...

  It would be really get if you could add a few more lines on "pin" the
  public key part.

The idea of pinning is the same as is used for trusted root CAs in browser. You keep a copy of the public key you trust in your software package. Then when verifying the signature, you check whether the received public key matches (any of) the stored, "pinned" public key. If it does you proceed with verification otherwise you immediately return with an invalid signature error. If binary size is a concern you can also hash the incoming public key and compare the hash against a hard-coded hash.

In theory you could also pin a public key of your own "CA" and force all signatures to present a certificate signed by that CA, but it seems like the simple pinning of the data-signing public key should suffice and the additional scalability in number of keys is not needed.


Authenticating Very Short (Sub-Block) Data If I'm encrypting very short/small data - like an int or a long (32 or 64 bits), does it make any sense to authenticate the ciphertext, when using an "online" mode of operation (like EAX)?

Essentially, guessing the plain text would (assuming no weaknesses in either the encryption or the authentication) be easier than forging the authentication tag if the plain text is shorter than the block size of the cipher - or equally hard if truncating the tag to the same length as the data when using EAX.

Are there any scenarios in which tags longer than the data would be useful? (Or are there any actual research results on this?)

Does any of this change if the key with which the individual ints are encrypted changes?

First, the fact that the data is "easy" to guess (in the sense that an attacker has a one-in-2^32 or a one-in-2^64 chance of guessing correctly) doesn't mean much if the attacker has no way of checking if his guess is correct. Or at least, it's not a problem with the cryptography.

Second, even if he does have that ability, the problem of protecting your data's secrecy is separate from the problem of protecting its authenticity. For example, it might be bad if an attacker can deduce that a message says "Yes", but it might be even worse if he can then tamper with the message so it now says "No".

In this example, the message itself was effectively only one bit long, but it definitely would make sense to have a long (e.g., 128 bit) authentication tag!

To answer your final question: No. As long as each key is random, then periodically changing your key is not a problem. In fact, in many situations it's recommended in order to limit how much data gets compromised if an attacker manages to obtain the current key.


Is it possible to demonstrate that md5(x) != x for any x? I am looking for an easy to follow explanation, if possible, that demonstrates/proves the validity (or not!) of this assertion:

for any X, md5(X) != X   (being X any string of 32 hex characters)

It is not known whether there is a fixed point or not. Since MD5 gives you 128 bits, you would need an input of 128 bits as well. That is you are really considering a function from the set of 128-bit strings to 128-bit strings. Assume that such a function is chosen at random. Then we can calculate the probability that the function has a fixed point. The answer is stated in this answer: https://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x. To unpack just a bit more:

Say you have any of the $2^{128}$ possible inputs. Then the probability that this is a fixed point is $(1/2)^{128}$ since, for example, the first bit would have to map to the first bit and so on. So the probability that the input is not a fixed point is $1 - (1/2)^{128}$. So the probability that no input will be a fixed point is

$(1 - (1/2)^{128})^{(2^{128})}$

because there are $2^{128}$ possible input.

The probability that there is a fixed point is therefore $1 - (1 - (1/2)^{128})^{(2^{128})}$. If you calculate this probability you get approximately 63.21 %.

So it is actually likely that there is a fixed point for MD5 or any other hash function for that matter.

Note that this doesn't prove that there is a fixed point, but it just says something about the likelihood.

The only way to demonstrate/prove whether or not there is a fixed point would be to compute all hashes of all 128 bit strings and compare them to the output.  But, as notes in the comments above, this is not very practical.


Encrypting many small messages (log-lines) What would be the best way of encrypting small mesasages to be stored in encrypted form? (This sounds like somthing a textbook would cover, but I haven't found any references).

Let's say I have many systems producing messages (log-lines) which I would like to transfer and store centrally in a secure manner. Using off-the-shelf products I could secure the transfer and storing of these messages independently, but I would like to investigate another approach: encrypting each message at the sendig system with the public key of the reciever, so that the messages can be stored as-is, and thus provide end-to-end encryption from the sender down to the storage medium.

First some definitions:

RSA(PublicKey, Message) means: RSA-encrypt Message with the given Key
AES(Key, IV, Message) means: AES-encrypt Message in CBC-mode with the given Key and IV
Message = gzip(plaintext)

I have come up with the following options:

I can encrypt each message with RSA:

Ciphertext = RSA(PublicKey, Message)

However, this would fail of the message is too long.

Or I could create a random AES-key for each message (and also use this as IV):

Key = Random()
EncryptedSessionKey = RSA(PublicKey, Key)
Ciphertext =EncryptedSessionKey, AES(Key, EncryptedSessionKey, Message)

However, RSA-computation is heavy and I probably cannot afford to do this for every message.  Thus, I can re-use the key for, say, 100 messages and do:

Key = Random() (re-key every 100 messages)
EncryptedSessionKey = RSA(PublicKey, Key)
IV = Random() (new IV for each message)
Ciphertext = EncryptedSessionKey, AES(Key, IV, Message)

The last one seems to be both secure and efficient. However, I really don't want to invent a system like this myself. Is there any best practices, research or textbook-examples I should look into?

Ok, answering myself then, trying to summarize all the good input from above.

First of all, this design will provide confidenciality to each log message, but it will not:

ensure the integrity of the log as a whole, it will be possible to insert or remove log-entries unnoticed
authenticate the sender of log-messages, a rouge client or a man-in-the-middle could insert fake log-messages

However, if this is OK (or you have other ways of solving these issues), this scenario is probably secure.

As for performance, on my machine I get the following numbers:

Just RSA: just below 4000 messages pr second
RSA and AES with a new key each time: just above 4K msg/sec
RSA and AES with a new key each 10 messages: 17 K msg/sec
RSA and AES with a new key each 100 messages: 25K msg/sec

Just RSA seems to have no advantage over RSA+AES, and there is an upper limit to message size.

Now, this just encrypts the same string over and over. For a more real-life test I will make new strings (serialized xml) and write these to disk, to se if the difference is still significant.

As for the use of gzip, I have tried a 218-byte xml-message which gzipped into 164 bytes (25% reduction in size). This is a relevant testcase in my scenario, but of course your milage may vary.

Edit: I have re-tested with different values for key-size and exponent. All of these are using RSA to encrypt an 128-bit AES session key, with a new key for each message (I guess in effect I am measuring the throughput of RSA-encryption of 128-bit random numbers).

keysize=1024 bits, $e = 2^1+1$: 7 tx/millisecond
keysize=1024 bits, $e = 2^{16}+1$: 10 tx/millisecond
keysize=2048 bits, $e = 2^1+1$: 11 tx/millisecond
keysize=2048 bits, $e = 2^{16}+1$: 4 tx/millisecond

This is using the default crypto-provider in java 7. I let each configuration run 20 iterations before starting the measurement to "warm up" the jit-compiler.

My environment:

java.vm.version: 23.7-b01
java.vm.vendor: Oracle Corporation
java.vm.name: Java HotSpot(TM) 64-Bit Server VM
file.encoding.pkg: sun.io
java.runtime.version: 1.7.0_15-b03
os.arch: amd64
os.name: Windows 7
sun.management.compiler: HotSpot 64-Bit Tiered Compilers
os.version: 6.1
sun.arch.data.model: 64


How does SSL secure the initial handshake? I'm reading the SSL specs, and it seems that the initial handshake has no authenticity protection at all. What is to prevent, say, an attacker from overwriting the "available ciphers" list with one that is full of broken, or even null, ciphers? Is there some sort of defense for this, or is this fundamentally unsolvable because the handshake part by definition cannot itself be authenticated (which leads to infinite regress)? Is there a way to anonymously authenticate the initial, non-authenticated part of an SSL connection?

The cornerstone of the handshake security is that the Finished messages, sent under the protection of the newly exchanged key (for encryption and MAC), contain hash values computed over all the handshake messages exchanged so far, including the list of cipher suites and all other parameters. As long as client and server don't negotiate the use of a cipher suite which can be broken instantaneously, these Finished messages reliably detect foul play.


In 2020, SHA-1 practically broken in chosen-prefix collision (CP-collision). Can double SHA-1 hashing prevent CP-collision? In a recent study SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust by Gaëtan Leurent and Thomas Peyrin. 2020, they showed the first practical chosen-prefix collision attack that required two months of computations using 900 Nvidia GTX 1060 GPUs.

Chosen-prefix collision (CP- collision)1: two message prefixes $P$ and $P'$  are first given as challenge to the adversary, and his goal is to compute two messages $M$ and $M'$ such that $H(P \mathbin\| M) = H(P' \mathbin\| M')$ where $\mathbin\|$ denotes concatenation.

They worked for two kinds of attacks;

They reduced the use of neutral bits BCJ+05 and boomerangs JP07 from $2^{64.7}$ to $2^{61.2}$
Also, they improved graph-based technique (LP19) to compute CP-collision from $2^{67.1}$ to $2^{63.4}$.

Actually, the CP-collision attack enables attackers to create some meaningful messages; however, classical collisions are not.
To demonstrate the attack they achieved a PGP/GnuPG impersonation (CVE-2019-14855).
The list of attacks on SHA-1

2005, collision with complexity $2^{69}$, Finding collisions in the full SHA-1, Wang et. al.
2013, chosen-prefix collision with complexity $2^{77.1}$, New collision attacks on SHA-1 based on optimal joint local-collision analysis, Stevens et. al.
2013, collision with complexity $2^{64.7}$, from the previous article.
2016, free-start collision with complexity $2^{57.5}$, Freestart collision for full SHA-1. Stevens et. al.
2017, collision with complexity $2^{63.1}$, The first collision for full SHA-1., Steven et. al.
2019, chosen-prefix collision with $2^{67.1}$ complexity, From collisions to chosen-prefix collisions, Leurent et.al.
application to full SHA-1
2020, collision with $2^{61.2}$ complexity, SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust, Leurent et. al. (The new article)
2020, chosen-prefix collision with  $2^{63.4}$ complexity, same paper above.

Questions:

Can a double hashing $h= \operatorname{SHA-1}(\operatorname{SHA-1}(m))$ mitigate the CP-collision?* It seems so, since the meaningful part will not exist for attackers as longs as they are not able to break double $\operatorname{SHA-1}$. This seems not feasible, yet.
An immediate follow-up question; if the answer is yes, should we design the new protocols based on double hashing?

*There can be many variants of double hashing.

a. No such double hashing doesn't do a bit of good. Anything which collides after a single hash will definetly collide after a double hash. It preserves all collisions and adds new ones.

We might consider other constructions which may provide some strength e.g $H(H(m) || m)$ however:

b. We have no need for any such double hashing of SHA1 as we have newer better hash functions. Most notably we have SHA3 which is by all accounts far from being broken


Would this prevent FNV1a 32 bit hash collision? I am considering the FNV1a 32 bit hash as part of a simple software security and authentication system. I am aware that FNV1a is NOT ideal but it may suit my needs.

I am aware that FNV1a has rather poor collision behavior, but I would like to know if it may be implemented in such a way as to minimize problems. Assuming pass-phrases are hashed in their entirety multiple inputs may have the same output, but what if each character of a pass-phrase is hashed and the hashes are concatenated in a string?

I suppose my questions is, is collision less likely for individual characters than for strings?

First of all, "Is collision less likely for individual characters than for strings?"

The answer to this is yes. In fact, experimentally verifying shows that for 8-bit ASCII characters the collision chance with FNV1a is 0. This is however not an impressive feat, seeing that the output is 4 times as large as the input.

However, using this you no longer have a hashing function in the traditional sense. Each character gets replaced by simple substitution table, and becomes 4 times as long.

As for security, this is useless. This is a simple unkeyed substitution cipher which can be broken by either statistical analysis within minutes, a good eyeball or even one chosen plaintext. This scheme doesn't follow Kerckhoffs's principle, which is also very bad.


How to use RCON In Key Expansion of 128 Bit Advanced Encryption Standard I have a question about RCON

here is my illustration...

this is the 128 bit key..

[2b] [28] [ab] [09]
[7e] [ae] [f7] [cf]
[15] [d2] [15] [4f]
[16] [a6] [88] [3c]

and then I will get this..

[09]
[cf]
[4f]
[3c]

and then I will put down the first 8bit(1byte) where it is the 09:

[cf]
[4f]
[3c]
[09]

after that I will change their value according to s-box..

[8a]
[84]
[eb]
[01]

and then I will xor that substituted 32 bit value to

[2b]        [8a]        [01]
[7e]  XOR   [84]  XOR   [00] <--- that is a RCON(4)
[15]        [eb]        [00]
[16]        [01]        [00]

My question is: How will I determine the RCON that I will use? Or will I only used this one?

[01]
[00] <--- that is a RCON(4)
[00]
[00]

But why?

The Rijndael/AES key schedule uses (for every some steps, depending on the key size) a non-linear function (I called it $f_i$ in my schematic image in a related answer) on a 32-bit column:

This function $f_i$ (note that $i$ starts with $1$ here) does the following steps:

substitute each byte, using the AES S-box.
rotate the whole column by one byte "down" (these two steps can be swapped around without effect)
XOR in the round constant $RCON[i] = [x^{i-1}, \mathtt{00}, \mathtt{00}, \mathtt{00} ]$. The values $x^{i-1}$ are to be computed in the same representation of $GF(2^8)$ as used in all other operations in AES (see at the end on how to do this), but you can also take them from a table in the Wikipedia article, or from the examples in Appendix A of the AES standard.

As you see, $RCON[i]$ consists mainly of zeros, the only effective part is in the first byte. This means, this step only modifies the first byte of the column, the others are unaffected.

So, in your example, you have this column 3 of the original key:

[09]
[cf]
[4f]
[3c]

Now we rotate this by one:

[cf]
[4f]
[3c]
[09]

Now we put this through the AES S-box (component wise):

[8a]
[84]
[eb]
[01]

And now the round step: This is round 1, thus we need $RCON[1] = [\mathtt{01}, \mathtt{00}, \mathtt{00}, \mathtt{00}]$:

[8a ⊕ 01]   [8b]
[84 ⊕ 00] = [84]
[eb ⊕ 00]   [eb]
[01 ⊕ 00]   [01]

This was $f_1$, and we'll now XOR this result with column 0 of the original key to obtain column 4 of the expanded key:

[8b ⊕ 2b]   [a0]
[84 ⊕ 7e] = [fa]
[eb ⊕ 15]   [fe]
[01 ⊕ 16]   [17]

After three more simple XOR steps to get column 5-7 we would then apply $f_2$ (which uses $RCON[ 2] = [\mathtt{02},\mathtt{00}, \mathtt{00}, \mathtt{00}]$) on column 7 and XOR the result with column 4 to get column 8, and so on.

The Rcon-array on Wikipedia contains the precomputed constants $x^{i-1}$ for $i$ from $0$ to $255$, so you would put $RCON[i] = [\mathtt{Rcon[i]}, \mathtt{00}, \mathtt{00}, \mathtt{00}]$. For AES-128, you only need the RCONs from $1$ to $10$ (as you need 44 columns of round key material), and here are these as a table (in hexadecimal form, as all constants in code font here):

   i        1     2     3     4     5     6     7     8     9    10
--------------------------------------------------------------------
          [01]  [02]  [04]  [08]  [10]  [20]  [40]  [80]  [1b]  [36]
RCON[i]   [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]
          [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]
          [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]

For AES-192 and AES-256 you need even less of these round constants, so putting all 255 of them in Wikipedia is a bit superfluous. Even for Rijndael-256-128 (i.e. 256-bit blocks and 128-bit keys) we would need only $(14+1)·8/4-1 = 29$ of these.

As mentioned by fgrieu in a comment, you can also calculate the $\mathtt{Rcon[i]}$ on the fly, as each of them is obtained from the previous by an doubling in $GF(2^8)$, which in the representation used in Rijndael is just a left-shift followed with a conditional XOR with a constant. In C-like syntax (using a twos-complement representation like every usual computer nowadays) this looks like this:

rcon = (rcon<<1) ^ (0x11b & -(rcon>>7));

An explanation: (rcon<<1) is the pure doubling (multiplication by $x$ in $\mathbb{Z}_2[x]$). rcon >> 7 is the first bit of rcon, i.e. either $\mathtt{0}$ or $\mathtt{1}$. -(rcon>>7) then is $\mathtt{0}$ or -1 (= $\mathtt{f...ff}$, i.e. all bits set). Thus (0x11b & -(rcon>>7)) is either $\mathtt{0}$ or $\mathtt{11b}$, and XORing with this just is reduction modulo the Rijndael polynomial $x^8 + x^4 + x^3 + x + 1$.

The same doubling operation is used in the MixColumns-step of the actual encryption operation, so you need to implement it anyways.


a homomorphic operation on Paillier encryption Assume  $N=pq$, where $p$ and $q$ are two strong prime numbers.

Also, assume we have  finite field $\mathbb{F}_u$ where $u$ is a $112$ bit prime number. Let $r_i$ be a uniformly random element of $\mathbb{F}_u$.

Let $(r_i)^{-1}$ be multiplicative inverse of $r_i$ in ring $Z_N$.

We encrypt a message as $c=E(r\cdot m)$ using Paillier encryption.

Question 1: Given $c$ and $(r_i)^{-1}$, can we "always" perform $c^{(r_i)^{-1}}=E((r_i)^{-1}\cdot (r_i)\cdot m)$ such that its  decryption value only contain $m$?

Question 2: given $E(m)$,  how can we chose its additive inverse $m'$ such that $E(m).E(m')=E(m+m')$ so its decryption value would be 0? should $m'\in \mathtt{Z}_N$ or $m'\in \mathtt{Z}_N{^2}$

Question 1: Given $c$ and $(r_i)^{-1}$, can we "always" perform $c^{(r_i)^{-1}}=E((r_i)^{-1}\cdot (r_i)\cdot m)$ such that its
  decryption value only contain $m$?

Yes. You can multiply arbitrary values $x$ into a message using paillier encryption and it will result in multiplication $\bmod n$ and thus you'd get $m$ back.

This would happen by  exponentiating the cipher text with the $x$, as $c^x\bmod {n^2}$ as you described.

  Question 2: given $E(m)$,  how can we chose its additive inverse $m'$ such that $E(m).E(m')=E(m+m')$ so its decryption value would be
  0? should $m'\in \mathtt{Z}_N$ or $m'\in \mathtt{Z}_N{^2}$

I don't think there's any way given a ciphertext of $m$ to construct a plaintext $m'$ that would yield $m+m'=0$ as this would trivially equal a plaintext recovery and thus a (nearly) total break of the encryption.

However, you can use the answer from question one to calculate the additive inverse ciphertext, which would be $c^{n-1}\bmod{n^2}$. If you multiply this with the original cipher text, you will get an encryption of $0$, to which you can add whatever you want (e.g. an encryption of 1?).

Alternatively you might as well just exponentiate the ciphertext with $0$ to get the same result...


ccrypt and its security I would like to know how secure is ccrypt to encrypt files (like images, videos and other non-plain text data) using single password of 20+ chars length.

It uses Rijndael with 256-bit block size and 256-bit key size.

Is there any better alternative to encrypt files of this kind or is it secure enough?

The following is an analysis of the CCrypt protocol described here. Note that this breakdown of ccrypt mostly focuses on possible weaknesses that may also be present in other protocols.

Key derivation

ccrypt does not apply a well known Password Based Key Derivation function. As no salt is applied rainbow tables can be constructed (although the generated keys must still be validated against the ciphertext by at least a single Rijndael decrypt).

Dictionary attacks are made easy as no work factor or iteration count is used by the protocol; CCrypt even contains code to perform a targeted search for passwords that are close to a given password. Initial verification of the resulting key can be performed against the magic after the IV is decrypted with the resulting $R$. That said, the resulting key is well randomized using all available characters, even if the protocol is relatively unorthodox.

Nonce & IV generation

The file encryption does not contain an authentication tag. Therefore anybody can create bogus messages. Messages may be swapped as well to fool the user into decrypting the wrong message. You just need a copy of the IV for an existing ciphertext for this. Non-authenticated encryption can be OK for providing confidentiality for stored ciphertext, as long as the user is aware of it. In general it is hard to protect against an adversary swapping ciphertext, even if integrity protection and authentication is added to the ciphertext. A warning with regard to the lack of integrity protection and authentication is included in the description of ccrypt.

The nonce is not fully random. If the input for the nonce generation can be made identical (mainly time-of-day in seconds & microseconds, process ID and count should be relatively easy to repeat) then an identical key stream will be generated for identical passwords. In that case high amounts of information about the plaintext could be retrieved by XOR-ing multiple ciphertext against each other (at least for initial block and possibly blocks of ciphertext). The lack of a secure random number generator on many platforms has been indicated as the reason for this design choice.

Password validation

There is an almost negligible chance of $1\over{2^{32}}$ (because the magic is 32 bits) that the wrong password is accepted to decrypt a ciphertext. This could however be exploited by an attacker claiming to have a correct password for a file.

Cipher usage

CCrypt uses it's own C source code for the Rijndael implementation, although it seems directly derived from the C code for the NIST competition. It is unknown if this implementation is secure against side channel attacks. It doesn't matter as much as CCrypt is mainly used to encrypt files locally.

Full block CFB is used as mode of operation. This is known to be a secure mode. An IV is generated and the highest block size and key size are used. So there are likely no big issues with how the Rijndael cipher is deployed.

Password security

As with any scheme to perform PBE (Password Based Encryption) the security of ccrypt is highly dependent on the quality of your password. A disadvantage of a scheme that only relies on symmetric encryption primitives is that you need to supply your password both for encryption and for decryption. For OpenPGP you would only require your password to unlock the private key during decryption.

Conclusion

In conclusion the key derivation scheme and the nonce generation are not standardized and leave something to be desired. The password is however hashed in such a way that it is unlikely that any entropy in it is lost. Rijndael - not AES - is deployed correctly so the protocol seems secure. The project only has one author as this time, but Peter seems to be responding to requests.

It would be advisable to make sure that nobody else is logged in when encrypting / decrypting your data as the implementation does not seem to be tested against side channel attacks. Furthermore, as the documentation indicates, you should not assume this protocol offers integrity protection or authentication of the plain- and ciphertext.


Checking if point is on EC twist Given a short Weierstrass elliptic curve $C$ over $F_p$ and a point $(x, y)$, it is easy to verify that $(x, y)$ either satisfies the curve equation (on-curve) or does not (off-curve).

In the case that it is off-curve, is there an efficient way to test if $(x, y)$ is on a quadratic twist of the curve? I can easily generate domain parameters $a, b$ of a twisted curve $C'$, but unless I have the correct coefficients, $(x, y)$ might not satisfy that particular curve equation $C'$ even though $(x, y)$ are on a twist of $C$.

Let $E$ be an elliptic curve over $\mathbf F_p$ given by the equation $y^2 = x^3 + Ax + B$. Then a quadratic twist $E'$ of $E$ is given by the equation $\beta y^2 = x^3 + Ax + B$ where $\beta$ is not a square.

Now you have a point $(x_0, y_0)$ you suppose is not on $E'$. Then to make it on a twist, you need to find $\beta$ such that $\beta {y_0}^2 = {x_0}^3 + Ax_0 + B$. If $\beta$ is not a square, then you found a quadratic twist of the curve with $(x_0, y_0)$ belonging on it.

Now, if you want $E'$ to have a short Weierstrass form, you can instead look for a non-square $\beta$ such that the following equation is satisfied:
\begin{equation}
\beta^3({y_0}^2 - {x_0}^3) - \beta Ax - B = 0.
\end{equation}
Then, $E'$ is given by the equation $y^2 = x^3 + A'x + B'$ where $A'=\frac{A}{\beta^2}$ and $B'=\frac{B}{\beta^3}$.

Example

Let $E$ the elliptic curve of equation $y^2 = x^3 - 3x + 60$ over the field $\mathbf F_{101}$ and the point $P=(5,17)$ that is not on the curve.

We will try to find the short Weierstrass equation of the twist $E'$ where $P$ lies on it.

We take the above equation and solve for $\beta$:
\begin{equation}
\beta^3 ({y_0}^2 - {x_0}^3) + 3 \beta x_0 - 60 = 0.
\end{equation}
With our favourite computer algebra software, we find $\beta = 67$. Then the equation of $E'$ is
\begin{equation}
y^2 = x^3 + 74x + 97.
\end{equation}

Let's check everything:

sage: p = 101
sage: E = EllipticCurve(GF(p), [-3, 60])
sage: q = E.cardinality()
sage: q
113
sage: x_0, y_0 = 5, 17
sage: E.is_on_curve(x_0,y_0)
False
sage: R.<X> = GF(p)[]
sage: f = X^3*(y_0^2 - x_0^3) + 3*X*x_0 - 60
sage: f.roots()
[(67, 1)]
sage: F(67).is_square()
False
sage: EE = EllipticCurve(GF(p), [-3/beta^2,60/beta^3])
sage: qq = EE.cardinality()
sage: qq
91
sage: sage: EE.is_on_curve(x_0,y_0)
True
sage: q + qq == 2*(p + 1)
True

The last instructions check the relation between the cardinality of $E$ and its quadratic twist.

Final remark.

This shows how to construct a specific quadratic twist having a specific point, but if you do this with another random point, not on $E$, then it might not be on the previously constructed twist $E'$.


Difference between collision resistance and target collision resistance For a hash function, what's the difference between Collision Resistance and Target Collision Resistance?.

I understand the definition of hash function collision resistance, but I don't know about Target Collision Resistance.

Pre-image resistant but not 2nd pre-image resistant? describes the relationship between the three basic hash function security notions: Collision Resistance, Second Preimage Resistance and Preimage Resistance.

In short, Collision Resistance implies Second Preimage Resistance (but not vice-versa) - there is a good diagram on page 4 of RogawayShrimpton04 that illustrates the relationships.

The notion of Target Collision Resistance (which was introduced in BellareRogaway97) is a type of Second Preimage Resistance, and is implied by Collision Resistance.

More formally, Target Collision Resistance describes the ability of an adversary to find a second preimage for a fixed message (compared to the more general notion of Second Preimage Resistance, where the adversary to find a second preimage for a randomly chosen message).

These notions actually sound really similar (and probably in practice are) if you think about real world hash functions, but make more sense when you consider the security notions (and proofs of them) use keyed hash functions - in TCR, the adversary tries to find second preimages for a fixed message over multiple experiments with random keys, while in general 2PIR the message and the key are random in every experiment.


KRACK - Is all-zero key installed by the acces point? I don't really understand (and I think it's not described in the official paper) how the encryption can work when the encryption key is set to 0 by a KRACK attack on a device using wpa_supplicant 2.4 or 2.5.

Does the access point have to install this all-zero key? how to force this installation?

No, only one side installs the all-zero key. Which side depends on the mode being attacked (the client in standard 4WHS, the server in FT). Generally, the KRACK attack allows the adversary to replay, decrypt, or forge packets in a specific communication direction.

Let's focus on the standard 4WHS here, as that corresponds to the case of your question.
Here, the client will install the all-zero key, while the AP will install the correct (and unknown to the adversary) encryption key derived from the 4WHS.
Thus, the adversary will be able to decrypt messages going from the client to the AP, but not the other way around. It will also be able to replay and forge messages towards the client (but not the AP).


challenge response for RSA I've got a homework question asking to explain challenge-response in reference to RSA encryption and signatures. There really doesnt seem to be much or any explanations online. can anyone help me out.

Basic Idea: For simplicity, assume the server $S$ is trusted.

Then all the server has to do is to prove that it has the private key $(n,d)$ corresponding to its public key $(n,e)$ which is trusted, say, via a PKI.

The client uniformly generates a random value $X \in Z_n,$ keeps it private, and then encrypts it into $$Y=X^e ~(mod~n)$$ and sends $Y$ to the server. The server
obtains $$Z=Y^d~(mod~n)=X^{ed}~(mod~n)$$ and sends $Y$ back to the client.

By the uniqueness of inverses modulo $\varphi(n)$ we know that $$ed\equiv 1~(mod~\varphi(n))$$ if and only if the private key is correct. Thus all the client needs to do is to check that $Z$ equals the original $X$ it had generated.

I have used plain RSA with no randomisation or encapsulation. There are many wrinkles if we want to protect against replay attacks, etc., but your question sounds like a basic question.

Edit: (Thanks to @fgrieu) copied for completeness of answer, hope he/she doesn't mind.

  In challenge/response, the answer's server is more generally known as
  prover; and the answer's client as verifier. The question also hints
  at using RSA signature for that: verifier generates and sends random
  $X;$ prover signs it as $Y=X^d~(mod~n)$ and sends signature $Y$;
  verifier computes $Z=Y^e~(mod~n)$ and verifies that $Z=X.$ The
  answer's method given above uses encryption, with the advantage that $X$
  is not known to attackers and can be used to derive a shared secret
  key. But the signature method allows $Z$ to carry information that the
  prover has signed.


Is it OK to substitute a PRF for a random oracle? Random oracles don't exist, but aren't PRFs essentially indistinguishable from them? So why can't we substitute pseudorandom functions wherever we use random oracles?

And if we can do this, why is there any controversy over substituting hash functions for random oracles, when we can instead use pseudorandom functions which do exist and are practically the same as random oracles?

Yes, when we're instantiating some crypto primitive that says 'insert Random Oracle here', we will in practice insert a PRF.

Now, you ask, why is that even slightly controversal?  Well, there are known constructions that are secure with a Random Oracle, but not secure with any specific PRF, see this paper for an example.  This has been taken by some as proof that the Random Oracle model ought not be trusted at all (as proof within that model need not apply in the real world).

On the other side of the argument, other people have pointed out that these constructions are highly artificial, and that attempts to avoid the Random Oracle model has resulted in worse security at times; see this paper to see this argument spelled out.


How to encrypt a short plain text? I want to encrypt a short plain text (i.e., 30bit), and the requirement is that length of cipher text is the same as the short plain text.

It seems that stream encryption methods like CFB-8 satisfies my requirement. My question is that

What is the cracking time of CFB-8 in brute-force-attack? Does the cracking time only depend on the key length?
Does the length of plain text influence the cracking time? if so, what's the relationship?
Are there any better methods for my requirement?

Do you need to reuse the key for multiple messages without any way to distinguish the role of each message, e.g. by a message sequence number, or file position for a collection of records in a single file?

If you have some short identifier that is never reused between each role, or if you need encrypt only a single message with each key, then you can pick your favorite stream cipher, say ChaCha or AES-CTR, with the message role (sequence number, file position, etc.) as the nonce, and just chop the first 30 bits off the stream.

If you must reuse the key for many messages with no way to distinguish the role of each message, then you need format-preserving encryption.


Formally, what is AES? AES is supposed to be a symmetric key block cipher. The theoretical counterpart to this is a pseudorandom permutation.
I'd like to say that AES is a PRP (well, supposedly at least), but that doesn't seem correct; while there are larger variants of AES, I don't see how the algorithm extends to arbitrarily large security parameters.
How do I view AES theoretically?

Applied cryptographers often see one of the three variants of AES, say AES-256, as a function:
$$\begin{align}E:\ \{0,1\}^{256}\times\{0,1\}^{128}&\to\{0,1\}^{128}\\ (k,p)\quad &\mapsto c=E(k,p)\end{align}$$
such that:

for all $k\in\{0,1\}^{256}$, encryption with key $k$ defined as follows
$$\begin{align}E_k:\ \{0,1\}^{128}&\to\{0,1\}^{128}\\ p\quad &\mapsto c=E_k(p)\underset{\text{def}}=E(k,p)\end{align}$$
is injective, surjective, and bijective (the three are equivalent for any function over a finite set), that is a permutation of $\{0,1\}^{128}$
there's an efficient encryption algorithm computing $E_k(p)$ from $k$ and $p$
there's an efficient decryption algorithm computing $p$ with $c=E_k(p)$ from $k$ and $c$ (note: not quite as efficient, but close).
it is practically impossible to distinguish a challenger/oracle implementing these algorithms with a fixed unknown value of the key $k$ chosen at random, from an oracle implementing a random permutation and its inverse.

Note: Condition 4 is only good for keys chosen independently at random, which is the main design criteria for AES. It's not applicable to related-key attacks or the ideal cipher model.
Note: The quantitative security-oriented cryptographer compares the advantage of a distinguisher succeeding at 4 to that of a generic attack requiring the same work and trying keys in sequence, and to a no-nonsense threshold.

The more theoretical-oriented cryptographers want to formally define "efficient" and "practically impossible". They do so by stating that the algorithms involved are in the class of polynomial-time algorithms; and using the notion of negligible probability. But these require a "security parameter" that goes to $+\infty$ as the input of a polynomial, and AES is only defined for $|k|\in\{128,192,256\}$ and $|p|=128$, which are bounded.
To solve that, we can use that AES is formally defined as a restriction of Rijndael, and section 12.1 of that observes:

The  key  schedule  supports  any  key  length  that  is  a  multiple  of  4  bytes. (…) The cipher structure lends itself for any block length that is a multiple of 4 bytes, with a minimum of 16 bytes.

That section also tells how many rounds there should be, and how ShiftRow can be extended for 128, 192 and 256-bit block, that we can further extend.
For parameter $n\ge128$, we can take block size $|p|=32\,N_b=32\,\lfloor n/32\rfloor$ and key size $|k|=32\,N_k=32\,(N_b-3+(n\bmod 32))$, with $N_r=N_k+6$ rounds. We are back to a standard framework where algorithms are written for arbitrarily high security parameter $n$, fed as input to polynomial-time algorithms as a bitstring of $n$ bits, conventionally at 1. When $n=131$ (resp. $n=133$ and $n=135$) we get AES-128 (resp. AES-192 and AES-256). For $n=128$, we get a 128-bit cipher with a toy-sized 32-bit key.
But I do not know any security analysis of AES that cares to do something remotely similar and study attack on large $n$. This shows the gap between theory and practice!
Note: There would be other ways to make AES a family of block ciphers indexed by a security parameter. In particular, we could define variants working for more granular values of $|k|$ and $|p|$, and working in $\mathbb F(2^j)$ for $j$ variable, rather than $j=8$ as in AES; and/or tweak the $32=4\, j$ to another multiple of $j$. However that matches AES even less than the above, which is somewhat supported by a document referenced in appendix D of the formal definition of AES.


Is there a specification for the "BEGIN RSA PRIVATE KEY" format? Until now I didn't find a specification (RFC or similar) for the file format that uses the BEGIN RSA PRIVATE KEY prefix and END RSA PRIVATE KEY suffix. Where is it defined? Is there an official name for it? It seems to be at least related to the series of PEM RFCs.

I am looking for reference information about the details of whitespace handling,
base64 details, joining of different keys in one file etc..

This question is NOT about the ASN encoding of the payload.

I'm here, because, I'm asking myself the same question as the OP.

PKCS#1 (RFC 3447) defines the ASN.1 structure: RSAPrivateKey, permitting the
expression of an RSA private key only.

PKCS#8 (RFC 5208) defines the ASN.1 structure: PrivateKeyInfo, permitting the
expression of any private key. (For an RSA private key, PrivateKeyInfo is some
packaging information, and a reuse of RSAPrivateKey from PKCS#1).

PEM (Privacy Enhanced Mail), is a defunct method for secure email. But, its
container format was borrowed for packaging cryptographic items.

RFC 7468 (Introduction): "For reasons that basically boil down to non-coordination or inattention, many
PKIX, PKCS, and CMS libraries implement a textbased encoding that is similar to
-- but not identical with -- PEM encoding."

Which reads as: Um, folk have decided to use bits of PEM to package thier
crypto files. Here we have a jolly good effort to try and formalise that...

Alas, RFC 7468 clarifies the PKCS#8/PrivateKeyInfo packaging as "BEGIN PRIVATE
KEY". But not the packaging of PKCS#1/RSAPrivateKey as "BEGIN RSA
PRIVATE KEY".

The "BEGIN RSA PRIVATE KEY" packaging is sometimes called: "SSLeay format" or
"traditional format" for private key. Which, as least, gives us a name for this
format, but, like yourself, I cannot find, and would welcome, something that
approaches a formal description of this format. I suspect this does not exist.


Difference between Verification and Public Key for Signature Schemes This is a semantics Question. Typically, in many asymmetric schemes, for this question specifically, digital signatures, we see that designers describe the key given to the verifier as Public Key.

However, in some contexts, specially identity based games, I would imagine the key used for verification should remain secret. Say anonymous credentials and some challenge response constructions.

My question is the following:

Should I always call the key used for verification "public key" even on those settings?
Is it ok to call it verification key on those settings instead?
I have seen some recent work, for example, on multivariate, lattice based and post quantum stuff in general, call it more and more verification key. They then assume is public, is it something that is coming to fore or there is a difference of meaning between the 2 terms?

Should I always call the key used for verification "public key" even on those settings?

Usually it is a public key, or at least it is called that in the key pair generation procedure of the cryptosystem that is used. Public key is in that case a more generic term - it may not be decided for what the key will be used after all.  Similarly, cryptographic API's will often have a specific class that performs the key pair generation, so in that case the more generic term "public key" is likely to be used.

  Is it ok to call it verification key on those settings instead?

Sure, and I've seen many cases where the shorthand SK and VK are used for "Signature generation Key" (or just "Signing Key") and "Verification Key". I'd probably prefer it because it is more precise; I guess there is no judge out there that decides these things for us.

Beware that SK is also often used for "Secret Key" which is kinda-OK, because private / signing keys are of course secret by definition.

  I have seen more work say on multivariate, lattice based and post quantum in general stuff call it more and more verification key they assume is public, is it something that is coming to fore or there is a difference of meaning between the 2 terms?

Yes, it is about usage. Many things are still based on RSA where you can also use a public key for encryption. In that case calling it a verification key doesn't make sense. I think that for signature generation / verification specific keys the term "verification key" makes perfect sense, especially if in that scheme the key is not public.

As an aside: beware that in many schemes it is possible to derive the public key from data such as signatures. There is nothing in the definition of signature generation that prevents that. Moreover, for many schemes you can directly calculate the public key from the private key, so you cannot swap the terms whenever you like to do so.

In short, don't assume that you can keep the verification key a (shared) secret; you'll need proof for that.


Is this a correctly formatted PGP session key packet? RFC 4880 may be full of information, but it can be incredibly vague at times, so im looking for someone who actually knows the answer to this.

Given this public key:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: BCPG v1.39

mQGiBE5B0h8RBAD533Z5bK1IpBx02QyQL0QoJE4uFRIMGDiwXuwmZzVl+R7Vlurd
GRLsCCbE6vOOh7XQVZGzLEBy9WNzZ9m+EbCfSVAYkjS6FhLws6hG6irrnS+b3JBf
gFJ8vNGF9Z7bhx+7y7NBk0IMyWkGnUkcnav73t5FQUI2faEBN4c/yAGJZwCgjcB7
3akWk9XVWvTCsiMXxpyvkukEALXsvB6cOoFEtQq9cQHjP63fBlvD94dhhMiM0cH6
hW9JotxdK+cxFGG9ZIWgoN2PWbMJka/H4W5EL6tS+YiNAR7I1Ozkt6X16GjnQUzZ
MlSpleK+KiKVN2anRaPEoOIinHrE3ZXd6QlJ/4+OJn4IVWmSEaJpFf4QNgvEu4rh
xinyBAD2RNzREOA+wpnFZ4lDt9NZXmXdxQME/l0J9XcvWhpGsxA/MATQKImy7N49
7GT/M38F+TrpBobag1O3buE99fOLyws4Tbc+sZMdHxoiGZDAIRNQS2rv475E6ktj
7vd5CYvOkA6+8sX1+hPcNlkHtHB1OFkJRsYp6k0zkyC9adjBM7QTYWJjIDxtYWtj
bUBhYWEuY29tPohGBBMRAgAGBQJOQdIfAAoJEDBSJUXPd92GRSQAoItbtbToOg7a
/hcg2sA/aBEQNwuxAKCGR69vmSoCWoBP5waPk0UsjM3BSbjMBE5B0h8QAgCUlP7A
lfO4XuKGVCs4NvyBpd0KA0m0wjndOHRNSIz44x24vLfTO0GrueWjPMqRRLHO8zLJ
S/BXO/BHo6ypjN87Af0VPV1hcq20MEW2iujh3hBwthNwBWhtKdPXOndJGZaB7lsh
LJuWv9z6WyDNXj/SBEiV1gnPm0ELeg8Syhy5pCjMAf9QHehP2eCFqfEwTAnaOlA6
CU+rYHKPZaI9NUwCA7qD2d93/l08/+ZtFvejZW1RWrJ8qfLDRtlPgRzigoF/CXbR
iEYEGBECAAYFAk5B0h8ACgkQMFIlRc933YZRrACfUnWTjHHN+QsEEoJrwRvFmvzj
bR4An24pTpeeN+I6R59O/sdmYsAhjULX
=sStS
-----END PGP PUBLIC KEY BLOCK-----

Can someone verify that the information below is correctly formatted?

Everything here is in hex. I might be missing a few 0s from the front of some values

Tag 1 version(3) + 8 octet keyid + PKA(0x10 = ElGamal): 03f940c4301a67779d10

Session key: b51ba8901efd091d2afcd26b560ea8899d9e2ddbf6aa5c4edea8292704f2fcfc
Checksum: 1092

EME_PKCS1_ENCODE(m): 0002c121793811f4f32f3f739b087f91e77491a0317342c45c6935a80009b51ba8901efd091d2afcd26b560ea8899d9e2ddbf6aa5c4edea8292704f2fcfc1092

k: 5f02cec2fd1f880f390f17dce824c3682015da7ea97c0053cfcdc5097d33fc263e42eeda5c9196a626fa90501a4f7a975061e9f9889f851fcb26e9c24538221e

g^k mod p: 01ff7672e5cc57aaa14b3fda05dee02ecede8a75eecb813060224c390e48f38d3bd41031c9d4659bfaa36246af145930a48d8b5dc5618b4506fb55f6347d5bddffc0

m * y^k mod p: 01ff45f15b84e8e7b95dfef0b52acea10aef4c20b3fc9b8f7c6f2487b2e43b8bfaf5ddebaeddc05643c348eb785559fa7dd74f7542b44ace3746d829fbf1f6392a53

This is a partial block created with only the data from above.

-----BEGIN PGP MESSAGE-----
Version:

wY4D+UDEMBpnd50QAf92cuXMV6qhSz/aBd7gLs7einXuy4EwYCJMOQ5I84071BAx
ydRlm/qjYkavFFkwpI2LXcVhi0UG+1X2NH1b3f/AAf9F8VuE6Oe5Xf7wtSrOoQrv
TCCz/JuPfG8kh7LkO4v69d3rrt3AVkPDSOt4VVn6fddPdUK0Ss43Rtgp+/H2OSpT
=YcRE
-----END PGP MESSAGE-----

is the packet correctly formatted? is the PKCS1 encoded data correct? Simply because pgpdump can read the packet doesnt mean its formatted correctly.

Anyone?

Here's what pgpdump thinks of it:

New: Public-Key Encrypted Session Key Packet(tag 1)(142 bytes)
        New version(3)
        Key ID - 0xF940C4301A67779D
        Pub alg - ElGamal Encrypt-Only(pub 16)
        ElGamal g^k mod p(511 bits) - ...
        ElGamal m * y^k mod p(511 bits) - ...
                -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02

So there's nothing obviously wrong, but you'd have to pass it through a full PGP implementation to verify that it's all OK.


32bit AES equals to 8bit AES? I am looking into an article about 32bit CPU/MCU software implementation of AES and there are some weird changes over there.
Like shift-rows.
It seems that the shift-rows in the 32bit implementation is shift columns instead.

So my guess is that the 32bit implementation returns different output than the 8bit implementation (the original).

Can you correct me ? or at least explain why it is still equal ?

The article : "Efficient Software Implementation of AES on
32-Bit Platforms"

So my guess is that the 32bit implementation returns different output than the 8bit implementation (the original).
  Can you correct me ? or at least explain why it is still equal ?

Of course, it's equal.  The AES function (for a specific plaintext, key) is well defined; and if you generate any other result, you're not doing AES correctly.

Of course, while processing, the implementation may decide to lay things out in a different order than what you might naively expect; as long as it generates the same final output, all is well (and, in fact, that is what they did)

  It seems that the shift rows in the 32bit implementation is shift columns instead.

No, in their implementation, they decided to lay the 4x4 matrix in memory so that a 32 bit value contains the 4 bytes in a specific row (and not a column).  That is, the matrix is 'transposed' compared to the representation you would normally expect.  This means that a 'shift row' operation involves rotate operations within the individual 32 bit values (or three of them; the top one remains unchanged), and that the 'mix columns' operation involves logical operations over all 4 32 bit row values.

They did that because doing that made things somewhat more efficient for them than the alternative ordering.  As long as they handle the plaintext->matrix, the matrix->ciphertext operations correctly, and the transpose the key schedule bytes appropriately, everything works precisely as expected.  At every point, the bytes in their transposed state are precisely the same model as the corresponding bytes in the (nontransposed) AES state.


Why does the Node crypto library do Diffie Hellman this way? I was sifting through the Node Crytpo library and I came across their Diffie Hellman utility class. Their class implements a generateKeys function that, in their words,

  Generates private and public Diffie-Hellman key values, and returns
  the public key in the specified encoding

My understanding of Diffie Hellman is that both parties only ever need to generate a single random number, not a public/private key. I suppose that you could call this random number a public key and that's what this function returns, but where does a private key come into this process?

I know that in Station to Station protocol a public/private key pair is used for signing. Is that what is happening here? Could this class be used for Station to Station protocol as is?

My understanding of Diffie Hellman is that both parties only ever need to generate a single random number, not a public/private key.

That is not correct.

Wikipedia’s entry covers it pretty well. Once two parties have agreed upon a domain (the (g, p) pair) each member generates their own private key. Their shared secret is equal to

(g ^ (a * b)) % p

where a is Alice’s private key and b is Bob’s. Of course, each side can do this calculation without the other party revealing their private key.


Question regarding reconstruction vector in LSSS Suppose we have a policy $A \wedge ( D \vee (B \wedge C))$ with attributes ${\{A,B,C,D}\}$. The set of subsets of attributes which satisfy this policy is ${\{{\{A,D}\},{\{A,B,C}\},{\{A,B,D}\},{\{A,C,D}\}}\}$ of which ${\{{\{A,D}\},{\{A,B,C}\}}\}$ is the set of minimal subsets.

We convert the above boolean formula into a LSSS matrix $L = {\{{\{1,1,0}\},{\{0,-1,1}\},{\{0,0,-1}\},{\{0,-1,0}\}}\}$ according to this(Pg. No 30).

I have a question regarding the yellow marked line taken from this(Page No. 7).

$\textbf{Is the resulting 0 a vector in $w \cdot M_i$ ? Is the first entry of the vector $w$ -1? }$
$\textbf{How do one go on to calculate this $w$?}$. It will be helpful if anyone can explain using the above LSSS matrix above and the unauthorized subset ${\{A,B}\}$.

For the tl;dr see the last few paragraphs.

LSSS Background

The construction of linear secret sharing you are referring to is based on the model of computation known as Monotone Span Programs.  Other papers  go into more detail and should help with further questions.

The paper that has given rise to your question is a proposed method to construct an LSSS from a given Boolean formula (equivalently, from an access structure).  For now, we will assume their method is correct and the derivation of the LSSS matrix is as they describe:

$\begin{array}{c}
  A \\
  B \\
  C \\
  D
  \end{array}
  \begin{pmatrix}
  1 & 1 & 0 \\
  0 & -1 & 1 \\
  0 & 0 & -1 \\
  0 & -1 & 0
  \end{pmatrix}$

We will denote this matrix by $M$ and assume we are working in a field $\mathbb{F}$.  For a dealer to share a secret $s \in \mathbb{F}$ in this scheme, he does the following:

Select any vector $\mathbf{x}\in \mathbb{F}^3$ such that $\langle \mathbf{x}, (1,0,0) \rangle = s$ (i.e. the inner product with the target vector is the secret);
Compute $\mathbf{y} := M\cdot \mathbf{x}$;
Give $\mathbf{y}[i]$ (the $i^{\text{th}}$ component of $\mathbf{y}$) to the party assigned the corresponding row of the matrix $M$.  So in this case, e.g. party $C$ will receive the third component of $\mathbf{y}$.

Now assuming the construction of the LSSS matrix is correct, then any set of qualified parties should be able to combine their shares to obtain the secret.  This is because the construction of the LSSS requires that the span of all of the rows held by any set of qualified parties must contain the target vector in their linear span.

In this example, $\{A,D\}$ is supposed to be qualified, and indeed adding one times the first row to one times the fourth row, i.e. computing $1 \cdot (1, 1, 0) + 1 \cdot (0, -1, 0) = (1, 0, 0)$, gives them the target vector.

This is useful because by linearity, parties $A$ and $D$ can use their shares to compute the secret using the same linear combination: i.e. $1 \cdot \mathbf{y}[1] + 1 \cdot \mathbf{y}[4] = s$.

The required linear combination is encoded in a vector: in the running example $\{A,D\}$, the recombination vector is $\mathbf{r}=(1,0,0,1)$, since we were required to add the first row to the fourth row.

Again assuming the construction of the LSSS is correct, we will also require that unauthorised sets of parties have no information on the secret.  This is true if and only if the target vector does not lie in the linear span of the rows held by those parties.

Let us denote by $M_U$ the submatrix of $M$ where we have selected only those rows owned by some unauthorised set of parties $U$.  So we have, e.g.

$ M_{\{A,B\}} = \begin{pmatrix}
  1 & 1 & 0 \\
  0 & -1 & 1
  \end{pmatrix}
$

To see that the colluding parties $\{A,B\}$ learn no information, observe that if $(1,0,0)^\top \not \in \text{im}(M_{\{A,B\}}^\top)$ then by the fundamental theorem of linear algebra, $(1,0,0)^\top \not \in \text{ker}(M_{\{A,B\}})^\perp$ and so there must exist some vector $\mathbf{w} \in \mathbb{F}^3$ such that $M_{\{A,B\}} \cdot \mathbf{w} = 0$ and $\langle \mathbf{w} ,(1,0,0)^\top\rangle \ne 0$.  (In other words, $\mathbf{w}$ must exist because otherwise every vector in $\text{ker}(M_{\{A,B\}})$ is perpendicular to $(1,0,0)^\top$, contradicting $(1,0,0)^\top \not \in \text{im}(M_{\{A,B\}}^\top)=\text{ker}(M_{\{A,B\}})^\perp$.)

In particular, we can find any $\mathbf{v}$ such that $\langle \mathbf{v} ,(1,0,0)\rangle \ne 0$ and $M_{\{A,B\}}^\top \cdot \mathbf{v} = 0$ and then set $\mathbf{w} = \frac{\mathbf{v}}{-\|\mathbf{v}\|_2}$ so that $\langle \mathbf{w} ,(1,0,0)\rangle = -1$ and $M_{\{A,B\}} \cdot \mathbf{w} = M_{\{A,B\}} \cdot \frac{\mathbf{v}}{-\|\mathbf{v}\|_2} = \mathbf{0}$.  This is the claim you highlighted.

The fact that we have found $\mathbf{w}$ already shows that union of the  shares held by the unauthorised parties provides no information on the secret, since adding the vector $k \cdot \mathbf{w}$ to the vector $\mathbf{x}$ that was used above to generate the shares encoded in the vector $\mathbf{y}$, where $k\in \mathbb{F}$ is any field element, provides the same set of shares for the unauthorised parties in question, since
we have shares
$ M \cdot (\mathbf{x} + k\mathbf{w}) = M \cdot \mathbf{x} + M \cdot k\mathbf{w} = \mathbf{y} + k M \cdot \mathbf{w}$
corresponding to secret $\langle \mathbf{x} + k \mathbf{w} , (1,0,0) \rangle = s + k \cdot -1$
and since $M_U \mathbf{w} = \mathbf{0}$, the shares held by $U$ can equally be shares for any secret, which we obtain by changing $k$ arbitrarily.  Consequently, the shares held by these parties cannot provide them with any information about what the secret is.

Computing $\mathbf{w}$

There is at least one $\mathbf{w}$ for each unauthorised set (assuming the LSSS has been constructed correctly). Note that you only need to find one $\mathbf{w}$ for each maximally unauthorised set (since this $\mathbf{w}$ will work for any subset too).

Computing the actual $\mathbf{w}$ as descibed in your reference involves finding any vector in $(M_{\{A,B\}})^\perp$ (which is called the cokernel or left kernel of $M_{\{A,B\}}$) which is non-zero in the first component, and scaling.  In the case of $\{A,B\}$, it is easy to find a $\mathbf{w}$ with the required properties by inspection: we can see that the vector $\mathbf{w} = (-1, 1, 1)^\top$ satisfies $M_{\{A,B\}}^\top \cdot \mathbf{w} = \mathbf{0}$, and it holds that $\langle (-1,1,1),(1,0,0)\rangle = -1$, which was what we needed (after transposing).

For larger matrices in this scheme, you just need a method for computing the cokernel of a given submatrix, and from there you take any vector $\mathbf{w}$ in that space satisfying $\langle \mathbf{w},(1,0,\ldots,0)\rangle = -1$, i.e. where the first component is $-1$.


Entropy test vs frequency analysis I'm currently doing the cryptopals challenges and for it's first set of problems it tells you to use frequency analysis of occurring letters to determine the likelihood of a key guess being correct and yielding legible english.

I was wondering, would calculating the entropy of the resulting plaintext not serve the same purpose, if not to a better degree seeing as it's not confined to the english language? Are there any benefits or drawbacks that one approach has over the other I'm missing?

I was wondering, would calculating the entropy of the resulting plaintext not serve the same purpose, if not to a better degree seeing as it's not confined to the english language?

First note that a cipher is susceptible to frequency analysis if it doesn't change the frequency at which characters occur. That is the "probability" of each substituted letter occuring is the same as the probability of the cleartext language. Now remember how the entropy is usually computed:

$$H(X)=-\sum_{x_i\in X} \Pr[X=x_i]\cdot \log_2(\Pr[X=x_i])$$

while replacing the probability terms for the measured approximation. Now as you can see entropy doesn't care where each probability value sits, if the same set of probabilities occurs you'll get the same entropy. And the set of probabilities is the same for each key for a given ciphertext susceptible to frequency analysis.

So "no", entropy will not help you here.


Block cipher modes used in real life There is a number of block cipher modes, including ECB, CBC, CFB, OFB, CTR and others.
After reading "Serious Cryptography. A Practical Introduction to Modern Encryption" by Jean-Philippe Aumasson, where the author described CFB and OFB as folklore which no one really uses,
I am curious which ones are most commonly used in the real world?
I think the one I come across most often would be CBC.
Would anyone be able to share some stats (which I didn't manage to get to), or make and educated quess?

CTR is the most used one with some additional authentication


Multi-party key agreement I have done a google search for "multi-party key agreement", and there doesn't seem to be anything more recent than about 2005.

Are there any practical multi-party key agreement protocols known?

To be more precise, I want a protocol which:

Allows multiple individuals to agree a single shared secret
An adversary cannot tell what the shared secret is by listening to the communications.
It should be authenticated so an active adversary cannot persuade a participant to communicate with a secret the adversary knows.

Note: I am aware of Multi-party Key Exchange protocol from lattice but a) that doesn't have any answers; b) I am not only interested in lattice cryptography (in fact, I would prefer something based on ECC or factoring).

Edit: Background
I want a system for encrypting a conference call.  If each caller sends their audio to every other participant with separately agreed keys, then the total amount of work required is $O(n^2)$ (and the work done by each participant is $O(n)$).  If everyone agrees a single shared secret, then we might be able to reduce the amount of work required.

Historically, both the difficulty and the risks involved in securely establishing shared keys in large networks has led to the invention of public-key cryptography. So you might first want to consider using digital signatures/asymmetric encryption instead of sharing the same secret between parties.

If you need all (or some) of the parties to collectively sign or encrypt a message, consider using threshold signature schemes with a Distributed Key Generation protocol. That will produce a key pair that is distributed among $N$ participants such that at least $k$ of them need to collaborate for performing a key operation. For discrete-log cryptosystems there's a paper by Gennaro et al that describes such a setup.

Edit: If you only need to establish a common secret (instead of a key pair) between all the parties, a simpler solution would be to use a generalized Diffie-Hellman key exchange instead. This works for honest participants with insecure communication channels. If the participants can be malicious, a more robust solution is described by Tseng, 2005.


How to retrieve the plaintext of a substitution ciphertext? So the other day, I was piqued by a ciphertext that was trivially encoded through substitution. Solvable only because we can use our eyes to determine word boundary word detection, etc. Trawling the net, there didn't seem to be any automated way of doing this, other than of course to generate a key the size of the alphabets.

How would one go about programmatically decrypting a substitution cipher given that all spaces have been removed?

It seems like there would be multiple runs of frequency analysis on single letters, then double letters, then finding out word boundaries. How would one go about solving this without resorting to a 26-factorial brute-force method?

I think frequency analysis is the preferred approach for breaking substitution ciphers. The more ciphertext you have, the better it is. My suggestion would be to do the following:

First, you compute two probability distributions:

a distribution that contains the probability of the symbols in a reference text of the same language and technical area than then expected message.
a distribution that contains the probability of the symbols in your ciphertext.

Once you have these distributions you have a significant knowledge. Instead of trying all possible permutations in brute force, you can now try the most probable ones first. For each permutation, you can check if the probabilities of the symbols in the ciphertext correspond to the probabilities of the symbols in the reference text.

The Kullbach-Leibler (KL) distance is often used to measure the similarity of two probability distributions. You will ideally start your search with the permutation that minimizes the KL distance and then proceed to permutations with a higher KL distance.

For each permutation you then substitute the symbols accordingly and you check if words that frequently appear in your reference text are also found in the decoded text. You keep the best solution which has the most matches, and you continue the search.

The probability to find a better decryption will decrease the longer you search. So you can just stop after some time. You have to decide when exactly the algorithm will stop, but here again you have the probabilites and the KL distance to help you make this decision.


Help understanding NIST HMAC The NIST (National institute of standards and technology) defines the HMAC standard as the following: $$\operatorname{MAC}(\text{text}) = \operatorname{HMAC}(K, \text{text}) = H((K_0 \oplus \text{opad} )|| H((K_0\oplus \text{ipad}) || \text{text}))$$ available in FIPS 198-1 (PDF).

I can see that the pre-shared key is XORed against internal padding and outer padding. I can also see that the results of which are not only hashed, but then concatenated together.

My question is how exactly is this used to ensure authentication/ integrity?

For example, If create a HMAC, how does my intended recipient use the HMAC sent with the message to ensure it is intact?

Also, given the inclusion of XORs, should I assume the inverse of these is calculated and somehow used in the process, as you can see I'm quite the novice, so some help would be very welcomed.

XOR is used here to flip about half the bits and create a large Hamming distance between the two versions of the key. It is not used to make the operation reversible. Making the operation reversible would not make sense in the first place: the hash that is applied afterwards is a one-way function and therefore not reversible.

The HMAC construction is used to make it impossible that collisions in the hash result in loss of security and to make sure that length extension attacks are not possible.

Bonus answers for the questions in the comment:

  Is authentication confirmed by the receivers knowledge of the pre-shared key?

Yes, message authentication is confirmed because the MAC can only be calculated if the sender has the same key as the receiver. Beware of replay attacks and communication reversal attacks though; these are not prevented by a MAC alone. In other words, you should uniquely be able to identify your messages and include that identification in the MAC for authentication.

  If we used AES with HMAC, would I need to compute this HMAC for every block of cipher text?

Yes, if you have ciphertext you need to authenticate all of it as well as the IV/nonce. If you're not sure which parts of the ciphertext to authenticate then you're better off using authenticated encryption (GCM or EAX for instance).


Which blind signature schemes exist, and how do they compare? I'm looking into blind signature schemes for use as digital cash. I have come across blinded RSA, and Lucre(DH based). Are there other schemes available, and how do they compare? I suspect there should be a elliptic curve scheme, which might have better performance than the other schemes.

In particular I'm interested in:

Performance - how expensive is it to create/validate the signature? I mainly care about the cost for the authority(does signing and verification), and less about the performance of the client (does blinding and verification)
Patents - Is the scheme patented? Have the patents expired?
Simplicity - Is it easy to understand? Is it easy to make subtle mistakes which compromise anonymity or security?

My current evaluation of RSA and Lucre:

Blinded RSA

Requires an RSA private key operation for signing. This is relatively expensive, especially if keys larger keys(say 2048 bit) are used.
Patented by Chaum, but the patents should have expired by now
Quite simple, even I understand it

Lucre

Not sure about the performance, but I don't expect much better performance than with RSA.
Paper claims it is patent free, at least in some variations
There are some subtle points. If used incorrectly the signer might be able to abuse being able to choose k in a way that compromises anonymity. I don't really understand it (yet).

Reading the paper a few more times, it seems like most variants of lucre aren't "real" signatures that can be verified by everyone. But rather you need to perform an interactive probabilistic proof. Some variants doesn't suffer from this problem, but they might have other problems.

My subjective impression is that I don't like lucre. It seems like its only raison d'être is that is avoids Chaum's patents. But if those are expired, this shouldn't be an issue anymore.

I'm still a newbie in the field, but trying to learn something about it I ran into these two papers that you surely know, in case not I'll point them out:

Blind signatures for untraceable payments, Chaum
Provably secure blind signatures schemes, Pointcheval

By the way if you look at the introduction of the second title it seems what your looking for.

A specific link on Electronic Cash from RSA Laboratories:

What is Electronic Money

By studying blind signatures I've read about a scheme based on ElGamal Signature Scheme, I'll provide the information I was able to glimpse.

You can find more details at the following links:

IEEE, A blind signature scheme based on ElGamal signature
Citeseerx, Generalized blind signature schemes

Blinded ElGamal:

Performances:

  Owner Alice needs to compute two online exponentiations modulo $p$
  with a |$q$| bit exponent and one offline inverse modulo $q$.

  Notary Nancy needs to compute just one online exponentiations modulo
  $p$ with a |$q$| bit exponent.

  Verifier Victor needs to compute two exponentiations instead of the
  three ones required for standard ElGamal scheme.

Note: you can find further references for even more efficient variants in the links I provided.

Patents:

I have no clue!Sorry about that...

Simplicity:

I got it all clear, if reading the papers you have any doubts post them and we can check together!


Is it possible to obtain AES-128 key from a known ciphertext-plaintext pair? I have a file, which was encrypted with AES-128 in ECB mode. I know the format of the original file and know that all files in this format have the same headers. So, I have an encrypted block and the original block.

Can I get the encryption key, using this information?

As far as is publicly known, no, you can't.

If you could, that would constitute a practical known-plaintext key recovery attack on AES, and the existence of such an attack would mean that AES would be considered totally insecure by modern cryptographic standards.

If you do figure out how to do that, publish it and you'll be famous.
(Or, if you'd prefer money over fame, take it to your local/favorite intelligence agency or organized crime syndicate.  But note that this option carries some significant risk, since whoever you sold that information to would now have a considerable interest in preventing you from selling it to anyone else).

One exception to this is the case where the keyspace is (or you suspect it may be) sufficiently small to allow a brute force exhaustive search of it.  That could e.g. be the case if the key is derived from a passphrase that may not have been chosen securely (that is, at random from a sufficiently large pool of combinations).  In that case — especially if no delibrately slow key derivation function was used to strengthen the key — you could just write some code (or build some hardware) to try all likely passphrases until you find one that gives the correct encryption.


Differences between hash- and encryption algorithms? There is a lot of confusion between hash- and encryption algorithms; I would like to understand:

When do we use a hash algorithm and when do we use an encryption algorithm (a cipher)?
How difficult it is to reverse hash- and encryption algorithms?
From the theoretical/mathematical perspective, what differentiates a hash- and encryption algorithm?

When do we use a hash algorithm and when do we use an encryption algorithm (a cipher)?

Hash functions are typically used to map an arbitrary-length (usually long) input into a fixed-length (usually short) and random-looking value. E.g., SHA-256 always outputs a 256-bit random-looking string (or digest) for any given input.

A very common property of hash functions is collision-resistance, i.e., it is very hard to find two inputs that generate the same output. This is very useful when the input size is very long, which implies that we can compress a big file/string into a small one while still maintaining its "uniqueness". (Of course, theoretically, there are many many long inputs that generate the same short output due to Pigeonhole principle, but they are very hard to find given reasonable computing resources.) Based on this property, hash functions have many good applications. For instance, one can use the hash values of big files to efficiently find duplicates, and some websites often publish the hash values of their downloadable application installation packages to guarantee integrity. However, hash functions themselves are not directly related to data privacy or confidentiality.

The other property that hash functions (are expected to) have is that they output random-looking values. This can be used to generate random keys given non-random (but high-entropy) inputs, i.e., the so-called key derivation functions.

Encryption algorithms (more precisely, encryption schemes) are designed to "hide" the input/plaintext with the output/ciphertext such that no one except those having secret keys can decrypt the ciphertext to get the original plaintext. They at least provide data confidentiality, and authenticated encryption schemes also provide integrity (hash functions can be used here).

  How difficult it is to reverse hash- and encryption algorithms?

Hash functions by design are hard to reverse, so are encryption algorithms without knowing the secret key. But if you know the key or if you want to play with the encryption algorithm with any key, then you can easily reverse it with a decryption algorithm using the same key. So, here the simple difference is that hash functions do not have keys. (Note that keyed hash functions are often discussed in the topic of message authentication codes.)

  From the theoretical/mathematical perspective, what differentiates a hash- and encryption algorithm?

Hash functions normally map long inputs into short ones while encryption algorithms often do the opposite to introduce randomness (to hide the input messages). Hash functions are deterministic while encryption algorithms are often probabilistic (otherwise the encryption scheme cannot be IND-CPA secure). Well, regarding similarities, they both generate random-looking outputs.


Is the SEED blockcipher still secure? I did found an old question which answers exactly this but it is from 2 years ago and i was wondering if there were any changes. I have not been able to find any new information on the cipher and am quite curious seeing as it's extremely fast.

I've tested it against a very fast (fastest I have found so far) AES implementation which took 392μs to encrypt 128 bytes and 400μs to decrypt 128 bytes.

The SEED cipher took 325μs to encrypt the same 128 bytes and 228μs to decrypt. This is enough to make it interesting for me though I still prefer AES since it is more well known and has been through more scrutiny.

Both tests were done with the same CBC method, so there might be some performance to be gained from a better CBC implementation but i think the one i have is already quite good, for those of you who are wondering i'm using the CycloneSSL library on a RX63N board (renesas development board).

So can SEED be trusted? Can i use it for sensitive data?

Short answer: Yes, I'd still trust SEED.

The topic you linked to is from 2013 (2 years) old and for cryptography nearly never any advances will be made for a 15 year old, rarely used cipher after just 2 years.

As the best cryptanalysis only penetrated half of the rounds back then I'd highly doubt there're any advances by now, as this is only a legacy cipher in most systems and hence not a target like AES which is in widespread use.

EDITED TO ADD(1): As pointed correctly in a comment, if you plan to secure data against nations / national intelligence agencies, you can not rely on the security of SEED and therefore must consider using AES(-192/-256) or maybe even multi-encryption with ciphers with different designs (-> SEED & AES & Threefish/ChaCha & Serpent).


What is the difference between a one-shot MPC protocol and a unbounded invocation of multiple MPC protocols? In this paper on pg. 1236, under the section "Security Against Continual Leakage", the authors say:

  "We further remark that the weaker security notion previously
  achieved cannot be extended meaningfully to continual leakage in the
  MPC setting. That is, it cannot address the setting where the $n$ users
  do not just perform a one-shot MPC protocol, but rather engage in an
  unbounded number of MPC protocols for many functions, and during
  each MPC invocation the adversary leaks $\ell$ bits from each of the honest
  party’s internal state."

I'm confused about the difference between a "one-shot" MPC protocol vs. "unbounded number" of MPC protocols.

I am envisioning something like:

MPC protocol 1: leaks $\ell$ bits from each honest party's internal state
MPC protocol 2: leaks $\ell$ new bits from each honest party's internal state
MPC protocol 3: leaks $\ell$ new bits from each honest party's internal state
...
MPC protocol $k$: leaks $\ell$ new bits from each honest party's internal state

If there are a total of $n$ honest parties, then you have a total leakage of $n \times \ell \times k$ bits.

But if you consider the "one-shot" MPC protocol, you get just $n \times \ell$ bits leaked.

They give an example of threshold cryptography and say that, when you have a bunch of parties that compute a decryption function jointly, you may end up with the entire decryption key leaked, because every time $\ell$ bits are leaked, you can think of it as if $\ell$ bits of the decryption key were leaked.

Why are the authors even considering this "unbounded number" of MPC protocols ?

Basically, there a many real-world problems where one might want to compute something on sensitive data several times.  Indeed, later in the paper you cite, the authors give several example, e.g.:

  "Medical Data: One may envision a huge database which contains the medical data of every patient in the US. To compute any global statistic on this data, one would not want to put complete trust in any single database. Instead, it is distributed to $n$ different databases. Each time they need to compute statistics on this data, they engage in an MPC protocol. As in the voting example, since these databases contain very sensitive information, an adversary may try to obtain this information via a leakage attack. Thus, to ensure security, the databases must run an MPC protocol that is secure
  against continual leakage."

The important words above are "each time".  It would not do much good to have a distributed database that was secure only the first time it was queried.


Showing the non-pseudorandomness of a generator I'm sorry if this question is too novice. It comes from a practice midterm in a cryptography course which I'm taking, and my confusion here is really that I don't know the "tools" that one uses in practice for this sort of question. The notation (and class) is Katz's.

I've been given a PRG $G(s)$; I'm trying to show explicitly that $s\mathbin\|G(s)$ is not a PRG. Intuitively, I'd expect both components to be random-seeming, so there's nothing obvious that sticks out to me to XOR or manipulate.

This is an attempt to answer my own question based on Squeamish's helpful comments. If terminology is unclear or misleading, please tell me!

Let $D(s) = \mathbb{I}\{s = x||G(x), x \in \{0,1\}^n\}$. Then, if our putative PRG is $G'$, $\Pr[D(G'(s)) = 1] = 1$ - that is, $G'(s)$ is always in the format that $D$ looks for. However, $\Pr[D(r) = 1]$ (where $r$ is uniform from $\{0,1\}^{2n}$) is $\frac{2^n}{2^{2n}}$, to reflect that $s||G(s)$ has a range of only $2^n$ - being completely determined by $s$ - while there are $2^{2n}$ possible values $r$.

Thus $|\Pr[D(G'(s)) = 1] - \Pr[D(r) = 1]| = 1 - \frac{2^n}{2^{2n}}$, a non-negligible function.


Is it true that Serpent and twofish are much stronger than AES? I heard that Serpent and Twofish are much stronger than AES, but it was chosen because it is faster. If that's true, please tell me why it is stronger.
Also: is it true that Twofish and serpent are better protected from brute force attacks because they take longer to en/decrypt?

SHORT: This is kind of true. However, things are bit different now. Better protection against brute force is inaccurate claim.

At the time Rijndael (AES) won the competition, it was faster, and sufficiently strong. After the competition, Rijndael (AES) has gotten faster (AES-NI and other hardware improvements). Also Rijndael (AES) has also gotten significant amount of analysis, but it has not been broken in a practical way. Therefore, Rijndael (AES) has been shown to be quite good pick.

The other AES finalists are also believed to be very good, but as they've not been as standardized they will lack interoperability. Also, we've gotten very good in making Rijndael implementations during the last two decades. Because Serpent and Twofish have gotten less attention, it may be harder to find as good implementations of these algorithms than it is to find very good AES implementation.

The difference in en/decryption speed between these algorithms does not translate into any meaningful difference in protection against brute force attacks.

For more information, see also earlier answer by B-Con to similar question regarding advantages of Rijndael against Twofish and Serpent at: https://crypto.stackexchange.com/a/5290.