Is HMAC prone to birthday attacks? Popular attacks on cryptographic hash algorithms are "birthday attacks" .
At high level ,

if a hash function produces $n$ bits of output, an attacker who computes only $2^{n/2}$ hash operations on random input is likely to find two matching outputs

Is the same true for HMAC ? Or are HMAC with any underlying Hashing (like MD5/SHA-2) prone to birthday attacks ? If not why not ?

Note : this question is not a duplicate of What are the implications of a birthday attack on a HMAC?

Is the same true for HMAC ?

Yes, HMAC outputs are hashes of something so after $2^{n/2}$ you expect two to match.

However, this alone does not help the attacker. The attacker cannot compute the MAC value themselves, so they need to wait for the user to generate that many values. And it does not amount to a forgery attack because the attacker cannot produce a MAC value for any other message than the ones for which they have already seen them.

Even if the attacker had a collision attack on the underlying hash that alone would not help. HMAC is provably secure under some lesser assumptions (second preimage resistance and pseudorandomness, say).

So yes the "birthday paradox" applies to HMAC, but no that does not mean an attack.


S-Box and it's linearity I am trying to figure out why it is necessary S-box's to be nonlinear. I have been searching for some materials but was not able to find out clear proof why it means that if we use S-box in DES, it would also be linear. I was watching Coursera's course for Cryptography. I didn't understand where this matrix $B$ comes from. We want to map 64 bits to 64 bits.

But why should we use $[m, k_1, k_2,\ldots,k_{16}]$ column?
How do we build $B$ matrix?

First, remember that we can write each of the ciphertext bits $$c_i = f_i(m_0,\ldots,m_{63}, k_1,\ldots, k_{63})$$ as the output of a non-linear functions $f_i$, $f_i \neq f_j, i \neq j$. If we remove the non-linear part from DES than this $f_i$ will be linear functions $f^l_i$. Now, turn back to matrix $B$;

How do we build $B$ matrix?

Once we constructed the linear $f^l_i$ 's than the construction of the matrix $B$ is easy. Write the $f^l_i$'s a row vector so that the inner product with $[m,k_1,k_2,\ldots,k_{16}]$ will give out $c_i$s. To construct them, we need the actual definition of the new linear S-boxes, then we can write a program over the linear-DES to find $f^l_i$'s and then the vectors.

But why should we use $[m,k_1,k_2,\ldots,k_{16}]$ column?

The non-linear DES version is now represented by a matrix $B$. Each $c_i$ is nothing but linear combination of $\{m_0,\ldots,m_{63},k_1,k_2,\ldots,k_{16}\}$. If you multiply by the column vector, it will give the ciphertext.

Where does 832 comes from

$832 = 16\cdot 48+64$, the 16 rounds of the DES, 48-bit key per round, and 64 is the plaintext size.

Why we have round keys $[k_1,k_2,\ldots,k_{16}]$ not the key bits in the equation.

The key generation of DES is not linear. To keep the equation in linear form the author of your document, preferred the round keys for the equations to keep the linearity.


What is the difference between DROWN and ROBOT vulnerability? It seems like the main idea is the same for both the vulnerabilities then what is the difference?

This attacks are quite similar since they both target TLS handshake and exploit a padding oracle on RSA decryption.
However, the way the attacker access this oracle is quite different.

DROWN attack

In this attack, the authors assume that the server uses the same RSA key for both TLS and SSLv2. We can have this situation, for instance, if the server still supports SSLv2 (which is bad but quite common according to the paper), or if the key is shared with another server supporting SSLv2 (sharing keys is never a good idea...).
Since SSLv2 is badly flawed, an attacker can use it to access the oracle and perform an improved Bleichenbacher attack on a message coming from the TLS handshake.

Bottom line: the attacker does not attack TLS per se, but the fact that the same key is used in a weaker protocol. This can be qualified as a cross-protocol attack, induced by poor key management and/or server misconfigurations.

ROBOT

Here, there is no need to assume key sharing or support of weaker protocols.
The authors developed a systematic tool to scan TLS implementations in the wild and see if they can obtain a padding oracle by various means (error codes, no response in case of error, ...). They found out that a lot of widespread implementations provide a padding oracle during the TLS handshake, meaning the Bleichenbacher vulnerability is still present, even in up to date implementations.

All implementations did not provide a "good enough" oracle to exploit the attack in a reasonable time, but still, this vulnerability should have been long gone.

TL;DR: The core attack is quite similar, but DROWN is a cross-protocol attack between TLS and SSLv2, whereas ROBOT point out that TLS by it self is still vulnerable.


Can you use repeating numbers like $\pi$, and $e$, as the Key to OTP ciphers? Since $\pi$ and other numbers repeat could you use them as a OPT key. Ex: a 5 character message is sent and the first 5 digits of $\pi$ are used. after that the next $X$ number of digits are used and so on. from what I understand of Cryptography (its my hyper fixation for the week) and potential 3rd party readers would have to know the number of messages sent and their length to try and decode the messages. if i understand it, it would be near impossible to brute force and would require digital forensics (data remanence can be an issue).
Obviously the community knows more than me, any insight would be much appreciated.

An OTP is completely broken if you use a key that can be predicted. As such, $\pi$ would be a terrible choice. The key needs to be unpredictable, nonrepeating, and completely random. $\pi$ satisfies the nonrepeating aspect, and (looks like it) satisfies the randomness attribute, but is predictable since I can simply search online for 1 million digits of $\pi$.
To clarify, any number people have actually heard of is a bad choice. $\pi$, $e$, the coefficient of rolling friction across a carpet, are all bad choices. You need to use a number that has never occurred before, and never will; aka randomly generated by you, not taken from a mathematical constant.


The computational complexity of discrete log I am trying to find out what the asymptotic computational  complexity, in terms of big $O()$ notation,  is for discrete log.  Specifically, consider an element of the field $x \in \mathbb{F}_{q}$, what is:

The worst case rigorously provable complexity of computing the discrete log of $x$ if a) $q$ is a prime or b) if $q = 2^k$?
The best known heuristic complexity of computing the discrete log of $x$ if a) $q$ is a prime or b) if $q = 2^k$?

This looks like a standard question and I have searched the web but I can't find clear answers to these questions (including on the wiki).

As a side note, are there particular fields for which discrete logs are easier than others?

An example of information from which I am not able to glean the answers to my questions is  the paper The Past, evolving Present and Future of Discrete
Logarithm.  Section 4 lists a number of relevant methods but no clear statement of their asymptotic complexity in terms of the number of bits needed to represent  the field element and $q$ (or $k$) that I can find.  It's possible I am just not interpreting the paper well of course.

The paper you mention actually does contain most of the answers at least as far as “heuristic complexity” is concerned (newer results improve the complexity bounds given in that paper in some parameter ranges, but not the ranges you are asking about). Note that the complexity of the discrete logarithm problem is usually given for a random $x$ (with respect to an arbitrary generator of $\mathbb{F}_q^*$), so the bit length of $x$ doesn't really come into play.

So the best known algorithm for discrete logarithms in $\mathbb{F}_q^*$ when $q$ is a random-looking prime is the general number field sieve (GNFS), which has a heuristic complexity of $L_q[1/3,\sqrt[3]{64/9}]$, where $L_q[\alpha,c]$ is a short-hand notation for $\exp\big((c+o(1))(\log q)^\alpha(\log\log q)^{1-\alpha}\big)$.

Still in the prime case, when $q$ has a special form (which roughly means that it can be expressed as the value of a polynomial with small coefficients at a small integer: think e.g. of a Mersenne prime), one can use the special number field sieve (SNFS) instead, and complexity drops down to $L_q[1/3,\sqrt[3]{32/9}]$ (so one can solve the problem for $q$ of roughly twice the bit size as for SNFS).

As for the case of $q=2^k$, the best asymptotic complexity is provided by Barbulescu et al.'s version of the function field sieve (FFS), which in that case runs in heuristic quasipolynomial time $2^{O((\log k)^2)}$.

All of these complexity estimates depend on heuristic assumptions of the form “such and such family of integers/polynomials contains roughly as many smooth elements as random integers/polynomials of the same size”, so making them entirely rigorous is probably hopeless. In practice, though, they work as advertised (extensive experiments support the estimates in most cases).

Oh, and as a final note, you can probably deduce from the above that the answer to the question of whether the discrete log problem is easier in some fields than others is yes. Basically, for a field $\mathbb{F}_{p^k}$ with $p$ prime, the complexity will depend on the relative sizes of $p$ and $k$ (this is the distinction between the small prime, medium prime and large prime cases of the discrete log discussed in the paper of Joux et al.), and to a lesser extent on whether $p$ has a special form in the sense alluded to above.


Right way to hash elliptic curve points into finite field I would like to know how I can implement several hash functions :

$H_1:\{0,1\}^* \rightarrow P $ with $P \in E(\mathbb{F}_q)$

and

$H_2:P \rightarrow \mathbb{Z_q}^*$

And others where the input data changes (for example $h:(P,\{0,1\}^* )\rightarrow \mathbb{Z_q}^*$)
With an elliptic curve of the form $y² = x³+ax+b$ over $\mathbb{F}_q $ where $q$ is a prime number, what is the correct way to construct those functions in my code ?

I planned to use some NIST or SECG recommended elliptic curves so I didn't generate all the elliptic curve points, thus for $H_1$ I can't just simply hash with an existing function and map the result to a point in a list (So I can't use this response ?) .
For the hash functions which take a point should I just hash the coordinates with a function like SHA-2 or another and apply a modulo on the output ?

I don't really know if my ideas are the right ways to go, I just want to implement these functions properly from a cryptographic standpoint, something that works without need to be perfectly optimized.

Thank you in advance

For $H_1$ it depends on a bit on what characteristics you require of your hash function. There is a thorough analysis from Brier et. al (https://eprint.iacr.org/2009/340.pdf). Here's the basics:

Method 1: One way to hash from $\{0,1\}^*$ to $E(F_p)$ is to first hash to $Z_p$ and then multiply by the generator. Universal Hash Functions as first described by Carter and Wegman (https://en.wikipedia.org/wiki/Universal_hashing) provide a simple mechanism to obtain an indistinguishable distribution. Given $q \geqslant p$ and random values $a,b \in q$ this can be constructed as:

$$H_{CW_1}(x) = ((a_1x + b_1) \text{ mod } q) \text{ mod } p$$

$$H_u(x) = H_{CW_1}(x)*G$$

$H_u$ hashes from ${\{0,1\}}^*$ to $E(F_p)$. Because $H_{CW}$ is uniform (i.e. the probability of a collision is $1/p$) in $Z_p$ it follows that $H_u$ is uniform in $E(F_p)$. This could be sufficient for some uses, however it should be noted that $H_{CW}$ is the discrete logarithm of $H_u$. If your use of a hash function depends on security of the ECDLP for the result then this is not sufficient.

Method 2: The second method, assuming a short Weierstrass represenation with $p \equiv 2 \text{ mod } 3$ is to use Icart's function to map directly to $x,y$ coordinates which are parametrically constrained to be on the curve $E(F_p)$. Icart's function $f(u) = (x,y) : u \in F_p$ is defined by:

$$v = (3a -u^4)/6u$$
$$x = (v^2 - b - u^6/27)^{1/3} + {u^2}/3$$
$$y = ux + v$$

Extending this to map $\{0,1\}^* \rightarrow E(F_p)$ is as simple as:

$$H_{CW_2}(x) = ((a_2x + b_2) \text{ mod } q) \text{ mod } p$$

$$H_I(x) = f(H_{CW_2}(x))$$

$H_I$ hashes from ${\{0,1\}}^*$ to $E(F_p)$. The derivation $(x,y)$ using Icart's function provides no gain on finding the discrete logarithm of $f(u)$, so it could be sufficient for some applications, however $f$ only maps to a distinct subset (about 5/8) of the points of $E(F_p)$, so it is not sufficient for appilcations which require a uniform/indistinguishable mapping.

(Note: there are alternate implementations to Icart's function explained in Brier et. al. which can be used for other curve equation forms and for $p \neq 2 \text{ mod } 3$)

Method 3: If you want something which is uniform and ECDLP-secure then you can simply combine the above two methods:

$$H_{us}(x) = H_u(x) + H_I(x)$$

For $H_2$ you likely want to securely hash the full string representation of the point (as doing something like using the x coordinate would have a trivial hash collision of $-P$) to $\{0,1\}$ and then reduce that to $F_p$. Something like:

$$H_{CW_3}(x) = ((a_3x + b_3) \text{ mod } q) \text{ mod } p$$

$$H_{Z_p}(P) = H_{CW_3}(SHA256(P_x | P_y))$$

Which will produce a secure, uniform result in $Z_p$


Storing a secure key in an embedded device's memory I am working on an embedded device which send/receive data and stored them in ciphertext mode (encrypted mode ). Now what's best approach for storing Keys (I used ARM CORTEX M series MCU) ?

Storing keys in the SRAM memory,in each booting sequence ,inject keys to the embedded MCU and store them in the SRAM memory. It is best way I think,then when MCU sense penetration (with tamper sensor or ...) it can erased SRAM quickly and reset itself. Disadvantage: if attacker success to pass tampers and access to device,how safe is SRAM memory (against code mining). I can't find any security ability for this memory in MCUs.
Generate keys and stored them in the flash memory in programming MCU. MCU flash memory's support CRP (code read protection) which prevent from code mining and with assist of its internal AES engine and RNG (random number generation) engine we can make a random key and encrypt flash memory and stored that random key in the OTP (one time programmable memory -a 128 bit encrypted memory), then in code execution we decode flash memory with RNG key and access to initial key and codes. Disadvantage: Keys stored in a non volatile memory, tampers will be useless and attacker have a lot of time to mine keys.
Stored key in the EEPROM memory,combination of 2 above approach, key stored in the non volatile memory but when tampers sense penetration EEPROM is erasable.
I consider LPC18S57FBD208(cortex m3 with 1MB of flash memory, 180MHZ, 136KB SRAM, 16KB EEPROM and a TFT LCD controller which i need to drive a 7" TFT LCD and AES 128 bit crypto engine) for that is there any other better suggestion?

part 2:
I am using a PCD (proximity coupling device or the card reader) like CLRC663 for reading RFID tags too.
connection between PCD and MCU is based on SPI,Becouse of unsecure and un-encrypted connection between them ,each attacker can sniff the connection and achieve the keys used for reading and writing to the RFID tags.
 what is your suggestion for this?

An issue with storing a key in RAM is, there are attacks that involve erasing the flash to unlock the device and then using a debugger to copy the RAM contents. Problem with internal EEPROM is the same as RAM unless you can lock it. External EEPROM is worse, unless you encrypt that.

My druthers would be store the key in flash and then lock the lock the processor to disable debugging access. If possible use a separate key for each and every device. If you copy the key to ram, make sure it's gets over-written when done.


How to convert ECDSA P256 curve signature to SECP256K1 curve? I would like to get the ATECC608A microchip to sign data with ECDSA secp256k1 curve, but the chip only signs using the P256 curve.

Is there an operation I can do using the original message and the signature under P256 that would produce a signature under secp256k1?

There is no way to convert a signature with one curve to another. If there were, one could trivially forge signatures by starting with an insecure curve and converting it to a signature in a secure curve.


RSA figuring out the recipient of a ciphertext I have this question I am trying to figure out the answer about RSA. I'd be grateful if someone could actually help me understand how the procedure would work. I am new to cryptography and with all the maths in it, I am barely understanding it.

Assuming that we have a sender A and 2 recipients B and C. This sender wants to send 12 messages.

If A wants to send to B he'd use B's public key $(n_B,e_B)$. Meaning:
$$\text{ciphertext}_i = (\text{plaintext}_i)^{e_B} \bmod n_B$$

If A wants to send to C he'd use C's public key $(n_C,e_C)$. Meaning:
$$\text{ciphertext}_i = (\text{plaintext}_i)^{e_C} \bmod n_C$$

An attacker gets the 12 ciphertexts A encrypted. He also knows the public key of B and C.

How can he determine whether A sent her messages to B or C?

First, we'll assume that $n_B > n_C$, and we'll assume that he has no knowledge of the plaintext messages (which, if $A$ uses randomized padding, which he ought, is an appropriate assumption, even if the adversary knows the text of the message).

Then, if any of the 12 messages $\mathit{ciphertext}_i \ge n_C$, then he knows that message cannot be to $n_C$ (because the result of the RSA encryption process is always an integer less then the modulus.  Hence, if all messages were to the same endpoint, then they all must be to $B$.

In contrast, if all 12 messages $\mathit{ciphertext}_i < C$, then it is possible that the messages were to either, however it is somewhat more plausible that there were to $C$, because of the possibility that, if there were to $B$, that fact would be leaked above.

Now, we can actually estimate the probability that the messages were actually towards $B$, but that fact wasn't leaked; RSA encrypted messages can be modeled as random values between $0$ and the modulus size.  Hence, the probability that all 12 encrypted messages happen to be $< n_C$ is approximately $(1 - n_C/n_B)^{12}$; how large that is depends on the relative magnitude of the two modulii.


Explanation of $z^{-1}$ and $T_{1,2}$ within E0 Bluetooth encryption algorithm I am trying to understand how E0 Bluetooth algorithm exactly works. I know that $y_t$ is the sum of $x_1$ to $x_4$ and can take values $0, 1, 2, 3, 4$. Also $S_{t+1}$ = $(y_t + c_t)/2$ and can be $\{0,1,2,3\}$. But I don't understand what $z^{-1}$ and $T_{1,2}$ means.

According to the Bluetooth core specification:

  $T_1$ and $T_2$ are two different linear bijections over $GF(4)$.

Picture and explanation is on page 164.

Can you please clarify this and provide some examples?

This article  Cryptanalysis of the Bluetooth Stream Cipher by Canniere et al. explains in details;

\begin{align}
T_1 : \mathbb Z^2_2 &\mapsto \mathbb Z^2_2\\
(x_1, x_0) &\to (x_1, x_0)\\
\end{align}

\begin{align}
T_2 : \mathbb  Z^2_2 &\mapsto \mathbb  Z^2_2\\
(x_1, x_0) &\to (x_1, x_1 \oplus x_0)\\
\end{align}

$Z^{-1}$ are 2-bit digital delay lines. $Z^{-1}$ is delay one sample and $Z^{-N}$ is delay by $N$ sample. This can be implemented by circular buffer in electronics and with arrays in software.

Why $T_1$ and $T_2$ are bijections? $T_1$ is bijection since it is just swapping the values. To prove that $T_2$ is a bijection; first, notice that it is surjective. To see it is an injective notice that we can find the inverse of every element on the range.

Extra:

To understand $\mathbb Z_2^2$ we need to construct it: We can also represent $\mathbb Z_2^2 $ as $\operatorname{GF}(2^2)$. It is the second-degree extension of $\operatorname{GF}(2)$ by the roots of the polynomial $x^2 + x + 1$. Let $\alpha$ is one root then the second root is $\beta  = 1 + \alpha$.

By using $1 + 1 = 0$ and $\alpha^2 = \alpha + 1$ we can build the addition and multiplication tables.

Addition:
$$
\begin{array}{c|cccc}
+  & 0&   1&   \alpha &  \beta  \\
\hline
    0&   0 &  1 &  \alpha &  \beta \\
1 &  1 &  0 &  \beta &  \alpha  \\
\alpha &  \alpha &  \beta &  0 &  1  \\
\beta &  \beta &  \alpha &  1 &  0  \end{array}
$$

Multiplication:
$$\begin{array}{c|cccc}
\cdot &   0 &  1 &  \alpha &  \beta  \\
\hline
0 &  0 &  0 &  0 &  0  \\
1 &  0 &  1 &  \alpha &  \beta  \\
\alpha &  0 &  \alpha &  \beta &  1  \\
\beta &  0 &  \beta &  1 &  \alpha
  \end{array}$$


Non-cryptographic hash function as MAC for stream ciphers I understand that for a stream cipher to be useful, there must be a way to verify that the message was not tampered with (bits were flipped by an attacker).

So, instead of using some cryptographic hash function, like SHA-2, with HMAC, what if I used a much simpler (and faster) hash function, like FNV hash algorithm, and encode its output together with the plaintext?

Like, suppose I have a 1000 bytes plaintext message, then I hash it with Fowler–Noll–Vo of 256 bits output, then concatenate them both, having a message+MAC with 1032 bytes.

Then I XOR this 1032 bytes message+MAC with 1032 bytes output of some stream cipher (the ordinary encode operation of most of them, like RC4 or those in eSTREAM portfolio).

What is the problem of this approach?

If I understand you correctly, you want to use $C = \mathrm{Enc}_{K,N}(m || \mathrm{hash}(m))$ as authenticated encryption. This is a bad idea, even for cryptographically secure hashes.

Consider an attacker who knows your plaintext $m$ and wants to replace it by $m^\prime$. He calculates $C^\prime = C \oplus (m || \mathrm{hash}(m)) \oplus (m^\prime || \mathrm{hash}(m^\prime))$ which is the valid ciphertext for $m^\prime$.

We had two related questions: How do unkeyed hash functions (for MDCs) provide security? and Is the encryption of a hash a good MAC?.

As alternatives to hash based MACs, you could consider:

Universal hashing
A bit annoying to implement, but features a security reduction to the security of the cipher.

AES-GCM is one a popular choice, but its performance isn't so great in software without specific instructions(AES-NI&co). With those instructions it's really fast, and it's a standard.
Salsa20-Poly1305 is an alternative. It has a fast implementation in NaCl which avoids timing attacks. Poly1305 can be used with any stream cipher and is fast in software.

SipHash

Fast in software, especially for short messages. It produces 64 bit MACs, which should be sufficient because MACs guard against online attacks. It's pretty easy to implement.

The main issue is that it's rather new and thus hasn't seen much analysis. I would only use it if security isn't super important.


Is there a correct way to generate a symmetric key? Looking in some cryptographic algorithms, I've realized that: The way the plain text is encrypted/decrypted is always specified, but what about the key? Every paper I've seen describing the algorithm never show a way to generate a key, but show the available key sizes.

This leads me to a question: How should I generate a key as someone who is implementing an algorithm? For example: The Twofish paper (https://www.schneier.com/paper-twofish-paper.pdf) says that Twofish has available key sizes of 128, 192 and 256 bits, but how should I create a 128 bit key? Not even the reference implementations I found contains code that seems to be aimed to be a key generation algorithm (again speaking of Twofish).

For a university work, I'll write a simple implementation of Twofish in C#, and I need a way to create a key but I don't know how to do it or even if there's a correct way to do this, that's why I ask this question.

A real example: When I encrypt anything with GnuPG (https://www.gnupg.org/) using symmetric keys, it does not generate any key or the like, it just asks for a password and does it. What's happening behind the scenes? How does GPG uses this password and how it's is related to the key generation?

Symmetric keys don't need to be in any particular format -- they're just a sequence of (pseudo)random bits.

Most programming environments provide some sort of "secure random" mechanism (a CSPRNG).  You can use this to acquire a byte array of the appropriate length (e.g. 32 bytes for AES256), which can be used as a key.  Be sure to pass in the raw bytes, and not, e.g., a hex-encoded string.

Alternatively, you may want to derive a key from some other source.  A Key Derivation Function (KDF) is a function that transforms some input into a key.  GPG uses a Password-Based KDF (PBKDF, also known as a "password hash") to transform a password into a symmetric key.

Many PBKDFs use an iterated hashing approach; you might be interested in reviewing the design of "PBKDF2", or see scrypt for a more modern design.  Generally though, as a developer, you can use an existing implementation and not be particularly concerned about the underlying details.

For completeness, there are also Key-Based KDFs such as HKDF that can derive symmetric keys from other keys, but I suspect that's not what you're after.


Why are 48 bytes appended to Libsodium encrypted messages if nonce is 24 bits? When encrypting a string through the Libsodium secret box feature, the ciphertext is 48 bytes longer than the plain text message ...

I am wondering why this is ... since the nonce is only 24 bytes.

Notice that $\operatorname{secretbox}$ has a $16$-byte MAC too. For reference, I've included $\operatorname{box}$ too.

$$
\operatorname{secretbox} : \text{24 nonce} + \text{0 xsalsa} + \text{16 poly1305}\\
\operatorname{box} : \text{32 curve25519} + \text{24 nonce} + \text{0 xsalsa} + \text{16 poly1305}
$$

However, the nonce is user-controlled and normally not included in the ciphertext overhead as it is usually never sent, often a protocol-level counter.

You say "secret box" but you mean the normal "box" which uses a public key. Your ciphertext is expanded with your $32$-byte ephemeral public key and the $16$-byte MAC.


How long can a RSA public key be? If I create an RSA of 4096 bits, what would be the range of the length in bytes of the public key in DER format?

Also, will the private key always be exactly 4096 bits (512 bytes)? Does the public key length depend on the actual length of the private key, or the length you specified (4096)?

You say DER, but you tag PGP which doesn't use DER -- and whose publickey block includes a lot of things beyond the RSA values (n,e). The DER encoding of a PKCS#1 RSA publickey of 4096 bits with a conventional e of 65537 (default at least for openssl and Java) is

30 82 02 0a   02 82 02 01 (n with leading 00)   02 03 01 00 01

with a total length of 526 octets. The DER encoding of a generic SubjectPublicKeyInfo which is always used in X.509 certificates and often in other places (including openssl and Java) adds an outer SEQUENCE and AlgorithmIdentifier and a wrapping BIT STRING giving a total length of 550 octets. If you mean something else, specify it more clearly.

For the private exponent see RSA: Most significant key bit always 1? .

But if you are concerned about the encoding of a private key, that is much more than just the exponent and (possibly) modulus; see https://stackoverflow.com/questions/5403808/private-key-length-bytes . In addition the privatekey is often encrypted, which usually expands the encrypted value and adds metadata about the encryption.

If you have a question about a particular key encoding with a particular program or protocol/format, you need be much more specific.


What are best known attacks for finding partial target pre-image? Just a follow up on this question since I don't have enough point to comment:
Does a partial preimage attack imply a preimage attack?

Partial target preimage attack: Given $M$ and t-bit partial target of $d \leftarrow H(M)$, find $M^*$ such that t-bit of $d^* \leftarrow H(M^*)$ is the same as the t-bit of $d$ at the same position.

My question is what best known attacks are.

In the generic setting, a $t$-bit partial preimage attack on an $n$-bit oracle $m \mapsto f(m)$ is the same as a full preimage attack on a $t$-bit oracle $m \mapsto \operatorname{trunc}_t(f(m))$.  If $f$ was uniformly distributed in $n$-bit functions, then $\operatorname{trunc}_t \circ f$ is uniformly distributed in $t$-bit functions, so there's no advantage to be had in knowing that it is a truncation of a larger oracle.

Of course, for particular functions $f$, there may be better partial preimage attacks, like $f(0^t \mathbin\| m) = 0^t \mathbin\| \operatorname{trunc}_{n - t}(H(m))$, $f(b \mathbin\| m) = H(m)$.  But we would need more particular details about $f$ like this to say.


Unleakable shared secret under realistic assumptions? Can two devices share a common secret in a way that an adversary who compromises one of the two devices after deployment is unable to reconstruct the shared secret, under the following assumptions:

before deployment, there is a secure initialization phase, e.g., in which a pre-established secret is stored in both devices
after deployment, the two devices are physically separated (possibly a few miles/km apart from each other) and unable to communicate with each other (including via any 3rd party)
during attack, the targeted device is offline (inoperable) for a few minutes
after attack, a compromised device leaks all data, thus, among others, all secrets
both devices do not possess tamper-proof hardware, not allowing to delete secrets upon tampering, etc.

Due to the assumptions, the common secret must be volatile, thus, being constantly changing data. Note that using a PRNG with a pre-established secret is not enough, since an adversary can after device compromise reconstruct the PRNG stream (having the pre-established secret).

A possible solution to this problem may be using an entropy source that produces the same random data on the two devices and has a very high throughput (maybe atmospheric noise or similar?). Before deployment, both devices pre-establish a secret filter that allows them to process the sheer amount of entropy from the source during deployment (e.g., listening on a specific channel, XORing every Xth bit, etc). During deployment, both devices constantly derive the common secret using entropy source and filter. An adversary may try to compromise a device, retrieve the secret filter, and reconstruct the common shared secret. However, as the target device is offline for some time during attack (see assumptions), the adversary misses so much data from the entropy source that he is unable to buffer this data and thus is unable to reconstruct the common secret in the end using the secret filter.

Do you know whether there is an entropy source that provides these properties? Or do you know another solution to this problem?

I think that the use cases for this requirement still need some clarification as they seem to be illogical and self contradictory.  So I'll answer the question posed in your last paragraph.  No. There is no entropy source that can satisfy the buffering requirement.

Firstly, it would be impossible to develop and randomness test an entropy source without recording it's output.  If you record the output, the attacker can record the output.  They will certainly be able to record a few of your minutes of attack time.  There is no way to prove randomness without storing the entropy stream and making multiple passes over it.  In other words, there are no pure streaming tests.  They all require some block of stored data for multiple passes, even something simple like FIPS 140-2 uses blocks of 20,000 bits.  No single pass over data can prove randomness, it takes a combination and then careful assessment of combined probabilities.  If you tested it, you made multiple passes, ero you recorded it.

Secondly.  It is impossible to record the same data stream from any practical entropy source (other than dice).  This feature works to the advantage of TRNG builders, but fatally against you.  In engineering terms, entropy sources don't produce any entropy at all.  The measuring system does, and totally determines it's quality and quantity.  Switch on the old analogue TV you kept.  You'll see static.  1% of that static is your true atmospheric noise in the form of the cosmic background radiation. 99% is other stuff populating the aether, some permanent, some transient.  Some of it will be localised from your hairdryer.  Ever heard a TV studio guest's mobile phone checking in with the local cell tower?  If you record a -100dB signal, there will be a huge proportion of unpredictable external noise.  There is a good example else where on this forum that mentions the ANU Quantum Random Numbers Server.  The developers specifically mention the difficulty of separating the true entropy signal from incidental system noise.

Thirdly.  Randomness extraction will blow it all out of the window.  All extractors use some form of hashing.  If you take the simple example of a 1024 * 768 bit matrix extractor, it requires 1024 bits of entropy to generate 768 truly random bits.  If one bit is different between your two devices (0.1% which is a virtual measurement impossibility), the 768 bit random outputs will be totally different by virtual of the avalanche effect.  Unless something funny is going on, no two TRNGs can ever produce anything like the same output.  They're always absolutely different.


With AES-CTR does the block input need to be implemented as nonce || counter? I am looking at an AES-CTR implementation (WebCrypto) and it takes an initialization parameter count which is an array of 16 bytes. It then asks you to specify length, or how many bits are dedicated to the counter (the rest will act as a nonce.) So if you specify e.g. length = 32 the block input will be nonce (96-bit) || counter (32-bit). It then says that the counter should be large enough that it does NOT wrap.
My question is why not just use the full 128-bits as a nonce AND counter. Initialize it with a random 128-bit value and increment the whole thing and as long as you don't wrap all the way to where you began then everything is fine.
https://developer.mozilla.org/en-US/docs/Web/API/AesCtrParams#Properties

Usually a 128 bit counter is implemented, and the 16 byte IV is really just the initial counter value, consisting of the nonce and a counter. The counter is generally an unsigned value. So your scheme is very possible, but other implementations may make other choices (and if you look at NIST SP 38A, Appendix B, about any scheme suffices).
The fully random IV scheme however has a problem. You never know how close the initial random value is to another initial random value. The chance of two counters out of $N$ counters being close to each other quickly increases with the number of IV's generated.
If you have a incrementing part consisting of $l$ bits then you can have $2^l$ separate counter values before you may run into a collision. There is still a birthday problem, but it is now at least quantifiable, and it's only an issue for the nonce, not for the entire counter. Furthermore, you know exactly how large your message may be.
Let's create an example, which one would you rather have of these initial IV's?
Fully randomized:
27df9ad9921861c7 b53ab03a aad9bf3f
27df9ad9921861c8 dca9d07a 2f50dc18

or nonce || iteration counter:
27df9ad9921861c7 b53ab03a 00000000
27df9ad9921861c8 dca9d07a 00000000

On the first you've got a random amount of counters for each message (in this case 0x84771CD9 or 2,222,398,681), for the second you've got exactly $2^{32}$ counters. Worse, in the first case you don't exactly know how much space you have, because you're not going to store the random values.
The fully random scheme is also somewhat slower as it requires more random bytes. It also requires careful handling of overflows, as you don't want to have an issue after you hit FFFFFFFF.
In short, if the random scheme has any advantage then I'm missing it; I would strongly recommend keeping to a concatenated nonce and counter as input block.


Restricting symmetric key usage I have a system where some clients communicate with a server. every client has its own name and role and some other parameters that sends these info to the server in every message and the server uses those info somehow...
All communications are encrypted with symmetric keys. I have a master key that only I and the server know it.
A client's key is derived from the master key this way:

client1_key=hkdf(16, MASTER_KEY, 'client1')

a client sends its encrypted messages to the server along its name/key ID, so the server can reconstruct the client's encryption key from the master key and the client name and decrypt the message. Other info like client's role are contained within the encrypted part because I wanted to reveal only the minimum/absolutely necessary information in clear text communication.

a problem here is that with this scheme, a client can claim, with the exception of its own name, other parameters that don't really belong to is. e.g. it can send any role it wants to the server and the server has no way to verify that those parameters are relevant to that specific client.

my solution to this problem was generating an HMAC over all restricted parameters and sending it alogn the other info (client name and encrypted message) to the server by every client. so each client receives its own key and the accompanying hmac that restricts the key use:

key_use_hmac=hmac_sha256(MASTER_KEY, client_name||client_role||another_parameter...)

then at the server this hmac is recalculated after extracting the client's parameters from its decrypted message and compared with that sent along the message by that client, if they match, the message is accepted, else the message is rejected.

an example of a message sent to server by a client:

name=client1, key_use_hmac=xxxx, encrypted_message=xxxxxxxxxxx

only name and key_use_hmac are send in clear text (key_use_hmac could also be sent within the encrypted part, but i thought it is not necessary at all - am i correct?).

I want to know if my scheme is sound enough or not.
thank you!

OK, so you have come up with your own key-authorization and transport encryption scheme.

The key authorization scheme is fine and and quite a standard solution. A similar approach is used on the web to ensure the user doesn't forge certain cookies.

The per-client key derivation and key management also looks good, but for the encryption there's a better solution than "plain" encryption:
TLS-PSK. (Transport Layer Security with Pre-Shared Keys)
In this case the client can claim an identity during the handshake and confirm it by owning and using the assigned pre-shared key. As a bonus the TLS implementation will take care of all the replay-protection and authentication issues and you will only leak the absolut minimal information during the handshake: the client's name. As an additional bonus you can combine PSK with ephemeral Diffie-Hellman ([EC]DHE) to gain forward secrecy and don't get your sessions' secrecy compromised just because the MASTER_KEY has been leaked at a later point in time.


Error correcting codes that are indistinguishable from random Suppose you have a public program P(n) which takes message n and generates an encrypted output (utilizing asymmetric cryptography) for some entity which has the private key to decrypt it.

Using a scheme such as Elligator (for elliptic curves) it is possible to have P which has output indistinguishable from random.

But a problem arises when the output is expected to be subject to corruption (bit flips). An application of error correcting codes seems to break the 'indistinguishable from random' requirement.

After considering the problem I arrived at the following consideration. The actual message n is encrypted by a symmetric encryption scheme using some shared secret, the same shared secret (after KDF) can be used to whiten (w/ stream cipher) the result after the application of error correcting codes to it. Would there be a problem with this approach?

This leaves the ephemeral public key (~256 bits) which due to Elligator is indistinguishable from random. But is subject to corruption. How can error correction be used on it such that the result is itself indistinguishable from random?

Edit:

There appears to be some confusion regarding the encryption part. It's a standard anonymous sender sealed box. https://libsodium.gitbook.io/doc/public-key_cryptography/sealed_boxes

ephemeral_pk ‖ box(m, recipient_pk, ephemeral_sk, nonce=blake2b(ephemeral_pk ‖ recipient_pk))

The 'indistinguishable from random' requirement is mandatory, there is a Markov chain that mixes it with a structured format. Extraction of this embed cannot be allowed to yield something containing detectable error correcting codes, betraying its presence. In its absence, actual noise with no statistical pattern is extracted instead.

The actual message n is encrypted by a symmetric encryption scheme using some shared secret

The symmetric encryption is keyed by what key?  Is it something that the encryptor picks?  If so, how does it get to the decryptor (as the decryptor would need it before he can attempt a decryption).  Is it something that both sides share?  If so, how is this 'public key encryption' (which typically assumes that the encryptor has access only to publicly available information)?
  And, if you do have a shared symmetric key, what are you bothering with asymmetric crypto?

On the other hand, might I suggest considering thinking about this 'indistinguishability from random' option (and why it is a requirement)?  In general, we usually don't need something that is literally indistinguishable from a set of random bits (some cases do arise; they're comparatively rare).  Instead, it is generally enough to have 'indistinguishable from a random selection from a specific set' (and it doesn't matter what that set it); that formulation preserves the IND-CPA property we are typically interested in.  And, if you just generate the 256 bit indistinguishable-from random word, and then apply your error correcting code to it, this set becomes 'the set of all valid code words in your error correcting code', which is enough for most purposes.

I had to put in some cavaet language in there, because there are some uses that really do require 'indistinguishability from a set of random bits'; what is your use case?


Mapping between subgroups and the integers This question is a companion to the equivalent question on elliptic curves.
Preliminaries
Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime $p$. However, for security reasons, we do not use all the integers in $\mathbb{Z}^*_p$ but only a subset of them. The subset is of size $q<p$ and $q$ is also a prime number. The subset is also chosen so that it also forms a group, $\mathbb{G}_q$, with closure under multiplication (a multiplicative subgroup). Number theory tells us that such a group can be found iff $q$ divides $(p-1)$.
With Elgamal in particular, messages must be encoded into $\mathbb{G}_q$. If the message is an $\ell$-bit bitstring $\{0,1\}^\ell$ and $\ell<|q|$, then it can be treated like an integer and will be in $\mathbb{Z}_p$ (and $\mathbb{Z}_q$) (we'll ignore the corner case of all zeros). The problem is that it is unlikely to also be in $\mathbb{G}_q$ (depending on how much smaller $q$ is than $p$).
Questions
How can you map numbers from $\mathbb{Z}_q$ to $\mathbb{G}_q$ and back when:

$p=2q+1$
$p=aq+1$ with an $a$ such that, e.g., |p|=1024 and |q|=160

(I'll accept the best answer for the second case)
(As the second case appears not to be possible—see my answer—I've accepted an answer for the first case)
Format
This question is somewhat rhetorical for me personally, but I think it is a good place to gather different answers in one place (and things have been slow). With that in mind, use one technique per answer. Also relevant could be encoding-free Elgamal (such as hashed Elgamal) that sidesteps the problem.

For $p = 2q+1$, one can note that elements of $\mathbb{G}_q$ are exactly the non-zero quadratic residues modulo $p$:

Since $p$ is prime, $\mathbb{Z}_p$ is a field. Hence, the polynomial $X^q-1$, being of degree $q$, cannot have more than $q$ roots in $\mathbb{Z}_p$. So $\mathbb{G}_q$ contains all the $q$ values of order $1$ or $q$.
If $x$ is a non-zero quadratic residue ($x = y^2 \mod p$ for some value $y$) then $x^q = y^{2q} = y^{p-1} = 1 \mod p$. Thus, every non-zero quadratic residue is a $q$-th root of $1$, therefore an element of $\mathbb{G}_q$.
Since $q$ is a big prime, it is odd, therefore $p = 3 \mod 4$. This implies that if $x$ is a quadratic residue, then $-x$ is not, and vice versa. Thus, there are $(p-1)/2 = q$ non-zero quadratic residues.

This yields the following mapping:

If $x \in \mathbb{G}_q$ then it is a square and has two square roots, $y$ and $-y$ for a value $y$. Computing the square root modulo $p$ is easy: $y = x^{(p+1)/4} \mod p$. $y$ can be viewed as an integer between $1$ and $p-1$. Set $z = y - 1$ if $y \leq q$, or $z = p - y - 1$ otherwise. This always yields a value such that $0 \leq z \lt q$, i.e. a value in $\mathbb{Z}_q$.
For the inverse mapping, just compute $(z+1)^2 \mod p$.


Can messages be recovered from signatures if the private key is known? If the message that was signed with a digital signature is not known, can it still be recovered if you have the private key?

In generally it will not be possible: the signature generation generally includes hashing the message, and secure hashes are one-way functions.

Often the hash can be retrieved during verification with the public key. This is for instance the case for RSA. If you have the hash you can try all possible messages until you find one that calculates to that same hash. This will of course only work if the message space is restricted; the higher the number of valid messages, the lower the chance to find the right one. With a secure hash with any kind of secure output you can however be certain that if a matching message is found that it is the right one.

If the signature verification requires a hash as input, e.g. for ECDSA you may be required to perform the whole verification, which will take longer, so searching may take more time.

There are signature schemes that provide (partial) message recovery (see ISO/IEC 9796-2). In that case the public key verification operation will return (part of) the message. This is useful for data constrained devices such as smart cards.

For verification the private key is not needed, so the answer is no. Having the private key doesn't bring you any benefit over using the public key.


How to estimate the hardness of SIS instances? The Short Integer Solution (SIS) problem is to find, given a matrix $A \in \mathbb{F}_q^{n \times m}$ with uniformly random coefficients, a vector $\mathbf{x} \in \mathbb{Z}^m \backslash \{\mathbf{0}\}$ such that $A\mathbf{x} = \mathbf{0} \mod q$ and $\Vert \mathbf{x} \Vert_2 < \beta$. This problem is at least as hard as the Shortest Independent Vectors Problem (SIVP) with approximation factor $\tilde{O}(\beta\sqrt{n})$ in $n$-dimensional lattices. Several proposed cryptosystems rely on SIS, most notable Ajtai's function in the original paper that defined the problem (link), the SWIFFT hash function (link), and several signature schemes (link) (link) (link).

However, I am confused about estimating the security offered by these cryptosystems in terms of the computational cost of a successful attack. Very few sources actually present a hardness estimate and those that do consider the appropriate root Hermite factor $\delta$ rather than a count of arithmetic operations.

For instance, the chapter by Micciancio and Regev (link) presents the following argument: There is an optimal number of columns of $A$ to take into account when attacking the SIS problem using lattice-based algorithms (presumably BKZ 2.0). Use too few columns and short lattice points might be too difficult to find (if they exist at all); use too many and the lattice will be too large. This minimum is found for $m = \sqrt{n \log q \, / \log \delta}$; at this point the average length of lattice points that can be computed in a "reasonable amount of time" is $2^{2\sqrt{n \log q \log \delta}}$, where $\delta$ is no less than $1.01$. So by requiring that $\beta < 2^{2\sqrt{n \log q \log \delta}}$, one guarantees that the SIS instance cannot be solved in a reasonable amount of time.

A similar treatment of the hardness of SIS instances is given by Section 3.2 of Lyubashevsky's 2012 signature scheme (link), which uses $\delta = 1.007$ for setting parameters. Micciancio and Peikert's 2011 signature scheme (link) mentions that setting $\delta \leq 1.007$ corresponds to $2^{46}$ core-years of lattice-redution, which is about $2^{100}$ cycles on a 1.0 GigaHerz CPU.

I have several questions regarding this. What makes it impossible or difficult to translate the parameters $(m,n,q,\beta)$ into an attack runtime estimate, and what is the significance of the root Hermite factor $\delta$ in this context? Given that $\delta$ is a useful tool, how does one translate between $\delta$ and attack complexity (in number of bits of security)? Given a target short vector length and lattice parameters, how to estimate the time before BKZ 2.0 finds a lattice point of this length? (Or, if this is not a sensible question, why doesn't this runtime matter?)

The value $\delta$ characterizes, how short a vector you can expect to find using an algorithm (typically used in the context of lattice reduction).
In particular, for a vector $\mathbf{v} \in \Lambda$ (where $\Lambda$ is a lattice), the associated $\delta$ (often also denoted by $\delta_0$) is defined to be such that $\| \mathbf{v} \| = \delta^n \det(\Lambda)^{1/n}$.
For those don't know how to take the determinant of lattices, see page 4 of this introduction lecture in the course "Lattices in Computer Science" given by Oded Regev.
This was introduced in GN08 in the context for lattice reduction, because it was observed that the $\delta$ for output vectors returned by lattice reduction converges (for growing $n$) to a constant for every type and parametrization of reduction.
Generally, reduction algorithms are parameterized and allow for a trade-off between output quality (i.e. size of $\delta$) and running time. The exact trade-off is still a subject to research, especially as reduction algorithms continue to improve, but a good summary of the state-of-the-art is given in APS15 (Section 3). Roughly speaking, translating a SIS instance to a $\delta$ required to break it, is relatively easy, but translating the $\delta$ to a running time is not as straight-forward. The reason is that the behavior of lattice reduction, the most efficient approximation algorithms to date, is not very well understood and the community has not converged on a model yet.
One issue with lattice reduction is that it uses an exact SVP solver (in lower dimension). In order to instantiate these solvers there are different algorithms, some behaving better in practice and others being asymptotically more efficient. This makes it hard to analyze exactly, how long it will take to obtain a short vector of quality $\delta$.


Do I need to use AE/AEAD in my particular scenario? Or is it redundant? This is my scenario:

A small structured text message (1-2kB) is to be sent over an insecure channel.
Everything except for the header portion (which contains a title, timestamp, category and tags) is confidential.
The message as a whole has integrity and non-repudiation as additional requirements.

This is how I intend to go about it after having done some crypto-related research:

Encrypt the message with AES-CBC/OFB/CTR (key is pre-shared). The IV is added to the front of the ciphertext.
Add the non-confidential portions to the output from (1).
Make a digest-hash(SHA512 or RIPEMD160) of the output from (2) and encrypt it with the message author's private key (public key is pre-shared). Add that to the output from (2).
Send it over the insecure channel.

<---IV---><---AES Ciphertext---><---Header---><---Signature--->

Question:

I know that MAC algorithms and digest algorithms were designed for different purposes, but in this case, my digest is not merely slapped onto the payload, it is asymmetrically encrypted.

So, would the choice of AES-GCM/CCM/EAX have added any additional security?
Does my scheme have any obvious vulnerability that I overlooked?

Any help is greatly appreciated.

EDITS:

Fixed a typo. OBC $\rightarrow$ OFB.
I did not realize that the hashing algorithms are already built into all the major signing algorithms; I thought you had to do it yourself. Thanks for clearing that up.

NOTE: I would have chosen Ricky D.'s advice, but comments cannot be chosen as answers.

In general signature creation contains the hashing part within the algorithm. A signature algorithm may also contain a padding mechanism such as PKCS#1 v1.5 or PSS for RSA. Finally it contains a one-way trap door function (modular exponentiation within RSA). Encryption has other requirements, and uses a different padding mechanism.

Basically you are encrypting a plaintext, and signing all the data including IV within the message. I don't see the need for either a MAC or an authenticated cipher; the signature is perfectly fine as authentication tag. That does not mean that your current scheme does not have weaknesses:

it does not provide forward secrecy (i.e. if your secret key is compromised, all the messages can be decrypted)
you have to keep both a private key and share a secret key
asymmetric operations are expensive (with regards to CPU) and you need a private and public key operation per message
no signer anonymity (eavesdroppers can prove that messages were sent by a specific sender)
as others have pointed out, encrypt-then-sign may have vulnerabilities you should be aware of in your protocol

Those drawbacks may be resolved by a careful choice of a TLS cipher suite (if you just require transport security).

Finally you may want to think about how you are going to setup key management.


Getting 88bytes cipher output from 48bytes input in AES The other day I saw this Hybrid Cryptographic Algorithm in the Google and felt curious about it. I am trying to understand this Hybrid Algorithm. And hopefully its not so hard to understand whats going on until AES portion comes up. Here in this research paper the author gives 48bytes input to AES and gets 88byte output from AES.

I hope the author won't mind that I copied a part of the image and gave it in here.

My question is, How is this possible? AES always gives cipher size that is divisible by 16. But 88byte is wired! Can anyone help me by explaining or giving a hint what might be the way to achieve this?

-Thanks.

I don't think it's useful spending time on trying to understand that paper, but if you look at the screenshots and compare to their "character counts", you see that they are counting base64 characters and including the padding characters in the count.

That means "88 characters" could be one IV + three blocks of AES output (512 bits in base 64 = 85.33 + 2.67 padding).


Does frequent key change weaken encryption? Following scenario:
We are using OTR for communication between Alice and Bob which means after each successfull message exchange a re-keying happens for both parties leading to new AES-keys for the encryption and MAC generation.

Lets say Alice and Bob exchange 1000 message-pairs which leads to 1000 re-keying occurrences.

An attacker Mallory is able to record all messages between Alice and Bob.

Mallory brute-forces her way through the encryption by choosing one possible encryption key and trying it for every single one of the 1000 message-pairs.
Doesn't this lead to giving Mallory a better chance of cracking the code of one message-pair because she can use a single key and try this key for 1000 message-pairs (thus weakening the encryption)?

A little further thinking:
Using a single encryption key over a long period might increase the possibility of exposure of the encryption key. So re-keying is an effective means against that. But comming from the above example, re-keying too often might also lead to a weak encryption.
Is there a trade-off between the two of them?

I am not a crypto-analyst or any expert and I am well aware that my language propably doesn't fit into the crypto world by means of being to broad in some statements or not specific enough. I have no problem in understanding probility theory if an answer needs to include it, although I prefer pragmatism over theory.

Strictly speaking, it does make a brute-force attack more likely to recover a key for any message pair, but the impact of recovering a single key is minimized by frequent re-keying, since that key can't aid the adversary in decrypting any other messages. If you don't re-key, a brute force attack is only marginally more difficult but success gives you everything instead of just one message.


Is there is a way to calculate the public key from the private key in pqNTRUSign algorithm? There is source code of this algorithm (https://github.com/NTRUOpenSourceProject/NTRUMLS). But this algorithm does not provide a function for generating a public key from a private key. Studying the function pq_gen_key in src/pqntrusign.c, I did not see how it can be done.

I believe that the implementation's API doesn't allow you to derive the public key from the private key.  Instead, the model is that both are generated at the same time by the pq_gen_key function; you are expected to keep around the public key that returns.

Now, with NTRU, one could compute the public key from the private key.  In fact, that is pretty much how pq_gen_key works; it creates the ring elements $f$ and $g$ (which together essentially make up the private key), and then compute the public key from that.  It's just that they haven't bothered exporting that specific functionality.


Proof by reduction vs. hybrid argument In many cases why going through the security proofs I have seen that some does it using a blackbox reduction to some known hardness assumption DDH and others do it using a hybrid argument by arguing the indistinguishability between the hybrids is equivalent to adversary's advantage in the DDH game.

What I don't understand how to decide when to use blackbox reduction techniques and when to use the hybrid one. Is there any good way to know which one is a good fit while proving security?

There is actually no difference between what you are describing. One of the issues with writing proofs, is that a separate reduction must be proven for every element of the construction (you cannot reduce security to a hash function and DDH in one shot). In order to facilitate this, one writes hybrid games and then proves each hybrid via a reduction. In some cases, you only need to reduce to one thing (e.g., DDH), in which case there is no need for any hybrids. However, even in these cases, some people prefer writing very clear hybrid games. The question of how to know what is best is really just experience and more experience. I refer you to Victor Shoup's tutorial on game-based proofs. I also have a tutorial on simulation-based proofs. These can help.


Generating S boxes that satisfy Coppersmith's criteria? I'd like to generate all possible 6-bit to 4-bit S-Boxes that satisfy the criteria for S-Box design given by Coppersmith, but I have a few doubts:

How many such S-Boxes are possible?
Is there any existing implementation of said boxes?
What would be the most efficient way to implement them?

Any help is appreciated, thanks!

For each of the $2^6$ possible inputs, there are $2^4$ possible outputs. Thus, there are $(2^4)^{2^6} = 2^{256}$ possible S-Boxes mapping 6 bits to 4 bits: you cannot exhaust this many possibilities.

You need to construct S-Boxes which satisfies all the criteria directly, in contrast to looking at all S-Boxes and then testing for the criteria.

You may have a look at "affine equivalence" to divide the search space (see e.g. [1]) and at DESL [2], a variant of DES which uses a unique S-Box satisfying most of the Coppersmith criteria as well as other ones [2].

[1] On the Classification of 4 Bit S-Boxes, Arithmetic of Finite Fields (2007)
[2] New Lightweight DES Variants, Fast Software Encryption (2007)


What happens when a RC4 stream gets corrupted? I want to encrypt a large file using RC4. But what happens if the encrypted file gets corrupted (bytes modified or lost)? Can I still decrypt the rest of the file correctly?

If not, what is the best solution? Split the file in X chunks, and encrypt those seperately?

If a large file enciphered using RC4 is partially corrupted, the uncorrupted portions remains fully decipherable, including what's after a corrupted portion if the corruption modifies this data's value, but not its length (a length corruption could occur e.g. for serial communication, but is unlikely on a hard disk). This is a property of all stream ciphers.

An exception is when there's an IV somewhat combined with the key to form the full key input of RC4, and this IV is corrupted; then the whole file is undecipherable, essentially as if the key was lost.

Another practical exception is if the deciphering program somewhat stops when encountering a corrupted disk block, or gets the keystream out of sync with the ciphertext in this situation (which is not unseen!); to recover from this without fixing the program, the corrupted file can first be copied to a good media, with the corrupted blocks replaced by arbitrary data (rather then removed).

Finally, the deciphering program could include a provision to check file integrity, and refuse to output the plaintext if it is corrupted; in that case, this deciphering program needs a change to skip this check.


Code used for McEliece cryptosystem In the McEliece cryptosystem, is choice of the code known to the attacker? And if a structural attack succeeded and the attacker found the generator matrix of the code, how did the attacker decode the encrypted message?

The "seed" code is known (via $G$) to everyone including the attacker, but the actual code used is unknown. The seed code coordinates are permuted on the right ($P$) after an invertible transformation $S$ applied on the left, forming a trapdoor. $S,P$ are secret. If the permuted generator matrix is $\hat{G}$ we have
$$
\hat{G}=SGP.
$$
If the attacker finds the (unpermuted) generator matrix, then they can just decode as explained in the next paragraph.
If the received ciphertext is $c=c'\oplus e,$ where $e$ is the noise vector added for security, and $c'=m\hat{G},$ the legitimate recipient can do
$$
\hat{c}=cP^{-1},
$$
and can decode $\hat{c}$ to $\hat{m}$ using the standard decoding algorithm for the code. Finally she can compute
$$
m=\hat{m}S^{-1}.
$$
You can check in a routine way this works.
Edit: To clarify where the security comes from, the masking via permutation and matrix multiplication produces an equivalent “pseudorandom” code with similar properties to the original code.
So the equivalent decoding problem looks like a decoding problem for a random code, and since decoding a random code is difficult, the strength resides in the multiplication and permutation, they are trapdoor information available only to the authorized decoder.
Note that the noise added must not be beyond the correction capability of the code. If it was, the legitimate receiver might decode to the wrong codeword even with the trapdoor information or fail to decode to the correct codeword.


Prove that two MACs with incremendal PRF application are not secure How do I prove the following MACs are insecure?

                                            1

                                            2

The following was originally written as an edit to the question, but I'm going to put it here instead because I think formalizing the schemes might well provide you with enough of a hint for you to solve this question yourself:

Let $f(k,m)$ be a pseudo-random function, taking as inputs a key and a message, and outputing a value of the same length as the key (eg AES-128).

Why are the following MACs not sure?

[ref]
$\tau = c_i \oplus c_2 \dots \oplus c_n$, where $c_i=f(k,m_i)$.
[ref] $c_0=k$, $c_i=f(c_{i-1},m_i)$ for $i=1,\dots,m$ and $\tau=c_n$

To prove something insecure, we provide an explicit adversary. That is, we provide a method for doing what the security model says we shouldn't be able to.

In this case, that means we need are allowed to ask the system to provide us with the tag on some messages $\mathcal{M}=\{M_1,M_2,\dots\}$. Then, we create a valid tag for some message $M'\notin\mathcal{M}$.

So, a more direct hint: If you have the MAC of message $M=(m_1,\dots,m_n)$, can you construct...

Another message with the same tag?
A longer message who's tag you can calculate?


is this authenticated key exchange protocol sound? too complicated? obviously flawed? (significantly reworded this question to fit better into crypto.se).

I have static RSA keypairs for both sides and an encrypted transport that needs symmetric keys, and need to exchange session keys. The library I base this on is OpenSSL, which doesn't seem to have some pre-canned AKC protocol for me to use, so I have to roll my own.

I thought about various options, all of which use RSA for authentication and session key exchange and an additional curve25519 ecdh exchange for perfect forward secrecy.

I wonder how complicated it needs to be. Right now I do this - to start a half-duplex connection (session and hmac keys for sending only), I send a fully random RSA challenge and the public ecdh key.

The other side responds by checksumming the decrypted rsa challenge and the ecdh key, thereby proving that it has the private key, and then enganges in exactly the same protocol in reverse, so there are two rsa and ecdh exchanges (this is because it is simpler than doing only one ecdh exchange, even if it is slower).

The devil is in the details, here are my questions:

is it safe to use the random rsa challenge for key material (I use hkdf to derice keys)? I.e. is it safe to use the random rsa challenge data both for authentication and for encryption keys? My gues sis yes, but I would like to have an informed opinion, not mine :)
how should the authentication proof (digest (rsa + ecdh)) be calculated? Is a straight sha512 safe? Right now, I use hmac(part-of-rsa-challenge, rsa-challenge + ecdh), but this might be overkill, and even detrimental, as the hmac key is part of the hashed challenge data.
should the authentication proof include the ecdh data? If it does, then tampering could be detected earlier, if it does not, then the decryption fails later. My guess is that it doesn't really matter for the security.
the rsa challenge includes the hkdf salt, and additional keying material used by both sides, and there would even be space to include the ecdh key in the rsa. is it best to take as little as possible from the rsa challenge and send e.g. ecdh and hkdf salt in cleartext, or is it best to have as much data inside the rsa challenge?
Should I use a kdf to derive as many keys as possible from the same key material, or should I use as much independent key material as possible, e.g., when I have 1024 bit key material, should I use a single hkdf to derive 4 session keys from it, or should I use four independent hkdf invocations of each 256 bit part of the key material?

Most of these more or less boil down to the first question: how much (if any) of the random rsa challenge should be used for session key material.

The standard advice in this situation would: use a well-vetted mechanism, like TLS (or DTLS, or some other similar scheme).  If you're not doing that, you'd better have a good reason, as designing your own key-exchange protocol is non-trivial and unnecessarily risky.


PRG - understanding the definition Say $G$ is a $PRG$ that expands its input by a single bit, so we define:
$$G'(x_1||x_2)=G(x_1)||G(x_2)$$
The exercise states to prove that $G'$ is also a PRG.
Now here is my confusion. $PRGs$ are defined for random seeds as input.
But as an adversary I know $G$. So for $x\in\{0,1\}^*$ I could always input
$$x||x$$
And now, I can check if both halves of $G'(x||x)=G(x)||G(x)$ are equal and know that this isn't random.

In the solution they assume that $x_1,x_2$ must be randomly selected as well. But then what is the point of an adversary?

The adversary must not be allowed to choose the seed.
(Otherwise, the definition would be trivially unsatisfiable, as the adversary could just check whether the returned string is $G(x)$ for their chosen seed $x$.)

The rationale behind this is that a PRG's seed is understood as (some kind of) a secret key, which the attacker must not be able to know or choose in any threat model. (After all, that's why the secret key is secret. Note that any cryptography trivially breaks when the attacker gets their hand on the key(s).)

By definition, a function $G\colon \{0,1\}^n\to\{0,1\}^{\ell(n)}$ with $\ell(n)>n$ is a pseudorandom generator (PRG) if any polynomial-time adversary is unable to differentiate between a truly random $y\in\{0,1\}^{\ell(n)}$ and the pseudorandom string $G(x)$ for a random seed $x\in\{0,1\}^n$ except for negligible probability.

Intuitively, what this entails is that the output of a PRG, when initialized with a sufficiently random seed, is "just as good" as a real random string.


Security of S/MIME in case of CA compromise Suppose Alice and Bob are exchanging messages using S/MIME, protected by certificates that have been issued by either the same CA or by two mutually independent CAs. There exists an adversary Mallory who wants to get the ability to compromise the confidentiality of the communication, or the integrity, or both. We may assume Mallory is subject to the following restrictions:

Mallory does not have access to the private keys of Alice or Bob. Mallory might however have access to the private certificate signing keys of the CAs.
Mallory has full access to the network communication between Alice and Bob.
Mallory wants to avoid detection. Primarily, Mallory wants an attack that is completely transparent to both Alice and Bob, and in worst case, an attack that will interfere in a detectable way with the communication, but only infrequently and can be rationally explained as network failure, software failure or hardware failure.
Normally, we might assume Mallory delegates most actions to an automated service. In particular, we might assume that even if Mallory has managed to compromise both confidentiality and integrity and in both directions, most of the time the exchanged messages will be let through without interference, and it might be hard for Mallory to alter the messages in real time, when some information (such as certificate thumbprints) is exchanged that might lead to exposure of the compromise.

Technically, Alice and Bob will normally establish a confidential channel by Alice sending a signed only message to Bob, Bob extracting the certificate of Alice, and replying with a signed-then-enveloped message to Alice. Given the first three restrictions, such an exchange might be trivially compromised in the following way:

Mallory creates a key pair $Pub_{FA},Priv_{FA}$ and a certificate $Cer_{FA}$ that is signed by a CA that Bob trusts and which (dishonestly) identifies Alice. Mallory creates a key pair $Pub_{FB},Priv_{FB}$ and a certificate $Cer_{FB}$ that is signed by a CA that Alice trusts and which (dishonestly) identifies Bob.
Alice sends a message $Sign_{Priv_A}(M_A,Cer_A)$ to Bob which is intercepted by Mallory who replaces it with $Sign_{Priv_{FA}}(M_A,Cer_{FA})$.
Bob sends a message $Env_{Pub_{FA}}(Sign_{Priv_B}(M_B,Cer_B))$ which is intercepted by Mallory who replaces it with $Env_{Pub_{FA}}(Sign_{Priv_{FB}}(M_B,Cer_{FB}))$.

Now, my concern is that this attack does not necessarily comply with the fourth restriction. For instance, if Alice and Bob somehow manages to, without detection, exchange certificate thumbprints over the compromised channel, the compromise will be detected immediately.

Are there any better attacks, or might we assume that the four restrictions make S/MIME relatively safe from attackers such as Mallory?

Edit: Mallory is a threat to the confidentiality and integrity of Alice and Bob. Conversely, Alice and Bob are a threat to the transparency of Mallory. Considering that Mallory gets to pick the targets Alice and Bob, but not the other way around, to what extent might Alice and Bob trust their confidentiality and integrity, based on their being such a threat to the transparency of Mallory, that Mallory might be safely assumed to not attack them?

No, since

compromising the communication $\:\implies\:$ compromising the PKI setup $\:\implies$

falsely claiming that a party generated a particular public key $\:\implies\:$ "if Alice … immediately."

.

Yes, we might assume that.

Note that, if the channel can carry voice, then faking a comparison can require voice impersonation.

This is the idea behind ZRTP (which admittedly is not for email).


Anonymous trust/reputation system Suppose there are 3 persons, Alice, Bob and Peter.

They are identified by their pseudonyms (public RSA keys).

Alice has a key Alice, Bob has Bob-Work and Bob-Friends. Peter has Peter.

Peter knows Alice. Alice expresses trust to Bob-Work.

Peter knows Bob-Friends.

The question is, How can Bob-Friends prove to Peter, that Bob-Work he's being trusted by Alice (and therefore Bob-Friends too), without revealing that Bob-Work and Bob-Friends belong to the same person, and/or plausibly deny such a fact?

NOTE: We do not discuss timing attacks here (such as "Please express trust to THAT pseudonym and I'll see who will appear as trusted to me afterwards")
I have a possible solution involving a "credit system", where participants emit "trust tokens" which can then be transferred by their recipients. But, this has a downside of having to support a LONG credit transfer history. Is there a solution that does not need it?

P.S. Please retag this question appropriately (reputation, trust etc) - I can't create new tags yet :)

You are probably looking for what is called "anonymous credentials".

An anonymous credentials system relates three types of parties: authorities, users, and verifiers. An authority (Alice) can issue a credential to a user (Bob), that certifies that the user satisfies some property (in your case, that would be "is trusted"). Credentials are unforgeable. Then, that user (Bob) can prove to a verifier (Peter) that it possesses the credential, without revealing anything about himself other than the possession of the credential (anonymity), even if the verifier colludes with other verifiers and/or the authority.

The way anonymous credentials systems are typically implemented is that a user has a single private key sk, and multiple corresponding public keys pk, pk', etc. (pseudonyms) that can be generated on the fly as randomized commitments on sk. Then, the credential issuing protocol is a special kind of signature scheme that produces a signature on the value inside the commitment; in that way, Bob can obtain a credential from Alice via his pseudonym Bob-Work, and prove possession of it under his pseudonym Bob-Friends, in such a way that the two pseudonyms cannot be linked to each other.

A good general introduction to anonymous credentials is Anna Lysanskaya's Ph.D. thesis, especially chapter 3.

Since 2002, there has been quite a bit of research and progress on anonymous credentials, so we have efficient instantiations supporting additional features like revocation or delegation.


How can an unlimited adversary distinguish PRF's from Truly Random Functions (TRF)? I'd like to know which strategy is adopted by an unlimited adversary to distinguish PRF's from Truly Random Functions

Let's first define the domain and range of the function we want to distinguish to be $M = \{0,1\}^m$ and $N = \{ 0,1\}^n$.

Now, what does it mean for a function to be truly random? It means that it was selected uniformly at random from the space $\mathsf{FUNC}(M, N)$, which consists of all functions from $M$ to $N$. How many such functions are there? I.e., how big is the space $\mathsf{FUNC}(M, N)$? Answer: $N^M = 2^{n \cdot 2^m}$ (exercise: prove this).

On the other hand, if the function is a PRF, then it was not drawn from the full space $\mathsf{FUNC}(M, N)$, but rather from a much smaller space indexed by the key of the PRF. That is, a PRF is formally a family of functions $\{F_k \}_{k \in K}$, where each member is a function $F_k \colon M \to N$. What we really mean when we say that the function is a PRF, is that we first pick a key $k \in K$ uniformly at random from the key space, and then we use the function $F_k$ indexed by this key to answer all queries. So how big is the PRF "function space"? It's simply the size of the key space $K$, i.e., $|K|$.

In the PRF distinguishing game we are then asked to distinguish a function which is either randomly selected from the set $\mathsf{FUNC}(M, N)$, or randomly selected from the family $\{F_k \}_{k \in K}$. For concreteness, suppose $M = N = K = \{0, 1\}^{128}$. Thus, in this case we are asked to distinguish a function which is either drawn from a set of size $2^{128 \cdot 2^{128}}$, or from a set of size $2^{128}$. Notice the massive difference in size between these two sets! The PRF family lives inside a tiny tiny tiny bubble of the whole space $\mathsf{FUNC}(M, N)$. In other words, the functions in the PRF family only exhibits a very tiny portion of all possible functional behaviors between the sets $M$ and $N$.

So how can we use this to distinguish whether the function we are given is truly random or only a PRF? Well, since we are an unlimited adversary, we can simply query the function at all possible inputs in $M$ to determine exactly which function in $\mathsf{FUNC}(M, N)$ we are dealing with. If the function does not belong to the function family $\{F_k \}_{k \in K}$, then we of course know that it was selected as a truly random function and not as a PRF. But if it does belong to $\{F_k \}_{k \in K}$, what should we guess then? I claim that we should guess that the function was selected as a PRF. Why? Well, if the function was selected uniformly at random from $\mathsf{FUNC}(M, N)$, what is the probability that it would happen to coincide with a function in $\{F_k \}_{k \in K}$? Answer: really tiny. (Exactly how tiny I leave to you to figure out).


Relationship between special RSA modulus and quadratic residue in CL (Camenisch-Lysyanskaya) signature I'm studying the CL(Camenisch-Lysyanskaya) signature (A signature scheme with efficient protocol proposed by Camenisch-Lysyanskaya).

However, I cannot understand the relationship between special RSA modulus and quadratic residue.

What is the relationship between Special RSA modulus and quadratic residue?

and please recommend the references for special RSA modulus.

The standard RSA ($c=m^{e}$ $mod(n)$) is not semantically secure, since it reveals one bit information about the message. This information is jacobi symbol of the message. You can find many resources about jacobi symbol but basically it states that a value is in $QR_n$ or not. In CL signature, we can handle with this situation easilly, since we determine the base values for exponentiation operations. If we choose the base values from $QR_n$, any exponentiation operation using them outputs another value from $QR_n$. Thus, there is no revealed information. Ofcourse, it comes with a disadvantage that any output of exponentiation is in $QR_n$ we decrase the number of possible outputs that we can get.


The danger of Hash collision in Schnorr NIZK We use Fiat–Shamir heuristic to turn Schnorr ZK to NIZK. So now NIZK is secure against chosen message attacks in the random oracle model, that is, ideal hash function: every unique query leads to a truly random response.
Ok, I get why our Hash function should not be reversible  - otherwise, we disclose skey.
But what is the danger of collisions?
Suppose, a prover computes NIZK proof (r,c):

c = Hash( g || V || pkey || User Id || Other Info )
r = v + skey*c mod q
V = g^v mod p, v - random

Even if I find any other combination that results in c, it's unlikely I can forge proof.

First, I do not think reversing the hash function will help you disclose skey as nothing in the Hash needs to be private. The Hash in Schnorr NIZK is a practical instantiation of the random oracle, not perfectly though. Here the random oracle is used to commit or sign V, so that you can not choose V based on c. Note that it is trivial to get V given y, c, g, r, and pass the verification $Vy^c = g^r$.

As for the danger of collisions, it may not be very relevant to the security proof. Hash functions are just how we implement random oracles in practice. I think a better way to look at this is as follows. If one can forge a proof, then c should be equal to the output of the random oracle with input (g, V, pkey, ...). This happens with small probability, as a random oracle always outputs a purely random value given a new input.


How did the Koblitz/Menezes papers affect the cryptography community? Two highly-critical papers by Koblitz and Menezes (two well-regarded mathematicians who've contributed to the crypto community) were published years ago: Another Look at “Provable Security” in 2004, Another Look at “Provable Security”. II in 2006.

Have these papers had any noticeable impact on how research is conducted in the provable-security community?  Or have these papers largely been ignored?

My impression (which is limited) is that the most researchers are pretty content with the state of security proofs, and it did not have much impact on changing the research agenda of the community. In fact, a related paper was strongly opposed by leading cryptographers. That is not to say the papers were ignored. They generated lots of discussion and maybe some self-reflection.

They are also, unfortunately, sometimes cited by people who do not really understand the issues and just have an axe to grind against papers being too technical.


Is stretching hash several times basically the same as bcrypt? As I understand it, the main advantage of bcrypt is stretching so it becomes slower to crack overtime. But, is using a "good enough" algorithm (e.g., SHA-2 family) then stretching until it's slow enough for your liking is pretty much the same as bcrypt?

Note: I understand scrypt is superior but let's assume bcrypt is the best for now.

bcrypt operates using the Blowfish block cypher. It does not use any kind of message digest function (such as MD5, SHA1, SHA-256, etc.) internally.

Of course, I think what you really wanted to ask was, "would using a traditional message digest function with some amount of stretching give similar security to bcrypt?", and the answer to that question is probably "no". However, we can't answer that because we don't really know how you would accomplish the stretching. It's probably reasonable to say that stretching in some way would achieve similar security, but you would need to account for what bcrypt was designed to do.

bcrypt does have the advantage that it's "slower" than the message digest algorithms, but that's not it's main goal. bcrypt was designed not only to be slow, but to scale poorly on FPGA and GPU architectures. As you mentioned, modern FPGAs have gotten quite a bit better and serve as reasonable means to break bcrypt, which is why scrypt was invented in the first place.

It should be noted that what you describe with the stretching is essentially PBKDF2, which has been shown to be less secure than bcrypt.


Fiat Shamir transformation of zero knowledge proof Consider the following three stage interactive zero knowledge proof

The prover sends some information $a$ to the verifier.
The verifier picks a challenge $c\in \{0 ,1\}$
Depending on the challenge, the prover responds with $r(c)$ that convinces the verifier of his knowledge.

Each round can be won with probability $\frac{1}{2}$ by a malicious prover and so we must play this for $k$ rounds till $\frac{1}{2^k}$ is sufficiently small.

The Fiat Shamir transformation replaces the challenge generation with a random oracle that generates $c$ instead. Let $i$ be the round number (we play $k$ rounds). Typically, one can use a hash function $c_i = H(p_{i-1}, a_{i-1})$ for this purpose, where $p_{i-1}$ is some input generated from prior rounds and $a_{i-1}$ is the previous round's commitment. The prover then generates a transcript of the following form after many rounds

$$T = \{a_i, c_i = H(p_{i-1}, a_{i-1}), r_i\}$$

It is not clear to me why this is secure. In each round, the dishonest prover can simply keep trying different $a_{i-1}$ until $H(p_{i-1}, a_{i-1})$ is the challenge he is prepared to meet. Since $c\in\{0,1\}$ (i.e. the range of $H$ is just $\{0,1\}$), this does not take him many tries. The prover will only include such challanges (which he is prepared to meet) in the transcript.

What exactly is the correct Fiat Shamir transformation that prevents this attack by a dishonest prover?

You are correct about the attack, given the way you have defined the Fiat-Shamir-transformed protocol.

Since Fiat-Shamir is subtle for multi-round protocols, the standard way to resolve this is to use parallel instead of sequential composition. Start with a protocol that has soundness error 1/2, and run it $k$ times in parallel (not in sequence) to amplify its soundness error to $1/2^k$.

Then apply Fiat-Shamir to the resulting protocol, which just has one round. All the challenge bits are generated from a single call to $H$ as $c_1 \cdots c_k = H(a_1 \cdots a_k)$. Note that if the prover is proving a false statement, then for any first protocol message $a_1 \cdots a_k$ there is at most one $c_1 \cdots c_k$ for which she can generate a totally convincing response. With $q$ queries to $H$, an adversary can find such a valid first message with probability only $q/2^k$.


How to find fixed points for DES weak keys Can someone explain me this  please I am a bit confused?  It's from a texbook I am reading (block cipher companion)  it says that:

  each weak key has  $2^{32}$ fixed points $m$ where $\operatorname{DES}_w(m) = m$ ( $w$ is a DES weak key). In other words encrypting a fixed point gives exactly the same point. To see this consider the $2^{32}$ ciphertexts after 8 rounds of encryption for which the two 32 bit halves are equal. For a weak  DES key, the round keys of the eighth and ninth rounds are equal. Thus the intermediate texts after seven rounds and after nine rounds of encryption will be equal. Since the round keys of the 7th and the 10th rounds are equal, the intermediate texts after 6 rounds and after 10 rounds of encryption will be equal. Continuing like this it follows that the plaintext will be equal to the ciphertext.

Now did not quite get :

Why are there $2^{32}$ fixed points?  And why after the eighth round of encryption the two halves must be equal?
What does the author mean by the intermediate texts exactly? And how are they being equal?

P.S.: This question is not asking for what the weak keys are. I am asking for "fixed points" not exactly weak keys. For this reason I think it is not a duplicate of any other question. There is one similar question to what I've asked for which I have checked and saw that no satisfactory answer has been given there either.
Here is the similar question with no proper answers:

What is the fixed point attribute of DES with weak keys?

I answer in hopefully didactic order.

  What does the author mean by the intermediate texts exactly?

The intermediate texts after $n$ rounds are the 64-bit quantities $L_n\mathbin\|R_n$, numbering these per the specification of DES. $L_n$ and $R_n$ are the halves.

  Why after the eighth round of encryption the two halves must be equal?

I do not know if the two halves must be equal. But we can prove that it is enough that the two halves are equal, which is what the quoted text does.

Ignoring $\mathsf{IP}$ and $\mathsf{IP}^{-1}$, the normal equations of DES encryption are, for $1\le n<16$:
$$\begin{align}
L_n&=R_{n-1}&&&R_n&=L_{n-1}\oplus f(R_{n-1},K_n)\\
L_{16}&=L_{15}\oplus f(R_{15},K_{16})&&&R_{16}&=R_{15}
\end{align}$$
As a consequence of the values of the four weak keys $z$, all bits in register $C$ are identical. Therefore $C$ remains invariant as it rotates during encryption. The same applies for $D$. Hence $K_1=K_2=\ldots=K_{15}=K_{16}$. Thus for $1\le i\le16$ we can replace $f(R_i,K_i)$ by a function $f_z(R_i)$ identical in all the rounds, for fixed $w$. The above DES equations turn into
$$\begin{align}
L_n&=R_{n-1}&&&R_n&=L_{n-1}\oplus f_z(R_{n-1})\\
L_{16}&=L_{15}\oplus f_z(R_{15})&&&R_{16}&=R_{15}
\end{align}$$
If $L_8=R_8$ (that is equals halves after round 8) then, by plugging this into the equations for $n=8$ and $n=9$, we get
$$\begin{align}
L_8&=R_7&&&L_8&=L_7\oplus f_z(R_7)\\
L_9&=L_8&&&R_9&=L_8\oplus f_z(L_8)
\end{align}$$
We plug the top two equations into the bottom ones, and get
$$\begin{align}
L_9&=R_7&&&R_9&=\bigl(L_7\oplus f_z(L_8)\bigr)\oplus f_z(L_8)\\
&&&&&=L_7\oplus\bigl(f_z(L_8)\oplus f_z(L_8)\bigr)\\
&&&&&=L_7\oplus0^{32}\\
&&&&&=L_7
\end{align}$$
We used associativity of $\oplus$, that $f_z$ is a function (and identical in all rounds), that for all 32-bit $X$ it holds $X\oplus X=0^{32}$ (the bitstring of 32 zero bits), which is the neutral for $\oplus$.

Wrapping up, we get $L_7=R_9$ and $R_7=L_9$. Thus "the intermediate texts after seven rounds and after nine rounds of encryption will be equal" within an inversion of left and right that the quotation mistakenly sidesteps.

We plug these results into the equations for $n=7$ and $n=10$, and get
$$\begin{align}
R_9&=R_6&&&L_9&=L_6\oplus f_z(R_6)\\
L_{10}&=R_9&&&R_{10}&=L_9\oplus f_z(R_9)\\
\end{align}$$
After simplification as previously, we get $L_6=R_{10}$ and $R_6=L_{10}$. And so on, up to $L_1=R_{15}$ and $R_1=L_{15}$. For the next step we must take care that the the equations for the last round reverse $L_{16}$ and $R_{16}$ compared to others. We obtain $L_0=L_{16}$ and $R_0=R_{16}$.

The 64-bit plaintext $P$ is such that $\operatorname{IP}(P)=L_0\mathbin\|R_0$ and the 64-bit ciphertext block $C$ is such that $\operatorname{IP}^{-1}(L_{16}\mathbin\|R_{16})=C$. It follows that $P=C$. Call that quantity $m$ and we have $\operatorname{DES}_w(m)=m$, Q.E.D.

  Why are there $2^{32}$ fixed points?

There are $2^{32}$ possible values for $L_8$, thus for intermediate text $L_8\mathbin\|R_8$ with $L_8=R_8$. By the above reasoning, each gives a value of $m$ with $\operatorname{DES}_w(m)=m$ for a given weak key $w$. And the values thus obtained must be distinct: DES encryption is deterministic for a given key $w$, thus the same input value can't give different intermediate texts after 8 rounds.

Hence there are at least $2^{32}$ fixed points $m$ for a given weak key $w$. I do not know how many more there might be, for each of the four $w$. However, we can tell that the counts are the same for the all-zero and all-one $w$ (ignoring parity bits); same for the two other weak keys. That follows from DES's complementation property.

  How to find fixed points for DES weak keys

One option is to modify some DES encryption code to start at round 8 with $L_8=R_8$. The ciphertext will be a fixed point for the weak key used. We can find $2^{32}$ of these for a given weak key $w$, by using a counter for $L_8$. When that's done for a weak key $w$, we can derive fixed points for the complement of $w$ by using DES's complementation property.


Miller Rabin - Error probability of .5 a possibility? I'm testing the property of Miller Rabin that the error probability is at most 1/4 when only a single base a is chosen and we iterate only one time. We are testing odd integers 90,000 to 100,000.

I've written up the implementation in Java and as the test is running, I'm seeing a lot of probabilities of .5. This leads me to believe that there is an issue with my implementation.

Some of the odd integers in which I'm seeing a .5 error probability are:
90007
91571
94343

There are plenty more (the test is still running).

Update: Here is the Algorithm I've implemented

 Miller–Rabin Primality Test
 Input: prime candidate ˜ p with ˜ p−1 = 2ur and security parameter s
 Output: statement “ ˜ p is composite” or “ ˜ p is likely prime”
 Algorithm:
 FORi = 1 TO s
    choose random a ∈ {2,3, . . . , ˜ p−2}
    z ≡ ar mod ˜ p
       IF z ≡ 1 and z ≡ ˜ p−1
          FOR j = 1 TO u−1
             z ≡ z2 mod ˜ p
             IF z = 1
                RETURN (“ ˜ p is composite”)
          IF z = ˜ p−1
             RETURN (“ ˜ p is composite”)
 RETURN (“ ˜ p is likely prime”)

Here is the implementation, if anyone could take a look and determine what the problem is I would really appreciate it.

Thanks

public BigInteger mr(int x, int y){
    int u = 0;
    BigInteger p = BigInteger.valueOf(x);
    BigInteger r = p.subtract(ONE);
    BigInteger a = BigInteger.valueOf(y);

    while (r.mod(TWO).equals(ZERO)){
        u++;
        r = r.divide(TWO);
    }

    BigInteger z = a.modPow(r, p);
    if ((!z.equals(ONE) && !z.equals(p.subtract(ONE)))){
        int j = 1;
        for (; j < u; j++){
            z = z.modPow(TWO, p);
        }
    }
    return z;
}

public boolean isPrime(int n){
    if ( n % 2 == 0)
        return false;

    for (int i = 3; i <= Math.sqrt(n) + 1; i+=2){
        if (n % i == 0)
            return false;
    }
    return true;
}

public static void main(String[] args) {
    double ea;
    MillerRabin mr = new MillerRabin();
    int count = 0;
    BigInteger ans;
    for (int n = 90001; n< 100000; n+=2){
        count = 0;
        for (int a = 1; a < n; a++){
            ans = mr.mr(n, a);
            if (mr.isPrime(ans.intValue())){
                count++;
            }

        }
        ea = ((double)count) / (n-1);
        System.out.println(ea);
    }
}

The problem is that you got the algorithm wrong.  You use it to generate an integer (which is one of 1, $x-1$, or $y^{x-1} \bmod x$, and then say "prime" if that integer is prime.

That's not correct; in fact, the three integers you list (90007 91571 94343) are each prime, and Miller Rabin should always return prime when given a prime.

Instead, the correct implementation of MR should:

if the initial computation is $y^{(x-1)/2^u}$ is 1 or $x-1$, conclude probably prime.
do $u-1$ square operations, if the result of any of them is $x-1$, conclude probably prime, if it is 1, conclude "composite"
if, after the $u-1$ square operations, you never hit $x-1$, conclude "composite"


How does the receiver compute the private key when using RSA? I understand the public key and the private key are generated at the same time. The payload is encrypted with the public key. Sender Alice sends public key $[n,e]$ and cipher text $C$ to Bob.

Now is Bob recomputing the private key $d$?

If Bob is computing the private key $d$, can a "Man in the Middle" who gets the public key and cipher text also compute the same?

Or is there a scenario in which both Alice and Bob know the value of $p$ and $q$?

I am confused. Please help me understand this in a scenario assuming Alice and Bob are located in two different geographical locations.

I understand public key and private key is generated same time.

Yes, Bob does that, and gives the public key to Alice.

  The encryption is done with public key. Sender Alice sends public key [n,e] and cipher text C to Bob. Now is Bob recomputing the private key "d"?

No, Bob created the private key, and so doesn't need to 'recompute' it; he just saves it in secure storage.

  If Bob is computing the private key d, a "Man in the Middle" who gets the public key and cipher text can also do compute the same?

No, the man in the middle didn't create the public/private key pair, and so (unlike Bob) he doesn't have the private key in storage.

The only nontrivial issue here is "when Bob initially gives the public key to Alice, how does Alice know she got Bob's public key (and not a "man in the middle" public key)?".  Solutions for this include such as a one-time out-of-band authentication (say, a phone call, which might be worth it if Alice is going to encrypt a lot of messages with Bob's public key), or a "certificate" (which is something signed by a trusted authority which says "Bob's public key is [XXX], sincerely Big Brother")