Probability of $D_k(a*k+b) =p$ for a PRP I'm wondering what the probability of a PRP having numerous keys (say 3 or more) with the same simple idempotent, or near identity, function.  For example, does there exist values of $p, a, b, x_1,$ and $x_2$ where more than two keys, $k$, have the property:

$
AES_k(p) = (x_1 \oplus (a*k) + b) \oplus x_2
$

I can abstract out E_k(p) as some PRP that yields an "unrelated" value:

$
R_1 = (x_1 \oplus (a*k_1) + b) \oplus x_2 \\
\wedge
R_2 = (x_1 \oplus (a*k_2) + b) \oplus x_2 \\
\wedge
R_3 = (x_1 \oplus (a * k_3) + b) \oplus x_2
$

Then, entirely informally, I reason that since there are $2^{128} R_i, k_i$ pairs the probability here is pretty high. Is that other peoples gut instinct?  Could someone help me formalize the math here a little since I'm stabbing around a little blindly?

EDIT:
Addition ($+$) and multiplication ($*$) are mod $2^{128}$.  The $\oplus$ operator is bitwise addition (exclusive-or).  Algebraically, I can see how two keys with this property trivial to derive ($x_2$ yields obvious flexibility) but I am unsure about the probability of this property holding for $N$ keys ($N>2$).

Edit 2

Adding more details on my thoughts:  We can get two keys for which this property holds through simple algebraic rewriting:

$
k_1 = random\\
b = 0, a = 1\\
p = D_{k1}(k_1\oplus x_1 \oplus x_2) \\
k_2 = random \\
x_2 = E_{k2}(p) \oplus x_1 \oplus k_2 \\
x_1 = E_{k3}(p) \oplus x_2 \oplus k_3 \\
$

At this point $x_2$ and $x_1$ are defined in a mutually recursive manner.  We are left with:

$
x_1 = E_{k3}(p) \oplus E_{k2}(p) \oplus x_1 \oplus k_2  \oplus k\\
0 = E_{k3}(p) \oplus E_{k2}(p) \oplus k_2 \\
$

I.E. Removing $a$ and $b$ from consideration, for an equation with two xored values the probability of two keys meeting this property is 1.  However, finding the value (if any exists) for the third key appears to be more involved - the above construction yields $E_{k3}(p) = E_{k2}(p) \oplus k_2$ which is similar to obtaining a key from a single chosen plaintext.

It is not obvious to me that adjusting $a$ or $b$ can be leveraged efficiently to solve this problem or make it computationally tractable.  This is the heart of my question.  Is it computationally feasible to find constants, including three keys, for which this property holds?

Let's look at some simpler relations first. I'll be sloppy with the probabilities, I'm only trying to gauge the order of magnitude.

The probability that $E_{k_1}(p) = k_1$ is $2^{-128}$ for a given $p$, but must be true for some $p$ with every AES-128 key $k_1$.

The probability that $E_{k_2}(p) = k_2$ for the same $p$ is $2^{-128}$ for a given $k_2$.
The probability that there is some $k_2 \not = k_1$ for which $E_{k_2}(p) = k_2$ is about $2^{128}-1$ times as much, i.e. quite likely.
The probability that there are three different $k_i$ for which it is true is again close to $2^{-128}$.

Now that was with a constant $p$ that we "found" with some key $k_1$. Take another key and there's another $p'$ for which a similar equality holds, and $p'$ is likely different. For that you can again look at all other keys, probably finding at most one other key that fulfills it, but finding three with probability around $2^{-128}$.

Go through all $p'$, of which there are a small factor fewer than $2^{128}$, and you are quite likely to find one for which three keys match $E_{k_i}(p) = k_i$. Not 100% likely, but maybe 10% or whatever.

Now you can make the equation more complex. If you XOR a random constant $x_1$ on the right side, you can approximate it as an independent equation. There are $2^{128}$ possible values of $x_1$ so now you are overwhelmingly likely to find one triplet of keys for which it holds. Might even find four, but probably not.

Your form is more complex so there's more freedom to choose the constants and $N$ is probably larger. However, my math was sloppy enough already that I won't guess at the value.


Are transposition ciphers insecure? Given plaintext: P[i], i = 1..N

Given stream of cryptographic numbers S[i, j], i = 1..N, S[i, j] in [1, j] generated by RC5 for example

We encrypt using Fisher-Yates shuffle algorithm:

for (int i = N, i > 1 ; i--) swap(P[i], S[i, i])

How to estimate complexity of breaking such chipher?

Is it lower than strength of S[i] generator?

How does it depend on value of N?

How does it depend on data we encrypt?

Unfortunately I was unable to find anything useful on topic.

P.S. Why not AES? Because chipertext is harder to detect using frequency analysis.

This is not very secure. You directly leak the symbol distribution, because only the order of symbols changes. For short enough messages this allows easy decryption – e.g. "dr olllWeoH" is quite clearly "Hello World". Even for long messages or binary values, the fact that you leak e.g. a crucial byte may be enough.

You also have not defined how the same key would be used to encrypt multiple messages. Using the same stream of random numbers would be fatal, allowing easy known-plaintext attacks at the very least. You would need an IV/nonce of some kind, which may itself make the fact that the message is encrypted detectable.

If the problem you are trying to tackle is hiding the fact that the message is encrypted, you should look into either steganography or format-preserving encryption:

Steganography  is about hiding secret messages in normal-looking messages. You could use a standard encryption algorithm (say AES-GCM) to encrypt the message and then hide it in a cover message using some steganographic scheme.
Format-preserving encryption, on the other hand, allows you to keep the encrypted message in the same format as the plaintext, which might be sufficient to hide the fact that it is encrypted. For example, database fields can be encrypted in place. Beware that depending on the application FPE is not necessarily as strong as normal authenticated encryption can be.


Is the security of an HMAC equally important as the security of the cipher itself? I'm a little unclear on how hash based MAC works... So I would like to know, is the security of your hash function as important as the security of the overall cipher? Basically, if you can crack the hash, does this compromise the cipher?

I understand that in most situations it isn't particularly feasible to crack either.

Based on your comment:

  Correct... But it looks like many HMAC systems basically end up including a hash of the plaintext+key alongside the ciphertext. So it seems like cracking that hash would effectively compromise the entire encryption, no?

you may have a misunderstanding of how HMAC is used as part of a cryptosystem, which is reinforced by the opening line of the question.

The HMAC input is not the plaintext+key, but rather just the ciphertext, or just the plaintext. A separate key is used as part of the HMAC process to change the initial value of the hash function to a secret. The input is then hashed with the secret IV, and then the output is hashed again with a different secret IV. That key that generates the secret IVs is not the same as the key used by the cipher.

Current best practice is to MAC the ciphertext, and not even attempt decryption if the authentication fails. If the plaintext is MAC'd, decryption is required first. When HMAC is used, if the plaintext was MAC'd, an attacker can corrupt the MAC or ciphertext and resend multiple times, forcing the recipient to decrypt the message every time. If the cipher was vulnerable to a timing attack, this method could be used to recover cipher key material. The same security against timing attacks must be provided to the hash function, since a ciphertext MAC failure would not even touch the encryption key, but could allow recovery of the MAC key. In this respect, the security of HMAC is as important as the security of the cipher. This is also one of the reasons the MAC key and cipher key are different, so recovery of one would not compromise the other.

One of the other reasons to MAC the ciphertext when using HMAC, is that processing an identical plaintext results in an identical MAC, whereas the same plaintext results in a different ciphertext when encrypted correctly with most modes, which is an important required property for many applications.

Because of the way HMAC uses the hash, it is more robust than the hash used. The offline attack that would compromise HMAC is a preimage attack, which would recover the original message, specifically the part that generates the secret IVs. Because HMAC hashes twice, this is extremely difficult even with a broken hash like MD5.

Alex's answer also brings up an important point. Even after key rotation, a broken HMAC (key recovery) does not recover the message, and only allows forging a MAC using that key, which is now no longer used. The MAC key must be secure for the life of that key, which is generally short enough that a brute force attack to recover it is all but infeasible. The key should also be large enough for the same reason.


Is my Enigma inspired cipher any good? I am working is a project that would implement a cipher that would output ciphertext that would be easy to transmit through morse code, just like they did in the days of Enigma.
Use of AES or the likes would of course work, but the downside is that since AES can encrypt 256 different values for each character, the resulting ciphertext would have to be encoded to limited character set to satisfy above requirement, eg to hex using only characters 0-9 and A-F. This will result in ciphertext that is at least twice as long as the original plaintext, so it be harder to transmit.
This got me working on a Enigma style computerized rotor based cipher, with some steroids. This is how I envisioned it would work:

It would have a larger character set of 47 characters ([A-Z][0-9][.+-?!&@:=] (I chose this because 47 is a prime number)
It would have 47 rotors, each with different mapping. Each rotor would have an identifier from the above 47 available characters
for encryption/decryption, 10 rotors would be chosen from 47, but a rotor can be chosen multiple times
Each rotor would step 1-4 times between each encryption, this would be determined by the rotor ID and its initial position.
No deflector, for decryption the cipher would simply be run through the rotors in opposite order. A character CAN map to itself so a big flaw in original Enigma is solved.

So the keyspace would be formed from selecting 10 rotors in random from 47, and setting an initial start position of each into any of the 47 possible positions. So Keyspace would be 47^20 = 2.77E33 or roughly 111 bits. So I suppose brute force attack is infeasible. we would use the key so, that first 10 digits are the chosen rotors, and remaining 10 digits are the initial positions of the rotors (IV).
The actual encryption would work like this. First we generate a random 10 character initialization vector (IV), and encrypt that with the above message key. Then we use the resulting ciphertext (10 characters long) as the new IV for the next 10 characters to encrypt and so on until we reach the end of the message. To decipher, we do this in reverse. We know that first 10 digits are the IV for the next 10 digits and so on.
Example, Plaintext is "HELLO+WORLD+OF+ENIGMA", Message key is "01234567899876543210" (for simplicitys sake, I did not actually run this through the algorythm)

Generate random IV, eg "ABCDEFGHIJ"
Encrypt above with messagekey "01234567899876543210", this results in "KLMNOPQRST", add that to ciphertext
Encrypt first 10 characters of plaintext ("HELLO+WORL") with key "0123456789KLMNOPQRST", this results in "K?+L&KMWI7", add that to cipher text which is now KLMNOPQRSTK?+L&KMWI7
Encrypt next 10 characters of Plaintext ("D+OF+ENIGM") with key "0123456789K?+L&KMWI7", this results in "8/HFP:=JGR", add that to cipher text which is now KLMNOPQRSTK?+L&KMWI78/HFP:=JGR
Encrypt remaining 1 character ("A") with key "01234567898/HFP:=JGR" which results in A, so final ciphertext is KLMNOPQRSTK?+L&KMWI78/HFP:=JGRA

The result is something that would be easy to transmit in morse code, as well as easy to spell over voice radio etc. It only adds 10 characters to the length of the original message.
But how secure would that be ? I know brute force would not be an issue. But assuming the rotor mappings are known, how about more sophisticated forms of cryptoanalysis ? One obvious thing I can think of is that the attacker would know the length of plaintext (=length of ciphertext less 10), but is that really an issue.

But how secure would that be ?

Not very; there's an obvious known-plaintext-attack that recovers the key settings with effort equivalent to about $2^{28}$ encryptions; that'd be less than a minute on a single CPU core (perhaps much less, depending on the speed of the cipher implementation).
Two obvious observations:

You count the initial positions of the rotors as 'key'; however you expose them in the ciphertext (and so the attacker would know them).  The only thing initially unknown to the attacker is the rotor selections (and the initial settings used to generate the IV; the attacker doesn't care about that)

There's an obvious meet-in-the-middle attack; with a known plaintext/ciphertext pair (with known IV settings), we can scan through all $47^5$ possible selections for the first five rotors, and encrypt the plaintext through the first half the cipher with those, coming up with $2^{47}$ possible intermediate values.  Then, we can scan through all $57^5$ possible selections for the last five rotors, and decrypt the ciphertext through the last half of the cipher, coming up with $2^{47}$ possible intermediate values.  Check the two lists for a common value - that'd be the rotor settings.

BTW: if you are really interested in this 'encryption with a reduced alphabet' problem (rather than just playing around with designing your own system), you might want to read up on Format Preserving Encryption...


Is there any semantic difference between predicate encryption and functional encryption? Predicate encryption(PE) arrived as a descendant of attribute based encryption. Attribute based encryption allows the encryptor to embody a policy to the ciphertext (Ciphertext-Policy based encryption) and the receipent to receive a key from a central trusted authority according to his attributes. If the attributes do satisfy the policy then the receipent can decrypts. Another less secure version is the key-policy based encryption whereby the encryptor associates with the ciphertext the attributes that he wills a potential decryptor to have and the key of the receiver comes with the policy. Because attribute based encryption reveals the policy(KP-ABE) and the attributes(CP-ABE) predicate encryption comes to solve this by allowing the receipent to apply a predicate if he owns a secret key of that predicate.

Functional encryption(FE)
As presented in the paper is a generalization of Identity based encryption, Attribute based encryption and predicate encryption. Instead of a predicate there is a function $f$ that evaluates the attributes of the ciphertext. At the paper the construction is given based on predicate encryption.

My question is what extra functionality FE provides in comparison with PE. Is there a drawback or a security leakage in PE that FE solves?
My intuition from the literature is that the contribution of FE is the generalization of the 3 previous mention crypto schemes(IBE,ABE,PE) into 1 scheme (research purpose for acceptance in a conference, not practical at all) and second is the area of applications. I understood that in PE if your secret key $sk$ lets you evaluate at $1$ a predicate $P$ over a ciphertext $c$ then you recover the plaintext but with the FE if $F_{sk}(c)=1$ then you learn the output of the function on the plaintext. I.e: the function might be a machine learning algorithm classifying spam so you learn if the message is a spam or no, but not the contents of the message. Is this correct?

PE is a subclass of FE.

This (from the other answer) is correct.

Also, from my understanding, your analogy is correct. PE returns the plaintext if the predicate evaluates to true. FE, on the other hand, returns a function of the plaintext.

We can say that PE is a subclass of FE, since we can use FE to implement PE. Just use the identity function.

Your example of $f$ being a machine learning function is an example of something that FE can do that PE cannot.


What is the relationship between entropy conditioning and final output bias in a TRNG? This question concerns the conditioning and output of true random number generators.  It refers to NIST Special Publication 800-90C, Recommendation for Random Bit Generator (RBG) Constructions. It defines an $ n $ length bit string as having full entropy (ideally random) as:-

  ...if that bit string is estimated to contain at least
  $ (1-\epsilon) n $ bits of entropy, where $ 0 \leq \epsilon \leq 2^{-64} $.

Now to obtain a bit string containing full entropy, the document recommends a conditioning operation listed in Appendix C.  The smallest internal block width of any of these functions is 64 bits for treble DES.

And the document also says that if you follow this recommendation, you'll get a full entropy $ t $ length bit string from the conditioner's output:-

  If $ t \leq \frac{n}{2} $, then the output string has full entropy output .

This is the common rule of thumb for outputting half of the hashed input entropy in a TRNG.  My question therefore is what is the relationship between $ \frac{n}{2} $ and $ 2^{-64} $?  More specifically, what would the maximum of $ \epsilon $ be for $ \frac{n}{4} $?

The notation is a little confusing because it uses the same letter $n$ for two purposes, so let's change it to be a bit clearer:

  An entropy source output string containing $2t$ bits of entropy can be conditioned into a string of $t$ bits that contains full entropy output using an approved conditioning function, where $t$ is the length of the output block of the approved derivation function (see SP 800-90B).

(Replaced $n$ by $t$.)

In other words, if we have a physical device that produces a string $\sigma$ with $2t$ bits of entropy, which is necessarily at least $2t$ bits long, and we can pick a conditioning function $C\colon \{0,1\}^* \to \{0,1\}^t$, then the string $C(\sigma)$ is $t$ bits long and has nearly $t$ bits of entropy—in particular, $(1 - \varepsilon) t$, where $\varepsilon < 2^{-64}$.

This is a statement of an assumption (in §4.2 ‘Assumptions’) about the entropy source, having at least $2t$ bits of entropy where $t$ is the length of the output block.

  The derivation functions in SP 800-90A distribute the entropy provided by the input string is $n$ bits (so that the length of the input string is $r$ bits for some $r \geq n$), and the length of the output string is $t$ bits, then the following is true:

  If $t \leq n/2$, then the output string has full entropy output (i.e., the output string has $(1 - \varepsilon) t$ bits of entropy, for some $\varepsilon \leq 2^{-64}$).

($t$ is the same as above now.)

In other words, if we have a string $\sigma$ with $n$ bits of entropy, which is necessarily at least $n$ bits long ($r \geq n$), then for any choice of derivation function $C\colon \{0,1\}^* \to \{0,1\}^t$ in SP 800-90A with $t \leq n/2$, the $t$-bit string $C(\sigma)$ has nearly $t$ bits of entropy—in particular, $(1 - \varepsilon) t$, where $\varepsilon < 2^{-64}$.

This is a statement of an assumption about the derivation function, like Hash_df, used as a conditioning function.  An example of a function that would fail to satisfy this property is one that, say, just gives the first $t$ bits of the input string.

Why should these relations hold?  See an earlier answer for some details.  The quick summary is that a rough approximation for expected entropy of the output $F(\sigma)$ of a uniform random function $F\colon \{0,1\}^* \to \{0,1\}^t$ on a string $\sigma$ with $t + k$ bits of entropy is $\lg 2^t (1 - e^{-2^k}) = t + \lg (1 - e^{-2^k}) \approx t - e^{-2^k}/\log 2$, so as long as $k$ is reasonably large we easily attain ‘full entropy’ in this model with $\varepsilon \approx e^{-2^k}/(t\log 2)$.

Picking $k \geq 64$ is plenty—and we are required to do that because the block size of every approved derivation function is at least 64.  We don't have a uniform random function in the real world, but the derivation functions of SP 800-90A don't seem to have any interesting properties that let us distinguish them from one, so it's a pretty good model.

What if you chose a string $\sigma$ with $n = 256$ bits of entropy, and a 3DES-based derivation function with an output block of $t = 64 = n/4$ bits?  Then $k = 192$, so $\varepsilon$ is really quite tiny, and we get ‘full entropy’ in a 64-bit string—although that's only just under 64 bits of entropy.

What if you chose a string $\sigma$ with $n = 130$ bits of entropy, and an AES-based derivation function with an output block of $t = 128$ bits?  The margin is smaller in this case: since $k = 2$, the approximation above (a) is not a very good approximation and (b) gives an $\varepsilon$ nowhere near $2^{-64}$.  Maybe we get more than 64 bits of entropy in the end, but that's not ‘full entropy’ for a 128-bit string.

At what $k$ do we draw the line?  To give a comfortable margin without having to think hard about it, we just say that you should use twice as much the entropy in the input as the ${\geq}64$-bit output is long, in order to reliably get ‘full entropy’ in the output.


AES-GCM GHASH calculation; I'm trying to make an GHASH() function and need some clarification.
Implementation is based on gcm-spec. Page 8 describes polynomial mult and page 27 has a "Test Case 2" which I use to verify result.

From my understanding X1 is a first round of GHASH function and effectively a result of multiplication of 16B of ciphertext and 'H'. From test case

X1<-C * H
X1<= '0388dace60b6a392f328c2b971b2fe78' * '66e94bd4ef8a2c3b884cfa59ca342b2e'

My implementation gives a different result. I also have tried some online tools which gave a totally different numbers as well :(

So the question is do I got it right that X1 is a result of multH(C,H)?

Thanks

Yes, you a right; also after running the GF(128)/GCM multiplication test I confirm that the product of the test values is

0x0388DACE60B6A392F328C2B971B2FE78 $\times$ 0x66E94BD4EF8A2C3B884CFA59CA342B2E = 0x5E2EC746917062882C85B0685353DEB7


textbook RSA signature scheme security Are textbook RSA signatures secure if an Adversary does not have access to ask signing oracle queries?

No, plain RSA signatures are existentially forgeable under a key only attack. This is because of the following attack strategy:

Given a verification key $(e,N)$, set the message to $m=s^e \bmod{N}$ for an arbitrary $s$ in the message space and set the corresponding signature to $s$. Output the message signature pair $(m,s)$ as a forgery.

It is easy to verify that this pair passes the verification equation.


Is C25519/Ed25519 "twist secure"? This recent new curve mentions something that's new to me: twist security.

http://safecurves.cr.yp.to/bada55.html

Are the existing C25519/Ed25519 curves secure against this form of attack?

Yes.

There are several different kinds of twist attacks. Curve25519 is safe against all the ones SafeCurves looks at. Specifically, the cost of a combined attack is $2^{124.3}$, which is considered safe.


What is the relation between hash chaining and chosen prefix attack I read that hash chaining can be used to prevent hash collisions, while the chosen prefix attack allows hash collisions for algorithms like MD5.
How are they related? Does hash chaining prevent the chosen prefix attack?

Hash chaining does not itself prevent hash collisions.  It sounds like you might have walked away with the wrong lesson from your reading.  You might want to read about the Merkle-Damgaard construction, which takes a collision-resistant compression function (for fixed-length inputs) and shows how to extend it to a hash function (for variable-length inputs).  Note: to prevent collisions, you need the compression function to be collision-resistant, and you need to use a proper chaining scheme.

Most modern hash functions, including MD5, use Merkle-Damgaard or some other chaining scheme.  Obviously, in the case of MD5, it doesn't prevent the chosen-prefix attack on MD5.


Many single-time use keys encryption scheme (not Shamir's Shared Secret) I'm looking for encryption scheme with the following properties:

There's a sequence of keys that can be used to decrypt the message
Strictly only one key from the sequence is required to decrypt the message
Keys need to be used in the order that is defined by keys sequence
Once used, the key can't be used again to decrypt the message (this implies some kind of transformation of encrypted message as part of the decription process)
It is not possible to derive keys from the sequence based on knowing any number of the keys from the sequence
The encrypted message is kept by third party (e.g. on a server), that
decrypts it for the receiver of the message on request, but only the receiver of the message keeps the sequence of the keys. In case of security breach, if the encrypted messages leak from the storage they're kept on, they're worthless for the attacker, because the third party doesn't keep the sequence of the keys. I know that it would be still possible to steal the message from primary memory when the receiver decrypts it, but the focus is on making the permanent storage of the message safe.

Since you already trust the server to securely delete the plaintext message after decrypting it for a client, you can trust it to delete the encrypted versions too.

So for instance the case of 3 keys K1 .. K3 and plaintext P, store K1(P), K1(K2(P)),K1(K2(K3(P))) since they all start with K1, that is the only key that can be used at first. after K1 is presented, apply it to everything in the series, so you end up with.
P, K2(P), K2(K3(P)). serve up P deleting it and store the rest as your new series for when K2 arrives. repeat the proceduce until the whole sequence and hence all the keys are used up.


How to deliver an encrypted message to multiple recipients without revealing keys Let's say I have generated a private and a public key. I create a message and encrypt it with the public key. I deliver this encrypted message and a private key to multiple recipients.

Why would I do this?

I want to be able to deliver a message that can only be decrypted. I don't want anyone to be able to encrypt a dummy message and deliver this to all recipients with them assuming it was from me.

I think I am on the right track using RSA - but somehow I need it all in reverse.

Also, if I give people the private key, and I keep the public key safe, am I right in believing that it's possible to generate a new public key just using the private key itself?

Let's take an example of my problem.

I create an encrypted message using my public key:

ajjfjdksdjkdfjfjdjfd (made up example).

The end user decrypts it using the private key to:

green:1234:table

All good so far. The above message and be authenticated very basically checked for the three strings within a ":".

However, as these encrypted messages could be from untrusted sources, I want it impossible for any untrusted source to be able to create these messages since they know the simple format. I don't want the key I provide be enough for them to reverse engineer the public key.

I am finding it hard to explain, I am hoping that this can be answered.

Also, if I give people the private key, and I keep the public key safe, am I right in believing that it's possible to generate a new public key just using the private key itself?

Correct. The private key contains the modulus, one or more of the primes, the private exponent and often some other relevant things. The public key is just the modulus and the public exponent, which is usually a small number, often 65537, and can be calculated with the private key even if it isn't.

What you actually need for your problem is authentication. You sign the data (e.g. with RSA-PSS), which you may have encrypted (whether with a symmetric key that you give the recipients or their public keys). The data can even be public if its secrecy does not matter.

The recipients can then use your public key (which they must somehow get first) to verify that the data was signed with your private key. Assuming you do not reveal your key, no one else can forge a valid signature.


Distributing blocks with validation and non-dependant list generation Problem
Suppose I have a system of nodes that can communicate with a parent node, but not among each other. Suppose then a file on the parent node is split up into blocks and divided among the children. The file is then deleted from the parent node.

If the parent were to then request the blocks back from the children, how can the original order be reconstructed without retaining a list of all the files on the parent. Additionally, to prevent one of the nodes from maliciously modifying a block, the parent would also have to validate the blocks coming back.

Optimal Solution
A system of naming the blocks of a file, where the list of files can be generated on any node given a seed. Given the list, a parent should be able to use the list somehow to validate the blocks coming back from children.

Attempt #1
So what I have got so far is the ability to minimally store a list of the blocks. I do so by naming the blocks as such:

block_0 = hash(file_contents)
block_n = hash(block_n-1) [hashing the name of the previous file]

This enables the order of the files to be retained by just keeping the seed (name of block_0), and the number of blocks (e.g. 5d41402abc4b2a76b9719d911017c592,5 --> seed,files). However this will not allow the files to be validated independently.

Attempt #2
Simply take the hash of each block and store that in a list. However this is not efficient and will result in a large amount of memory allocated to this task alone if a large number of blocks need to be tracked. This will not do.

How about embedding each block's MAC to the next? So that $b'_0=b_0||MAC(b_1)$, with the last block having the MAC of $b_0$. To make it even easier to identify a corrupt block, $$b'_n=b_n||MAC(b_{n-1})||MAC(b_{n+1})$$

where $||$ denotes concatenation. To identify the order of the blocks, simply try to fit them together as they come, or embed each block's $n$ to it.


Why are inputs to boolean functions usually modelled as random variables? I ask this because it might one of those things that "everybody knows/does", but never gets written or explained anywhere... Is it just a matter of aesthetics (in the mathematical sense of the word), or is there a more specific (read: practical) reason for doing this? (as opposed to say, talking about a priori and a posteriori probabilities, as Claude Shannon did in his Communication Theory of Secrecy Systems?)

PS: This question might be relevant in the broader field of study of Boolean functions, but I am interested in the case of crypto applications.

PS2: I couldn't find a more suitable tag than "randomness", as "boolean-functions" or "random-variable" do not exist...

Why are inputs to boolean functions usually modelled as random variables?

A bit of clarity is needed here...
the Cook–Levin theorem
says that it is possible to translate each program into a boolean formula, so it is clear that the input of a program is almost never random.

I believe your question refers to binary satisfiability problems.
The formers are extremely important decision problems which are studied in the field of Theoretical Computer Science.
Example of such a problem:

Given an instance $\sigma$ of 3SAT (boolean formula in CNF with exactly 3 literals per clause) is there a distribution of variables such that $\sigma = 1$ ?
This decision problem is known to be NP-complete.

Why are they so important? well, for so many reasons that it is impossible to list all of them but the main ones are two:

circuit design/algorithm design:
Each Boolean formula corresponds to a circuit and to a Turing Machine (algorithm), so it is useful to know which formulas produce results and which ones are blind alleys (contradictions).
NP-completeness: KSAT (with $K \geq 3$) is known to be NP-complete,
which means that every other problem in the complexity class NP (nondeterministic polynomial time) can be reduced to an instance of SAT, therefore it is useful to have efficient algorithms for it.
Unfortunately, an efficient (polynomial time) algorithm is not yet known. Finding it would prove that P = NP and would guarantee the discoverer a million dollar.

Regarding cryptography, someone has proposed cryptographic methods based on sat
but, perhaps taken by enthusiasm, they had not thought that creating a public key based on an instance of SAT could be as expensive and intractable as validating the instance itself.


Quantum Resistance Characteristics - why symmetric? I have heard that public key cryptography may be “totally broken” by Quantum computers running Shor’s algorithm, whils symmetric key ciphers are safe, but Grover’s algorithm may require twice as many bits in the keys.

Can someone please elaborate on what exactly is going on underneath, to say these things? What exactly does Shor’s algorithm do and how bad is it? How exactly are symmetric key ciphers not susceptible to this? How do we know we can’t do better than Grover’s algorithm later, making ALL ciphers susceptible? And finally, if you can fit it into your answer, what are the measures taken by the latest public key ciphers submitted to NIST that purport to overcome these problems?

I have heard that public key cryptography may be “totally broken” by Quantum computers running Shor’s algorithm

Cryptosystems based on discrete logarithms and factoring are vulnerable to Shor's algorithm.

These cryptosystems do not comprise the entirety of "public-key cryptography", because "public-key cryptography" includes digital signatures, not just public-key encryption and key agreement.

The following types of cryptosystems are not completely broken by quantum algorithms:

Hash-based digital signatures
Code-based systems (e.g. McEliece)
Lattice-based schemes
Multivariate schemes

So "public key cryptography is totally broken by quantum computers" is too broad of a conclusion.

It is more accurate to say "The most common schemes such as RSA, DH, and ECC are broken again quantum computers, but there are more schemes in existence then just those three."

  ...while symmetric key ciphers are safe, but Grover’s algorithm may require twice as many bits in the keys.

This is more or less accurate. There is some debate whether or not an actual doubling of key sizes is strictly necessary. And it should be noted that Grover's algorithm also influences hash functions.

  Can someone please elaborate on what exactly is going on underneath, to say these things? What exactly does Shor’s algorithm do and how bad is it?

What does it do

Shor's algorithm uses a combination of a classical computation algorithm and the quantum fourier transform to factor numbers.

The problem of integer factorization is hard when the product to be factored consists of large prime numbers. A typical RSA modulus consists of two large prime numbers multiplied together $N = p * q$.

Shor's algorithm uses the quantum fourier transform to find how long it takes $f(x) = a^x \bmod N$ to cycle through all the possible outputs back to the beginning. So it looks for an $r$ such that $a^{x + r} \bmod N \equiv a^x \bmod N$, with the additional condition that $r$ is even so that $r/2$ can be obtained. The rest of the algorithm actually uses classical computation, finding the value of $r$ is the hard problem that the quantum algorithm solves. Finally, $gcd(a^{r/2} + 1, N)$ and $gcd(a^{r/2} - 1, N)$ are both nontrivial factors of $N$. (Where "nontrivial" means "not counting $1, N, -1, -N$", because those aren't helpful). The complete algorithm can be found in the wikipedia article about Shor's algorithm.

You can also use Shor's algorithm to compute discrete logarithms, which breaks Diffie-Hellman type cryptosystems. I don't understand the details of how to do so, so I will refrain from going into details.

How bad is it?

  On a quantum computer, to factor an integer $N$, Shor's algorithm runs in polynomial time (the time taken is polynomial in $log\ N$, which is the size of the input)

It's bad. We really need the best attack to take exponential or at least sub-exponential time in order to have security with reasonable and practical sized values. A polynomial time algorithm for solving a problem basically makes that problem not useful for cryptography. Of course, you can technically try to use (much) larger parameters to make up for the difference... but that's not nearly as practical or graceful as we would like.

How exactly are symmetric key ciphers not susceptible to this?

The ability to find the period of a function is not necessarily useful for breaking a symmetric cipher. In order to do anything, you would need access to (at least) an encryption oracle. There is a paper about using Simon's algorithm to break symmetric modes of operation, but the attack model they use is pretty powerful: The adversary must prepare a superposition of all possible plaintext-ciphertext pairs, which is not trivial.

Basically, symmetric block ciphers and stream ciphers tend to use highly non-linear components which destroy any useful relations between inputs/outputs. Asymmetric designs tend to rely on such relations in order to achieve their goals. This means that asymmetric designs tend to incorporate more structure, and the structure can be exploited as a weakness.

How do we know we can’t do better than Grover’s algorithm later, making ALL ciphers susceptible?

Because it has been proven that:

  ...any quantum solution to the problem needs to evaluate the function $Ω(\sqrt{N})$ times, so Grover's algorithm is asymptotically optimal.

What are the measures taken by the latest public key ciphers submitted to NIST that purport to overcome these problems?

They are built on problems that are not known to be vulnerable to quantum algorithms. Using non-abelian groups seems to be helpful in regards to resisting quantum algorithms.

Note that "not known to be vulnerable" does not mean "It is proven that there cannot exist a quantum algorithm that solves the problem", it just means that there is no publicly known quantum algorithm for solving these types of problems.


What is the run-time on finding collisions with MACs,...? I've recently read the claim that finding collisions on block cipher may be not a difficult task, if an attacker can control the key and the message.

So, given a pseudo-random function $f:\{0,1\}^m \times \{0,1\}^{l_0} \times ... \times \{0,1\}^{l_k}\rightarrow \{0,1\}^n$, what is the expected run-time for finding a collision?

$f$ may be any MAC or anything similar.

For $m>n$ and without any other input the answer is trivially $\mathcal O(\sqrt{n})$ (standard hash function), but do the additional inputs change anything?

For blockciphers the case usually is trivial, as second pre-image security is easily broken. Given a pair $(M_1,K_1)$ one can compute $(D_{K_2}(E_{K_1}(M_1)),K_2)$ to trivially obtain a collision.

What is the run-time on finding collisions with MACs...

Well, the definition of a MAC is of the form "if you don't know the key, then it is infeasible to ...".  This definition does not assert anything if you do know the key (or are able to select it); hence it does not provide any nontrivial lower bound.

In particular, with common MACs (e.g. CMAC, Carter-Wegman MACs), it is trivial to generate second preimages.  For CMAC, we can actually generate preimages; we just select an arbitrary prefix (of a multiple of the block length), and compute what the last block needs to be to generate the target image.  For Carter-Wegman MACs, we can generate second preimages by looking into the almost universal hash function, and trivially generating a second message that produces the same hash for the given key (at least, for every au hash I've heard of).

On the other hand, we come to HMAC.  For HMAC, we can generate collisions between two different keys in two ways:

If HMAC is given a short key (no longer than the hash block size), it xor's it into the IPAD/OPAD patterns.  That implies if we append a zero byte to the key, say, $K_2 = K_1 || 00$, then the result of the xor's will be the same, and so $HMAC(K_1, M) = HMAC(K_2, M)$ for any $M$.
By taking advantage that, if the key is longer than the hash block size, HMAC first hashes the key, and then uses that hash as the key.  Hence, we can select two different keys, $K_1$ (which is long), and $K_2 = Hash(K_1)$, then we have $HMAC(K_1, M) = HMAC(K_2, M)$ for any message $M$.

If we disallow those approaches (and perhaps say that the keys must be the same length), then it is easy to see that finding a collision with HMAC is no easier than finding a collision in the underlying hash function (as a collision in the HMAC will imply a collision in either the upper or lower hashes of the HMAC, or in the hash that preprocesses long keys).

So, bottom line: the definition of MAC does not ensure making finding collisions (assuming the attacker knows the key) difficult; we can find MACs (such as HMAC with a fixed length key) where it is believed to be difficult; we can also find MACs where it is easy.


Itoh Tsuji algorithm I'd like to use the Itoh-Tsujii algorithm for a dynamic substitution table, but I do not get the following line:
$$r\ \gets\ (p^m - 1)\,/\,(p - 1)$$

And why can $r$ be used to calculate the multiplicative innverse of a number in a Galois field containing $p^m$ elements by calculating it in the field $GF(p)$ and use this result to calculate the inversion in the $GF(p^m)$ field?

I have recently detailed the use of Itoh-Tsuji in the article on Curve9767 (section 3.6).

In the description below, I write elements of $GF(p^m)$ as polynomials in $GF(p)[z]$, taken modulo a given irreducible unitary polynomial $M$ of degree $m$ (since all finite fields with the same cardinal are isomorphic to each other, the choice of a specific $M$ has no importance for security, but some choices of $M$ allow for better performance, as will be shown below). We consider the problem of computing the inverse $a^{-1}$ of a given element $a \in GF(p^m)$ (with $a \neq 0$).

$p^m-1$ is a multiple of $p-1$; in fact, the quotient is:
$$ r = \frac{p^m-1}{p-1} = 1 + p + p^2 + p^3 + \cdots + p^{m-1} $$
For any $a \in GF(p^m)$ distinct from zero, we can express the inverse of $a$ as:
$$ a^{-1} = \frac{a^{r-1}}{a^r} $$
This is true for any integer $r$, but for $r = (p^m-1)/(p-1)$, this leads to fast inversion thanks to two main facts, detailed below.
Fact 1: $a^r \in GF(p)$. Indeed, $(a^r)^{p-1} = a^{p^m-1} = 1$ (since $p^m-1$ is the order of the group of invertible elements in $GF(p^m)$). Thus, $a^r$ is a root of the polynomial equation $X^{p-1} - 1 = 0$. However, all non-zero elements of $GF(p)$ are roots of that polynomial (by Fermat's Little Theorem), and there are $p-1$ non-zero elements in $GF(p)$, and $X^{p-1} - 1$, being a polynomial of degree $p-1$ in a field, cannot have more than $p-1$ roots. Therefore, the roots of $X^{p-1}-1$ are exactly the non-zero elements of $GF(p)$, and $a^r$ is one of them.

This implies that inverting $a^r$ is much easier than inverting in general an element of $GF(p^m)$, since we can work in $GF(p)$. There are various methods for computing inverses modulo $p$, but if $p$ is small, Fermat's Little Theorem works well (i.e. raising $a^r$ to the power $p-2$).
Fact 2: computing $a^{r-1}$ is inexpensive, thanks to the Frobenius automorphism. The $j$-th Frobenius automorphism (for $j >= 0$) is:
\begin{eqnarray*}
\Phi_j : GF(p^m) &\longrightarrow& GF(p^m) \\
a &\longmapsto& a^{p^j}
\end{eqnarray*}
i.e. $\Phi_1$ is just "raising to the power $p$", and $\Phi_j$ is "applying $\Phi_1$ exactly $j$ times".

This operator is a field automorphism: $\Phi_j(ab) = \Phi_j(a) \Phi_j(b)$ and $\Phi_j(a+b)$ = $\Phi_j(a) + \Phi_j(b)$ for all $a, b \in GF(p^m)$. This makes it linear (if we interpret $GF(p^m)$ as a vector space of dimension $m$ over $GF(p)$) and thus reasonably easy to compute: if:
$$ a = \sum_{i=0}^{m-1} a_i z^i $$
then:
$$ \Phi_j(x) = \sum_{i=0}^{m-1} a_i \Phi_j(z^i) $$
Moreover, if $GF(p^m)$ is defined with a modulus of the form $M = z^m - c$ for some constant $c \in GF(p)$ (there are constants $c$ that ensure that $z^m-c$ is irreducible, as long as $m$ divides $p-1$), then $\Phi_j(z^i) = c^{ij(p-1)/m}$, and applying $\Phi_j$ on any value $a$ becomes a matter of multiplying the $m$ coefficients $a_i$ of $a$ by $m$ constants that are easily precomputed. This makes $\Phi_j$ inexpensive (much cheaper than a single multiplication in $GF(p^m)$).

For any $a \in GF(p^m)$, we can compute $a^{r-1}$ by using a few multiplications and Frobenius operators:
\begin{eqnarray*}
t_1 &=& \Phi_1(a) &=& a^{p} \\
t_2 &=& t_1 \Phi_1(t_1) &=& a^{p+p^2} \\
t_3 &=& t_2 \Phi_2(t_2) &=& a^{p+p^2+p^3+p^4} \\
t_4 &=& t_3 \Phi_4(t_3) &=& a^{p+p^2+p^3+p^4+\cdots+p^{8}} \\
& & \ldots & &
\end{eqnarray*}
With about $\log m$ multiplications and applications of a Frobenius operator, one can obtain $a^{r-1}$.

Using all of the above, the complete inversion algorithm of $a \in GF(p^m)$ is then:

Using multiplications and the Frobenius operators, compute $a^{r-1}$.
Multiply $a$ by $a^{r-1}$ to get $a^r$ (this multiplication is made easy because we know that the result is in $GF(p)$, so we have only one coefficient to compute; the other ones are all zero).
Invert $a^r$ in $GF(p)$ (using for instance Fermat's Little Theorem).
Multiply $a^{r-1}$ by $a^{-r}$ (this multiplication is also easy, since $a^{-r} \in GF(p)$).

In Curve9767, which uses the field $GF(9767^{19})$, I can get the complete cost of the inversion down to about 6 to 7.7 times that of a multiplication in $GF(p^m)$, which is fast enough to seriously contemplate the use of affine coordinates for the operations on the elliptic curve. By comparison, usual algorithms for inversion modulo a 256-bit integer $n$ will take between 50 and 300 times the cost of a multiplication modulo $n$.

All of that is said in the generic context of $GF(p^m)$. Itoh and Tsuji first described it for $GF(2^m)$, i.e. with $p = 2$, in which case the Frobenius operator $\Phi_1$ is simply "squaring". Moreover, with $p = 2$, inversion in $GF(p)$ is a no-operation (since $GF(2)$ has only a single non-zero element, which is $1$, and $1$ is its own inverse), so $a^r = 1$; the inversion of $a^r$ and the multiplication by $a^{-r}$ can then be skipped. On the other hand, with $p = 2$, the modulus $M$ cannot be $z^m-c$ for some $c \in GF(2)$ because neither $X^m$ nor $X^m-1$ is irreducible over $GF(2)$, and you need an irreducible modulus to get a field. This makes the Frobenius operators somewhat more complex to compute (but still quite efficient).


How to encrypt 1-to-1 chat application for dummies A bit of a general question from someone who is pretty much a rookie when it comes to cryptography:

So I have an app where users are able to chat with each other 1-to-1 (no group chats). Currently the app stores all messages as plaintext in the db for backup, so that each time a user connects to the chat they are synced with what is in the db. I would like to figure out how to store the messages in the db in a way that they are only readable by either of the participants in the chat.

Could you guys point me in the right direction in terms of what type of encryption to use? Is Public Key Cryptography suitable for this use case?

There are two solutions which vary in their integration complexity but also in their feature-set.
Solution 1: The Signal Protocol
The Signal Protocol is, well, the protocol used by the famous Signal-Messenger and which was also adapted in quite a few other popular messengers such as WhatsApp. It is designed to perform best in the situation you're in: asynchronous chat applications. As such it ensures forward secrecy and allows to confirm other parties at any point. As a bonus there's the famous libsignal which should greatly ease implementation.
If you can this is absolutely the solution you should take.
Solution 2: E-Mail Encryption methods
If however integration of the Signal Protocol proves impossible for your deployment, the usage of standard E-Mail encryption methods should still work. Basically you let each party generate public-private keypair(s) and then use your favourite PGP encryption and signing library to sign and encrypt the message as if they were emails or you could use your favourite S/MIME library to do the same. However this doesn't provide forward secrecy and gives non-repudiation to the messages (ie "everyone" can verify that X send the message Y). Key confirmation can be solved by your provider (for when the users trust you) and by comparing key hashes by the users if they meet in person.
This is the second best solution which you should implement if the Signal Protocol really isn't an option.


Do Export Restrictions Still Apply To The Key Length of RC4? I've just read a paper from 2004 which stated that the RC4 encryption algorithm was restricted to a 40 bit key size when exported from the USA; however the reference for this information (Applied Cryptography - Schneieir) was published in 1996.

Here's the link to the paper "The effectiveness of brute force attacks on RC4".

I'm relatively new to cryptography but as far as I'm aware, a lot of the old export laws have been relaxed. Was the key length of RC4 still restricted in 2004? If so, is that still the case?

Thanks for any help.

Afaik, the general export restrictions on keylengths of common ciphers were lifted during the Clinton administration. Here's the relevant wiki article.


Perfect Secrecy for two distinct messages We say that and encryption scheme $\pi$ is perfectly secret for two distinct messages, if for all distributions over $\mathcal{M}\times\mathcal{M}$ ($\mathcal{M}$ is the message space), for all $m_1,m_2\in\mathcal{M}$ such that $ m_1\ne m_2$ and all $c_1,c_2\in\mathcal{C}$ (where $\mathcal{C}$ is the cypher text space) such that $\text{Pr}[C_1=c_1\wedge C_2=c_2]>0$ then $$\text{Pr}[M_1=m_1\wedge M_2=m_2|C_1=c_1\wedge C_2=c_2]=\text{Pr}[M_1=m_1\wedge M_2=m_2]$$

I am trying to come up with an encryption scheme that satisfies this definition. So far this is what I have come up with

Say $\mathcal{M}=\{0,1\}^l, \mathcal{K}=\{(0,1),(1,0),(0,0),(1,1)\}^l, \mathcal{C}=\{0,1\}^l$

$k\leftarrow\text{Gen}(\mathcal{K})$

Now let $m_i$ denote the $i^{th}$ bit of $m$.

Let $c_i$ denote the $i^{th}$ bit of $c$.

And let $k_{il}$ denote the $l$ bit of the $i^{th}$ pair in $k$ and  (l=0 for the first, l=1 for the second)

$\text{Enc}_k(m):$ For all $m_i$ in $m$ (iterating through bits)

if $m_i=0$:
    $ c_i=m_i \oplus k_{i0}$

else: $c_i=m_i \oplus k_{i1}$

Return $c$

$\text{Dec}_k(c)$: For all $c_i$ in $c$ (iterating through the bits of $c$)

if $c_i=1$:
    $m_i=m_i \oplus k_{i0}$

else: $m_i=c_i \oplus k_{i1}$

Return $m$

Does this work? I feel like it should because essentially what we've done is essentially create a key that can perform a one-time pad twice safely

Let $m_i := 0$ and $k_i := \langle 0, 1 \rangle$. Then $c_i = Enc_{k_i}(m_i) = m_i \oplus k_{i0} = 0\ \oplus\ 0 = 0$. But then $m'_i = Dec_{k_i}(c_i) = c_i \oplus k_{i1} = 0\ \oplus\ 1 = 1$, and we have $m_i \neq m'_i$. The same holds for $m_i := 1$ and $k_i := \langle 1, 0 \rangle$. So your encryption scheme might give perfect secrecy, but it does not allow you to decrypt the message.

This is because your encryption scheme effectively loses information from the message when encrypting with a key of $k_i = \langle 0, 1 \rangle$ or $k_i = \langle 1, 0 \rangle$, and for these keys the ciphertext $c_i$ is solely determined by the key:

$Enc_{\langle 0, 1 \rangle}(0) = 0\ \oplus\ 0 = 0\\
Enc_{\langle 0, 1 \rangle}(1) = 1\ \oplus\ 1 = 0\\
Enc_{\langle 1, 0 \rangle}(0) = 0\ \oplus\ 1 = 1\\
Enc_{\langle 1, 0 \rangle}(1) = 1\ \oplus\ 0 = 1$

If you reduce the keyspace to $\mathcal{K} = \{\langle 0, 0 \rangle, \langle 1, 1 \rangle\}^l$ you effectively have a regular one-time pad.


How to select a good scale for letter frequency in a text? I needed to use a scale in a code to determine which sentence in a file has been encrypted by a single-character key.

The scale that i currently used is:
+2 for every occurrence of a vowel or a space and +1 for other alphabets, numbers and some characters.
The sentence with the maximum value using above scale helped me in finding the solution.

Is there some standard scale used by cryptographers based on character frequency?

You can compute a statistical distance measure between the observed letter frequencies in your candidate plaintext and the typical letter frequencies in English text.

There are a number of different ways to measure the similarity between two statistical distributions, and I'm not aware of any theoretical or empirical studies on which of them would be optimal for recognizing correctly decrypted plaintext.  However, in practice, the specific choice of distance measure seems to be of secondary importance compared to things like the amount of ciphertext available, knowledge of the nature of the plaintext, and the choice of which statistical features of the plaintext (e.g. individual letter frequencies, pair frequencies, vowel/consonant frequencies, etc.) to measure.

Thus, I'd suggest starting with something simple, like the total variation distance, which can be calculated simply by taking the difference between the observed and the expected frequency of each letter and summing their absolute values together, or the $\chi^2$-divergence, for which you need to sum the squares of the differences between the observed and the expected frequencies, divided by the expected frequency.

The full formulas also involve some constant factors that only depend on the message length, but for simple comparison purposes, the raw sums are enough.  The $\chi^2$ distance is particularly useful if you need to estimate the absolute likelihood of a message being generated according to some given (e.g. uniformly random) distribution, although this requires some additional steps that are not needed for simple ranking by relative likelihood.


Repeated Vignère Cipher I was looking into the Vignère Cipher when I thought of something.

Would you improve the security of the cipher if you shifted each letter (from the text you want to encrypt) with each letter of the key?

Also, given that the mathematical expression of the cipher is:

  $$C_i = E_K(M_i) = (M_i+ \sum_{i=0}^{l-1}K_i) \pmod {26},$$ where $l$ is the lenght of the keyword $K=K_1K_2\ldots K_l$.

(the encryption part anyway)

How would you express the concept I just explained mathematically?

Do you mean that if you have a key of length $l$ say $k_1, ..., k_l$, and a plain $m_1, ..., m_n$, that you want to do $c_i = m_i + \sum_{j=1}^l k_j$ ? (Each plain letter is added with each key letter)

If this is the case, this is exactly like doing a Caesar cipher with 1 shift for all of the letters.


Methods of Learning Cryptography We're currently approaching the end of our semester, but I've found that our homework is starting to consist more of encrypting and decrypting using different types of algorithms instead of learning any other core fundamentals. Even though we've switched over from symmetric to asymmetric algorithms. I'm wondering if we're missing any other core fundamentals in a semester of learning cryptography? We've seemed to just focus on different types of algorithms this entire semester along with what aspects of cryptanalysis they meet. What else are we missing? (This is for personal use to learn more on the side)

Learning Cryptography in academic is something between science and practice. For science part,the aim is to studying and focus on topics related to cryptographic primitives(building block of cryptographic protocols).Based on categorizing these primitives, we can learn them easily:

Unkeyed primitives-----> Arbitrary Hash Functions,One way permutation,Random sequences
Symmetric-key primitives ----->Symmetric ciphers(Block ciphers,Stream ciphers),Arbitrary length hash functions(MAC),Signatures,Pseudo-random sequences,Identification primitives
Public-key primitives------->public-key ciphers,signatures,Identification primitives.

In this category, fundamental Topics like signatures, Hash,Identification,Pseudo-random sequence generators highlighted. Also topics such as Authenticated encryption,secrete sharing and subjects related to key-management based on cryptography.

In the practice part, the intention is to design and implement a cryptosystem, which means that use the logic of cryptographic primitives in an algorithm and then evaluate its soundness based on mathematics. In this side, we can name topics as cryptanalysis and attacks(theoretic  and implementation),methods for designing a cryptosystem,Lightweight cryptography and ways of implementing ciphers and cryptosystems in different devices.

At the end, examination of different ciphers and cryptosystems, gives analyse and design method ideas and also the way of using them in real world.


Idea for secure password hash-likes, is this feasible/usable/workable? (Hand moved from stackoverflow.com,due to suggestion)

Since breaking password hashes has become a new passtime for scriptkiddies, I thought of the problem and came up with a novel(?) idea.

store the pass as offset+number instead of hash
the number is a product of two large primes
the password is converted into a number , offset is added and that prime is used to divide the number. If it divides AND the divisor is the larger of the two primes the password is correct.

by definition , each hash is unique and each password can be hashed in many different ways depending on the offset. Breaking one hash means you have to factor the number(which is hard), then find a word which corresponds to a number that is largerprime-offset (which is trivial).

To generate use function f() to turn password into a password-number (not important) , generate two random primes larger than 2^4096 or however much is enough. Take the larger prime and calculate prime-passwordnumber=offset. Multiply the primes to get "number". store number and offset.

To check. use function f() to turn password into a password-number, add offset to find prime. divide number with prime to get the other prime. Check that the first prime was the bigger of the two. If so, password was correct.

f() might be for example utf-8 encoding of the password understood as a large binary integer.

I don't see anything horribly wrong with your proposal.  On the other hand, the obvious question would be "what advantage would this approach have over, say, PBKDF2 with a good salt"?

In your proposal, it is infeasible to recover the password from the hash (short of brute-force); that's also true of PBKDF2.
In your proposal, the hash is randomized (and so the same password doesn't always result in the same hash); that's also true of PBKDF2.

In addition, in your proposal, generating a hash is moderately expensive (it isn't cheap to find large random primes); with PBKDF2, it's no more expensive than validating a password.  I can't see any reason why you'd want to make generating a hash an expensive operation.

Given that this proposal doesn't appear to have an advantage over well-accepted techniques, I can't recommend it.


Malicious DH parameters without using composite numbers I know that it's possible to generate DH parameters that lead to it being easy to attack (e.g. trivial composite numbers), but is it possible to create a malicious parameter that is not a composite number (and thus passes an arbitrary number of Miller-Rabin tests) but still makes attacking the DH group easy? It should be trivial to detect if the parameters have been generated to intentionally fall victim to the small subgroup attack, and the SNFV becomes impractical with realistic key sizes.

Questions similar to this have been asked before, but they seem to focus on composite numbers.

[Update: See this answer to another question for an example of a back door that can't be detected, but can probably be excluded by demanding a rigid process like RFC 2412 as was used for all the RFC 3526 groups.]

If there were a known way to put a back door into Diffie–Hellman parameters, it would be excluded by standard criteria for selecting them.  poncho's answer to the question you cited provides some examples of criteria we normally use and how to test them and what goes wrong if you don't; there are a couple more references in an answer I wrote.

For finite-field DH, there's little reason to use anything other than the RFC 3526 groups, which use a modulus of the form $$2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi \rfloor + c)$$ where $c$ is the smallest nonnegative integer making this number a safe prime congruent to 7 modulo 8.

For elliptic-curve DH, there's little reason to use anything other than X25519 or X448 except perhaps in exotic applications where essentially the same security criteria might be applied to maximize other performance objectives.


What's the difference between PBKDF2 and HMAC-SHA256 in security? Being a software developer, I haven't dealt with crypto so far. So I know very little, sorry for that already.

I am aware that you should use bcrypt, scrypt, Argon2 or PBKDF2 for generating a hash from a password. However, I have a question about PBKDF2.

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

PBKDF2 uses a pseudorandom function, for example HMAC-SHA256.

What I understand is that PBKDF2 uses HMAC-SHA256 for c iterations. Why not just use HMAC-SHA256 directly?

I know that you should not use SHA256 for passwords because it's basically "too efficient". So, is HMAC-SHA256 way less efficient, and if so why cannot we use it direclty?

Why does PBKDF2 need a PRF?

Perhaps you can explain it so that even I, who has not much to do with crypto stuff, can understand it. ;-)

HMAC is still very efficient. It's used in PBKDF2 not for the lower efficiency (that's handled by iterating it many times) because of the fact that it takes two inputs. That lets the password and other data be combined in a safe manner, invlunerable to some of the issues that just using SHA256 alone could create.

PBKDF2 isn't doing H(H(H(...H(Pwd + salt))...), it's doing HMAC(Pwd, HMAC(Pwd, ... HMAC(Pwd, Salt + number)...), where + denotes concatenation and the number is a block index. So the iterations use the password as the key for the HMAC in each stage, and stages other than the first are HMACing the output of the previous stage. This mixes the password in to every iteration of the result, instead of just the first iteration.

Hopefully that explains both why HMAC alone isn't enough and the obvious follow-up question of why HMAC instead of just SHA-256.


Non-numeric Diffie-Hellman? It may seem that this is a programming question, but I just need advice on the cryptography side of the question. I want to implement the Diffie-Hellman key exchange algorithm on iOS (since no free library with easy integration exists). I'm wondering how the implementation would be if the parameters would be – for example – 128 bytes of data, instead of integers.

I'm looking for instructions so that I find out how I should implement it because performing such operations on non-integers is quite ambiguous to me.

Sorry if it's a newbie question, but I'm new to this concept.

Any suggestions is really appreciated.

Diffie-Hellman relies on a mathematical problem on positive integers. To use it with bytes you just have to convert the bytes to - or use the bytes as - an integer. Usually this would be a unsigned big-endian (or network order) integer.

For Diffie-Hellman the parameters consist of the modulus and the base. The public value could be 1024 bits (128 bytes). 1024 bit cryptography is considered "legacy strength" for discrete logarithm related problems though.

With Java for instance the conversion can be as easy as new BigInteger(1, data) where 1 indicates a positive integer and data is a byte array.


Understanding how padding works when using Block Cipher I'm trying to understand how padding works when using block ciphers.

  Padding may be required when the size of the plain text is not a multiple of the block size

If that's so, then I don't understand the results I am getting on my Ubuntu VM.

I created a .txt file in size of 20 bytes, encrypted it using AES128-ECB. I then ran a command to check the encrypted .bin file size and it was 32 bytes as expected.

What I don't understand is the following scenario — I created another .txt file, this time in size of 32 bytes, encrypted it using same method and when I checked the encrypted file's size I got 48 bytes and not 32.

My question is why is it I am getting 48 bytes instead of 32? Obviously this time the plain text's size was a multiple of the block size and yet it treated it as if it wasn't.

The padding scheme being used in your example for the block cipher is PKCS#7 Padding.

This scheme specifies that:

  The value of each added byte is the number of bytes that are added, i.e. N bytes, each of value N are added.

The thing is, if the plaintext is multiple of the block size, then a whole new padding block is added. In this case it will be a block of 16 bytes with value 16.

   This is necessary so the deciphering algorithm can determine with certainty whether the last byte of the last block is a pad byte indicating the number of padding bytes added or part of the plaintext message.

That's why your ciphertext has a size of 48 bytes when the plaintext is 32 bytes. That is one ciphertext byte for each plaintext plus a whole new block of padding


Must the ciphertext be longer than the key for symmetric encryption? I am planning to encrypt the different fields of a database independently, using a symmetric encryption scheme (probably 3DES). Since some of the fields are as small as an integer, may that be problematic?

From the point of view of security, there is no problem with a key being longer than the ciphertext – 3DES has a 168-bit keysize and a 64-bit blocksize so for small messages it results in a ciphertext shorter than the key (at least without counting an IV).

However, in most block cipher modes the message gets padded up to a multiple of the blocksize, so a single 16-bit integer would result in at least 64 bits of ciphertext. That can get a bit inefficient if you have a lot of very small fields.


How does authentication work for SSH login with a public key? For SSH public key authentication in Cisco IOS it is sufficient to add RSA public key hash instead of content of that public key.

For example:

ip ssh pubkey-chain
  username admin
  key-hash ssh-rsa 539197BB0F11CE77A123334A97859E30 admin@server

From cryptography point of view, how does authentication actually work in such a case – public key hash on one side with corresponding private key on another?

I thought that we have to have a pair of keys exactly. Not a public key's hash on one side and a private key on another.

The goal of authentication is to verify the identity of a party to communication, i.e. to check that they are who they claim to be. Two parties are involved: the verifier, and the requester. Here the verifier is the server and the requester is a remote user, but in other cases they could have different roles.

Authentication using asymmetric cryptography involves several steps of reasoning.

Only the legitimate requester knows the private key. Everybody else is unable to make computations that require the private key.
The verifier is able to tie the public key with an identity. Maintaining the association between the public key and the identity is the responsibility of the verifier. In this case, the association is made through a configuration file on the server that says “the public key whose has is … is user #42 authorized to log in as admin”.
In order to be authenticated by the verifier, the requester must perform a computation that requires the private key corresponding to a public key. This can be either a signature that the verifier verifies, or an encryption whose result the verifier decrypts.
The combination of (1), (2) and a successful (3) allows the verifier to conclude that the requester has the identity associated with the public key.

In order to perform step 2, the server needs to have the public key. But it doesn't need to store the public key. It's ok if the requester sends the public key. The verifier calculates the hash of the public key sent by the requester and compares it with its stored hash. If the hash is correct then the requester has proved the association between the public key and the identity (because it's unfeasible to find a public key with the same hash as the expected one). When the requester proves that they know the associated private key, they have thus proven their identity to the verifier's expectations.

In a nutshell, it's ok for the verifier to store only a hash of the public key because:

functionally, because the requester sends the public key;
in terms of security, because knowing the hash allows the verifier to validate the public key.

This principle of hashing a public key is used all the time on the web, when browsers authenticate websites (so in this scenario, the requester is the website and the verifier is the browser). On the web, there's an extra step where a browser doesn't even know the hash of the website's public key before connecting. What the website sends in addition to its public key and to the proof of possession of the private key is an assertion of the form “this is the hash of the public key of www.example.com”, cryptographically signed by a certificate authority that the browser trusts. This assertion is called a certificate. (In fact, things are more complicated, but I gave the basic principle.)


Ciphertext with uneven letter distribution I have a ciphertext encrypted with an unknown method. It is part of a challenge (personal quest), so I can not post it.
The letter statistics is the following:

y : 10
w : 8
x : 8
t : 5
v : 5
e : 5
c : 5
d : 5
u : 4
z : 4
f : 3
b : 2

Because of the uneven letter distribution and repeating two letter sentences, I tried to approach as a monoalphabetic substitution cipher without luck. I tried manually and also with this python code.

The previous challenge was a Caesar cipher, so I do not expect any complicated method. Are there other encryption methods which produce such a letter distribution?

UPDATE: I am no more interested in this challenge. Here is the whole question, if someone is interested:

This is your first personal quest. Decipher it in order to access Level Two!
But before that, a little something to put you on rails. Easy as 1-2-3:
hotstteitmegpdnoctnooruglsmloabsnheismralgyeasjlsacshhlwssznlusmablesrafhosuprh

Don't fear the random(). Some even seek for it...
VXZDVWWWFYBWYWWCEUWWFXZXZUEYDTETXTXYZDVXVYDYBCYECTXYYDCEFUTUCXVY

I would have expected Vigenère and Playfair ciphers to reduce the skew in the letter distribution, so I think you can rule them out for the time being. Here are some other things you could consider:

Perhaps one of the letters corresponds to a space:

  hello world → itssgxvgksr

Perhaps there is no letter "e" in the plaintext

  A Void by G. Adair → Q Cgor wn U. Qrqok

Perhaps the text was encrypted using a monoalphabetic cipher with homophones (so that two or more letters in the ciphertext correspond to the same letter in the plaintext)

  hello world → itxyg vgkxr

Perhaps the text was encrypted with an additional transposition step

  hello world → itssgvgksr → isggstsvkr

If the ciphertext contains mixed upper and lower case letters, then perhaps it's just been Base64 encoded:

  hello, world → aGVsbG8sIHdvcmxk

If the letters are printed using different styles (e.g., different colours or sizes), then perhaps this is a Baconian cipher

  hello → 00111 00100 01011 01011 01110 → rrvuv ysljq akjsz amshc wvieh


Is it safe to encrypt random data using ECB mode? If I have 48 random bytes, is it safe to encrypt them using ECB mode? Or is there still a good reason to use another mode like CTR, CBC, etc.?

Context is this: I am creating something like a TLS session ticket where the master secret is encrypted using a server side key and sent down to the client.

I will still use HMAC. Basically, I use ECB of these 48 bytes followed by HMAC-SHA256 of the ciphertext. I have nothing against CBC, CTR, etc. But a colleague mentioned that for completely random values you can use plain ECB too and I fail to see how he's wrong.

ECB leaks if blocks are identical. For uniformly random data identical blocks become likely when you encrypt about $2^{n/2}$ blocks with an $n$ bit block cipher. CBC and CTR mode develop similar weaknesses when they encrypt that much data.

=> As long as you encrypt reasonable amounts (up to a petabyte or so) of random data with a 128 bit block cipher, like AES, a passive attacker doesn't learn anything useful from observing your ECB encrypted messages.

Still I see little reason to use ECB when you could use something stronger. You're coupling the security of your encryption to assumptions about the data you're encrypting. If a future version of your software changes the properties of the data, you need to remember that you need to replace the encryption.

Against active attackers you need to add some kind of MAC, either via a generic encrypt-then-mac combination or by using an authenticated mode of operation, like GCM.


RSA - Recover private key if each letter is encrypted separately and we got n,e,m I'm curious if is it possible to recover a private key from insecure RSA implementation - each letter of the plaintext is encrypted separately (and no padding).
Let's say I have plain-letters, cipher-letters (for every value of plain-letters), public key $(e, n)$.
I know that it is insecure usage of RSA, but I want to know if it is possible to somehow calculate the private key which was used to encrypting.
If I understand RSA correctly we could have 256 equations (for every ASCII character):
\begin{align}
m_0 &= {c_0}^d  \bmod  \\
m_1 &= {c_1}^d  \bmod   \\
m_2 &= {c_2}^d  \bmod   \\
\vdots & \quad \vdots\\
m_{254} &= {c_{254}}^d  \bmod   \\
m_{255} &= {c_{255}}^d  \bmod  \\
\end{align}
We only don't know d. I read about CRT but seems like not applicable here. Can somebody explain/point if is it possible?

Encryption letter by letter without padding is very insecure, at best as a mono-alphabetic substitution cipher. But no, it practically does not help one recover a private key matching a known public key. As far as we know, the least costly general method involves factoring the public modulus $n$ part of the public key.
An exception: for extremely small $n$ and/or pathological choices of $(n,e)$, a working private key $(n,d)$ sometime is $(n,e^k)$ for some small integer $k\ge0$. Thus trying a few small $k$ with the help of a few plaintext/ciphertext pairs might be a viable strategy. Silly exercises where $d=e$ or even $d=1$ works are not unseen. And it's common that $d=e^2$ or $d=e^3$ works in exercises that encrypt letter by letter using a 3-digit $n$.

Recovering a working private key $(n,d)$ is not the same a recovering the private key $(n,d)$. For the later, we must factor $n$, and know something about how the private key was computed, or have some other hint (like examining side channel information from a device using the private key). When $n$ is the product of two distinct odd primes $p$ and $q$, methods to obtain $d$ include:

Computing $d=e^{-1}\bmod((p-1)\,(q-1)/\gcd(p-1,q-1))$ (the common modern practice and the one mathematicians prefer, for it gives the smallest working positive $d$).
Computing $d=e^{-1}\bmod((p-1)\,(q-1))$ (still commonly taught).
Computing $d=e^{-1}\bmod((p-1)\,(q-1)/2)$ (that saves the GCD operation while often offering the same minor performance benefit).
Choosing a prime $d$ at random in some interval like $]\max(p,q),p\,q[$, and computing $e$ from that (as in the original RSA article). Now we can find $d$ for sure, or not, depending on what we know about how $e$ was computed, and what the interval really was.

More generally, it is generally believed that no amount of known or chosen plaintext or ciphertext helps recover an RSA private key. But we have no proof of that statement, despite efforts of literally generations of researchers. See this question.


Solve a Modular Exponentiation It might be common, but if we had to solve an equation like this $m=s^{e}$ mod $n$ where $m,e,n$ are known. How can we find $s$. What optimisations could be applied? And what would the complexity of finding $s$ be relative to $n,e$?
Moreover, if we use GNFS or anything similar what does the complexity express exactly. For example, what do we mean when we say that for 1024-bit key the complexity for factoring it is ~86.7?

Finally, why can't we reform the equation like $m=s^e$ mod $n$ => $m+k*n=s^e$ => $s=(m+k*n)^{1/e}$ and start trying different k, as long as, we just want to find an s satisfying this equation?

Thank you

When $n$ is prime, solving for $e$-th roots modulo $n$ is easy, since it suffices to compute $d = e^{-1} \pmod {n-1}$ and then $s = m^d \pmod n$. If $n$ is not prime, but is instead a RSA modulus (a composite integer that is the product of two big primes), then the problem becomes apparently hard (in the sense that we don't have a clue how to do it efficiently) and is known as, indeed, the RSA problem.

The most efficient known methods to break the RSA problem, for non-special values of $m$ (e.g. the values which result from the padding step in standard RSA encryption and signatures), rely on integer factorization. If you can factor $n$ into its prime factors, then the RSA problem can be solved efficiently. Note the important point: we do not know if the RSA problem is equivalent to factorization; the RSA problem cannot be harder than factorization, but it might be easier. It is just that, right now, we do not know any RSA-breaking algorithm which is more efficient than factorizing the modulus.

The most efficient known method for integer factorization is GNFS, whose complexity is expressed as a barbaric-looking equation which you will find on the Wikipedia page. This is asymptotic complexity, so it does not given readily applicable results for two reasons:

The expression is valid for a big enough modulus; it does not tell whether a specific modulus length (say, 1024 bits) is sufficient for the expression to be at least approximately correct.
In practical terms, we want to express attack complexity in terms of dollars, not operations. In particular, the mathematical expression speaks only on CPU cost, not on memory cost, and says nothing about parallelization.

For big cracking jobs, a key to efficiency is how well we can split the problem into individual units which can run in parallel of each other, and how much data they have to exchange with each other. Heavy clusters achieve a lot of raw power through a lot of parallelization, which works wonders for, say, meteorological simulations, but not so much for integer factorization.

Roughly speaking, GNFS consists in two main phases, the sieve and then the linear reduction. The sieve is amenable to some rather high level of parallelization. For big integers (say, 1024-bit), the linear reduction appears to be the bottleneck. It is very hard to parallelize, and our best method so far is to find a big computer with an awful lot of very fast RAM. Existing "supercomputers" are ill-suited for such jobs. In fact, baring some non-trivial algorithmic enhancement for this phase, breaking a 1024-bit RSA modulus will require special-purpose hardware which exists only theoretically (we have plans, but turning plans into silicon takes money, time, and a lot of extra thinking).

Some people have tried to estimate how much this would all cost, and compared that to the cost of breaking a symmetric key through brute force (there again with dedicated special-purpose hardware). The result depends on a lot of parameters, including how much developers are paid (academics tend to think in terms of "developer = PhD student = free") and how many keys you try to break (hardware can be reused). Depending on who does the estimate, a 1024-bit RSA modulus will be deemed "as robust" as a symmetric key in the 75 to 85 range, meaning that it would cost the same to break it (note that this range hides a 1000-times factor !).

This site is the usual reference for pointers to the relevant papers.


how to avoid attack on Certificate Revocation List by the owner of the private key? suppose A owns the private key, and its correspondent certificate locates in site of CA.

B request for A's certificate from CA for verifying the signature sent to him/her.

There is an attack exists as follow:

A send message with signature to B.
A send revocation request to CA after confirming the message is successfully accepted.
B received the revocation information from CA.
A repudiate the message.

As for it is totally possible that a private key owner keep using the key before he/she find the key has been compromised. So, in the above case A can successfully make repudiation.

My question, is the above attack really applied to real life ? how to avoid if so?

edit: under the assumption that the attack is raised intentionally by private key owner, it is totally different from the case that attacker use the time difference between A requests for revocation and B receives the inform, which can be mitigated by OCSP.

Yes one could do this, the repudiation wouldn't be very convincing.

The CRL really isn't very relevant. A person can always claim his private key was stolen. His credit card was stolen or his car was stolen.
We see people commit hit and run, realize what they have done park the car somewhere and report it stolen. Denying a credit card transaction etc.
If the car is reported stolen well before the hit and run that would be convincing proof.

As with CRL it would be convincing if the revocation is clearly before the transaction. But a revocation very close in time to the transaction doesn't provide a very convincing repudation though theft is plausible it is not common. And the private key owner could still be held responsible for his private key.

CRLs should not waive responsibility the second they are posted.


Will publishing two or more public keys of the same RSA private key cause a security risk? I want to make an end-to-end messaging platform where everyone is identified with a unique random private key. Everyone uses other peers' public keys to identify and send encrypted messages and verify received messages signed by the public keys. Now I want to use multiple public keys for each peer and maybe give peers access to two or more public keys of a private key.

Can other peers find out if some known public keys belong to the same private key or not? And if they found out, does it put the private key at risk of being cracked or create other security issue?

You can't have two different public keys for the same RSA private key.  That's just not how RSA works.

Well, almost.  There's a minor technical loophole, and it's the fact that RSA has equivalent keys.  In particular, the public keys $(n, e)$ and $(n, e + \lambda(n))$ are equivalent, in the sense of producing the same ciphertext for the same (padded) plaintext.  But there are two reasons why you never want to publish two such equivalent keys:

It's useless, since they're literally equivalent.  You might as well just send the same public key to both peers.  Encrypting a message (or verifying a signature) using a large public exponent is slower anyway, so it's best to just do things the usual way and use one of the standard small public exponents like $e=3$ or $e=2^{16}+1=65537$.
It completely breaks the security of the system.  Knowing two equivalent public keys with different exponents $e$ and $e'$ lets anyone learn their difference $\delta_e = |e - e'|$, which must be a multiple of $\lambda(n)$.  Knowing a non-zero multiple of $\lambda(n)$ is enough to solve the modular congruence $ed \equiv 1 \pmod{\delta_e}$ and obtain the private decryption exponent $d$ (or something equivalent to it — RSA private keys can also be equivalent but not identical in exactly the same way as public keys).

So, you know, don't do that.  Just generate your RSA key pairs the usual way, with one public key for each private key and vice versa.  And remember that the public key is supposed to be public, so you can always share the same public key with any number of people.

Ps. While copyediting your question, I noticed that you mentioned signing messages.  With RSA signatures (and digital signatures in general), you cannot (usefully) sign messages with public keys, but only with the private key.  So e.g. if Bob wants to send a message to Alice, he should sign the message with his private key, and then encrypt the signed message with Alice's public key (and make sure before signing that the message says it's for Alice, so that she can't just re-encrypt it with Charlie's public key and make it look like Bob sent it to Charlie).

Also, it's generally not a good idea to use the same key pair for signing and encryption, even if algorithms like RSA technically allow it.  So in practice, every peer should really have two private RSA keys (one for signing, one for decryption) and every other peer should know the public keys corresponding to both of them (so that they can both encrypt and verify signatures).

Pps. For a simpler and more practical solution, ditch RSA entirely and replace it with e.g. NaCl / libsodium crypto_box.  It's simpler and faster, the keys and signatures are smaller, you only need one keypair for each peer, and since it's an all-in-one integrated solution, it's a lot harder to use it wrong and end up with a security hole than it would be if you insisted on rolling your own signing and encryption scheme with RSA.

Or, perhaps even better yet, don't try to design your own messaging protocol at all, but just use an open source implementation of some published and well studied protocol such as Signal.  Designing a good and secure messaging protocol is not easy, with all sorts of non-trivial details like protecting past conversations from the possibility of a later key compromise.  It's much easier to just use an existing protocol designed by smart people who have already considered those details and found ways to handle them.

(Even if you do insist on making your own messaging protocol, it's at least a good idea to review some widely used and studied existing protocols like Signal and see what issues their designers have considered and how they've dealt with them.  That way, you get a chance to learn from other people's mistakes instead of your own.)


Plausibly deniable authentication for agents on multiple teams Here's a problem that I've been thinking about:

An individual, Alice, wishes to authenticate herself.
She may wish to authenticate to Bob (who is on the blue team) that they are both on the blue team.
She may wish to authenticate to Charlie (who is on the green team) that she is on the green team.
However, when approaching a person, she has to send a message that could authenticate her to either of the two (as she does not know which one she is approaching)
The goal is for members of the blue team to not know she is on the green team, and for members of the green team to not know she is on the blue team.
Additionally, Eve, who is on the red team, should not be able to determine anything about which teams alice is on due to the message.

How would one construct such a system?

It would be possible to do this if the authentication method was designed to allow for redundancy. The simplest example would be if team members authenticated to each other with a password, but they were allowed to send redundant characters along with the password. (I'm assuming here that all teams use the same authentication method!)

So let's say the blue team password is "BERRY" and the green team password is "LEAF". Now, the string "ASDBERRYFOO" would successfully authenticate a blue team member. However, "FOOBERRYLEAF" would successfully authenticate a member to both teams! The teams don't know each others' passwords, so the latter does not look any more suspicious to anyone than the former. Eve doesn't know the passwords of red or blue teams either, so she cannot know whether that string actually includes a password to one or more teams.

Of course, this method is highly vulnerable to replay attacks. Eve can very well just go ahead and send "FOOBERRYLEAF" to anyone she might encounter, and that way she would find out that it authenticates to both blue and green teams (even if she still doesn't actually know the passwords -- they might as well be "OOBE" and "RYLEA"!).

One could try to improve the scheme by only accepting a certain authentication string once -- so if "FOOBERRYLEAF" has been used, it shouldn't work again. Alice can still create an unlimited amount of similar strings as she knows the passwords.

A better method would be to use one-time passwords so that even the "BERRY" part does not repeat.

The redundancy part is still my main issue though: why would anyone actually use a scheme where the same message could be interpreted in two different ways? Obviously my "FOOBERRYLEAF" example is too naive. I think in reality you wouldn't just concatenate strings, but you'd find some clever hash collision or something like that to achieve the same result. But I'll leave that part for others to ponder...


Can I always derive a key pair from password+salt with libsodium? I'm using libsodium to create public/secret key pairs from a password and salt combination by using crypto_pwhash_scryptsalsa208sha256 to generate a seed and passing that seed to crypto_box_seed_keypair.

Is it safe to recreate the key pair using the password+salt every time I need to use it so I don't have to store the keys (encrypted or not) anywhere in the system?

I would store the salt, and ask for the password again every time it is needed.

Is it safe to recreate the key pair using the password+salt every time I need to use it so I don't have to store the keys (encrypted or not) anywhere in the system?

The problem with that is that your public key then effectively becomes a password hash, meaning anyone who sees it will be able to mount a dictionary attack on your password to generate the private key that corresponds to it. They will need access to the salt for the attack, of course, so in that case your salt effectively becomes a secret.

So there is not really a great difference to storing an encrypted (random) private key vs. storing a (random) salt that allows deriving the private key. However, when deriving the key directly from the password you should use a strong random number as a salt, not something unique but guessable, like a timestamp or an email address.


Difference of full codebook and non full codebook While reading a paper about Dynamic cube attack, I saw two terms:
full-codebook and non-full-codebook attacks.
What do they mean?
What is the difference?

Regards

In full codebook, data complexity equals to all input of cryptosystem and in non full codebook is less than it.

For example in SIMON 32/64, if data complexity=2^32, the attack is full codebook,
and if DC < 2^32, the attack is non full codebook.


Encrypting passwords I am using Android's keystore to generate a key which is protected by fingerprint authentication. This key can be used to encrypt any secrets. In my case, I want to encrypt a user password (which is needed to access the app contents. Usually that's a reasonably strong letter-number-special-characters password.). The encrypted password is stored in the app's preferences. While these preferences are not fully public, I don't consider them secure storage.

Assuming an attacker has access to the encrypted password, I would like to expose as little as possible about the password itself. One thing that comes to my mind is password length. From the length of the encrypted text, it can be seen if the password is more than 16 characters or not. (I could hide this by always appending random text to have a fixed length of text for passwords < N characters, with N sufficiently high).

Are there any more serious issues? Is there any best practice on how to encrypt user passwords?

Since you are talking about password-based encryption, the best practice is to use a slow password-based key derivation function to derive the encryption key and only store the salt (and parmeters used). You can verify the correctness of the password by using authenticated encryption, which you should most likely be doing in any case.

The password hash used could be scrypt, or I suppose argon2.

Since you are using this in a password manager -type situation, the encrypted data is passwords, which is fine. The above advice is only about the master password that is used to secure the database. That should not be stored in plaintext or encrypted form and even its hash does not need to be.


RSA Duplicate-Signature Attack I'm trying to duplicate an RSA signature, and am having trouble at the last couple of steps. I'll detail what I've tried.

I used OpenSSL to generate some 128-bit RSA parameters. Here are my public modulus and exponent:

N = 0xdb52a89a63825f9e498144c240f5c23b
e = 65537

The (hashed, unpadded) message and signature are:

m = 200491217728191104277162087173636532728
s = 238661990926400143633637156414542417630

To verify the signature, we check $s^e = m \mod N$. I want to craft public parameters $(N',e')$ such that $s^{e'} = m \mod N'$. I found an algorithm to do this here, in Section 4.1.  To do this, I choose two primes such that:

$N < pq$
$p-1$ is smooth
$q-1$ is smooth
$m$ and $s$ should each be primitive roots mod $p$ and mod $q$
$\gcd(p-1,q-1) = 2$

The primes need to be smooth so that I can solve the discrete log problem in small subgroups with the Pohlig-Hellman algorithm. $m$ and $s$ need to be primitive roots so that the discrete logs exist.

I chose two primes:

p = 18446744073709558081
q = 18446744073709755467

$p-1$ has factorization $2^6\cdot 3^2 \cdot 5 \cdot 167^2 \cdot 409 \cdot 761 \cdot 859^2$.

$q-1$ has factorization $2 \cdot 13 \cdot 107 \cdot 701 \cdot 15647 \cdot 23099 \cdot 26171$.

They satisfy all the properties listed above. $N'$ is easy:

N_prime = p*q = 340282366920942343108801213731143778827

I used Pohlig-Hellman to compute $e'_p = e' \mod p$ and $e'_q = e' \mod q$. I verified these exponents solve $s^{e'_p} = m \mod p$ and $s^{e'_q} = m \mod q$.

ep = 12805870501641979644
eq = 12267640565537452735

Now here's where I'm stuck. I think I should be able to stitch together $e'_p$ and $e'_q$ with the Chinese Remainder Theorem to get $e'$:

e_prime = CRT( (ep, p-1), (eq, q-1) ) = 199703471997348597303557477228581222008

But I don't think this will work since the $p-1$ and $q-1$ are not coprime (the GCD will be at least 2 since $p-1$ and $q-1$ are always even). Besides, when I test it, it doesn't work:

pow(s, e_prime, N_prime) = 20617548250412763970655475611439323667
m % N_prime = 200491217728191104277162087173636532728

Also, for RSA, we need $\gcd(e', (p-1)(q-1)) = 1$, but for me, this quantity is 24. The source I linked to also proposes a solution, but it didn't work for me either.

Anyone have any advice and where I'm going wrong?

You forgot step 4:

  $m$ and $s$ should each be primitive roots mod $p$ and mod $q$

$m$ is not a primitive root mod $p$.  We can easily deduce that (without the bother of actually performing any nontrivial math) from the relation you gave:

$$s^{e_p} = m \bmod p$$

for $e_p$ even; hence $m$ must be a quadratic residue, and hence cannot be primitive.

As $e_p$ is even and $e_q$ is odd, there is no solution to the CRT...

For your reference, $m$ will be a primitive root of a prime $p$ if, for every prime factor $r$ of $p-1$, we have $m^{(p-1)/r} \not\equiv 1 \bmod p$