Is the One Time Pad secure in additive Rings? Let's assume all operations are done on $\mathbb{Z}_p$ where $p$ is a large non-prime number.

To mask a value $a$, we do the following:

Pick a uniformly random value: $r$, from the ring.
Do as follows: $c= r+a \bmod p$.

Question: Is the above one-time pad secure?

The classical xor-based one-time pad can be generalized to finite groups.

Let $(G,*)$ be such group with order $p$ and $*$ is the group operation(like the xor).
The message, the pad and the ciphertext are elements of $G$.

Now to encrypt a message $m \in G$, choose $k \in G$ uniformly at random and set $c = m * k$. One of the security proofs of the one-time pad consists of showing that $c$ does not give any information on $m$(i.e to find $m$ we might as well pick a $c'$ at random and ignore $c$ completely).

More precisely, if $M$ is a random variable for messages distributed somehow, $K$ is a uniform random variable for the keys, and $C = M*K$ the random variables for the ciphertexts.

What we need to show is that $C = M*K$ is independent of $M$. i.e $C$ does not give any information on $M$.

Proof: We want to show that $P_{C|M}[c|m] = P_C[c]$. First, It's easy to see that $C$ defined as above is uniform(i.e $P_C[c] = \frac{1}{|G|}$). Next observe that $P_{C|M}[c|m] = P_{K|M}[c*(m)^{-1}| m] = P_K[c*(m)^{-1}] = \frac{1}{|G|}$. This follows form the fact that $K$ and $M$ are independent.

Therefore we showed the 'perfect secrecy' property of this constriction.


Reusing the random exponent for ElGamal encryption with different plaintexts In the basic ElGamal encryption scheme, we encrypt a message $m$ as $(g^r, h^r m)$, where $g$ is the group generator and $h$ is the public key of the recipient.

If the sender has another message $m'$ to send to the recipient, can they use the same random $r$ in the construction without decreasing the security of the scheme? More generally, with $n$ different messages $(m_1, m_2, \dotsc, m_n)$, is it safe to encrypt them as $(g^r, h^r m_1, h^r m_2, \dotsc, h^r m_n)$?

No,  you can't. In this case, an attacker can compute $m_1/m_2$ by multiplying the first ciphertext for the inverse of the second and, for instance, determine if $m_1=m_2$ or not. This should not be possible in a secure scheme.


Encryption Key derivation from numeric PIN? I want to store data encrypted within an Android application. Keeping an encryption key safe outside the app is not an option so I looked into password derived key algorithms.

I found a nice example from Android on the blog-post “Android Developers — Using Cryptography to Store Credentials Safely ”. Let me quote the significant code:

public static SecretKey generateKey(char[] passphraseOrPin, byte[] salt)
                                  throws NoSuchAlgorithmException, InvalidKeySpecException {
    // Number of PBKDF2 hardening rounds to use. Larger values increase
    // computation time. You should select a value that causes computation
    // to take >100ms.
    final int iterations = 1000;

    // Generate a 256-bit key
    final int outputKeyLength = 256;

    SecretKeyFactory secretKeyFactory = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1");
    KeySpec keySpec = new PBEKeySpec(passphraseOrPin, salt, iterations, outputKeyLength);
    SecretKey secretKey = secretKeyFactory.generateSecret(keySpec);
    return secretKey;
}

This method seems to imply that it's good practice to use a PIN for key derivation.
Isn't that way too easy to brute force?

In other PIN applications there is an external system that limits the number of attempts making this approach safe. In this application however I can't see how a PIN can be safe.

On a compromised system the user has the encrypted data and knows from the app/code that the pin is an $n$ digit number. So he can brute force every $10^n$ possibility and use the encrypted data to see if decryption with that derived key/pin combination returns any valid data.

Is it correct to state that password key derivation requires an alphanumeric password to be safe

Edit:

In general I understand alphanumeric passwords are better than numeric. I'm interested in feedback on my theory that I make it even easier to brute force the pin since all data except for that pin is stored on the mobile device.

I'm also looking for alternatives. Is there a way to make this safe knowing we only have a pin as secret input from the user?

It is common that the attacker has at least as fast platform as somebody generating the key. Thus, brute force attacker can test all 4 digit PINs in 1000 seconds or 17 minutes (based on 100 ms seconds mentioned in the question).

BTW, it is fairly common to use larger iteration counts than minimum of 1000 and longer times (like anything that takes 1s to process. On modern platforms, counts of 10000 or 100000 can be completely reasonable). In addition, it is common to punish wrong attempts with delay to slow down guessing.

In case the attacker has access to some computing power, like ASIC circuitry designed for cracking PBKDF2, they may be able to break the secret, for instance, 1000 times faster i.e, the could guess 10000 pins/passwords per second (assuming key derivation takes 100 ms seconds on the device).

--

For PIN and PBKDF2 to be secure against attacks, it is often mandatory to do these:

Attacker cannot get direct access to the storage on the device (to get values needed for breaking the secret offline with specialized devices)
The device does not allow to try many PINs very quickly (increasing delay after trying).
Too many miss attempts lock the device.

But, generally using good passwords is much more secure than using PIN codes.
This is my earlier answer on security of PIN or password when materials needed for brute forcing are available for the attacker.


The GCD strikes back to RSA in 2019 - Good randomness is the only solution? When someone collects lots of RSA public modulus, the first thing that comes to mind is;
$$\text{GCD them all}$$
If you calculate the GCD of two different RSA modulus and if the result is not 1 then you find one of the factors. This has been actively studied in

2012 - Heninger et. al Mining your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

These researchers collected 5.8 million unique TLS certificates and 6.2 million unique SSH host keys. In the combined collection, there were 11 million distinct RSA moduli and they were able to factor 16,717 distinct public keys. I.e. breaking 23,576 (.4%) of their TLS certificates and 1,013 (.02%) of the RSA SSH host keys.

2012 - Lenstra et. al Ron was wrong, Whit is right

They collected 6.2 million digital certificates across the Internet they found that approximately 4.3% of these certificates fully share their RSA modulus with another.

2013 Bernstein et. al, Factoring RSA keys from certified smart cards: Coppersmith in the wild

The researchers investigate Taiwan’s national “Citizen Digital Certificate” database that contains more than two million RSA modulus. They have efficiently factored 184 distinct RSA keys. They are noticed that some of the primes occur more than was like p110 occurs 46-times. The reason was the flawed random-number generators in some of the smart cards.

2016 - Hasting et.al, Weak keys remain widespread in network devices

To see the response of the vendors and end-users, the authors examined 81 million distinct RSA keys and were able to factor 313,000 keys (.37%). They see that a significant number of new devices from Huawei, D-Link, and ADTRAN was vulnerable.

2016 Barbulescu at. al RSA Weak Public Keys available on the Internet

They crawled GitHub SSH-RSA keys between 22 December 2015 and 7 January 2016. They were only factor 1 with 512-bit. They also analyzed a ransomware database that contains 2048-bit RSA that contains none weakness.
From raw X.509 certificates collected during 2012, they tested 26177420 1024 bit RSA keys tested, 63502 (0.25%) keys were found to be factorized.

2018 - N. Amiet and Y. Romailler, researchers from Kudelski, Reaping and breaking keys at scale: when crypto meets big data.

They collected 340M RSA keys and 210k are broken. 1 key out of 1600 is vulnerable to batch-gcd by written by Chapel.
And recently;

2019 - Researchers at KeyFactor Factoring RSA Keys in the IoT Era

They scraped 75 million RSA certificates from the Internet between 2015 and 2017, a total of 250,000 could be completely broken. That is 1 in 172 shares a factor.
One solution to prevent the common factor is a public database. That is downloadable so that one can test their new modulus with the GCD. Of course, such a database has another issue. The reason that causes the same prime generation, the randomness process, can be exploited by some attackers. In any case, the attackers can scrape their database as researchers.
Questions:

Can A good random number generator solve this issue if we consider we are using RSA-2048 and let say we need 1 billion RSA modulus?

What is the probability that we can select a prime at least twice if we only consider 1024-bit numbers?

Why don't we generate the primes in different bit domains like 1024,1025,1026,1027-bit,...

The solution is simply to make sure that you have good randomness. At the size of the numbers we are considering, the probability of a repeat when using good randomness is extremely small. To make this clear, there are well over $2^{1000}$ prime numbers of length 1024. The probability of a repeat at any reasonable number of primes chosen, when using true randomness, is so small that it's not worth considering. To be more exact, if we generate $t = 2^{50}$ random primes of length 1024 (this is 1,000 trillion), then the probability of a repetition is smaller than $\frac{t^2}{2^{1000}} = 2^{-900}$.

True randomness isn't that helpful, so the NIST recommendation is to take a random seed for your PRG at double the length of the bit security you are looking for. So, assume RSA-2048 is 128-bit security (it's actually a bit lower by estimates, but let's ignore that detail for here). Then, you should be using a 256-bit truly random seed, and using that in a PRG based on something like AES-256. In this case, the chance of getting a repetition is still essentially 0, even if thousands of trillions of keys are generated. Again, to be more exact, the probability would be upper bound by $\frac{t^2}{2^{256}} = \frac{2^{100}}{2^{256}} = 2^{-156}$.

The main challenge is how to make sure that good randomness is used. It's much cheaper and easier to generate identical devices on a factory line that have nothing unique. In this case, each device needs to generate its keys by itself later, and the easiest thing again is for it to use its own internal state. This doesn't work. The best option is to write a fresh random 256-bit seed in every device during production (in a factory, it's not a problem at all to have a machine with a true random generator that can generate the seeds that are written to the devices). If this isn't done, then there needs to be some way of securely delivering a good seed to the device. It's possible to "add in" any entropy that can be generated locally as well, but this cannot be the primary source.


Voronoi regions of lattices with dimensions $\leq 16$ Is there any idea about calculating the exact Voronoi regions of lattices with dimensions $\leq 16$?
Thank you!

Micciancio and Voulgaris [https://cseweb.ucsd.edu/~pvoulgar/files/voronoi_full.pdf] gave a $\tilde O(4^n)$ algorithm to computer Voronoi relevant vectors, which should be reasonable for $n=16$.
However, this may be painful to implement exactly this algorithm. Though an important remark of that paper is that you can you can deduce the $2^n$ Voronoi relevant vector by solving CVP, relatively to the $2^n$ cosets of $\frac 1 2 L$ in $L$.


Decrypting RSA encrypted messages with repeated use of p,q I require help with the following assignment.

The Assignment

  A company by the name "Secure Keys" is very good at creating random prime numbers, however a new CEO decides to cut costs and use random numbers more than once in generating RSA key pairs.

  100 messages from this company were intercepted, all messages contain the cyphertext and the modulo used for decryption, we also know that their RSA encryption uses e = 65537 (2^16 + 1)

  You are to decrypt the files and find the message containing the flag.

I'm lost in how to approach this problem, since I know that having the n,e isn't enough to decrypt a single message and I failed to connect the repetition on prime numbers used part.

The assignment, or at least the part of it that you've quoted, seems somewhat ambiguous, but I'm going to assume that it means that among the RSA moduli there are pairs $(n_A, n_B)$ that share a common prime factor $p$ (i.e. $n_A = p \cdot q_A$, $n_B = p \cdot q_B$, with $q_A \ne q_B$).

In that case, you can trivially find the shared prime factor by calculating the greatest common divisor of the two moduli $n_A$ and $n_B$, e.g. using the Euclidean algorithm.  Even if you don't know in advance which moduli share a common factor, you can simply test each pair of moduli: the GCD of any two numbers is always, by definition, a divisor of both of them, so if you find any two RSA moduli whose GCD isn't 1, you've just factored both of them.

Note that this is not just an artificial exercise, but a practical attack against poor quality RSA key generation implementations found in the wild.  For a demonstration of this attack (and more details on how to efficiently carry it out in practice), see e.g. the paper "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices" by Heninger, Durumeric, Wustrow and Halderman (2012).

Ps. See also this related question from a few years ago.


What are the first 4 and last 2 bytes in DH parameter files? When we generate DH parameters file in PEM format, like this:

-----BEGIN DH PARAMETERS-----
MCYCIQDyl7rfGI2GywHp7JC7juWhv3VL+skipzl/329sQCEBQwIBAg==
-----END DH PARAMETERS-----

or

-----BEGIN DH PARAMETERS-----
MIGHAoGBAdilyft4T5FJO0xga8hzoBcUmAZRTlxE930Dfda4LaC8TFsQkibgUYPJ
AuFWuAnKgjWjLH80Pt1shilYdd8b7vL2TL2/e3BBNr4sr8DJLLa7p04mt0t4CSKO
Cp+/pqanm6Mq9xJ3Wo4SDrx70czGhwi5ZNLwwusez9Djwq8dX8IDAgEC
-----END DH PARAMETERS-----

besides additional header and footer lines, there are 4 bytes at first and 2 bytes at the end of the base64 line, and it depends to the DH parameters. How I can generate them knowing DH parameters?

PEM consists of a header and footer that identify the object that has been encoded. It may sometimes also contain some arguments behind the header line. The actual data is base 64 encoded. You can view the contents by decoding it using a base 64 encoding.

Now the DH parameters are encoded using ASN.1 BER, which is a binary encoding. This encoding is used for most if not all PEM encoded structures. ASN.1 is a data description language. ASN.1 structures can be seen as a tree with constructed nodes (sequences) and primitive nodes (strings, byte arrays, integers and such) all using network ordering. These nodes are generally encoded using tag-length-value (TLV) encoding. As the tag for a SEQUENCE is the value 30 (in hex), the first base 64 letter is almost certainly an M.

The version of base 64 used by PEM pads anything that isn't a multiple of 4 characters (three bytes) to 4 characters using the = character.

So the first characters and the amount of = characters at the end is mainly dependent on the size of the parameters rather than their value.

This is the contents of the ASN.1 tree in the contents of your PEM text:

SEQUENCE(2 elem)
  INTEGER(256 bit) 1097277930034063274792561151504789680016548759529511363308187422232757…
  INTEGER2

and

SEQUENCE(2 elem)
  INTEGER(1025 bit) 331904441233693192104476260016584324479133460055459757886261577377912…
  INTEGER2

generated using the ASN.1 decoder here.


How to use CPA on AES128-CBC with constant Key and IV to leak info? I'm doing a challenge in which I need to login to a server as an admin to capture a flag.
I can enter an $id$ and a $password$ only consists of 'a-z', '0-9','-', '_' characters.
The flow is as follows:

The client side creates a message of a specific format:
$$M = {id}\text{-}{password}\text{-}{cookie}$$
Where "$\text{-}$" acts as delimiter and $cookie$ is a constant postfix to ensure that the message was sent from the expected server (kind of like a signature).
Then the client adds padding of null bytes and encrypts $M$ using AES128-CBC and the same key $k$ and same iv $IV$ is used every time, for which I don't have access to.
The ciphertext is encoded in hex and sent (I do have access to the sent message)

After some analysis I found that if I obtain $cookie$ I can login as an admin.

What attack should I try to implement?
Can I get my hands on $IV$ or even $k$ using CPA when they are reused in CBC mode?
What additional information I should try to gather which can help me?

The strategy you need to apply here, is basically the same as with most other oracle attacks:

You construct a message such that you can verify your guess for a single byte, then you adapt to guess the next byte until you are done.

In this specific case you would pick the user-controlled message length such that one byte of the cookie is in the same block as the tail of your message, encrypt that. Then you make your input one byte longer and try all possible values for the cookie byte until the corresponding block is equal to the encryption of the cookie byte.

Now you repeat this process for the second byte and so on.


Motivation for the definition of statistical distance Statistical distance is a widely used measure in cryptography for comparing two distributions. One can define various other measures for capturing the differences between two distributions, but why do we prefer to use statistical distance? What is the physical significance of statistical distribution definition, which goes as follows:

Let $X_1$ and $X_2$ be random variables with domains $D_1$ and $D_2$, then the statistical distance between $X_1$ and $X_2$ is defined as:

$\delta(X_1,X_2) = \dfrac{1}{2}\sum\limits_{x \in D_1 \cup D_2}|Pr(X_1 = x) - Pr(X_2 = x)|$

I found this definition in the second chapter of the textbook titled "Secure Multiparty Computation and Secret Sharing".

Statistical indistinguishability (i.e., negligible statistical distance) implies computational indistinguishability, but is typically easier to prove since it does not require a computational argument with a reduction and all that stuff.

Of course, it is not always possible to prove computational indistinguishability in that way; statistical indistinguishability is a stronger, information-theoretic notion.


Does the diffie helman rachet in double ratchet do anything if one side never replies? I am a little confused on how this functions so apologies in advance if the question is naive.
The way i understand it, the function of the standard sending and receiving ratchets in Double Ratchet is to provide backward secrecy. Since the ratchets continually pass the key through a KDF, the attacker cannot deduce previous keys if he somehow keys a hold of the current one.
The issue is, this does not provide forward secrecy, since the attacker can now tick along with our ratchets. This is where the DH Ratchet comes into place.
I am reading from http://cryptowiki.net/index.php?title=The_Double_Ratchet_Algorithm#Diffie-Hellman_ratchet
Alice and Bob both have a DH keypair generated. This keypair is seperate from the keys used in the sending and receiving ratchets.
When Bob sends a message, he sends his DH public key. When alice receives it, she uses hey private key and forms a new key from those two. Now Alice has new key(lets call it K1) for her ratchets.
Then when Alice sends a message to Bob, she sends her private component and generates a new DH keypair since this one was used on both sides. Bob can now use this to derive the same K1 key. Bob generates a new DH keypair since this one was already used to compute K1 on both sides.
My issue with this understanding is, what if Alice never responds? Bob will keep sending his public key. Since he only ratchets on receiving messages, his DH Rachet will never activate and there is now no forward secrecy for the N messages he sent?
Also alice will receive the same public key multiple times. Surely this is an issue. Keys should be changing on sending,no?
I know theres something I'm missing here. Any help is appreciated.

Bob will keep sending his public key. Since he only ratchets on receiving messages, his DH Rachet will never activate and there is now no forward secrecy for the N messages he sent?

If there are indeed no answers over the ratcheted channel, this is correct.
However, some implementations send their receive receipts via the ratcheted channel, meaning that the ratchet is only not advanced if the recipient never actually receives the messages or can't send the confirmation.

Also alice will receive the same public key multiple times. Surely this is an issue. Keys should be changing on sending,no?

This is not an issue, the protocol instructs which public key to use, which should be the first new one.


What's the difference between symmetric and asymmetic multilinear map? In pairing-based cryptography, we have 3 types, namely Type-I, where $\mathbb{G}_1 = \mathbb{G}_2$, and in Type-II and Type-III we have that $\mathbb{G}_1 \neq \mathbb{G}_2$, however in Type-II we have an efficiently computable homomorphism between $\mathbb{G}_1$ and $\mathbb{G}_2$, however in Type-III, we do not have this homomorphism.

Now, going over the definition of multilinear maps here [BWZ14] (pages 4 and 5), the authors define two multilinear maps, where one is called asymmetric. Where the asymmetricity come in this situation? As in the first definition (which I just called symmetric for a lack of a better name), do we have to consider that all the $n$ groups $\mathbb{G}_1,\ldots,\mathbb{G}_n$ are the same group? Because, there the definition does not say this. And why the use of integer vectors for indexing in the asymmetric case?

Symmetric means that the source group and all the intermediate groups are the same, i.e. $\mathbb{G}_1 = \mathbb{G}_2 = ... = \mathbb{G}_{n-1}$ using the notation of the paper you linked, while asymmetric means that they can be different.

Check, for instance, remark 1 on the original paper about multilinear maps.

And about the vectors as indices, the aim is just to identify the levels more clearly. Since you have $2^n$ levels, you could use numbers from $0$ to $2^n-1$ to identify them, but then, increasing the levels with the multiplication would not have this nice interpretation of adding the entries of the vectors (or, equivalently, doing a union of the sets that represent the levels).

In several papers, for the symmetric scenario, we have a ring $R$ and an invertible element $z \in R$. Then, the map goes from $(z^{-1}R)^n$ to $z^{-n}R$. But, since the schemes are actually graded, you can apply the map partially and get elements in $z^{-k}R$ for $k < n$. Then, this $k$ is the level.

So, basically, we have elements of the form $r_i / z$ and you can multiply $n$ of them to get $(\prod_{i=1}^nr_i) / z^n \in z^{-n}R$.

In the asymmetric scenario, instead of a single $z$, we have $z_1$, .., $z_n$. Then, the map goes from $z_1^{-1}R \times ... \times z_n^{-1}R$ to $(z_1^{-1}\cdots z_n^{-1})R$.

So, you have elements $r_j / z_i$ and you can multiply them. But now, you can get any product of $z_i$'s in the denominator, so, it is easier to represent the levels by the exponents of each $z_i$, or, equivalently, with an $n$-dimensional integer vector.

For example, considering $n = 4$, an element $r / (z_1 z_3)$ is in level $(1, 0, 1, 0)$, and an element $r' / z_4$ is in level $(0, 0, 0, 1)$. Therefore, combining them (applying the map partially), gives us $r r' / (z_1 z_3 z_4)$ that is in level $(1, 0, 1, 1)$.

Thus, the vectors used to represent the levels tell us which groups were already used in evaluation of the map.


When do we need composite order groups for bilinear maps and when prime order? Why we need bilinear groups of composite order? What's the special security property of the composite order group in comparison with one of prime order? To put it in another way when do we need composite order groups for bilinear maps and when prime order?

A composite order group is like having a 2-dimensional vector space, because of the Chinese Remainder Theorem. More concretely in the context of a bilinear map, if $g$ is a generator with order $N=pq$, then $g_p = g^q$ generates an order-$p$ subgroup, and $g_q = g^p$ generates an order-$q$, and $e(g_p, g_q) = 1$. They cancel each other out, and so you can think of $\{g_q, g_p\}$ as an orthogonal basis for the a 2-dimensional vector space.

The way this is typically used is that the bilinear "functionality" of a scheme is carried out in one dimension (e.g., in the exponent of $g_p$) while the other dimension (e.g., the exponent of $g_q$) is used for "blinding". Orthogonality ensures that the blinding factors just disappear after the bilinear map.

Recently, Okamoto & Takashima have developed a framework for cryptographic constructions using prime-order bilinear groups (called dual-pairing vector spaces, DPVS). It is a nice abstraction that allows you to build (from prime-order groups) $n$-dimensional orthogonal vector spaces that have a suitable pairing. It's like having the above effect, but now even with of a product of $n$ primes! I think most people in the field believe that prime-order constructions can be "ported" to prime-order groups, using these DPVS techniques.


How to calculate plaintext from modpower cipher Let $a$ be the plaintext message, $e$ be a small prime exponent (such as 11, 13, 17 etc.), $b$ be cipher text and $n$ be a large modulo (non-prime).
Suppose that:
$b \equiv a^e \space mod \space n$
If we know $b$, $e$ and $n$, can we possibly calculate $a$?

It is conjectured to be hard to recover $a$ given only $b$, $e$, and $n$. This is called the RSA assumption. If an efficient factorization algorithm exists, this assumption is false.

However, it is possible that the RSA assumption is false and there exists no efficient factorization algorithm. In other words, the hardness of factoring might not imply the RSA assumption is true.

In your question you merely call $n$ a large non-prime modulus. You have to be a little careful about the primes that make up $n$; there are lots of ways to screw up and accidentally make it easy to factor $n$.


bcrypt collision probabilities assuming same password and work factor? What is the likelihood of 2 bcrypt hashes colliding if they use the same work-factor and input?

Are bcrypt's salts large enough to prevent this from happening?

What is the likelihood of 2 bcrypt hashes colliding if they use the
  same work-factor and input?

You're describing this: $\tau_1,\tau_2=\text{bcrypt}(pw,cost), \Pr[\tau_1=\tau_2]$. This means that the collision probability comes down to the length of the salt. bcrypt uses 128-bit salts. So you expect to find a collision after doing roughly $2^{64}$ hashings (assuming you're PRNG is good).

If you really want to find a collision, $2^{64}$ is feasible. Especially if you'd use FPGAs / ASICs. The practical relevance of this is low though as you rarely see password database (with the same password) beyond $2^{35}$ and even then collision resistance isn't an all that important property of password hashing (what can you do if the tags collide?).


Why does RSA OAEP add this many zero bytes? The choice of $n_\text{Len}–K_\text{Len}–2\,H_\text{Len}–2$ zero bytes seems arbitrary to me and I can't see any reasoning for why it was chosen and it doesn't look like the zero bytes being replaced at any point either? Why was this specific formula used? From section 7.2.2.3 of Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography:

  b. Construct a byte string $PS$ consisting of $n_\text{Len}–K_\text{Len}–2\,H_\text{Len}–2$ zero bytes. The length of $PS$ may be zero.

  c.   Concatenate $HA$, $PS$, a single byte with a hexadecimal value of
  01, and the keying material $K$ to form data $DB$ of $n_\text{Len}–K_\text{Len}-1$
  bytes as follows:

  $$ DB = HA \mathbin\| \text{PS} \mathbin\| 00000001 \mathbin\| K,$$
  where $00000001$ is a string of eight bits.

The choice of $n_\text{Len}–K_\text{Len}–2\,H_\text{Len}–2$ zero bytes seems arbitrary

No. It's actually tight given what RSAES-OAEP does:

allow any modulus $n$ of $n_\text{Len}$ bytes,
$H_\text{Len}$ bytes for the hash of the tag,
$H_\text{Len}$ bytes for an unconstrained random seed,
length of the message (that is, the value of $K_\text{Len}$) encoded in the padding.

$n_\text{Len}$ is the number of bytes to represent the modulus $n$, that is $\left\lceil b/8\right\rceil$ where $b$ is the modulus size in bits. An all-ones bitstring encoding a value less than $n$ needs to be $b-1$ bits, thus we can't use more than $n_\text{Len}-1$ bytes for the padded message. From that we need to remove $H_\text{Len}$ for the hash of tag, and $H_\text{Len}$ for the seed. By a counting argument we need at least one bit to encode the length of the message, which is variable and must be encoded into the padding. That one bit has been rounded up to one byte, and that's all the leeway there is to fit the message of $K_\text{Len}$ bytes.

The scheme to encode the length of the message is that the message is left-padded with a bit at 1, then bits at 0 for what remains. Decoding the bit length of the message (equivalently, removing the padding) remains simple. This scheme is maximally compact for long messages: if RSAES-OAEP allowed bit-sized messages, it would allow messages up to $8\,K_\text{Len}+7$ bits. With such allowance, the entire padding (bits at 0 and the bit at 1) would provide nearly no redundancy: over the $n_\text{Len}–2\,H_\text{Len}–1$ bytes used for message an padding, only the all-zero bitstring would be invalid.


How does a key actually work in symmetric ciphers My sky-high level understanding of modern cryptography is as follows: There is an algorithm and a key. The key or key pair is a randomly generated number (I think). The algorithm describes transformations to be applied to the plain text in order to encrypt it. The key is a specific piece of information that is needed by the algorithm to complete this process of encrypting the plain text. What I do not understand is how, precisely, do the algorithm and key interrelate. One can look at a schematic for, i.e. Serpent and see lots of arrows, boxes, feedback loops and so on. To an interested lay person such as myself, I cannot see:

What the key does to that set of processes or even where it fits in
How it is employed such that it's uniqueness effectively 'locks' the ciphertext.

I apologize for the preposterously rudimentary nature of this question. I do appreciate this board is populated by those with a sophisticated understanding of this subject. However, this has been bugging me for ages and here is an obvious place to ask.

Finally, I understand there isn't a single response to this inquiry given there are different types of keys used for different purposes. In the interest of addressing this, please assume I am referring to the encryption of plain text using a symmetric key algorithm that was fit-for-purpose in 2001 or later.

My sky-high level understanding of modern cryptography is as follows: there is an algorithm and a key.

Sure, a key is generally generated for a specific cryptographic algorithm that takes a key.

  The key or key pair is a randomly generated number (I think).

Not necessarily. AES and Serpent just take a key consisting of random bits. RSA uses two random primes that are used to create the key pair, where the keys consist of multiple parts, at least an exponent and modulus generated from these primes. Or it could be a random in a specific range for the private key of ECDSA or ECDH, where the public key is actually a point on the curve. That private key is probably closest to "a number".

  The algorithm describes transformations to be applied to the plain text in order to encrypt it.

If that algorithm is a cipher, then yes.

  The key is a specific piece of information that is needed by the algorithm to complete this process of encrypting the plain text.

Not sure about the emphasis in that description of the key, as there are other possible pieces like an IV that are required. It's a bit more than that; it is the piece of information that is at least required to complete the process.

  What I do not understand is how, precisely, do the algorithm and key interrelate.

That depends on the algorithm, the algorithm specifies what kind of keys are acceptable, and how large they may be (if there even is a maximum).

  One can look at a schematic for, say, Serpent and see lots of arrows, boxes, feedback loops and so on. To an interested lay person such as myself, I cannot see what the key (i) does to that set of processes or even where it fits in; (ii) how it is employed such that its uniqueness effectively 'locks' the cipher text.

That depends entirely on the algorithm. In block ciphers such as serpent there is a lot of transposition and diffusion going on, generally trying to create an avalanche effect so that many bits is affected even within a single round.

However, with the asymmetric RSA cipher the private key is used for modular exponentiation during decryption and in ECDSA for point multiplication during signature generation. Exponentiation and point multiplication are more mathematical constructs than the bit operations that are common in symmetric ciphers.

  Finally, I understand there isn't a single response to this inquiry given there are different types of keys used for different purposes. In the interests of addressing this, please assume I am referring to the encryption of plain text using a symmetric key algorithm that was fit-for-purpose in 2001 or later.

I've tried to explain it in the simplest way possible, also showing that it matters quite a bit what kind of algorithm we are talking about.

I'd study a bit more about block ciphers and try and e.g. implement S-AES (or SimpleAES, I'm not sure if there is an official name) if you're more of a developer type that learns by acting.


One-time pad XOR question For a one-time pad to be truly secure, do I need to use XOR? In other words, is a numerical OTP as secure as a XORed one?

I'm new to cryptography, so this might not even make sense.

You do not need to use XOR as the combining operation. You can use modular addition as the encryption function and modular subtraction as the decryption function and it will remain information theoretically secure.

XOR is typically used because it is convenient -- it is its own inverse (an "involution"), and it is smaller/simpler to implement in hardware than adders and multipliers.


Problem related to the discrete logarithm problem Let $G$ be a generator of a cyclic group in which the discrete logarithm problem is hard and $x$ and $u$ be scalars of the group such that $X = xG$ and $U = uG$, respectively. We want to compute $J = x^{-1}U$. Is it possible to calculate it without knowing $x$, even if we know $u$?

This problem is equivalent to the Computational Diffie Hellman problem; this remains true even if we know $u$.
See this paper for details; in summary:

Suppose we have an oracle that, given $G$, $X = xG$ and either (depending on the oracle type) $U = uG$ or $u$, gives us the value $J = x^{-1}uG$.  Then, we can use this Oracle to construct a second Oracle that, given $H, aH$, computes $a^2H$ (by passing $G = aH$, $X = H = a^{-1}G$, $U=G$ (or $u=1$), and recovering $J = (a^{-1})^{-1} \cdot 1 \cdot aH = a^2H$.  We can then use this second Oracle to solve the CDH problem (given $G, aG, bG$, we compute $(2ab)G = (a+b)^2G - a^2G - b^G$, and then do a point halving.

Suppose we have an oracle that solves the CDH problem, that is, given $H, aH, bH$, gives us the value $abH$.  Then, given $G$, $xG$, we can compute $x^{-1}G$ by setting $H = xG$, $aH = bH = G = x^{-1}H$ and $bH = H$.  We give this to the Oracle which gives us the value $(x^{-1} \cdot x^{-1}) H = x^{-1}G$.  Then, we can convert that value into $J$ by either multiplying it by $u$ (if we know it), or invoking our CDH Oracle one more time with the inputs $G, x^{-1}G, uG$.


Is any specific packet cipher mode to be prefered for use with – for example – UDP? Cipher modes typically assume data is streamed or read from a reliable channel with guaranteed ordering. However, many communication transports, such as UDP, are not reliable and don't guarantee order of delivery.

I can imagine that there are are some cipher modes which are packet-oriented and can deal with unreliable, unordered datagrams. Is any specific packet cipher mode to be prefered for use with – for example – UDP? And if, what would be the advantages or disadvantages of its alternatives?

All of them can be used to deal with unreliable, unordered datagrams; as long as you can derive an IV for the UDP packet then a cipher mode of operation should succeed. You need some kind of unique method of identifying the packet of course. Note that (the information used to generate the) IV may be public.

Usually you need some way of identifying the packet in the protocol anyway, otherwise you cannot put the packets in the correct order after you've received them out of order.

The form and properties of the IV of course depend on the mode of operation. For instance CBC requires an unpredictable IV, while reuse of the IV in CTR and related modes of encryption will immediately leak information about the plaintext.

CCM is an authenticated mode of operation that was specifically designed for data packets. It consists of a specific combination of CBC-MAC and CTR mode encryption.

EAX has been specified as a successor of CCM and is a lot easier for general use, but it does not include a specific message format to adhere to. So the I/O of EAX is more like GCM, even though internally it has more in common with the CCM mode of encryption.

[EDIT after re-reading the question]

Note that it is not a good idea to rely on cryptography to reorder your datagrams. If you want to reorder, use a sequence number. If you want to verify the reordering, you can of course use a MAC or signature.


Preserving Confidentiality and Integrity in a Public channel Let's say I've got two people that are trying to talk in a public channel $A$ and $B$ and they want to preserve their confidentiality and integrity.

Which cryptographic algorithm would they want to use? Symmetric, or public key based? Also, what type of algorithm suites best and in what key size?

In my understanding, given the fact that the channel is public – and therefore considered unprotected – they will have to use public key first and send a symmetric key after that, thus securing the channel. Regarding key exchange they could use Diffie Hellman or RSA, and on symmetric key MAC.

Is this correct? Could they do it easier? Is there a safer way?

Which cryptographic algorithm would they want to use?

That will really depend on the situation. To select the algorithms one should ask himself (at least) the following questions:
Which standards do you trust? Which standard do you have to use? What computations can you afford?

  Symmetric, or public key based?

It again depends on the situation. Usually you'll use a combination of both, however there are valid use-cases for using only public key cryptography (usually extremely short messages) and for using only symmetric cryptography, usually when performance is a constraint or when a shared secret has already been established (i.e. with embedded devices or in a  session resumption scenario).

  Also what type of algorithm suites best and in what key size?

The algorithms really depend on the situation given. Generally however, 128 - 256 bit symmetric encryption, 256 - 512 bit hash functions, 256 - 512 bit elliptic curves and / or 2048 - 4096 bit classical asymmetric cryptography (RSA, DSA, ...) is in use.

Considering your third paragraph:
In a nutshell, you're right. You first negotiate a symmetric key using asymmetric cryptography (RSA or (EC)DH) and then use symmetric crypto to protect your payload. What you described is basically opportunistic encryption, because neither party takes measures to ensure the authenticity of the other party. This means a man-in-the-middle attack would certainly be possible and thus an active attacker could break the scheme.

  Is there a safer way?

There is: Transport Layer Security (TLS).
TLS is the standard solution for secure real-time data transport and even has some nice security proofs. TLS can take care of all the situations you can possibly encounter: You can use a pre-shared key, you can authenticate against a server with a password (via SRP), you can use a certificate (or just a public key) for only one or both parties and even is widely deployed with famous libraries being OpenSSL, LibreSSL, BoringSSL, ....


Can an RSA (private) modulus contain (hex) zeroes? Consider a public modulus that is supposedly 4096 bits. But since it contains two hex pairs of zeroes, i.e. ...:00:...:00... such that the bit length of the decimal value instead becomes 4093 bits, is it actually a 4096 bit key or not?

I hope my question is vaguely intelligible.

Edit:
modulus is here https://pastebin.com/adYe0F7g
The reason for my (stupid) question is that I was told it would have the size of 4096 bits, but when I do what I see many do in for example Python to calculate the bit length -> int(hexN, 16).bit_length() it turns out to be 4093.

There is no such thing as a "private modulus". There are the secret primes and the secret exponent, and there is the public modulus. Assuming you are talking about the primes or the secret exponent, are these bits in the most significant (leftmost) position, or are they somewhere in the middle or end? If they are in the most significant position, then they do not count towards the size of the integer. After all, any finite integer at all can be thought of as having an infinite number of leading zeros! If the zeros are somewhere within the integer, they serve to change its value. A random integer is expected to have a few null bytes.

Think about it this way: there is no difference between 0123 and 00123 (both are the same number), but there is a big ten-fold difference between 1230 and 12300, despite both adding a single zero. Of course this is base 10 whereas hex is base 16, but the principle is the same and zero means the same thing.

You can easily calculate the size of your key by taking the ceiling of the binary logarithm of the public modulus. That is, you can calculate $\lceil\log_2(N)\rceil$ for an integer representation of the public modulus $N$.


Understanding multiplication in the AES specification I am reading through the AES specification and am not able to wrap my head around the multiplication definition (section 4.2).

In section 4.2 why is the modulo chosen as {01}{1b} which is $283$ and not $255$? The irreducible polynomial is $m(x)=x^8 +x^4 +x^3 +x+1$. Is there a significance to this seemingly random choice? Later on in the explanation it also says the modulo operation produces values that can be represented in a single byte. How is that possible if the modulo is performed over $283$?
Later on the same section in the example {57} • {83} is computed to be $x^{13} +x^{11} +x^9 +x^8 +x^6 +x^5 +x^4 +x^3 +1$ - which is $11129$. Using a calculator it appears this is wrong. Its coming out to be $11397$. What am I missing?
In section 4.2.1 (multiplication by $x$) it says - It follows that multiplication by $x$ (i.e., {00000010} or {02}) can be implemented at the byte level as a left shift and a subsequent conditional bitwise XOR with {1b}.

Here again I don't get it. By my understanding it should be a left shift followed by modulo with {01}{1b}.

Can someone please explain this to me?

011b is a hexadecimal representation of the polynomial $m(X) = X^8 + X^4 + X^3 + X + 1$ (so you should never regard it as an integer). This polynomial has coefficients in the finite field $\mathrm{GF}(2)$, which is just the math-y way to say that its coefficients are in $\{0,1\}$:

hex | 0    1    1    b
bin | 0000 0001 0001 1011
x^n |         8 7654 3210

The 1-bits indicate which power has a coefficient of $1$. When you take any polynomial and divide it by $m(x)$, which has degree $8$, the remainder will have degree smaller than $8$, so using the same representation scheme as above, it can be represented on one byte.
57 and 83 are likewise representations of polynomials using that same method, I will leave it to you to check that when you multiply those two polynomials, you do indeed find the asserted result.
Your understanding is correct, those two operations are the same. But again, remember that you are working on polynomials, not integers.

EDIT: It's important to understand the difference between the objects AES manipulates and those you are used to. When you think of a data type which takes only one byte, you think of integers in $\{0,\dots,255\}$ with the usual addition and multiplication modulo $256$. The problem with those numbers is that while they have all the nice properties we are used to for addition, they fail catastrophically for multiplication: you can take two non-zero numbers (which ones?), multiply them, and obtain $0$!

This is not acceptable for AES: it requires a "nice" multiplication operation, meaning that when you multiply two non-zero elements, you want to obtain a non-zero element. This weird system of polynomials modulo $m(X)$ does exactly this.


What are standard cryptographic assumptions? I am struggling to understand what is meant by "standard cryptographic assumption".

The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions."

But what are standard cryptographic assumptions? I suppose that

FACTORING: Given a positive integer $n$, find its prime factorisation.
Quadratic Residuosity Problem (QRP): Given an odd composite integer $n$ and $a$ with Jacobi Symbol $(a|n) = +1$ decide whether $a$ is a quadratic residue or a pseudosquare modulo $n$.

are commonly assumed to be difficult and thus "standard cryptographic assumptions". Is why GM is provably secure? But what about the RSA Problem (RSAP)?

  Given are a positive integer $n$ that is a product of two distinct odd primes $p$ and $q$, a positive integer $e$ with $\gcd(e, (p-1)(q-1)) = 1$ and an integer $c$. Find an integer $m$ such that $m^e \equiv c \pmod n$.

Is RSAP also commonly supposed to be hard? Is thus RSA provably secure?

I am struggling to understand what is meant by "standard cryptographic assumption".

‘Standard assumption’ broadly means an assumption that has withstood the scrutiny of many smart cryptanalysts for a long time.  Examples:

We think that, for uniform random 1024-bit primes $p$ and $q$, solving $y = x^3 \bmod pq$ for uniform random $x$ is hard given $pq$ and $y$.

Why?  The best way anyone has been able to figure out how to do it is by factoring $n$ to recover $p$ and $q$, and the best known methods—ECM and NFS—cost more than anyone has the budget for.
We think that solving $y = \operatorname{AES}_k(x)$ for uniform random $k$ is hard given $x$ and $y$.

Why?  The best way anyone has been able to figure out how to do it is essentially by a generic search, and the best known methods—parallel rainbow tables, parallel distinguished points—cost more than anyone has the budget for.

Half-examples:

Pairing-based cryptography.  Pairings are highly popular in academic cryptography at conferences but see very little use in the real world, outside exotic cryptocurrency applications.  The security story for pairing-friendly elliptic curves is nowhere near as stable as the security story for elliptic curves for more traditional DLOG applications like Diffie–Hellman key agreement and Schnorr signatures.
SVP, LWE, and other lattice problems.  Lattices are a promising area for post-quantum cryptography, but there is a large design space with a complicated security story that has not stabilized yet—no matter how many completely incomprehensible arguments Chris Peikert and Dan Bernstein have about average-case/worst-case reductions on Twitter.

Non-examples:

Conjugacy search in a braid group.  Braid cryptography is not widely studied by cryptographers and most existing proposals turn out to be broken.
SIMON and SPECK.  These block ciphers are popular among spooks trying to muscle their way into international standardization, but it turns out standards bodies are no longer happy to accept the word of spooks without technical justification these days, and also block sizes smaller than 128 bits are foolish.

  The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions."

This is an example of academic obfuscation, and evidence that Wikipedia is a terrible resource for learning about cryptography.  What it means is:

We proved a theorem,1 and the theorem involves pretty number theory2 and asymptotic growth curves!3

1 This is what provable security means.  It does not mean that the theorem has any real-world consequences whatsoever.

2 This is what ‘standard assumptions’ means here: ugly problems like inverting DES are not allowed, but pretty problems like factoring a product of uniform random primes are allowed.

3 Not formally stated: We are only interested in asymptotic growth curves of attack costs for families of problems, so DES is doubly disqualified both because it's ugly and because there's only one DES, whereas you can consider the problem of factoring as a function of the size of the factors.  (‘Provable security’ treatment with concrete parameter choices, sometimes called ‘exact security’, didn't come until a decade later with the help of Bellare and Rogaway.)

To be fair, the GM paper was helpful for setting down some formalizations like semantic security for public-key encryption, which is essentially equivalent to the modern standard of ciphertext indistinguishability which we use today.  But the GM encryption scheme?  Completely useless, even if there is a theorem.

This kind of obfuscation—and fetishization of number-theoretic prettiness—leads people down regrettable paths like adopting Dual_EC_DRBG, which admits proofs of ‘number-theoretic-based security’, as major national cryptography standards simply by virtue of being number-theoretic, propelled by prestidigitators like Dan Brown whose principal area of expertise is obfuscating gaping back doors among reams of analytic prose that nobody can get through.

  Is RSAP also commonly supposed to be hard? Is thus RSA provably secure?

The RSA problem—computing $e^{\mathit{th}}$ roots modulo a product of large secret primes—is commonly supposed to be hard.  There are public-key encryption schemes and public-key signature schemes built out of RSA that have theorems—e.g., RSAES-OAEP, RSA-KEM, RSASSA-PSS, RSA-FDH—which are even somewhat useful in relating the difficulty of breaking the security of the cryptosystem (distinguishing ciphertexts, forging signatures) to the difficulty of computing $e^{\mathit{th}}$ roots modulo a product of large secret primes.

But I recommend that you stay away from the dishonest term of art ‘provable security’ because it obfuscates what you're actually saying—especially in the form ‘X is provably secure’.

Whether a scheme has ‘provable security’ or not is irrelevant to users or engineers making decisions about building systems—the conclusions of cryptanalysts about what cryptography will withstand attack are what's relevant to them.  ‘Provable security’ is really about guiding cryptanalysts to focus their effort.  There's no point in analyzing AES-CTR separately from AES, because any way to break AES-CTR either (a) depends on on misuse of CTR, (b) is based on AES's nature as a permutation rather than arbitrary function, or (c) implies an attack on AES.  That's because there is a useful theorem relating any attack on AES-CTR to an attack on AES itself.

Similarly, there's not much point trying to forge RSA-FDH signatures without trying to compute $e^{\mathit{th}}$ roots, because—thanks to a useful theorem—we know that any work done on one problem translates immediately to the other, as long as the hash function doesn't interact in any interesting way with RSA (which would be quite astonishing).  So cryptanalysts can ignore the details of RSA-FDH and focus on computing $e^{\mathit{th}}$ roots to give us confidence in the security of RSA-FDH.


Proof of the Diffie-Hellman Key Exchange Could someone please provide the math proof;
$$ ((g^a)\bmod p)^b \bmod p = ((g^b)\bmod p)^a \bmod p $$

Let $g^a = x \bmod p$ then  $k \in \mathbb{Z}$; $$g^a = x + k \cdot p$$ Now take $b$-th power of both sides and $\bmod p$.
\begin{align}
(g^a)^b &= (x + k \cdot p)^b \pmod p\\
g^{ab} &= x^b + x^{b-1}(k \cdot p) + \cdots + (k \cdot p)^b \pmod p\\
g^{ab} &= x^b \pmod p
\end{align}
Similarly;
Let $g^b = y \bmod p$ then $g^b = y + \ell \cdot p$ now take $a$-th power and $\bmod p$ and arrive
$$g^{ab} = y^a \pmod p$$
Therefore $$x^b = y^a = g^{ab} \pmod p$$


Can a CSPRNG, seeded with a key, be used to generate a byte sequence as long as the plaintext to XOR it with that? Given a “safe” (meaning: brute-force is your only shot) cryptographically strong PRNG, wouldn't it be safe to encrypt data using the CSPRNG to create a key as long as the data and then encrypt the data by XORing it with the key?

Yes it would.

As CodesinChaos reminded us in his comment:

  We call that a (synchronous) stream cipher.

Look up RC4 and A5/1, two of the most statistically popular ciphers in the universe.  Also compare to a correctly generated one time pad.  Not a lot else to say at this point.


Can an ephemeral RSA key give forward secrecy? Suppose party A generates an ephemeral RSA key and sends the public key to B.  Party B then generates a symmetric key, encrypts it with Party A's public key and sends the Ciphertext to Party A.  Party A then decrypts the key that party B sent.  Parties A and B then use the key that B generated to encrypt data.

Does that meet the definition of Perfect Forward Secrecy?  If so does that mean that RSA could still be used in a protocol like TLS and meet the new Perfect Forward Secrecy requirement?

Yes and yes and it already (almost) does.

Forward secrecy is defined with regards to the notion of "long-term secret". The idea is that any secret that is stored for a long time is potentially amenable to ulterior theft. Forward secrecy is obtained when stealing long-term secrets does not allow breaking past communications, and the easiest way to achieve such secrecy is to use ephemeral keys: if a key is not stored anywhere, then it cannot be stolen afterwards.

In older days, SSL/TLS implemented some "export" cipher suites that were meant to comply with the then-strict US export regulation on cryptographic software. When using an "RSA_EXPORT" cipher suite (like TLS_RSA_EXPORT_WITH_DES40_CBC_SHA), the server would have a long-term RSA private key; if that long-term RSA key was longer than 512-bits, then the server would generate a 512-bit ephemeral key pair, sending the public part as a ServerKeyExchange message, signed with the long-term RSA Key. This mechanism was, ironically, meant to support the opposite of forward secrecy, in that the goal was to allow the encryption to be broken through even in cases where the long-term secret was not stolen. However, it demonstrates the mechanism just well: server sends an ephemeral public key for the key exchange, and that public key may be of type RSA.

Some noteworthy details:

Though the server sends a RSA public key in a ServerKeyExchange message that it signs itself, and thus can potentially generate an ephemeral key pair, nothing forces the server not to reuse or even store that key pair. In fact, since generating a RSA key pair is a relatively expensive operation, most servers were reusing such key pairs for long period of times; possibly, the 512-bit key pair was stored in a file, or generated upon process startup and reused for weeks. This allows an attacker some time to break the key (512-bit RSA can be broken with relatively little computing power) and use that knowledge in some Man-in-the-Middle attack. This has been dubbed the FREAK attack.
Though the "ephemeral RSA" mechanism was defined, it was not updated to longer key lengths, because implementing it was felt to be too clunky and expensive. When SSL/TLS implementations use ephemeral keys, they do so with Diffie-Hellman (DHE cipher suites) or an elliptic-curve variant thereof (ECDHE cipher suites). Diffie-Hellman allows for very efficient generation of a new key pair, contrary to RSA. Moreover, ECDH tends to be a lot more efficient than RSA, both in terms of CPU (less work) and bandwidth (public elements are smaller).

Using ephemeral RSA key pairs would make sense in the very specific context of an very small, powerless client talking to a big server. On the client side, this would entail only public RSA operations (signature verification, asymmetric encryption) that can be made very fast by using a very small public exponent (e.g. $e = 3$). Clients that are so small that they cannot perform an ECDHE key exchange in reasonable time also have a hard time running a full-fledged SSL/TLS protocol, because of network issues (bandwidth, latency because of the two round-trips...) and lack of readily available implementations that comply to the server constraints of such platforms (code size, very little RAM...).


libsodium x25519 and Ed25519 small order check Studying libsodium implementation of x25519 and Ed25519 I saw that it performs an small order check comparing given inputs with a hard coded blacklist of values. Is this list exhaustive or it is a list of currently known invalid points?

Source code:

X25519 blacklist

Ed25519 blacklist

Short answer: You don't need to worry about the blacklist or point validation unless you are designing an exotic protocol.

Medium answer:

It depends on what you are trying to do.  There is a short blacklist, and a much larger set of points (too large to list) that may cause you trouble—but only if you are setting yourself up for trouble by using the primitives in an unusual novel protocol and expecting unusual security properties from them.

The ‘blacklisted’ points have low order: each point $P$ has the property that there is a very small number $n$, in this case always a divisor of 8, such that $[n]P = \mathcal O$.  Thus there are only at most 8 different scalar multiples of each of these points.

This significantly reduces the number of possible shared secret values that someone computing a ‘shared secret’ using their private secret scalar $n$ and a malicious peer's ‘public key’ $P$, nearly or completely negating the contribution of the secret scalar $n$ of which there are $2^{251}$ possibilities.  None of the low-order points are actually valid public keys: the standard base point $B = (9, \dots)$ does not generate them.

In sensible protocols, you normally don't need to worry about these points at all:

In an interactive key agreement, (a) a malicious peer is usually out of scope, (b) a MITM should be detected by authenticating the transcript, and (c) you hash the entire transcript of the key exchange including the shared secret and the hapless sap's public key $[n]B$ to produce a session key for a subsequent conversation.
In a signature system, you rely on verification under known public keys; a malicious signer giving one of the ‘blacklisted’ points is out of scope.  Blacklisted points in signatures can't fool verifiers—the signature scheme would be horribly broken if they could.

For more details on validation, see Trevor Perrin's article on point validation in such protocols.

Any other properties, you have to be very careful about, e.g. uniqueness of public keys or signatures—and here the blacklist is not sufficient.  Why is the blacklist not sufficient for some obscure applications requiring obscure security properties?  If $P$ is a point of low order, and $n$ is a legitimate user's secret scalar, then for any point $Q$ generated by the base point $B$, $[n](P + Q) = [n]Q$.  This happens because every legitimate secret scalar is a multiple of 8, the cofactor, and so annihilates $P$, i.e. $[8]P = \mathcal O$ is the identity.  Such incautious design of a novel protocol requiring novel security properties thoroughly flummoxed Monero last year, after a casual comment by Trevor Perrin explaining this.

Long answer:

The groups that X25519 and Ed25519 work in have some nontrivial structure which make the so-called ‘invalid points’ relevant.  I'll focus on X25519.

Every group has an identity element, which we call $\mathcal O$.  Every element $P$ of a finite group (written additively) has a finite order $n = \operatorname{ord}(P)$, the smallest positive number of times that adding it to itself $P + \cdots + P = [n]P$ yields the identity $\mathcal O$.  The order of the identity is 1; all other points have order greater than 1.

X25519 works in the prime field $\mathbb F_p$ where $p = 2^{255} - 19$, also known as $\mathbb Z/(2^{255} - 19)\mathbb Z$.  Specifically, it works on bit string encodings of the $x$ coordinates of points on the curve $$E/\mathbb F_p \colon y^2 = x^3 + 486662 x^2 + x.$$  Every curve point $P$ except the identity $\mathcal O$ has an $x$ coordinate, which we will call $x(P)$.  We additionally define $x_0(P) = x(P)$ when $P \ne \mathcal O$, and $x_0(\mathcal O) = 0$.

It turns out that if $P \in E(\mathbb F_{p^2})$ has $x_0(P) \in \mathbb F_p$, then for every integer $n$, $x_0([n]P) \in \mathbb F_p$, and every $P$ with the same $x_0(P)$ has the same $x_0([n]P)$.  That is, scalar multiplication keeps the $x$ coordinate in the base field $\mathbb F_p$ and not in an extension field, and the $x$ coordinate of the scalar multiple $[n]P$ is uniquely defined by the $x$ coordinate of the base point $P$.  This is Theorem 2.1 of the Curve25519 paper.

You don't need to understand all the details—suffice it to understand that since we work only in encodings of elements of $\mathbb F_p$, the only points we ever have to worry about are those in the group $E(\mathbb F_{p^2})$ with $x$ coordinate in $\mathbb F_p$.  (Why might we have to worry about $\mathbb F_{p^2}$ at all, a quadratic extension of $\mathbb F_p$ that adds fabricated square roots to nonsquare elements of $\mathbb F_p$?  There are some $x$ coordinates for which $x^3 + 486662 x^2 + x$ is nonsquare, so there is no corresponding $y$ coordinate in $\mathbb F_p$, but there is one in $\mathbb F_{p^2}$.)

The group $E(\mathbb F_p)$ of $\mathbb F_p$-rational points, or roughly those whose coordinates are in $\mathbb F_p$ and not an extension field (more precisely, the fixed points of the componentwise action of the automorphism group of $\overline{\mathbb F_p}$ that fixes $\mathbb F_p$; this definition works with projective coordinates too), has $8 p_1$ elements, where $p_1 = 2^{252} + 2774231777737235353585193779088364849$ is prime, and 8 is called the cofactor.  By a standard theorem of group theory, the order of every element of $E(\mathbb F_p)$ divides $8 p_1$.  This means that every element of $E(\mathbb F_p)$ has one of eight possible orders: $\{1, 2, 4, 8, p_1, 2p_1, 4p_1, 8p_1\}$.

The twist group, which is the subgroup of $E(\mathbb F_{p^2})$ with $x$ coordinates in $\mathbb F_p$ and $y$ coordinates not in $\mathbb F_p$, has $4 p_2$ elements, where $p_2 = 2^{253} - 5548463555474470707170387558176729699$ is also prime.  This is the group that we don't ordinarily work with (there is no multiple of the standard base point in this group except the identity), but which about half the possible $x$ coordinates that X25519 can handle will decode to.  Thus, the order of every element in the twist group divides $4 p_2$, and therefore the only eight possible orders are $\{1, 2, 4, p_2, 2p_2, 4p_2\}$.

Legitimate X25519 users choose public keys of the form $x_0([8a]P)$, where $P$ is a standard base point of prime order $p_1$, and shared secrets of the form $x_0([8a]B)$, where $x_0(B)$ is their peer's public key.  The factor 8 means that the public key $x_0(B + Q)$ for a point $Q$ of order 8 (also called an 8-torsion element) yields the same shared secret as the public key $x_0(B)$, because $[8a](B + Q) = [8a]B + [8a]Q = [8a]B + [a][8]Q = [8a]B + [a]\mathcal O = [8a]B$.  A malicious peer could choose such a $B + Q$, which is bitwise distinct from $B$ but always yields the same shared secret.  A malicious peer could choose $B$ not of the form $[8b]P$ at all but rather a point of low order, which would reduce the number of possible shared secrets to 1, 2, 4, or 8.  E.g., they could choose $\mathcal O$; then the ‘shared secret’ would be $x_0(\mathcal O) = 0$—that's where the zero check comes from.

The blacklist is the list of all points that will give zero as the ‘shared secret’.  It does not list all illegitimate public keys—there are too many to list, of the form $B + Q$ where $B$ is a legitimate public key (of which there are $p_1$ possibilities) and $Q$ is on the blacklist.  The only way to detect legitimate public keys is to confirm that $[p_1]B = \mathcal O$.

But for most protocols the threat model that could cause trouble by substituting illegitimate public keys is irrelevant because the same attacker, the same malicious peer, could cause trouble in all sorts of other ways anyway.  For example, in DNSCurve, which was probably the original application of X25519 using static-static DH key agreement, the only problem that a malicious nameserver or user could cause by using an illegitimate public key is to leak the peer's secrets on the wire to an eavesdropper—which they could do anyway.


Is there a ready report about character order frequency in most common passwords? There are charts about most used letters in English. What about the letter order? For example letter X has a bigger chance to appear than letter Y as the first character and something else for the 2nd character.

In terms of English language, what you are asking about are digram frequencies.

http://www.viviancook.uk/SpellStats/DigFreqs.html


Common reference string in NIZK I want to ask that does the common reference string in NIZK have to be
random?

Or can it be anything?

The common reference string in NIZK does not have to be uniformly distributed.

It is to be sampled from whatever distribution the NIZK protocol specifies.

However, the common random string in NIZK does have to be uniformly distributed,

and the setup strings in NIZK also have to be uniformly distributed.


Calculating distance between two vectors using Paillier homomorphic encryption I am basically trying to perform euclidean distance calculation in the encrypted domain (Paillier encryption). Using the homomorphic properties of Paillier, the squared euclidean distance formula can be written as (paper):

$\newcommand{\opn}{\operatorname}$
$$\underbrace{\opn{Enc}\left(\sum^d_{i=1}p_i^2\right)}_{\text{(I)}}\cdot \underbrace{\opn{Enc}\left(\sum^d_{i=1}q_i^2\right)}_{\text{(II)}}\cdot \underbrace{\prod^d_{i=1}\opn{Enc}(q_i)^{-2p_i}}_{\text{(III)}}$$

I tried implementing this in matlab using two sample vectors a and b but I seem to be getting a completely wrong distance when decrypted. The euclidean distance of the two vectors without encryption is 100.5883 but when applying the above formula and then decrypting the result I get 10118

%I'm using the variable precision integer toolbox (vpi) to handle large numbers in Matlab
a = [10, 58, 23, 59, 78, 11];
b = [87, 15, 12, 32, 41, 22];

p = 708481;
q = 708497;
r = 461563;

n = p * q;

% calculating (I) from above equation, i.e. a^2
encA =vpi(zeros(size(A))); %initialize vector for encrypted values
sumA = 0;

for i=1:length(A)
    encA(i) = PaillierEncrypt(A(i), p, q, random_r); %this will encrypt the value at index i in the vector
    sumA = sumA + (A(i))^2;
end

enc_sumA = PaillierEncrypt(sumA, p, q, random_r); %now encrypt the summed value

% below is for (II) and (III) in the equation i.e. b^2 -2ab
encB =vpi(zeros(size(B)));
sumB = 0;
enc_prodAB = vpi(1);

for i=1:length(B)
    encB(i) = PaillierEncrypt(B(i), p, q, random_r);
    sumB = sumB + (B(i))^2;

%the below block is to assist in determining the mod of a negative exponent, basically it allows for this to run without error: mod((encA)^(-2*vpi(B)), n*n);
    a2 = encA(i); %the encrypted base
    d2 = (-2)*vpi(B(i)); %the exponent that is a non encrypted scalar
    n3 = n*n;

    negpowermod = @(a,d,n2) minv(powermod(a,abs(d),n2),n2);

    result = negpowermod(a2,d2,n3);

    enc_prodAB = enc_prodAB * result;
end

enc_sumB = PaillierEncrypt(sumB, p, q, random_r);

dist = enc_sumA * enc_sumB * enc_prodAB;

Ive commented the above code as best I could to explain what I am doing. I'm sure I messed up the implementation somehow.

Some guidance would really be appreciated. Thanks

I don't see your problem.
10118 is indeed the square of the euclidian distance ~100.5883


2DES and 3DES against a DES build with complimentary I saw this complicated question and I am not really sure about it, would appreciate your view on it.

Is the following build stronger than 2DES or 3DES with 2 different keys (or even normal DES)?

$DES(DES(x,k),\overline{k})$

what I think is that in regards to a $2^{56}$ key space, we need to perform the following:

regular DES: we need to schedule the key $k$, and then test $E(k,m),k'$;
regarding 2DES/3DES with two different keys: unsure, but I think that in this case we need to schedule $k_1 = k$ and $k_2 = \overline{k}$. I would appreciate seeing how to properly decide if it makes it a stronger build than those (2DES,3DES - both with two different keys).

For simplicity sake (and question sake) assume that the adversary has a small amount of known plaintext:ciphertext pairs.

Is the following build stronger than 2DES or 3DES with 2 different keys (or even normal DES)?
$DES(DES(x,k),\overline{k})$

It is only slightly stronger than DES; it is considerably easier to attack than 2DES or 3DES.
The most practical attack against DES is brute force; simply try the various possible keys until you stumble on the correct one.  With a known plaintext/ciphertext pair, this takes an expected $2^{55}$ DES evaluations.
Against your design, because the key is still only 56 bits, this brute force method is still practical.  In your case, this takes an expected $2^{56}$ DES evaluations.
We generally don't know the attacker's capability to that much precision, a factor of 2 increase in the work effort is well below our uncertainly (and hence are effectively the same).
In contrast, 2DES can be attacked with the same approximate work effort; however the algorithms that do that require a significant amount of memory, and are harder to parallelize (and hence are, in practice, more difficult to do).
Also, if you think that your design forces two DES key schedules for every DES key tested, that turns out not to be the case.  Because of the DES key complementation property, we have:
$$DES(DES(x,k),\overline{k}) = \overline{ DES( \overline{ DES(x, k) }, k)}$$
Hence, a key can be tested by performing two DES evaluations on the same key, and an intermediate complementation.


How to ethically publish the result in case we prove that P = NP? Suppose a researcher discovers that $P=NP$, and has an efficient algorithm for some common NP-Complete problem.  Given the implications for cryptography, what would be the most ethical way for them to reveal this knowledge to the world, without causing the downfall and destruction of technological civilization?

I'll try to answer what I view to be a much easier question to answer, while still (in my view) capturing the "essence" of the problem.

How can one "prove" that they have an efficient algorithm for an NP-complete problem without publishing the algorithm?

There are many things one can do, but the simplest is to solve challenges.
There are a large number of computational challenges which have been posted over the years, for example:

RSA factoring challenges

Lattice Crypto challenges

If one solved a variety of these challenges in extremely high dimension and posted the solutions publicly, it would very quickly erode confidence in the hardness of the underlying problems.
After waiting a suitable amount of time, you could then publicly post your algorithm.
Of course, it is difficult to talk about what a "suitable amount of time" is for public disclosure that would break all of cryptography, which is why I avoided your initial question.


Proof of lemma 1 Paillier encryption In the original paper of Paillier, lemma 1 shows why $n$ must divide the order of $g$. What I don't understand in the proof of this lemma is why $g^{x_2-x_1}(y_2/y_1)^n$ implies $g^{\lambda(x_2-x_1)}$. Where does this result come from?

This is obtained by raising to $\lambda=\lambda(n)$: since the order of any element in $\mathbb{Z}_{n^2}$  divides $n\cdot\lambda$, the second part cancels out:

$$\begin{align}
    g^{x_1-x_2}\cdot(y_2/y_1)^n=1\bmod{n^2} &\Leftrightarrow\\
   g^{(x_1-x_2)\cdot\lambda}\cdot(y_2/y_1)^{n\cdot\lambda}=1\bmod{n^2}&\Leftrightarrow\\
  g^{(x_1-x_2)\cdot\lambda}\cdot 1=1\bmod{n^2}&\Leftrightarrow\\
g^{(x_1-x_2)\cdot\lambda}=1\bmod{n^2}
   \end{align}$$


Is this method of salting effective? So this is my first post on this forum, so bear with me if I sound stupid. I am creating my own web application with JavaScript and MongoDB. I am storing all user information in a Mongo table, and currently this is the hashing algorithm I used to store the passwords:
function generatePassword(input) {
     return Buffer.from(crypto.createHash('sha256').update(input).digest('base32')).toString('hex').toUpperCase();
}

So, from what I recall from previous Cyber Security classes, sha256 has been long cracked, therefore deeming it insecure for storing passwords. I understand this being my web application I will not be experiencing security breaches, but I want to show that I have the awareness and knowledge to correctly and securely store the passwords. Therefore, I thought that if I changed up the code a little bit by using this:
function generatePass(input) {
     input = input + "455kjnr2902rug5348934";
     return Buffer.from(crypto.createHash('sha256').update(input).digest('base32')).toString('hex').toUpperCase();
}

I guess my questions are, is this
a. An effective salting method? If not, how would I go about salting the password?
b. Is there a more secure way of doing this? Is this basically useless, or useful?
Thanks in advance to anyone who can help!

Sha256 has not long been cracked, but it's not useful for human-generated passwords. You want a key stretching function. SubtleCrypto provides PBKDF2 (documentation), which is fine. Other libraries might support bcrypt, scrypt, or Argon2, any of which would be better.
Salts should be unique per user. This is so that when two users have the same password, the hashes will be different. This prevents a variety of attacks, like rainbow tables or looking at the frequency of hashes. Having a constant value appended to the password doesn't make these attacks any more difficult.


How resilient to attackers with extreme resources available is this encryption method? How could the following scheme be made more resilient to attacks capable of utilizing massive amounts of resources?

Assume all random values are cryptographically secure.

Key derivation: scrypt using a random 16 byte nonce. The work factor is 1048576 which takes a GB of memory and ~3 seconds to compute on a 2500k.

Authentication: HMAC with SHA-512 as the hash function. Authentication key is the SHA-512 of the AES key. HMAC checks are done using equal time compare.

Encryption algorithm: AES-256 in CBC mode using a 16 byte random IV.

Asymmetric keys are used in TLS which allows access of the encrypted data over a network.
4096 bit RSA is used due to ease of generation.

The end result of the cipher text can be described like so:

nonce | iv | cipherText| HMAC Digest

Thanks!

EDIT: Sorry guys I should have described my use case. This is for encrypting a specific file.

The authentication is used to securely ensure that the file hasn't been tampered with as well as check the key before decryption.

All looks pretty secure except for your auth key derivation. You should use a better key derivation method like HKDF instead of just SHA-512.

I don't think your random nonce is doing anything in this scenario - an attacker who wants to brute-force a weak password wouldn't be slowed down by a nonce transmitted in the clear. Why not just use a randomly-generated AES key and a key exchange scheme? This would really confound an attacker with massive (e.g. nation-state level) resources. The NSA would laugh at your puny attempts to use scrypt to slow down brute-forcing.

EDIT: Wikipedia's article on Diffie-Hellman key exchange should get you started.


Can you help me understand some details about the attack using SSL3 POODLE bytes? I have read some articles or books (e.g., “Bulletproof SSL and TLS”) about POODLE, but they still don't answer my questions – which are:

From https://www.openssl.org/~bodo/ssl-poodle.pdf,

  Usually, the server will reject this record, and the attacker will simply try again with a new request.

My question is:

Because this paper doesn't mention the attacker how to try again, I guess the attacker need try to modify the last byte ($C_{n-1}[15]$, from 0x00 up to 0xFF) of $C_{n-1}$ to reveal the cookies’ first previously unknown byte. I want to make sure if my understanding is correct or not?
From Adam Langley's blog (https://www.imperialviolet.org/2014/10/14/poodle.html)

  The critical part of this attack is that SSLv3 doesn't specify the contents of padding bytes (the •s). TLS does and so this attack doesn't work because the attacker only has a $2^{-64}$ or $2^{-128}$ chance of a duplicated block being a valid padding block.

My question is:

How does Adam get the chance ($2^{-64}$ or $2^{-128}$) in TLS?

to try again, I guess the attacker need try to modify the last byte

No. Some other (symmetric) padding oracle attacks do that, but here the attacker can't tweak the prior block and try another decryption because the MAC error already caused the session to be terminated. Instead the attacker causes the client (browser) to make a new request with the same data, and thus the same target plaintext (the cookie byte), but a random new key and state (IV). Statistically 1/256 of the time the last bytes in the $C_{i-1}$ (edited) and $C_{n-1}$ ciphertext blocks will be a 'lucky' pair that combines with the target (last) byte in $P_i$ so that the tampered plaintext block $P'_n$ ends with the desired value, 15 or 7 depending on the cipher blocksize. I.e. depending on your point of view either 1 of 256 values in $C_{n-1}$ reverses $C_{i-1}$ or 1 of 256 values in $C_{i-1}$ reverses $C_{n-1}$; the math treats them identically. For a slightly longer explanation, see my answer here or Steve Peltz's here.

  How does Adam get the chance ($2^{−64}$ or $2^{−128}$) in TLS?

Since TLS unlike SSLv3 checks all the padding octets, there is only one valid all-padding block out of all possible blocks the size of the blocksize of the cipher, which is either 128 bits for AES Camellia SEED or ARIA, or 64 bits for triple-DES or IDEA -- or original DES or the deliberately weakened 'export' DES-40 or RC2-40 if still used, although even implementations that still used SSLv3 protocol prior to POODLE should have disabled the single-DES and export ciphersuites.


Distributed Shamir's secret sharing Wikipedia on its page for Shamir's secret sharing scheme provides a python implementation that applies the idea. This algorithm will generate a (k, n) threshold scheme so for example we could split a secret in 6 parts and we would need only 3 of them to recreate it.

But isn't the idea of this scheme to be used by a number of various agents that each one will generate only a part of the key and share it? This way each agent can then create the secret key by combining the parts he will receive.

What would be the proper way to make this algorithm distributed and not generating everything in one computer?

Each participant can create his own random k,n secret sharing and send one share to each other participant.
Each participant can then add up his sub-shares to get his final share.

Due to linearity the resulting is also a valid shamir secret sharing.

This produces a random shared secret. If there is something you want to protect with it, we need to ask who knows it initially?


How to recover a message with shared modulus for textbook RSA Same message sent to two users encrypted with textbook RSA, known $n$, $e_1$, $e_2$, $c_1$, $c_2$. Show how the attacker can recover the message.
Problem statement

Consider an RSA system with $n=143$, $e_1=7$ and $e_2=17$. Suppose the same message $m$ was sent to the two users above and the attacker observed the ciphertext $c_1 =42$ and $c_2 =9$. Show how the attacker can recover the message.

Official solution

Use Extended Euclidian algorithm to find $a$ and $b$ such that
$a\,e_1 + b\,e_2 = 1$. Then we obtain $m$ as ${c_1}^a + {c_2}^b \bmod n$ thus $m=3$

My attempt at solving the problem
Having read this and watched this, I did the following, but I get the wrong answer:
Using the Extended Euclidean algorithm I get $a = 5$ and $b = -2$ for  $a\,e_2 + b\,e_1 = 1$. (According to the comment section of the YouTube video, $a$ from the video, let's call it alpha, needs to be greater than or equal to $b$ from the video, let's call it beta; alpha = $e_2$ and beta = $e_1$.)
Then
$$\begin{align}
m &= ({c_2}^a + {c_1}^b) \bmod n\\
i &= {c_1}^{-1} \bmod n\\
m &= ( {c_2}^a i^{-b} ) \bmod n\\
i &= 42^{-1} \bmod 143\\
42i &= 1 \bmod 143\\
i &= (1+143\times \nu)/42\\
\nu &= 37\implies i = 126\\
m &= ({c_2}^5 + i^2) \bmod 143\\
m &= (9^5 + 126^2) \bmod 143\\
m &= 136 \neq 3
\end{align}$$
Could someone please help me figure out what I am doing wrong?
Edit:
Here's my work (in a corrected way), and in a way that won't expire (since the message where I showed my work will eventually expire), in case it helps someone else:
For 1 to 3 of the "Hint to derive the correct equation" part:
To prove that m^1 mod n = m, we know that since m < n and anything less than than the divisor yields the dividend in a modulo expression.
Then, using the properties you mentioned ( the x^(u+v) and x^(uv) stuff from here: https://crypto.stackexchange.com/revisions/81829/21 ), with the constraints described in (4) from here ( Definition of $x^u \bmod k$ ), I get
m = m^1 mod n
m = m^(a e_1 + b e_2) mod n
m = [m^(a e_1) mod n] ] m^(b e_2) mod n] mod n
m = ({[m^(e_1) mod n]}^a) mod n ({[m^(e_2) mod n]}^b) mod n
m = ({C_1}^a) mod n ({C_2}^b) mod n
m = {(C_1^a) mod n (C_2^b) mod n} mod n
m = (C_1^a · C_2^b) mod n.
From the constraints described in (4), we know that it must be the case that gcd(C_2,n) = 1 (which can be seen in the (4) from the case where u < 0, k > 1 and gcd(x,k) = 1, assuming x = C_2 and u = b < 0) for the modular inverse labelled as i, here ( RSA cracking: The same message is sent to two different people problem ), to be defined, and therefore for the whole expression for the (plaintext) message m to be defined (unless C_1^a * C_2^b yields an integer, even if a < 0 or b < 0).

what I am doing wrong?

Accepting as fact a recipe with an equation, rather than deriving it.
Illustration: « Then we obtain $m$ as ${c_1}^a + {c_2}^b \bmod n$ » is stated rather than derived. And wrong.
As an aside the question reverses $a$ and $b$ (or is it $c_1$ and $c_2$, or $e_1$ and $e_2$): they are correct per the official solution which asks $a\,e_1 + b\,e_2 = 1$, but the calculation then made assumes and states $a\,e_2 + b\,e_1 = 1$.
Hint to derive the correct equation:

Prove that $m^1\bmod n=m$, by combining the definition¹ of raising to an integer exponent, the assumed range of $m$ in textbook RSA, and the definition² of the $\bmod$ operator.
In this equation, substitute $1$ with $a\,e_1 + b\,e_2$ where $a$ and $b$ are the Bezout coefficients such that $a\,e_1 + b\,e_2=1$.
Properly use properties³ of modular exponentiation. In cryptanalysis it's OK to assume plausible preconditions when that's necessary, but it remains good to verify them (or the result derived) in the end.

Suggestion: apply this technique with a slightly larger $n=14835196795348830319$, $(e_1,e_2)=(3,5)$, and $(c_1,c_2)=(14562201346830272020,1832973312396331965)$. As a bonus find the menu by expressing $m$ in hex. The point of these larger numbers is that guessing the Bezout coefficients and inverse is harder, and slightly more computer skills are needed.
More mathematically interesting, for a different method is needed, which would still work if $n$ was too large to factor directly from its value: with the same $(n,e_1,e_2)$ find $m$ for $(c_1,c_2)=(11810011337245959646,2207245693327700143)$.

Note: in actual use, RSA encryption

Does not reuse the same $n$ among several public keys, making this particular attack fail.
Does not directly encode the message as $m$, but rather adds randomness to the message in order to form $m$. That makes it extremely unlikely that $m$ is reused (it would be enough to allow some other attacks including with different $n$).
Uses $n$ with several hundred decimal digits in order to resist factorization. $n=143$ can be factored mentally, and the larger $n$ is factored in a small fraction of a second using a computer, which allows to find $m$ by using the normal RSA decryption equation, without needing $c_2$ or $e_2$.

Appreciation: taking at face value the statement that the extended Euclidean algorithm was used, the question shows fair skills to apply equations and algorithms, despite the inversion of $a$ and $b$. Be assured that the goal of such exercises is not learning the equations used. It's to learn to derive the necessary equations. That's easier when one gets the hang of it, and more fun. It's more reliable, and thus gets higher marks (which is a valid sub-goal) even when the reasoning is not considered in the notation. As a skill it's more useful, more adaptable, less likely to go obsolete, or unused and forgotten.

¹ ² ³ : See this definition of $x^u\bmod k$ and related typographical conventions, or refer to a previous version of the present answer.


Randomness test question from FIPS 140-1 and comparison with 140-2 In FIPS 140-1 there are 4 statistical random number generator tests (The Monobit Test, The Poker Test, The Runs Test and The Long Runs Test. Then FIPS 140-2 came along and supposedly tightened the criteria for these tests. I'll provide a short summary of the changes here:

The Monobit Test

Count the number of ones in the 20,000 bit stream. Denote this quantity by X.

FIPS 140-1: The test is passed if 9,654 < X < 10,346.
FIPS 140-2: The test is passed if 9,725 < X < 10,275.

The poker test

Divide the 20,000 bit stream into 5,000 consecutive 4 bit segments. Count and store the number of occurrences of the 16 possible 4 bit values. Denote f(i)as the number of each 4 bit value i, where 0 ≤ i ≤ 15.

Evaluate the following:
X = (16/5000) * (SUM i=0 -> i=15 [f(i)]^2) - 5000

FIPS 140-1: The test is passed if 1.03 < X < 57.4.
FIPS 140-2: The test is passed if 2.16 < X < 46.17.

The Runs Test

A run is defined as a maximal sequence of consecutive bits of either all ones or all zeros, which is part of the 20,000 bit sample stream. The incidences of runs (for both consecutive zeros and consecutive ones) of all lengths ( >= 1 ) in the sample stream should be counted and stored.

The test is passed if the number of runs that occur (of lengths 1 through 6) is each within the corresponding interval specified below. This must hold for both the zeros and ones; that is, all 12 counts must lie in the specified interval.
The test is passed if the number of runs that occur (of lengths 1 through 6) is each within the corresponding interval specified below. This must hold for both the zeros and ones; that is, all 12 counts must lie in the specified interval. For the purpose of this test, runs of greater than 6 are considered to be of length 6.

FIPS 140-1:

Length of Run   Required Interval
1  2267-2733
2  1079-1421
3  502-748
4  223-402
5  90-223
6+ 90-223

FIPS 140-2:

Length of Run   Required Interval
1  2343–2657
2  1135–1365
3  542-708
4  251-373
5  111-201
6+ 111-201

The long runs test

On the sample of 20,000 bits, the test is passed if there are no long runs.

FIPS 140-1: A long run is defined to be a run of length 34 or more (of either zeros or ones).
FIPS 140-2: A long run is defined to be a run of length 26 or more (of either zeros or ones).

So in general there are appears to be a narrowing of the criteria to pass the tests. I have a few questions however:

In FIPS 140-2 these tests are listed on page 57 but are striked out. I.e. there's a line through all the text. Why is this? In the draft 140-3 the tests do not appear at all..?
Does this narrowing down of the test criteria from 140-1 to 140-2 make for a better and stronger RNG if it passes the narrower/stricter criteria? Or does that make it weaker because there's less allowed variance?
For The Runs Test, when implementing this and checking if the run is within the required interval e.g. 2343–2657 is this inclusive or exclusive? So if the run was 2343 or 2657 is that a pass or fail?

Q1: Why are these tests stroked out?

These tests are stroked out on pages 57-58 of the current FIPS 140-2 because they are no longer part of the current FIPS 140-2 standard, since Change Notice 2 of 2002 December third, where these pages belong.

My guess for the rationale of removing these tests is that

It was realized that the very principle of using theses RNG tests and bounds was unsound:

When testing a Cryptographically Secure Pseudo-RNG, a " cryptographic algorithm test using a known answer " (of 4.9.1) is good enough, and a statistical test on the output of a PRNG only a nuisance: the only errors it can report are false positives (else the very definition of the CSPRNG would be broken, when the intend is to test the implementation)!
When testing a True RNG, fact is that it is very hard to make a physical TRNG source that pass these tests (especially those in FIPS 104-2) with decent reliability, without some amount of conditioning between the actual TRNG source and the test point, especially if you account for process and temperature variation (on the field you will often get failures at a rate MUCH higher than predicted for a perfect RNG). This can be fixed e.g. with a LFSR inserted after the TRNG, but then a breakdown of the TRNG source will typically NOT be caught by the prescribed tests!

It was realized that mandating these test " when the module is powered up " (as required at least for level 4) is impractical in some unattended applications, culminating with Smart Cards (which admittedly do not aim level 4), where:

There can't be an operator to reset a "RNG test failed" condition.
There can be hundreds of devices (millions for Smart Cards), implying an unacceptable number of field failures in combination with 1 and false-positives in the mandated tests.
In addition, a Smart Card can be accidentally powered up several times per second in the normal (or at least practically unavoidable) operation of the device; I've witnessed applications powering off/on any unrecognized contact Smart Card like there's no tomorrow, and that will also occur when a contactless Smart Card is left in front of some perfectly reasonable ISO/IEC 14443 or NFC readers. So it would have been needed some creative redefinition of " powered up " implying intend to use rather than mere establishment of operating power.
We want to be ready fast after power-up.

Thus if you made something per the letter of FIPS 140-1 or FIPS 140-2 before Change Notice 2, it was bound to sometime report failure (and stop functioning save for a sometime impractical human action) even if it worked fine; and this sorry state of things was not a good insurance that it would stop working if the most probable and dangerous cause of field failure occurred (TRNG source stuck, almost stuck, or otherwise non-operative, like synchronized to power-supply ripple). And attempts to reduce the rate of false positives to the bare possible minimum would tend to seriously worsen the risk of letting a dangerously defective device run.

Q2: Are the changes an improvement?

The removal of the prescribed test is a great improvement. Now, competent implementors are at least able to make something that reliably operates when not defective, and reliably stops operating when it becomes defective. And the incentive to add conditioning (like a LFSR) that allows to pass certification at the expense of actual field security is gone. Previously, with some perfectly sound TRNG sources (like with a bias of a few percents, which is fine when followed by a CSPRNG), what was prescribed could not be the main defense against likely defects of the TRNG source. All modern methodology for RNG certification, like AIS31, recognize the need for some access to the TRNG source before conditioning, or/and a model of the source, and adapting the tests to that (including making more comprehensive tests when a first one failed).

Changes in test limits made from FIPS 140-1 to FIPS 140-2 with Change Notice 1 make each of the tests significantly dramatically more stringent (and thus much more impractical when used to test an unconditioned TRNG, and generating more false positives even for a conditioned one or a CSPRNG). I think I remember reading or hearing (sorry for the imprecision of that uncertain non-reference) that at least some of these changes are also related to the fact that the tests are not independent (thus it matters to the false positive rate if the 20000 bits in the 4 tests are from the same or different runs, the later significantly increasing the false-positive rate). The changes in the acceptance level in the runs test made in FIPS 140-2 Change Notice 1 (from FIPS 140-2 before that) is documented (page 54) to be a " correction ", that seems credible. Notice that the question gives, for the runs test of FIPS 140-2, a table of the erroneous bounds of FIPS 140-2 without Change Notice 1.

Update: As pointed by poncho in a comment, the increase in false positive rate from FIPS 140-1 to FIPS 140-2 (CN1) is dramatic, more than a hundredfold in the monobit test assuming a perfect source:$$1-\sum_{i=9,655}^{10,345}{20,000\choose i}/2^{20,000}\approx1/974,603\text{ for FIPS 140-1}$$ $$1-\sum_{i=9,726}^{10,274}{20,000\choose i}/2^{20,000}\approx1/9,662\text{ for FIPS 140-2}$$
What's worse, if one defines a good source as one that is less biased than some threshold (a reasonable requirement for a physical TRNG), the false positive rate can go from rare for FIPS 140-1 bounds to totally disrupting for FIPS 140-2 bounds; that probably eased making the right decision and removing the tests altogether.

Q3: Are bounds for the run test inclusive?

Perhaps that could be determined by computing the odds of failure with and without the limits of the intervals given for a true random source, and seeing if some some round number emerges.

But why care? Statistical tests of the output a conditioned RNG, including any CSPRNG, is pointless; and has not been indispensable to get rubber-stamped since late 2002. And while the statistical test of an unconditioned TRNG source are necessary (and the tests in FIPS 140-1&2 rather sound), the acceptance levels of FIPS 140-1, and much more FIPS 140-2, are typically too harsh unless there is some backup strategy (like redoing a more complete test; notice that redoing the same test drastically alter the meaning of its original acceptance level).


Disrupting MITM attack against 3DES by intermingling plaintext and inter-mediate ciphertext between rounds Let's say someone implements 3DES with three separate 56-bit keys and an attacker is attempting to execute a MITM attack.
Here is the encryption plan designed to attempt to disrupt the MITM attack, or at least make it more expensive.  You grab 192 bits of plaintext and shuffle them into three 64-bit blocks, intermingling between all three sub-blocks, if less pad with PKCS#7 padding to be multiple of 192.
My initial suggestion would be byte 0 is 1st byte of 2nd block, byte 1 is 1st byte of 3rd block, byte 3 is 1st byte of 1st block, byte 4 is 2nd byte of 2nd block, etc.  A  matrix or maybe a key specific columnar transposition would definitely be preferable as long as it is not too expensive.
You then perform the first round of DES encryption on the first block with the first key, the second block with the second key, and the third block with the third key, in parallel if feasible.
You shuffle the 192 bits of intermediate ciphertext afterward, again intermingling bytes between the three blocks and then do the second round, encrypting what is now the first block with the first key, the second round with the second key, and the third block with the third key.
You continue to shuffle the blocks and repeat until 48 rounds of encryption have been performed.  You're not changing the keys, so I don't think there should be any re-keying penalty.  Shuffling blocks of binary data is a pretty efficient and simple operation that should not add much performance penalty or implementation complexity.
Would this make the MITM attack more difficult, while turning it into a 192-bit block cipher in the process?  How significant would the performance penalty be when compared to standard 3DES?

3DES
What is described here is not 3DES (Triple DES or TDES and officially the Triple Data Encryption Algorithm (TDEA or Triple DEA)). Let us call the $E$ as DES encryption and $D$ as DES decryption. Then we can write 3DES encryption as
$$E(k_3,D(k_2,E(k_1,message)))$$ with independent keys $k_1,k_2,k_3$.
The provided security by 3DES with 3 key is not 192-bits. It is around 122-bit. Therefore the 2 key variant is preferable and it is called 2TDEA.
$$E(k_1,D(k_2,E(k_1,message)))$$ in 2TDEA $k_1 = k_3$ and $k_1$ and $k_2$ are independent.
To apply the Meet-In-The-Middle (MTIM*) attack one needs cascaded ciphers. So that one can divide the encryption/decryption calls and approach from left and right build a table and find the keys with a couple of known-plaintexts.
Your Design
Your design uses the internals of the DES in a way that you defined a new cipher that has a 192-bit block size with 168-bit keys size. There is no cascading there, therefore, MITM attack is not possible.

Is it secure ( i.e. does really provide 168-bit security), we don't know. It is a new design and needs a new analysis.

*The MITM here, should not be confuse with Man-in-the-Middle attack. The later attack is an active eavesdropping