Theoretically, what if I were to change some magic numbers in, say, AES? Purely theoretically. I know it's a bad idea to try to invent your own encryption and that's not the intention here. Just a thought experiment.

Say, I change some or all of the magic numbers used in, say, AES (but this would also apply to other algorithms) and create "AES-RobIII". Of course, this would be incompatible with the current AES algorithm.

First: I know these numbers are chosen (usually) very carefully (sometimes maybe even crafted so that they can contain a secret backdoor, but I'm not interested in conspiracy theories, etc). How are these numbers chosen generally and I assume there are many ('infinite') variations possible? Do they come from an 'RNG' (tuned to some specific rules)? Are they chosen 'manually'? I know they have to satisfy some polynomial(s) but do they (the cryptographers designing the algorithm) just start with a random seed or pick a specific number or...?
Since these magic numbers are, along with the algorithm, out in the open (as any good encryption algorithm should be), I could theoretically pad the encrypted message with them and 'load' these tables with the numbers before the algorithm is kicked off to encrypt/decrypt, right?
Then why have these numbers as constants in the algorithm (unless size is a priority of course) in the first place? Or why don't we have, say, AES-I, AES-II, and AES-III with the only difference being another set of magic numbers? You could even consider the table(s) of magic numbers used a sort of "extra key" so, say, a company could use their generated (similar to how private/public keypairs are generated for example) set of numbers internally for extra added security when stuff would leak. I realise it won't add much (if anything at all) but added complexity but I was just wondering.

Again, I realise this won't add any advantage of any meaning (probably), if at all, but I was just wondering. Also, this question is based on the assumption that if I change any of the magic numbers and encrypt something with it and then try to decrypt it (with the same, altered, magic numbers) it would still decrypt correctly.

Update: the answers so far seem to focus primarily on AES, but that was just an example. I could've picked any algorithm (though I realise that details may differ per algorithm). I also realise that AES is plenty strong enough and that AES is implemented in a lot of hardware; though I don't see a problem if you can load these magic values in some 'registers' or 'dedicated ram for this purpose' (but I understand it would be a lot less performant and use up a whole lot more wafer space). I was/am looking more from a theoretical point of view where speed or practicality don't (really) matter.

How are these (magic) numbers chosen?

It heavily depends on what algorithm and which of its magic numbers. They seldom are entirely arbitrary. In AES, it is often taken the lowest value such that a certain mathematical property holds, with that property (demonstrably or plausibly) working towards security. In other algorithms, it could be values that pre-existed in another context (like mathematical constants), often screened so that some criteria is met (e.g. being odd).

  Are they chosen 'manually'?

Quite often so. Or, as is the case in AES S-boxes, an auxiliary program is used.

  I could theoretically pad the encrypted message with them and 'load' these tables with the numbers before the algorithm is kicked off to encrypt/decrypt, right?

Yes.

  Then why have these numbers as constants in the algorithm?

Occam's razor. And other good reasons, among which:

Introducing parameters rather than constants, especially along messages, could very realistically open to attack. For example, if AES S-boxes where a parameter prefixed to a short AES-GCM message, an attacker could change a bit in these constants in the prefix and see if the message gets nevertheless accepted by the receiver despite that change, meaning with high likelihood that the particular S-box entry for this bit was not active during decryption, which would reveal a lot of information about message and key. That could allow recovery of message and key with a realistic number of attempted decryptions.
Changing constants to variables would make hardware implementations slower, larger, more power-hungry and complex. In the case of AES, the standard constants are carved into modern CPUs.
Changing constants may invalidate complex optimizations (for speed or side-channel leakage) that went into translating the constants to hardware or software. In the case of AES S-boxes, see e.g. Joan Boyar and René Peralta: A Small Depth-16 Circuit for the AES S-Box, in proceedings of SEC 2012.

  You could even consider the table(s) of magic numbers used a sort of "extra key"

There are better ways to obtain that. For example, what's fed to the key input of AES could be obtained with a Key Derivation Function applied to the normal key and extra key.


ECDSA pubkey recovery issue I try to recover public key from the given message $m$ and pair $(r, s)$ using curve that satisfies standard RFC7091. I am using algorithm from one of secp256k1 implementation but it seems that not any random $k$, that is $0<k<N$ give me a pair $(r, s)$ that I can recover a valid public key. I did check this question How does recovering the pubkey from ECDSA signature works and tried to use curve with this parameters $P=23, a=13, b=10, N=19, G=(18, 2)$ but I've got a valid pubkey with specified message only on very small subset of values $k$.

Is there any solution how I can calculate restrictions for $(r, s)$ generated pair to determine that my signature will be recoverable or I just have to try re-do signing operation until I get a valid one?

UPDATE:
I have figured out that there are different algorithms for signing/verifying in ECDSA and RFC7091:

In ECDSA we compute s as $s=k^{-1}(z+rd_A)\mod n$
In RFC7091 we compute s as $s=(zk+rd_A)\mod n$

where $z$ is the hash of message, $d_A$ is the private key, $k$ is random in $0<k<n$, $n$ is the subgroup order and $r$ is calculated similar to both algorithms.

So the recovery formula for pubkey in ECDSA: $Q=r^{−1}(sR−zG)$ shouldn't work correctly because of different value of $s$ producing by both algorithms.

Is there any possibility to modify recovery formula to work for RFC7091 standard?

The signature validation logic from RFC7091 is effectively:

$$r \stackrel{?}= abs( h^{-1}sP - h^{-1}rQ )$$

where $r, s$ are values from the signature, $h$ is the message hash (converted into an integer), $P$ is the EC group generator, and $Q$ is the public key, and $abs$ is a function that maps a point to its x coordinate.

You know everything except for $Q$; you can recover that by using simple algebra; you would find the two points $R, R'$ with $r$ as an x-coordinate, and then $Q$ is one of:

$$r^{-1}(sP - hR)$$
$$r^{-1}(sP - hR')$$

(where you compute $r^{-1}$ modulo the curve order)


Is this an instance of a Diffie-Hellman problem? Let $\mathbb{G}$ be a cyclic group of order $p$ with generator $g$, and let $m\in\mathbb{G}$.
Problem: Given $c=m.g^{k.a}$ and $v=g^a$, where $k,a \in \mathbb{Z}^*_p$, output $k$.
Is this an instance of a Diffie-Hellman problem? Because the only way I see to solve this is to try $v^i, i\in \mathbb{Z}^*_p$ until we stumble on $i=k$, but since $g^{k.a}$ is also hidden by $m$, I do not think searching for $i$ is a viable method.

As stated the problem is insoluble as zero-knowledge of $k$ is provided (unless we know something about $m$).
To see this, let $x$ be any integer $0\le x\le p-1$ and let $m':= m\cdot v^{-x}$ then we see that $c=m'\cdot g^{(k+x)a}$ and we see that $k+x\pmod p$ is an equally valid output unless we have some reason to choose $m$ over $m'$.


Indistinguishable encryptions in the presence of an eavesdropper I'm trying to understand how the messages $m_0$ and $m_1$ can be distinguished here. I understand the adversary game, so in short: Adv chooses $m_0$ and $m_1$, one them is encrypted and Adv is able to tell which one has been encrypted.

My understanding is that (ignoring the ctr for the moment, because its the same for each encryption):

$F_k(1+ m_{01}) = F_k(1111), F_k(2+m_{02})= F_k(1111)...$
$F_k(1+ m_{11}) = F_k(0001), F_k(2+m_{12})= F_k(0010)...$

We know if $m_0$ is encrypted then each block will be the same, if $m_1$ is encrypted instead we should get some random. If someone could explain if my understanding of $F_k$ is correct and if there is some significance in $m_1$ and why it's all 0. Or am I overthinking this...

Your understanding is correct. There is no particular significance to $m_1$ being all zeroes, it is just a simple and convenient way to ensure that the inputs to $F_k$ will be all distinct, which is what we need in order to produce a pseudorandom string.


Certificate Verify in SSLv3 I'm trying to figure out the SSLv3 protocol for educational purposes and having hard time understanding mutual certificate authentication.

When the client requested to provide a certificate it also has to send a CertificateVerify message:
CertVerify = Sigclient(pre_master_secret, Msg1, Msg2)

Why the public key of the client is not used like it used for the server?

Lets use the text from the protocol for reference:

  After verifying the server's certificate, the client encrypts a
     pre_master_secret with the server's public key.  By successfully
     decoding the pre_master_secret and producing a correct finished
     message, the server demonstrates that it knows the private key
     corresponding to the server certificate.

  When RSA is used for key exchange, clients are authenticated using
     the certificate verify message (see Section 5.6.8).  The client signs
     a value derived from the master_secret and all preceding handshake
     messages.  These handshake messages include the server certificate,
     which binds the signature to the server, and ServerHello.random,
     which binds the signature to the current handshake process.

And your question is:

  Why the public key of the client is not used like it used for the server?

The method of establishing the secret is kept identical for SSLv3 with client authentication. The client authentication is added to the protocol. This way the implementation of the key agreement can remain the same, with or without client authentication. There is no need for a second pre_master_secret or random either, one is sufficient to derive the session keys.

Now the server is authenticated by being able to decrypt the pre_master_secret send to it by the client. This shows it has the private key that belongs to the public key within the (verified) server certificate.

The client on the other hand does not perform any operations with the private key in this protocol. On the other hand, the private key must be used over session specific data; if this wasn't the case the private key operation would be vulnerable against replay attacks. So a signature over the session data is used instead. No additional random values or challenges are required.


Key-Bijective Secure Symmetric Encryption Methods In AES, an N-bit message is mapped 1-to-1 message-to-output (for a fixed key).
If we use a key with N bits, however, the key is not mapped 1-to-1 key-to-output
(for a fixed message).

So, is there any secure symmetric encryption method with a 1-to-1 key-to-output
mapping?

In the end, I'm just looking for a hash function h(m,k) with no collisions
over m (for a fixed k) and no collisions over k (for a fixed m), but it seems
easiest to leverage encryption methods research.

You are asking for a function $h(m, k)$ such that for fixed $m$, $k \mapsto h(m, k)$ is a permutation, and for fixed $k$, $m \mapsto h(m, k)$ is a permutation.  Obviously $m$, $k$, and the output of $h$ must be in the same space.  Suppose they live in a group $G$ (written additively), e.g. they're bit strings interpreted in $\operatorname{GF}(2^n)$.  For any fixed permutations $\pi$ and $\sigma$, $(m, k) \mapsto \pi(m) + \sigma(k)$ satisfies this.  (It seems likely that this is the only shape $h$ can have, but I haven't ruled others out.)

However, you presumably have some security goals in mind.  For example, you probably want to require that $\pi$ and $\sigma$ be difficult to invert; otherwise, a known-plaintext attack would lead to key recovery from the ciphertext $c = h(m, k)$ by $(m, c) \mapsto \sigma^{-1}(c - \pi(m))$.  One option would be $x \mapsto (g^x - 1) \bmod p$ where $p$ is a large prime and $g$ is a generator of $(\mathbb Z/p\mathbb Z)^\times$; this is a permutation of $\{0, 1, 2, \dots, p - 2\}$, inverting which is tantamount to computing discrete logs.  (One could also use $x \mapsto x^3 \bmod pq$ for large secret primes $p$ and $q$, if one wanted a permutation with a back door.)

It might help to know what you wanted to use this for!


Can I hash a secret key and used the hash as key ID? I am using AES-CBC to provide confidentiality for protocol messages. I want to allow the receiver to know the secret key by using a key ID. For this I hash the secret key to generate a key ID. Every time the sender wants to send a message, the sender appends the key ID to the message to allow the receiver to bind the key ID with a secret key.

Is hashing the secret key to generate a key ID a secure mechanism?

I would do it a little differently so there is less of a relationship between the ID and the key

Encrypt a block of all 0s with the key; $X$ = $E_k(0_{128})$

Hash X; $H$ = SHA256$(X)$

Truncate the hash to 32 bits (8 hex characters)

Encrypting a block of 0s and truncating is generally how a key check value is generated, as block ciphers are designed to resist key recovery, the intermediate hash step is there for extra security, so you are not exposing a known ciphertext value.

I would not consider a direct key hash safe, some software may use that internally, and you do not want that exposed


How to forge a Shamir secret share? On this website, we have a lot of questions and answers devoted to Shamir secret sharing. We make it clear that Shamir secret sharing does not guarantee integrity. When we want integrity, we need to use a verifiable threshold scheme. But it is never explained how a malicious secret is actually forged.

Consider an easy setup of the scheme with 2 shares and threshold $k = 2$. Assume the adversary knows the secret message $m$ and share 1 (but not share 2). The shares are evaluated at $x_1 = 1, x_2 = 2$.

How does the adversary forge a chosen secret $m'$?

For us to make it exciting, let's first define the meaning of two sample messages:

$m : $ "yes, in case of m.a.d., do fire the missiles"
$m' : $ "no, do not fire missiles"

Let's guess that the current president has chosen $m$ as the message, and we the adversary (and holder of share 1) want to change it to $m'$.

Recall that the polynomial is of the following form:

$$p(x) = a_1x + m$$

We know share 1. In other words we know a value $y_1$ such that :

$$y_1 = a_1 + m $$

So now we have two values. This is enough to get the original polynomial back. We now know the original polynomial, and can reconstruct the second share:

$$
\begin{align}
p(x) &= (y_1 - m) \cdot x + m \\
y_2 = p(2) &= (y_1 - m) \cdot 2 + m
\end{align}
$$

During the recombination phase of the algorithm, the secret $m$ will be constructed by computing $2y_1 - y_2 = m$. We can rewrite this equation and compute a new forged $y_1'$:

$$
y_1' =
\frac{m' + y_2}{2} =
\frac{m' + (y_1 - m) \cdot 2 + m}{2}
$$
Which simplifies to:
$$
y_1' = y_1 + \frac{m' - m}{2}
$$

Now we have constructed a new share which will, together with the second share, combine to the new secret message $m'$.

We see that in your (my?) case we could indeed choose any new message $m'$.


Meaning of epsilon in proving a PRG is predictable/ un predictable I am quite confused, I have been following a course on crypto provided by Dan Boneh, this is the lecture I am confused with - https://www.youtube.com/watch?v=EjWap3szsPk time stamp 8:58 - 11:00

I don't understand the meaning of epsilon in this situation, I know epsilon is a symbol in math that is used for a positive number approaching 0.

What does he mean by the PRG is predictable if the probability is greater than 1/2 + epsilon for some non negligible epsilon?

if someone could explain this in a little more dept and in more laymans terms if possible would be greatly appreciated.

transcript - we say that G:K -> {0,1}^n is predictable if

∃ "eff" algorithm A and ∃ 1 < i < n-1 s.t

k <- K pr[ A(G(K) |1,...., i =  G(K) | i+1] > 1/2 + ε for some non negligible ε

we say that G is predictable if there exists a efficient algorithm A and there is some position 1 between 1 and n-1 such that we look at the probability that we generate a random key, if I give this algorithm the prefix of the output (the first i bits of the output) the probability that it's able to predict the next bit of the output is greater than half + epsilon for some non negligible epsilon.

Loosely, ‘negligible’ means small enough to ignore.  A difference in probability of $2^{-128}$ is likely small enough to ignore; a difference in probability $2^{-10}$ may not be.

Formally, in the language of complexity theory, a function $f\colon \mathbb N \to \mathbb R$ which assigns to each natural number $n$ a real number $f(n)$ is negligible if it goes to zero faster than the inverse of any polynomial—that is, if for any polynomial $p$, there exists a number $n_0$ such that for any $n > n_0$, $|f(n)| < |1/p(n)|$.

For example, $n \mapsto e^{-n}$ is a negligible function.

  Sketch of proof: Let $p(x) = x^d$; at what point $n_0$ do we have $e^{-n} < 1/n^d$, or $e^d < n^n = e^{n \log n}$, for all $n > n_0$?  We don't need to solve this exactly—it suffices to set $n_0 = d$; as long as $n > n_0 = d$, $n \log n > n > d$, so $n^n = e^{n \log n} > e^d$ and thus $n^{-d} > e^{-n}$, or $e^{-n} < 1/n^d$ as desired.  Finding the corresponding bound $n_0$ for other polynomials left as an exercise for the reader.

In the language of complexity theory, we usually consider ensembles of cryptosystems that scale with a security parameter, and we consider the asymptotics of the growth curves of the user's cost and the adversary's cost as the security parameter scales.

The same is true for algorithms more generally, which is why software engineers will casually talk of quicksort's $O(n^2)$ worst-case time but $O(n \log n)$ average time, because it's a useful proxy for estimating concrete costs—and, unlike a measurement in seconds or joules, it doesn't change if you move from one machine to another, which is helpful for understanding how it will scale if you feed it more and more data even if you use a slightly faster machine.

Of course, we must be careful not to lose sight of the concrete numbers without asymptotics: while it is proven[1] that multiplication can be computed in $O(n \log n)$ bit operations, you'll still get an answer faster in wall clock time using a naive $O(n^2)$ algorithm for any input that is possible to work with in practice.

Similarly, while the Blum–Blum–Shub pseudorandom generator has a polynomial-time reduction theorem relating the difficulty of distinguishing BBS output to the difficulty of factoring the BBS modulus, the concrete security of BBS[2] (paywall-free) is such that it costs $2^{43}$ bit operations to generate a mere 128 KB of data at a ~100-bit security level, using somewhat old estimates for factoring costs.  At 2.5 GHz, that takes a minute of computation.  In contrast, e.g., AES-256 can generate the same amount of data in microseconds at a much higher security level.


Difference between stream cipher and block cipher I read that

  A typical stream cipher encrypts plaintext one byte at a time, although a stream cipher may be designed to operate on one bit at a time or on units larger than a byte at a time.

(Source: Cryptography and Network Security, William Stallings.)

A block cipher encrypts one block at a time. The block may be of size one byte or more or less. That means we can also encrypt a block of one byte by help of a stream cipher as a stream.

So, what exactly is the difference between a stream cipher and a block cipher?

A block cipher is a deterministic and computable function of $k$-bit keys and $n$-bit (plaintext) blocks to $n$-bit (ciphertext) blocks. (More generally, the blocks don't have to be bit-sized, $n$-character-blocks would fit here, too). This means, when you encrypt the same plaintext block with the same key, you'll get the same result. (We normally also want that the function is invertible, i.e. that given the key and the ciphertext block we can compute the plaintext.)

To actually encrypt or decrypt a message (of any size), you don't use the block cipher directly, but put it into a mode of operation. The simplest such mode would be electronic code book mode (ECB), which simply cuts the message in blocks, applies the cipher to each block and outputs the resulting blocks. (This is generally not a secure mode, though.)

Some early encryption schemes like the one used by Caesar could be categorized as a "block cipher with 1-character blocks in ECB-mode". Or generally, everything that has a code book.

We usually use other modes of operation, which include an initialization vector and some kind of feedback, so that every block of every message is encrypted a different way.

A stream cipher is a function which directly maps $k$-bit keys and arbitrary length plaintexts to (same arbitrary length) ciphertext, in such a way that prefixes of the plaintext map to prefixes of the ciphertext, i.e. we can compute the starting part of the ciphertext before the trailing part of the plaintext is known.
(Often the message sizes might be limited to multiples of some "block size", too, but usually with smaller blocks like whole bytes or such.)

If a part of the plaintext repeats, the corresponding ciphertext usually is not the same – different parts of the message will be encrypted in different ways.

Often such stream ciphers work by producing a keystream from the actual key (and maybe an initialization vector) and then simply XOR-ing it with the message – these are called synchronous stream ciphers.  Other stream ciphers might vary the encryption of future parts of the message depending on previous parts.

Some block cipher modes of operation actually create a synchronous stream cipher, like CTR and OFB mode.

You should never reuse a key (and IV, if applicable) of a synchronous stream cipher (which includes block ciphers in streaming modes) for different messages, since this can lead to compromises. (And even for the same message it will show that you repeated a message.)

Note that in actual usage you will also want a MAC, e.g. integrity protection, for your message. (Some schemes are broken in case of a chosen-ciphertext attack, for example, and such a MAC will prevent this (if you only pass the message to the decryptor after checking the MAC).)


Multiple keys for the same ciphertext Say you have a plain text:

  How are you today?

and you encrypt it so it becomes:

  LKD03Loel03skj1Q03

Now you have multiple people that need to know the plain text of this cipher text but you do not want them to have the same key. It might be they each come up with their own password or they all have a key which identifies that individual.

Now one way of doing this would be adapting this answer so every user encrypts the one key with their own key so you'd get ten encrypted files (for ten people) of the same key. (I don't know if this is good practice but I think it's a secure option.)

Are there any other ways of having different people using different keys to get the same plain text from the same cipher text (and vice versa)? Is there a special algorithm for this?

In short: hybrid encryption.

Encrypt the content with a random symmetric key. And encrypt this key with the public key of each recipient.

Then all you need is a public key from all the people you want to share the content with. It doesn't even have to be the same public key cryptosystem for all the receivers.

  It might be they each come up with their own password or ...

Passwords alone are quite useless, and if you just use a password as key in a crytposystem, you screwed up badly. From a practical point of view, the concepts of a key and a password might be quite similar, from a security perspective they are not.

Of course you can design a system, where the users actually have to enter a password to decrypt their locally stored private key, like it is done for ssh keyfiles. But that is another issue.


How does the challenger choose the message randomly in the one-wayness security game of PKE? I have read some papers that give the definition of one-wayness of PKE schemes.

Let $\Pi = (G,E,D)$ be a PKE scheme, and the security game of OW-CPA is defined as follow:

$$\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(k) = \Pr\left[ m = m' \left\vert
\begin{gathered}
(pk,sk) \gets G(1^k) \\
m \gets \mathcal{M}_{k} \\
c \gets E_{pk}(m) \\
m' \gets \mathcal{A}(pk,c) \\
\end{gathered}\right.\right]$$

We say $\Pi$ is secure in the sense of OW-CPA if $\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(\cdot)$ is nelgibile.

My question is that how does the challenger choose $m$ over $\mathcal{M}_{k}$ randomly? Is $m$ an element picked uniformly from $M_{k}$?

If $\mathcal{M}_{k} = \mathcal{M} = \{0,1\}^*$, $m$ cannot be picked uniformly from $M_{k}$.

If $|\mathcal{M}_{k}| = \mathrm{poly}(k)$, then $\Pi$ cannot be secure in the sense of OW-CPA if $\mathcal{D}_{k}$ is uniform.

Let $F$ be the sample circuit, then
$$\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(k) = \Pr\left[ m = m' \left\vert
\begin{gathered}
(pk,sk) \gets G(1^k) \\
m \gets F(\mathcal{M}_{k}) \\
c \gets E_{pk}(m) \\
m' \gets \mathcal{A}(pk,c) \\
\end{gathered}\right.\right]$$

Assume that the distribution of message is $\mathcal{D}_{k}$, thus $m$ follows $\mathcal{D}_{k}$. We cannot define that $\Pi$ is OW-CPA secure if for every distribution $\mathcal{D}_{k}$, $\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(\cdot)$ is negligible, because it is not OW-CPA secure if $\mathcal{D}_{k}$ is a one-point distribution.

Perhaps, we may define the PKE scheme as $\Pi = (G,E,D,F)$ where the sample circuit $F$ is given at first. But the notion of IND-CPA or SS-CPA does not need $F$.

[FO99] Secure Integration of Asymmetric and Symmetric Encryption Schemes

[BF03] Identity-Based Encryption from the WeilPairing

[GH05] Security Notions for Identity Based Encryption

Generally in cryptography papers, if a distribution is not specified, either it's uniform, or the results are essentially determined by characteristics of the distribution like its min-entropy.*

In the Fujisaki–Okamoto paper, $\mathtt{MSPC}_k$ (corresponding to $\mathcal M_k$) could be taken to be a set of cardinality $2^{\operatorname{poly}(k)}$ sampled uniformly at random, or it could be a more generally distribution itself with min-entropy $H_\infty = \operatorname{poly}(k)$.  It's not clear from the paper but the results hold either way.
In the Galindo–Hasuo paper, the notation is explicitly defined as such in §2.

Obviously the upper bound on advantage is at least $2^{-H_\infty}$, or $1/\!\left|\mathcal M_k\right|$ in the uniform case.

It is true that OW-CPA (or ‘OW-Passive’ as some authors call it, because there's no oracle involved) does not imply IND-CPA—for example, the RSA trapdoor permutation $x \mapsto x^3 \bmod n$ has OW-CPA security but not IND-CPA security.  This is why, e.g., RSAES-OAEP exists: to shoehorn a message $m$ from some nonuniform distribution into a nearly uniform random ‘message representative’ $x$.

(A simpler generic approach, of course, is to choose $x$ uniformly at random and then use $H(x)$ as a secret key for a symmetric authenticated cipher, as RSA-KEM does, and as is the modern paradigm for new cryptosystems like the NIST PQC submissions; this is what the Fujisaki–Okamoto paper is about.)

* This is a rule for readers, not for authors.  Authors: Please say ‘uniform’ if that's what you mean!


How can an encryption scheme be indistinguishable with multiple messages but vulnerable to an adaptive chosen-plaintext attack? In order to be indistinguishable with respect to multiple messages, wouldn't the scheme need to be nondeterministic? How would this then possibly be vulnerable to an adaptive CPA?

If you're asking about block ciphers. Yes, it's possible.  Security against non-adaptive attacks does not imply security against adaptive attacks.  A simple example of a block cipher that is secure against non-adaptive attacks but insecure against adaptive attacks would be a random involution.  No, it doesn't need to be nondeterministic.

We say that a function $f:X\to X$ is an involution if $f$ is bijective and $f(f(x)) = x$ for all $x \in X$.  Suppose we have a block cipher $E:K \times X \to X$ where $E_k(\cdot)$ is an involution for all $k$.  Then $E$ is not secure against adaptive chosen-plaintext attack: an attacker can request the encryption of $x$, then request the encryption of that ciphertext, and check whether the result is equal to $x$.  However $E$ can be secure against non-adaptive chosen-plaintext attack.

An example construction of such a block cipher would be

$$E_k(x) = \text{AES-Decrypt}_k(\text{AES-Encrypt}_k(x) \oplus 1).$$

This is secure against non-adaptive chosen-plaintext attack (assuming that AES is secure) but insecure against adaptive chosen-plaintext attack.

If you're asking about encryption schemes. Yes, it's possible.  Security against non-adaptive attacks does not imply security against adaptive attacks.  It's easy to construct counterexamples.

For instance, consider the following encryption scheme.  To encrypt a message $m$ under key $k=(k_1,k_2)$, we first check whether $m=k_1$.  If $m \ne k_1$, then we pick $r$ randomly (subject to the constraint that $r\ne 0$) and output the ciphertext $c=(r,\text{AES}_{k_2}(r)\oplus m, k_1)$.  Otherwise, we output the ciphertext $c=(0,m,k_1)$.

This is a crazy-looking encryption scheme, but it is possible to show that it is secure against non-adaptive attacks: basically, it is just counter-mode encryption of a single-block message (since the attacker has no hope of guessing $k_1$).  However, this is completely insecure against adaptive attacks: an attacker who observes one ciphertext can learn $k_1$, from whence they can pose a chosen-plaintext message that lets them build a distinguishing attack.


Reusing PGP key when generating SSL Certificate Authority? Does it make sense to reuse some of the keys from my PGP (GnuPG, GPG) key block when generating my own SSL Certificate Authority (a toy one for myself and a few web services of mine)?
In an ideal world people would have one key pair in a trustworthy hardware device, and they could use it to certify everything, e.g. their own SSL Certificate Authority (as opposed to generating an RSA key with Openssl as it is advised in every online tutorial).
Is it possible?
Are there any benefits to it?
(I know about Monkeysphere, but that's a somewhat different story.)

No, in general re-using keys is not advisable. Even if you would have a secure token then it would be better to have multiple keys stored in it.

In general the level of security required for certificate authorities is higher than the security required for personal use of a key. If you later want to your CA key within a smart card or HSM then it should also be able to perform your PGP operations. This is not that likely.

You will have the same issue if you want to revoke your CA or private key; keeping a key operational after revoking it for one particular use is not good practice. So a revocation of the key for one use should (and hopefully would) imply revoking it for the other use as well. One good reason of revocation would be to use a key of a larger size for one of the two protocols.

Then there is the problem that some protocols may interact with other protocols, as CodesInChaos already stipulated. It may also be that some protocols are less safe than others. For instance, decryption with an RSA private key is generally considered less secure than performing a signature generation (in general, an attacker has more influence on the ciphertext). So it is common practice to separate encryption and signing keys - see e.g. the key usage attributes in X5.09v3 certificates.

Maybe you could deploy the same access mechanism for the keys though.

Almost forgot: yes, it is possible. RSA keys are generally the same for most protocols - it could be that it is not advisable to have a very short public exponent (say, the value 2 or 3) for some protocols, but that's about it.


Why would Carter-Wegman-style message authentication not be broken by P = NP? Researching about the implications of P = NP to cryptography I found someone say that the only cryptography left standing would be the one time pad and Carter-Wegman-Style message authentication. While the one time pad seems obvious, I am not sure about Carter-Wegman-Style message auth. Can anyone explain this?

While the one time pad seems obvious, I am not sure about Carter-Wegman-Style message auth.

What they are talking about is a Carter-Wegman authentication method that uses a stream of random bits as a part of the process (just like a one time pad uses a stream of random bits to encrypt).

Normally, when we implement CW, we use some almost universal (au) hash function, and pair it up with some cryptographical object.  The au hash function processes the message being MACed; and then use the cryptographical object to disguise the au hash output.

How this works: using the au hash implies that someone who doesn't know the au hash key cannot generate two messages that have a nontrivial probability of hashing to the same value (and there are a number of constructions where this is provable).  However, someone who sees the au hash output can deduce rather a lot; hence we disguise the intermediate au hash to generate the full hash with the cryptographical object.

In a one-time-pad setting, one of the things we could do is replace the cryptographical object with "xor the au-hash with the next set of pad bits"; this also effectively disguises the hash output, and so satisfies the criteria (and an oracle that can do NP cannot recover the au-hash, because (just like the one-time pad), there's not enough information to do so).  Note: actually, in this construction, you'd need a delta almost universal hash function; if you care about those details, ask in a separate question.

On the other hand, those two wouldn't be quite the only things that would be left in the cryptography toolbox.  In addition, we have:

Secret Sharing (where if someone has fewer than the requisite number of shares, they literally don't have enough information to reconstruct the secret)
Some key distribution schemes (where someone issues key shares to parties, two parties can generate the same key, and no one else with fewer than k key shares (where k is a security parameter) have enough information to reconstruct their secret.


Multiple AES/ECB encryptions of different data with same key all end with same pattern We have used "AES/ECB/PKCS5Padding" with a 256 bit key. We encrypt different streams of data (blockwise) with the same key. Each encrypted stream ends with same pattern.  What is the reason for this?

ECB is possibly the wrong choice for your application, you more likely want CBC or some other mode.  See https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_Codebook_.28ECB.29 in particular the picture of the Tux penguin for an example of why ECB does not work with duplicated data.

So now the question is why you would have duplicated data at the end of your output.  This is because of the way the padding is working.  You said you were using PKCS5Padding and it, by design, always adds a full extra AES block at the end of the of input.  (You can see https://en.wikipedia.org/wiki/Padding_%28cryptography%29 but that doesn't appear to cover PKCS #5, but maybe this is useful What is the difference between PKCS#5 padding and PKCS#7 padding )

It appears you are working in Java, and so I coded up a quick little bit of Java test code, to demonstrate what is happening:

encryptData(secret, cipher, "A123456789012345678901234567890", "First Example");
encryptData(secret, cipher, "B123456789012345678901234567890", "Second Example");
encryptData(secret, cipher, "C123456789012345678901234567890", "Third Example");

Which produces this output:

First Example(32 bytes)
0000: CE F9 BF 06 1B 70 5F E5 C2 E7 2D 49 E3 BE A1 EC
0010: D6 E7 45 DE 6B 05 F5 FB 95 87 FC DD EE 57 40 FC
Second Example(32 bytes)
0000: 5F 5F 8E EE D8 FC F9 55 AD EA 5F 76 D8 5D FD C1
0010: D6 E7 45 DE 6B 05 F5 FB 95 87 FC DD EE 57 40 FC
Third Example(32 bytes)
0000: 26 27 23 96 82 39 3D D0 9C DF 51 83 0F A7 20 F6
0010: D6 E7 45 DE 6B 05 F5 FB 95 87 FC DD EE 57 40 FC

As you can see, all three different inputs produce the same output for the last block of:

0010: D6 E7 45 DE 6B 05 F5 FB 95 87 FC DD EE 57 40 FC

When I re-run the code, making the changes necessary for CBC mode (with a preset IV instead of a random one), the output changes to this:

First Example(32 bytes)
0000: 77 F7 51 60 59 F4 54 3C 31 9B F4 C6 72 1C C8 63
0010: C0 D9 32 35 49 93 A7 BA B1 6D 65 EC 66 7D 3C 98
Second Example(32 bytes)
0000: FE B8 B2 1F B9 56 73 AF 61 B3 50 9E DC 69 F3 C6
0010: 1F 5C F0 40 FD 1D 30 D0 CA 5C 0F 06 1B 2E 89 67
Third Example(32 bytes)
0000: 6E 85 6A 02 CA 0B E4 33 E3 29 47 D9 B5 C0 86 01
0010: AE A0 AA 22 1F 12 E5 6A 10 31 9D 0F 99 8F 9A 6E

Here you can plainly see the blocks are all very different.

I have posted the code examples for each case into a pastebin.  They rely on some library code to dump the bytes to hex, but I don't think you need that code for your own work, so I didn't worry about including it, and it would be easy to replace.

 ECB: https://pastebin.com/FSbJ5AfE
 CBC: https://pastebin.com/PP8c44J4


How to exchange authentication keys I am trying to create a secure Bluetooth Low Energy connection. The peripheral server (the main device other people would connect to) would need to service many clients (users) and due to hardware limitations, I would not be able to let the hardware manage security (essentially, it has a limit of 4 keys, i.e., 4 users).

I have researched and have decided on the following general scheme.

Use AES128 for encryption.  The key is held in the server and client, assuming that is done securely.

To do this, the device can generate a random "password" and make it visually appear to the user, which has to enter it on his client device (smartphone). The smartphone, which has generated the AES key would use the password to encrypt the key and send it to the device for storage.

Use SHA-256 with a cryptographic key to authenticate messages. I know that this should be done after the encryption.
Upon connection, generate an authentication key and send it to the other one.

I thought about this (not using a static authentication key), so that an attacker cannot record the messages of a session and replay that later. I guess this must be a well-known problem.
Question 1: How can the key be reliably sent from one to the other?
Question 2: Who should be the one generating this authentication key? The server device? Or the smartphone?

To know which encryption key to use, the userid could be sent in plaintext.

Question 3: Is it possible not to send userid in plaintext and still be able to understand which key to use for the communication? Does it matter?

On each message passing, derive a new authentication key from the previous one.

I thought about this, so that if an attacker hijacks a session, previously sent cyphered messages in this session would look invalid.
Question 4: What algorithm could be used to derive a new key from the old one, ensuring that the result is also a "good" key (high entropy and such)?

Use an IV to make sure the same message (a command to the server device) encrypts to different messages every time.

Question 5: Should this also change on every command similar to the authentication key?

Regarding Question 1, during the authentication key exchange, HMAC doesn't seem to be possible, so I was thinking of sending the generated key only encrypted. The other end of the communication can recover the authentication key by decrypting the message. Question 6: could an attacker be able to recover the key by pretending to be on the key-receiving end of the communication? How about if it is pretending to be on the key-sending end?

Regarding Question 2, I am inclined towards having the smartphone generate a key, as it probably has better access to cryptographic libraries (as opposed to the device, which runs on a microcontroller).

Regarding Question 3, I cannot see a problem with an attacker knowing which userid the communication is established with. A system with multiple users with visible ids is, I think, as secure as a system with a single user. Then again, I'm not a security expert.

Regarding Question 4 and 5, I am guessing a pseudo-random number generator seeded with the authentication key/IV should do.

First, some notes on your choices of primitives:

AES-256: You don't need to use AES-256 unless the data you want to protect needs to remain confidential for more than 30 years
SHA-256 for authentication. Don't use plain SHA-256. Either use HMAC-SHA-256 using an encrypt-then-authenticate approach or (even better!) use AES-GCM or AES-EAX as your mode of choice as the two provide authenticated encryption (AE) and the likelihood of errors is much less.

Now to answer your questions:

If you store a key on both devices long-term-wise I think your questio means "How to securely transmit / negotiate a session key for authentication and encryption?". Well you could use ECDH to let both devices negotiate a key, but I assume this isn't possible in your case. In this case you simply generate a key at random, encrypt it using the long-term key and send it to the device, preferably using an AE mode, as you only have to manage one key then.
Who should generate a key? The one with access to the better randomness sources, usually this is the more powerful platform having more user interaction. (in your case the smartphone I think)
The answer on this depends on your situation. If the user-id is just some random number and if you're not too concerned with privacy of your users, you can send it in plain. If the user-id actually holds information (like a name) you could the connecting device send a nonce $N$ along with $Tag=H(N||ID||N)$. Then the device could try out all (4!) IDs and look for the match. This wouldn't expose the user-ids at any point in time in plain. If the user-id is low entropy and you want to protect it very hard, usage of a password hashing scheme (PHS, as function $H$ instead of SHA-256) may be an option to put more work effort to find the ID.
What you describe here is similar to the famous OTR protocol. To
perform the operation you need you'd simply use a key-based key derivation function (KBKDF/KDF) like HKDF. But be aware, as soon as the devices get out of sync (i.e. a message is lost), you'd need to renegotiate a new session. And note: using this approach doesn't provide forward-authenticity. Meaning if an old key get's stolen, all subsequent keys of the communication can be derived. In my eyes it's sufficient to use AES-GCM for the whole session and don't change with every message, as this means unneccessary performance overhead. You could simply renegotiate the connection every now and then to get a similar property.
Yes. Usually IVs are meant to be message-specific. This would result in you sending a new IV with every message. To avoid replay attacks you may also want to consider using message numbers.
If you do the setup as described at the beginning (using the password copied from the device to the phone) and you do already use authentication at this point, you're safe, assumed that the transmitted password wasn't intercepted, because an attacker can't fake the authentication tag. (excluding faking of the sender) He can't get the key on the receiving end, because this would mean he can decrypt the key, encrypted using the password which is impossible for any good password (random, 20 chars, lowercase, uppercase(, numbers))

I hope this answers your questions.


If a cryptanalytic breakthrough is made, what process should be followed? If a researcher manages to make a cryptanalytic breakthrough on a cryptographic algorithm or protocol that is in use, what should they do?

Has this ever happened before? What are the implications for release and how do those relying on such systems ensure they are not caught in a situation where the crypto-system on which they depend is trivially broken?

Specifically:

What details would you make available online?
Who would you release full details to?
How are affected parties notified?

Well, first off, the question doesn't arise that often in practice.  People do find cryptographical weaknesses; however, generally they are purely of theoretical interest, or if they could be used in a real attack, it may take quite a while before someone figures out how to use it.  As an example of the second case, Ms. Wang announced an efficient way to create MD5 collisions; this is a severe break of the MD5 security properties, but it took people quite a while to figure out how to translate that into being able to obtain a bogus certificate (by asking for an innocuous one from a CA).

On the other hand, it does happen on occasion; one example that springs to mind is WEP and the key recovery attack.

Now, in my opinion, the ethical thing to try to do is to get people to stop using the broken protocol, and switch to something which doesn't have known weaknesses.  However, in practice, that appears to be difficult.  Once they have a system in place, quite a lot of people are loathe to update it.  In addition, when cryptographical hardware is involved, sometimes the fix involves hardware modification, and so updating things would involve real money (rather than just a software update).  One example of someone ignoring an announced attack would be the TJX credit card breach; this attack was done using the WEP key recovery attack that was announced 5+ years earlier.

So, what should we do?  Well, I don't see any good options.  Not publishing the result doesn't appear to work (we leave the weaknesses in place for the blackhats to find and exploit).  Publishing the result does mean that some will update, but others won't bother.  Publishing the fact that we have a result will generally mean that you won't be taken seriously (unless you're already a cryptographical Big Name), and the blackhats will be alerted that there is a weakness.

My personal feeling is that publishing the result is the "least worse".

[Hmmmm, we're supposed to avoid statements based on opinions; for a question about ethics like this, I don't see how I can avoid it]


How should I incrementally sign a large set of documents? Say I have a large set (i.e. unordered collection of unique elements) of documents, each of which is around 4KB in size.  I'd like to sign that set with a private key so that anyone can verify the signature with the corresponding public key.

Additionally, I'd like to be able to modify the set by adding or removing elements and generate a new signature incrementally (in the sense of Bellare, et al.) which may be verified incrementally.  This new signature should be the same as if I had signed the modified set from scratch instead of incrementally.

My first thought was to use a Merkle tree, but such a tree would need to be transmitted, stored, and updated along with the set itself, which is undesirable.  Edit: The overhead of this scheme isn't as severe as I thought, since the signer need not explicitly transmit the Merkle tree and its updates to the verifier(s).  Instead, they just need to agree about how to build and update the tree independently, and in a way that the (amortized) costs of incremental updates are low.

Later, I learned about incremental multiset hash functions and came up with the following scheme:

Compute the SHA256 hashes of each document in the set and combine the hashes using integer multiplication modulo a large prime q.  Call the result H.
Sign H with the private key.
Modify the original set by adding or removing an element, and calculate the new hash H' as H times the SHA256 of the added element (or the inverse of the SHA256 of the removed element) modulo q.
Sign H' with the private key.

Verification proceeds likewise, except that H and H' are verified with the public key in steps 2 and 4, respectively.

Is this scheme secure?  How large would q need to be?

Is there a better option available?

a new signature incrementally (in the sense of Bellare, et al.) which may be verified incrementally

IMHO this seems to be related to long content, where for a (relatively) small update, the "re-reading" the whole content may be not practical. If you have a large set of smaller documents (4kB) I see no reason why you should treat them as one large content.

I don't know if it will help you, but this is what I've see in one big publishing organization, where they need to ensure integrity of the published (legal) content.

a hash is computed for each content
there a list of published documents and a composite hash of the hashes of each document (sorted list)
the composite hash is signed

using a HSM it requires user intervention (manual PIN entry) to sign anything, so they sign only the whole list ensuring integrity on level of the whole list of documents. In this case the list is more or less static (it doesn't change)

  Sign H' with the private key.

effectively that's what the publishing organization is doing - just skipping steps 2 and 3. If a new content is added / removed / updated, just content of the small document is to be hashed and the list of document hashes is updated (and signed) yes, you will need to maintain a sorted list of the documents


Format of EC SubjectPublicKeyInfo I am unable to account for an extra 0x00 byte in an EC SubjectPublicKeyInfo structure.

> openssl asn1parse -i -in ecpub.pem -dump
0:d=0  hl=2 l=  89 cons: SEQUENCE
2:d=1  hl=2 l=  19 cons:  SEQUENCE
4:d=2  hl=2 l=   7 prim:   OBJECT            :id-ecPublicKey
13:d=2  hl=2 l=   8 prim:   OBJECT            :prime256v1
23:d=1  hl=2 l=  66 prim:  BIT STRING
  0000 - 00 04 d0 ee 64 61 7b 90-48 a2 a9 5f b5 a3 da 67   ....da{.H.._...g
  0010 - 53 56 91 e0 cf 5b b8 85-3e 05 0c b9 e6 95 c3 8d   SV...[..>.......
  0020 - 26 ab d7 ee 47 94 38 61-1e cd 07 e6 90 0b 3d 4a   &...G.8a......=J
  0030 - 6a df c5 d5 9f f3 11 91-53 00 ff 0e 91 93 49 44   j.......S.....ID
  0040 - 4c 58                                             LX

In the BIT STRING representing the public key in octet form, what is the 0x00 byte that precedes the 0x04 byte (which I was expecting to be the first byte)? Without the mysterious 0x00 byte, the public key comes out to 65 bytes and the entire structure lines up with the SEC1 specification.

The BIT STRING value starts with a single byte that indicates the number of bits that are not used. Bit strings may be of any size and they may therefore not be a multiple of 8. So they start with the number of bits that should be skipped at the end. In your case, it tells the user that all bits of the last byte 58 (01011000 in bits) are part of the value.

Most of the time the BIT STRING encodes a byte array anyway, so it will generally be set to 00 instead of one of the other 7 possibilities.

The first bit is the leftmost bit, and the final bit is the rightmost bit. But that's only of importance if the order of bits is of consequence. In this case the BIT STRING contains the uncompressed EC point $W$ so it is not important.

You can find this, and more in the Layman's guide to ASN.1 by  Burton S. Kaliski Jr. section 5.4 "BIT STRING", and of course the standard documents ITU-T X.680 and X.690 (both payware, so I won't link).


(Re) How to validate AES decryption was successful? I'm developing a local file encryption/decryption software (AES-256 CBC),
which I want to validate decryption was successful or not.

so I decided to add an additional MD5 hash of plain data to end of plain data and encrypt it together,
and when decryption, calculate the MD5 hash of decryption data(except last additional MD5 hash) and
compare it with last additional MD5 hash.

I want to know if this idea is safe to use.

Is it a bad idea?

What you are trying to do is called Authenticated Encryption, the combination of encryption and authentication in on scheme.

The simplest form of it is doing encryption and authentication seperately either by authenticating the plain text (Mac-Then-Encrypt or Mac-And-Encrypt) or doing it the other way round: Encrypting first and then calculating the checksum over the ciphertext. None of the three variants are inherently insecure, but the latter version is considered the most secure these days and it is also the easiest one to get right.

What has to be noted is, that you should not just calculate a hash as you suggested but a MAC instead (like HMAC-SHA256), which can not be forged by an adversary. A hash alone only protects the integrity of the message helping you against errors but not against attackers.

Apart from these, there are also encryption modes which combine the encryption and authentication in one operation. If you do not have a particular reason for sticking with AES-CBC, these modes would be preferred.
The most popular of these modes would be AES-GCM, other options include AES-CCM, AES-OCB or ChaCha20-Poly1305..


Implement Google Adiantum else where? Google made the headlines with its new Adiantum encryption method, and i read (TechCrunch) that:

  In the meantime don’t expect any instant gains, but future low-power
  devices may offer better security without having to use more expensive
  components — you won’t have to do a thing, either.

So mobile phone which does not have any hardware dedicated to crypto will still be able to encryption as perhaps an equal speed.

My question: can we use this technology in some other places which does not have such hardware? does it makes sense? (e.g in a web browser, having an implementation in WASM of Adiantum).

Keep in mind that Adiantum was designed for one particular use case: block-based disk encryption.

In other contexts, especially in a web browser context, storing an IV and an authentication tag along with the ciphertext is not a problem. So you can stick to traditional AEADs, that will be faster than Adiantum in addition to being easier to use securely.


Is it possible for Alice and Bob to both sign a message "simultaneously"? Let's say that there is a message which is considered valid if signed by both Alice and Bob.

Alice could sign the message and then give it to Bob, so that he can sign it and give it back to her.

But, for various reasons, Alice doesn't want Bob to have a fully-signed message that she doesn't also have. If she just signs it and sends it, he could sign it and not send it back.

Is there some way that both of them can sign the message (maybe interactively?) so that it doesn't become valid for Bob if it isn't also valid for Alice?

(This could be done by a trusted third party who would simply escrow the message until it had received both signatures, and then release both signatures to Alice and Bob. Of course, I want a solution without a third party.)

This is one of the earliest questions that was asked in modern cryptography. There is a proof that you cannot achieve completely fair contract signing. However, there are some reasonable alternatives. There is one direction called "gradual release" which I personally do not like. A model that I think has a lot of promise is called the "optimistic model". In this model, there is a trusted third server that is only invoked in case one of the parties cheats and may obtain a signature without the other. This model is very nice in the sense that once the server exists, there is no motivation to cheat since anyway an adversary knows that it cannot gain anything. I note that the server is trusted to answer when a party asks for its "help", but does not learn anything. This model was introduced by Silvio Micali in Fair Electronic Exchange with Invisible Trusted Parties. You can read more about this model in Optimistic Fair Secure Computation by Cachin and Camenisch, and Analysis of a Fair Exchange Protocol by Shmatikov and Mitchell.

Another direction which I really like is called Concurrent Signatures. In this model, one party gets the signature first. However, if the other party sees the signature then it can use that to complete its own signature. So, it's actually not fair (one has the signature first) but if the first ever wants to enforce anything with its signature then it would have to show it to the second, in which case the second can complete the signature it is supposed to receive. In most practical cases that I can think of this is sufficient, and it elegantly bypasses the impossibility results that exist. This model has the advantage that you don't need a (minimally) trusted third party (which is problematic in practice).

Finally, I'll point to the recent use of Bitcoin to ensure fairness. The paper How to Use Bitcoin to Design Fair Protocols shows how to do this (albeit theoretically). The idea here is very very nice.


How to determine r' in pederson commitment? Can someone help me with that question? Assuming that someone knows $log_g(h)$ so that he can calculate any message $m'$ for commitment $c$, how to determine $r'$ in?

Assuming that someone knows $log_g(h)$ so that he can calculate any message $m'$ for commitment $c$, how to determine $r'$ in?

First, we assume that he already knows the 'true' value of the commitment $c = g^m h^r$ (as this is the prover who is cheating).  Then, assuming he knows the value $x$ s.t. $g^x = h$, then he sets $r' = r + x^{-1}(m - m')$; then, the pair $m', r'$ is a valid opening of the commitment, as $g^{m'}h^{r'} = g^m g^{m'-m}h^{r + x^{-1}(m - m')} = g^m g^{m'-m}h^r g^{(m'-m)} = g^m h^r = c$


What's the purpose of key-rotation? What's the purpose of key-rotation?

Does it have any effect on the probability of keys being breached in the first place? Does it refer to avoiding access after a breach to all past data, all future data, both or none?

As @SEJPM notes, the primary purpose of rotating encryption keys is not to decrease the probability of a key being broken, but to reduce the amount of content encrypted with that key so that the amount of material leaked by a single key compromise is less.

However, for signing keys there is a concrete reason: say it takes $X$ months of computation (expected value given your threat model) to crack a key, and you rotate your signing key every $X-1$ months and revoke the old one, then by the time an attacker has cracked the key, any new signatures produced by the attacker will either be A) rejected by clients because of key expiry, or B) back-dated to before the key revocation (which should also raise warning in clients).


Using same modulus for RSA I know that there exist some attack when using same modulus.
Can two different pairs of RSA key have the same modulus?
RSA cracking: The same message is sent to two different people problem

But with a little modification,
$m$ is the plain-text
$N$ is the RSA modulus
$r_1, r_2$ is the random padding
$e, s$ is the public exponent
$C_e, C_s$ is the cipher-text

encrypt as follow
$$С_e = (m + r_1)^e   \bmod N$$
$$С_s = (m + r_2)^s   \bmod N$$

If attacker only knows $C_e, C_s, r_1, r_2, e, s, N$.
Is it possible to know $m$?

It seems the RSA cracking: The same message is sent to two different people problem does not work?

Yes, it is possible. Like SEJPM suggested, you can use a variant of the Franklin-Reiter related-message attack to accomplish this. Let $\Delta = r_2 - r_1$. Compute $\gcd(X^{e} - c_e, (X + \Delta)^{s} - c_s)$ over $\mathbb{Z}/n\mathbb{Z}[X]$, which yields the linear polynomial $X - (m + r_1)$. Recovering $m$ is now trivial. This, of course, will only be reasonably efficient for small exponents $e$ and $s$; but it should be quite doable for common exponents below $65537$.


Can you recognize a low private exponent from a public key? In the RSA cryptosystem, Wiener, Boneh and Durfee showed that low private exponents can be efficiently recovered. Is it possible to see from a public key alone whether the private exponent (d) is small? Is the public exponent (e) then necessarily large? Is it possible to have a small private exponent when e=65537?

When generating keys, $d$ and $e$ are each others modular inverse:

$d \times e \equiv 1 \pmod{ \lambda(n)}$
$d \times e = 1 + k \times \lambda (n)$

Unless $d = e = 1$, this means that $d \times e$ is at least $\lambda(n)$, otherwise it would not "wrap around" to become $1$. So $k$ is at least $1$:

$d \times e \ge 1 + \lambda(n)$

This means that at least one of $d$ and $e$ is at least $\sqrt{1 + \lambda(n)}$, otherwise they wouldn't multiple to be greater.

$d \ge \sqrt{\lambda(n)}$, or $e \ge \sqrt{\lambda(n)}$

If we set $e = 65537$, it must be $d$ that is large. It is not possible to have a key with a low private exponent that also has a low public exponent. A key with a low private exponent has to have a public exponent that is at least $\sqrt{\lambda(n)}$.


Where is the authentication tag stored in file encrypted using AES-GCM? So I am using cryptopp to encrypt a file in a project and I am using AES-GCM.
I have a 256bit key and a 128bit ivec and a 128bit tag that I use to encrypt files.

However, I want to know where the authentication tag is stored? I notice if I specify a tag size of 0 then the encrypted file size is the same number of bytes as the original file.

Is the authentication tag simply appended to the end of the file?

The authentication tag is defined as an output parameter in GCM (see section 7, step 7 of NIST SP 800-38D). In all the API's I've encountered it's appended to the ciphertext. Where it is actually placed is up to the protocol designer. The protocol designer may well consider the place behind the ciphertext as ad hoc default though. The name "tag" of course kind of indicates that it should be tagged to the ciphertext and that may well mean direct concatenation.

The tag is often considered part of the ciphertext within an API. This means that the API is less flexible, and that it requires the buffering of the ciphertext (up to the size of the tag value) as the decryption routine otherwise doesn't know where the ciphertext ends and the authentication tag starts. This means in turn that the online property of the counter mode encryption is damaged.

So in generally it is better to treat the authentication tag as separate parameter as API designer, and leave the location of the authentication tag up to the protocol designer. The protocol designer may well choose to prefix the ciphertext with a length component, which would render the buffering unnecessary.

In your case it doesn't help to directly look at the GCM specification, you need the protocol or API specifications. I would suggest to look for it at the end of the ciphertext if the location hasn't been strictly defined. The tag size should be a valid, predefined parameter value.

In RFC 5116: An Interface and Algorithms for Authenticated Encryption the authentication tag is explicitly placed at the end of the ciphertext for GCM mode encryption. This is due to the following requirement in section 2.1:

  There is a single output:

  A ciphertext C, which is at least as long as the plaintext or
  an indication that the requested encryption operation could not be performed.

and further explained by section 5.1:

  The AEAD_AES_128_GCM ciphertext is formed by
     appending the authentication tag provided as an output to the GCM
     encryption operation to the ciphertext that is output by that
     operation.

This RFC is - for instance - used by the TLS specifications. Note that the size of the ciphertext is made explicit in those specifications, which means it should be easy to separate the tag from the actual ciphertext.


What does it mean that a protocol realizes "strong mutual authentication"? What does it mean that a protocol realizes "strong mutual authentication"? And What does it mean that a protocol realizes "weak mutual authentication"? Can you define them formally ?

I have found a definition for "strong mutual authentication" (not formal):

  Strong mutual authentication requires not only matching conversation records: all principals’ records of the content and the order of all messages must coincide, but also matching views of the intent: all principals’ views of the purported sources and the intended destinations of all messages should also coincide.

Strong with regards to cryptographic protocol usually means that the protocol is secure if the underlying primitives can be proved cryptographically strong. In your case, that could be because authentication is performed using a symmetric cipher and a key that is only distributed for 2 participants.

But as indicated in the comments, "strong" depends on context, you won't get any assurances from it by itself.


Is a keyed PRF a MAC? I remember I read that a MAC can be considered as a PRF.

Can a variable-length input keyed-PRF be considered as a MAC?

Usually. $\:$ A variable-length input keyed-PRF is a [PRF's output length]-bit MAC.

In particular, a variable-length input keyed-PRF with long output is automatically a MAC.


Security of key schedule that only XORs a key with constants Suppose that:

$MK \in \{0, 1\}^{n}$ and the main key of a block cipher.
$RK_{r} \in \{0, 1\}^{n}$ and is the $r$th round key.
$RC_{r} \in \{0, 1\}^{n}$ and is the $r$th round constant.
$RK_{r} = MK \oplus RC_{r}$

What's the security of this key schedule. I'm imagining that it is not very strong.

This key schedule is Totally Linear. If two Master Keys $MK$1 and $MK$2 have a difference of d, all the round keys will have difference of d with probability of 1. This makes the cipher vulnerable to Related key Attack. But its hard to workout and comment without the knowledge of the cipher description that how badly such key-schedule effects the security of cipher

The PRINCE – A Low-latency Block Cipher for Pervasive Computing Applications have very simple key-schedule, and its designers say

  for our cipher it holds that decryption for one key corresponds to
  encryption with a related  key.  This  property  we  refer  to  as
  α-reflection

For more information about key-schedule requirements see "What are the requirements of a key schedule?"


PRNG that takes input a $n$-bit string and gives output a $2n$-bit string? Recently, I'm reading one paper of Boneh and Zhandry. They have mentioned a pseudo random number generator that takes input a $n$-bit string and gives a $2n$-bit string as output. They just used it as a generic construction.
I want to learn specific construction of such kind of PRNG. Please refer me any link or please explain me the construction of such PRG.

It can be consctructed in many different ways.

I will just give an example using HMAC-$\mathcal{H}$ where $\mathcal{H}$ is a hash function which returns a $x$-bit hash.

So if you want to use a PRNG which takes $n$-bit inputs and returns $2n$-bit output, you could act this way:

Divide the input into $\frac{x}{2}$-bit blocks $B_i$
For each block $B_i$ computes $B'_i = \text{HMAC-}\mathcal{H}_K(B_i \space || \space i)$ where $K$ is the symmetric key used for the HMAC computation and $||$ denotes concatenation.

In that case, note that the property $n$-bit input returns a $2n$-bit output is confirmed only if $n \mod \frac{x}{2} = 0$, but you can still truncate the result after HMAC computations to get the expected output length.


Basic Public key question I'm studying public key cryptography, but still, there's something that I'm not able to understand. I know that, in order to communicate with the server the client must use the public key of the server, but what happens when the server needs to send a message to the client?

It can't use its private key since anyone would be able to decrypt the message, so my question is:  Does the client have a public key?

... what happens when the server needs to send a message to the client?

The server uses the symmetric key that the client sent to the  server.

  Does the client have a public key?"

Sometimes.


Why does NIST want 112-bit security from 128-bit key size for lightweight cryptography? In NIST's Submission Requirements and Evaluation Criteria for the Lightweight Cryptography Standardization Process document it is stated that:

3.1 AEAD (Authenticated Encryption with Associated Data) Requirements
An AEAD algorithm shall not specify key lengths that are smaller than 128 bits. Cryptanalytic
attacks on the AEAD algorithm shall require at least $\mathbf{2^{112}}$ computations on a classical computer in a single-key setting. If a key size larger than 128 bits is supported, it is recommended that at least one recommended parameter set has a key size of 256 bits, and that its resistance against cryptanalytical attacks is at least $\mathbf{2^{224}}$ computations on a classical computer in a single-key setting (The bolds are mine!)

Why does the NIST require 112-bit security from at least a 128-bit key on AEAD?
From the security perspective, they should require 128-security. Any attack that reduces 128-bit security can lead to more attacks. What is the rationale behind this requirement?

And similarly for the hash functions;

3.2 Hash Function Requirements
Cryptanalytic attacks on the hash function shall require at least $\mathbf{2^{112}}$ computations on a classical computer. The hash function shall not specify output sizes that are smaller than 256 bits. (The bolds are mine!)

From the values, we can hint that they consider the collision resistance. Similar questions;

Why does NIST require 112-bit security from 256-bit hash functions?
What is the rationale behind this requirement?

From the security perspective, they should require 128-security.

Why?
NIST has a requirement for a minimum security strength of 112 bits for all things cryptographic, at least for the present.  You see it everywhere in their documents.  For example, in Transitioning the Use of Cryptographic Algorithms and
Key Lengths it says

For the Federal Government, a security strength of at least 112 bits
is required at this time for applying cryptographic protection (e.g.,
for encrypting or signing data). Note that prior to 2014, a security
strength of at least 80 bits was required for applying these
protections, and the transitions in this document reflect this change
to a required security strength of at least 112 bits.

Apparently, the cryptographers at NIST believe that 112 bits of security is sufficient for now.  128 bits is coming though.

SP 800-57, Part 1 includes a transition to a security strength of 128
bits in 2030; in some cases, the transition would be addressed by an
increase in key sizes.

Do note that this is their minimum requirement for the US Federal government, your requirements may be different.


Using AES for smaller blocks in a Feistel network I was wondering how decryption would work for FPE in the case of cycled Feistel ciphers. I understand that simply reiterating through the networks with reversed key order will generate the ciphertext inputted at the beginning of the network.

The ciphertext is a bit representation of some number, so I'm just expanding the number to search for correct length before stopping.

However, the question that I have is that I am using AES as my round function. However, I need significant padding (0s), as the AES block size is 128 and the block size (of each half) is significantly smaller at 10-30 bits. I am simply appending these 0s to the end of my string, then using AES to get an encrypted 128 bit output.

At this point, I am not too sure what to do. I truncate by removing the last ~100 bits and only taking the beginning of the string. However, this seems to me as if I am losing data, and I cannot understand how I would be able to decrypt using this same method.

Is this simple method of truncating actually the correct way of implementing AES for smaller blocks, or should I be padding/truncating in a different way? Also, if it is correct, could someone explain why it is or link me to some relevant literature?

Cheers!

I have seen the related link Recover plaintext from truncated ciphertext using AES for FPE , but I either don't understand the comments or a solution was never posted.

In a Feistel network you can use ANY function and it will be invertible. Of course, in order to get security you need the function to fulfill some property. One of the main reasons to use a Feistel network is to get a pseudorandom permutation. For this to work, you need 3 or 4 rounds of Feistel with a pseudorandom function (with tweaks or independent keys at each round). Now, truncated AES is a pseudorandom function (and a very efficient one) so this is a good idea. You can pad with zeroes as you said, but you MUST also add the round number into the padding (this is the "tweak"), or alternatively use a different key in each round. The latter option is much less efficient since you need to run the AES key schedule multiple times. The use of the round function essentially guarantees a "computationally independent" pseudorandom function in each round (and so essentially the same as using a different key in each round).

In order to see that it works, just draw it and trace the decryption. The magic of Feistel is that you don't need to invert the round function in order to decrypt.


Using enigma and missing one word/sentence After you set up all rotors, position and plugs in Enigma machine. If you don´t get the signal of one word or one sentence... your enigma settings are desynchronized. How you can recover from this situation? Do you need to wait until next day?

I imagine some radio guy in the middle of the battle and I find very difficult to keep track of every message.

As long as the plaintext has some sort of recognizable structure, it wouldn't be that hard to identify where a letter has been omitted. Here's an example (generated using the default settings of this online Enigma simulator):

Plaintext:  THEQ UICK BROW NFOX JUMP SOVE RTHE LAZY DOG
Ciphertext: OPCI LLAZ FXLQ TDNL GGLE KDIZ OKQK GXIE ZKD

Suppose the 15th letter of the ciphertext (N) is omitted. This would result in the following decryption:

Ciphertext: OPCI LLAZ FXLQ TDLG GLEK DIZO KQKG XIEZ KD
Plaintext:  THEQ UICK BROW NFVH JAOW FSNA TPPT ESUW BM

Clearly there's something wrong after the word BROWN, so let's reset the machine to its initial settings and insert an additional X after this word in the ciphertext:

Ciphertext: OPCI LLAZ FXLQ TXDL GGLE KDIZ OKQK GXIE ZKD
Plaintext:  THEQ UICK BROW NHPX JUMP SOVE RTHE LAZY DOG

This is much better, but now we have the word HPX, which makes no sense. A consecutive run of unlikely characters suggests that we inserted the extra character in the wrong place.

Therefore, the F in the original plaintext was probably correct, and the middle word of the plaintext must be F.X (with the . representing a character that was lost in transmission). There aren't many words that fit this pattern, and it isn't hard to guess which one is correct.

Obviously this method would be harder to use if a message contains clusters of missed and/or incorrect characters. But in that case the wireless operator at the receiving end could just request a retransmission of the message. I don't see why they would have to wait 24 hours.


Question on proof of coin-tossing in "how to simulate it" I am reading Professor Lindell's "How To Simulate It - A Tutorial on the Simulation Proof Technique" paper, which is very enlightening.

I am trying to follow through the proof of the security of Blum's coin-tossing protocol and have some questions: in the end of page 41 it says ": Let $b_1$ be the value committed in the commitment $c$ sent by $A$ (since $A$ is deterministic and this is the first message, this is a fixed value)."

I don't understand why we can assume $A$ is deterministic?
In general, should the security proof work for probabilistic adversaries?

Actually, a probabilistic adversary $A$ can be viewed as a deterministic adversary with a random tape: $A$ just picks a random string in the beginning and then run deterministically according to that fixed string. In the proof, the simulator $S$ uses the real-world adversary $A$ as a black box but can control its random tape (because a random tape always contains fair random strings that can be generated by anyone). So, $S$ can simulate the output of a probabilistic adversary $A$ by first choosing a random string $r$ then dealing with the resulting deterministic adversary $A'=A(r)$.


How exactly would someone attempt to analyse ciphertext produced by popular encryption products such as Truecrypt/PGP? I am interested in understanding what the process would be if an attacker wished to attempt to decrypt data secured by common tools such as OpenPGP, Truecrypt or the like. Are there any documented records of such undertakings, or papers I can read to understand how a cryptanalyst approaches breaking an implementation? What would happen to break such a system? Can such systems be brute forced realistically?

From the perspective of someone who is a non-cryptographer but runs penetration tests against, well, anything really, there is a very simplistic answer that is generally correct in the real world:

Assuming the implementation of the encryption algorithm is not flawed (I know, not always a good assumption, but the common open source tools get a lot of peer review so it is an assumption I use) and a strong algorithm is used with a strong passphrase or shared secret, the reality is that breaking such a system is usually successful through misconfiguration or lax procedures on the part of operators.

This may lead to finding a copy of a passphrase on paper, in shared memory, in a backup, through a keylogger or even used for something else with weak password protection. So a real world attacker will usually take the easy route and look for wetware failure.

A strong passphrase and strong algorithm, by their very nature, are used to make the average time for a brute force attack beyond any useful time (caveat - the tool could get it on the first try, which is why we use averages, but as @Thomas says - you could win the lottery this week. Odds are just very very low!)


Explain the mathematical definition of a cryptosystem using words So when googling "cryptosystem" I found a Wikipedia page which contained a mathematical definition of a cryptosystem. Find this definition below.

Could someone tell me what that what the last line means, in words instead of using mathematical signs? Maybe it will help my understanding of it.

  Mathematically, a cryptosystem or encryption scheme can be defined as a tuple $(\mathcal{P}, \mathcal{C},\mathcal{K},\mathcal{E},\mathcal{D})$ with the following properties.

  $\mathcal{P}$ is a set called the "plaintext space". Its elements are called plaintexts.
  $\mathcal{C}$ is a set called the "ciphertext space". Its elements are called ciphertexts.
  $\mathcal{K}$ is a set called the "key space". Its elements are called keys.
  $\mathcal{E}= \left\lbrace E_k:k\in \mathcal{K}\right\rbrace$ is a set of functions $E_k:\mathcal{P}\rightarrow \mathcal{C}$. Its elements are called "encryption functions".
  $\mathcal{D} = \left\lbrace D_k:k\in \mathcal{K}\right\rbrace$ is a set of functions $D_k:\mathcal{C}\rightarrow\mathcal{P}$. Its elements are called "decryption functions".

  For each $e\in \mathcal{K}$, there is $d\in \mathcal{K}$ such that $D_d(E_e(p))=p$ for all $p \in\mathcal{P}$.

The direct translation would be something like :

  For each key $e$ in the set of keys $\mathcal{K}$, there is a key $d$ also in the set of keys $\mathcal{K}$ such that the decryption function using $d$ as a key, called $D_d$, when applied to the encryption function using $e$ as a key called $E_e$ is the identity function, so that when both are applied in a succession, starting with $E_e$, to a plaintext $p$, one will recover the same plaintext $p$.

So, for each encryption key $e$, there is a decryption key $d$ (possibly the same key) which allows to decrypt the content encrypted using the key $e$.


Can a cryptographic hash be used as a cryptographic RNG? Say I roll a six sided die 200 times (6^200 = ~2^517) and string all the results together into a long string of numbers and hash then result with SHA-512. Can I use that result for cryptographic purposes such as keys? Can I then use the hash of that result to generate more keys?

Yes, the output should have an entropy of 512 bit (or slightly less). Using it as a key is a good idea. If you want to generate more than 512 bits of key material out of the 512 bit you need to use a Key Derivation Function (KDF). You do not need to stretch the key, because it is no password and has a high amount of entropy - enough to make any brute force attempt impossible.

To do this, you can take the HMAC algorithm. Use a unique number (you can use a counter, it doesn't need to be random) as the message and the original key as the HMAC key. The result is your first real key material. If you need more, use another unique number (you can increment the counter for example) and compute the HMAC with this new number. Do this as long as you want, until you got enough keys. If you do this, don't use the original key material for anything else. If it ever leaks to an attacker, he/she can construct every other key with this original key material.


Security of AES counter mode vs. CBC mode For AES-CBC to be CPA secure the IV that is used has to be randomly selected for each packet. If the IV is predictable than the encryption is not CPA secure. Is the same true for AES-CTR mode? that is, for AES-CTR mode the first counter must be random or it can be a nonce?
Thanks

The requirement for the AES-CTR input blocks is, that they should be unique during the lifetime of a key. In most of the cases a random 96bit nonce is used with a 32bit counter that starts from 0. If the same input block for AES-CTR occurs twice, AES-CTR is not CPA secure any more. In this case, this can be due to a counter-overflow after $2^{32}$ blocks or due to colliding randomly chosen 96bit nonces (birthday paradox: 50% chance after $\sqrt{2^{96}}$ messages. Consider the following case:

Two distinct 1-Block messages $P$ and $P'$ are sent under the same key $K$ (that might be negotiated beforehand) and with the same nonce $N$. The attacker knows that the related cipher texts $C$ and $C'$ where calculated by XORing them with the keystream (which is based on the nonce and the counter):

$C = P \oplus E_K(N,0)$

$C' = P' \oplus E_K(N,0)$

Then the attacker can simply xor the cipher texts

$C\oplus C' =  P \oplus E_K(N,0) \oplus P' \oplus E_K(N,0) = P \oplus P'$

and he obtains the ''distance'' between the two plain texts. Due to redundancies in the English language, he might be able to determine $P$ and $P'$.

This problem is also known as the "two-time-pad". Once the same keystream is XORed with the plaintext, we get into trouble. Therefore, it is important, that the input for the AES encryption is unique during the lifetime of a key. It does not have to be unpredictable, just unique.


Can we use witnesses generated by OpenSSL's Rabin-Miller primality test to help factorization? If I have a 2048 bit value used as the modulus for an RSA exchange, and OpenSSL's BN_is_prime() has determined that that value is not a prime, does that mean that OpenSSL has found a strong Rabin-Miller witness?  If so, if we could get OpenSSL to output the witness(es), how might that help us in the factorization of the value?

does that mean that OpenSSL has found a strong Rabin-Miller witness?

Yes, it does.

  if we could get OpenSSL to output the witness(es), how might that help us in the factorization of the value?

No, it wouldn't help; for most composite numbers, the vast majority of values are Rabin-Miller witnesses (it's provable that at least $\frac{3}{4}$ always are, but for most composites, the ratio is very close to 1).  By far the most frequent for the Rabin-Miller to claim compositeness is that the random value $x$ is a value for which $x^{n-1} \ne 1 \bmod n$ (and so you never hit a 1 or a -1 in the sequence); such a value $x$ proves that $n$ is not prime, but gives no indication of the factorization of $n$.  Now, if you found an $x$ for which you fail for the other reason; because Rabin-Miller hit a 1 without hitting a -1 first, such an $x$ would immediately yield a factorization.  However, such values of $x$ occur only extremely rarely in practice.


Is TweetNaCl secure enough? I decided to use TweetNaCl in my project and did some tests. For some reason, its Ed25519 signing mechanism gives me very short public and private keys, as opposed to RSA, though RSA, as I it explained to me, is not secure.

So can I trust this implementation, experts, please?

As explained in the link posted by bkjvbx, the short keys and signatures offer the same security level as ~3000-bit RSA.

Regarding the implementation, TweetNaCL's code has been written by experts, has been carefully reviewed and is something you can trust. The only catch is that it is very slow.


Usability of padding scheme in blinded RSA signature? In Wikipedia's article on Blind signature, in the section Dangers of blind signing which describes RSA blinding attack one reads the following

  This attack works because in this blind signature scheme the signer
  signs the message directly. By contrast, in an unblinded signature
  scheme the signer would typically use a padding scheme (e.g. by
  instead signing the result of a cryptographic hash function applied to
  the message, instead of signing the message itself), however since the
  signer does not know the actual message, any padding scheme would
  produce an incorrect value when unblinded.

Could someone please explain the meaning of the part I emphasized?

In the blind RSA signature scheme the blinding of a message
$m$ (to be blindly signed) is multiplicative with value $r^e$, where
you ensure that $r$ is invertible modulo $N$.

So if the sender receives the signed blinded message back from the
signer, he can unblind by multiplying with $r^{-1}$, yielding $s\equiv
m^d \pmod N$ which is a valid (textbook) RSA signature for $m$.

Padding by the sender

Note, that $m$ could also be the result of any padding method for RSA
signatures, which however
needs to be applied by the sender before blinding. By denoting this padding as $f$ we can simply
consider the blinded message to be $m'\equiv f(m)r^e \pmod N$ (which clearly can be unblinded after blind signing).

Padding by the signer

Denoting the blinded message which is sent to the signer as $m'\equiv
mr^e \pmod N$, then padding by the signer means that the signer
changes the blinded message $m'\equiv mr^e \pmod N$ to some $m''$ before
signing. Padding methods for RSA signatures hash the original
message (possibly with some parameters), padd the hash value to some
certain format and the result is then interpreted as an element in
$Z_N$, which is then exponentiated with the private signing exponent
$d$.

Observe that in doing so the signer padds an already blinded message and denote this padded blinded
message as $m''=f(m')=f(mr^e)$. If such a padding to the message $m'$ received by the signer is applied by the
signer, then the signature obtained by the sender for $m''$ will be $s' \equiv (f(mr^e))^d \pmod N$
and then unblinding, i.e., computing $s'\cdot r^{-1} \equiv (f(mr^e))^d\cdot r^{-1} \pmod N$,
will yield some element from $Z_N$ which is clearly not a valid signature $m^d\pmod N$ for the message $m$ the sender wants to be signed
(for padding functions $f$ we assume to be applied, i.e., involving hashing. Clearly, if $f$ is the identity function then it works, but that is no padding).


Simple multiplication as an encryption method There was a time when I wondered about multiplication as an encryption operation. That was when I was thinking in terms of modular multiplication. But how about based around simple multiplication.

Pretend $M$ is a message represented as a number. $K$ is the secret key. Encryption is $C=M \times K$ and decryption is $M=C \div K$. Pretty simple and probably untouched. Has anyone ever suggested this?

As Ricky Demer comments above, an obvious weakness of this scheme is that if you know (or can guess) the plaintext $M$ corresponding to any ciphertext $C$, then you can immediately recover the key by calculating $K = C/M$.  Modern ciphers are generally expected to resist such known-plaintext attacks, making your cipher insecure by any current standards.

In fact, even if we don't know any plaintexts, there are still ways to attack your cipher.  For example, let's say that we've intercepted $k$ ciphertexts $C_1, C_2, \dots, C_k$, and we wish to decrypt them.  The obvious attack is based on the fact that, by definition, each of the ciphertexts is divisible by $K$.  More specifically, $$\gcd(C_1, C_2, \dots, C_k) = K \cdot \gcd(M_1, M_2, \dots, M_k),$$ where $\gcd(\dots)$ denotes the greatest common divisor of the ciphertexts and the plaintexts respectively.  Assuming that the plaintexts are not specifically chosen to all share a common divisor (in which case we might as well regard this deliberate common divisor as part of the key), as the number of intercepted messages $k$ grows, the probability that $\gcd(M_1, M_2, \dots, M_k) = 1$ approaches 100%.

Thus, having intercepted enough ciphertexts, we may calculate $K' = \gcd(C_1, C_2, \dots, C_k)$, which can be done efficiently e.g. using Euclid's algorithm, and be reasonably confident that $K' = K$, possibly times a small factor coincidentally shared by all the plaintext messages.  Thus, we can try decrypting the ciphertexts using $K'$ and see if the results look like plausible messages; if they do not, we can either intercept more ciphertexts, or simply try multiplying the decrypted plaintexts with small factors of $K'$ and see if this yields more plausible-looking results.  Either way, it should not take too many ciphertexts to recover the key and intercept all the messages.

Of course, the attacks above are only practical if the same key $K$ is used to encrypt multiple messages.  If the key for each message is (somehow) chosen independently at random, they do not yield any useful information to the attacker.

However, even in this case, your scheme still leaks some information to the attacker.  As a basic observation, we may note that, if $C$ is not divisible by some number $X$, then $M$ also cannot be divisible by $X$.  This observation alone is enough to show that your cipher lacks semantic security, which, again, makes it insecure by modern standards.

For a more concrete attack, let us assume that you regularly send messages consisting of the same plaintext $M$ (say, "nothing to report"), with different keys $K_1, K_2, \dots, K_n$.  With sufficiently many message, it's very unlikely that all the keys would just happen to share any common factor (unless this is done deliberately, in which case we're just back at the fixed-key case), so I can simply compute $M' = \gcd(C_1, C_2, \dots, C_n)$ and be reasonably confident that $M' = M$.

(Of course, for a more advanced attack, I can look for factors that are shared by most of the ciphertexts you send, which most likely correspond to either repeated plaintexts or repeated keys.  Then, observing any ciphertext that doesn't share one of these factors would be a strong indication that something unusual is going on.)


Use of OAEP in RSA Encryption I am working on creating an RSA Algorithm and learned that OAEP is a padding scheme that is commonly used before encrypting using RSA. Is this step necessary? Will it harm the integrity/security of the encrypted text?

Is this step necessary?

Yes. Assuming you don't want to adopt a RSA-KEM based approach, you need some form of padding to gain full IND-CCA2 security (textbook RSA even lacks the much weaker IND-CPA security!) and OAEP is the preferred such scheme, having a security reduction for IND-CCA2 (that is, it's IND-CCA2 as long as some reasonable assumptions hold).


Does DDH hold in $Z_N^*$ where N is product of 2 large primes I know that DDH does not hold in $Z_p^*$ because given $g, g^a, g^b, x$, we can compute legendre symbols of $g^a, g^b$ and compare it with legendre symbol of $x$. The same attack doesn't work when we consider the group $Z_N^*$ where N is product of 2 large primes. This is because computing jacobi symbol without knowing factors of N is hard by Quadratic Residuocity assumption. So, does DDH assumption hold in $Z_N^*$?

The same attack doesn't work when we consider the group $Z_N^*$ where N is product of 2 large primes. This is because computing jacobi symbol without knowing factors of N is hard by Quadratic Residuocity assumption.

This is incorrect: computing the Jacobi symbol can always be done in polynomial time, and does not require knowing the factorization. You're confusing it with the hardness of computing residuosity (i.e., checking whether an element of $Z_N^*$ is a square). DDH does not hold over $Z_N^*$. It is however conjectured to hold over $J_N$, the subgroup of elements with Jacobi symbol 1, see pages 23-24 of my paper.

EDIT: a screenshot of some old slides of mine: each element of $Z_N^*$ can have Jacobi symbol 1 or -1, and if it has Jacobi symbol 1, be square or non-square.


How to save the data in a non-trustworthy db, so the next time I read from the db, I know that I've read actual and not an old version of the data? Assume I encrypt a message, A1, and save it. Later I replace the message A1 with a new message, A2. I do not trust the message storage.
Now I want to read the last message. How can I verify that I've read the last message? An attacker can substitute the message A2 with A1 and I will not notice that.

The first idea is to memorize the last message. This will work with last message, but how can I verify that I have all my messages in the database? I think I can save a signed list of message signatures together with the date of last modification of the database. This way I only need to memorize the last database edit date. Will call this the control message.
I also need to make sure that there was no substitution while I compose the control message.

How is this done usually?

What I need, is a secure counter. A counter with properties:

it is stored in an insecure database
can't be replaced by an older version without knowing the key
it only supports increment/decrement operations
if possible, two users, at the same time, should be able to increment the counter (concurrency) without side effects
the counter can fail with some probability. Instead of N, it can be sometimes set to N-1. I do not want an attacker to set the counter.

I'm not a professional cryptographer, but you don't seem to be asking a cryptography question. Set aside the encryption part for a second, and I think you're asking for something impossible.

The two parties in your example are only communicating over the storage system.
The only way they are alerted to new versions is by checking the storage system.
And yet, you also say that the storage system is unreliable, or can be hacked.

In that case literally anything can happen.

Even if both parties "remembered" the last versions they saw, either one of them could change the state of the system, do something bad, and then flip it back to an earlier state before the other one noticed. Or, a third party could do the same and fool both of them.

If you had one secure channel, you could use it to prove some things about an insecure channel. But in your example that doesn't exist.


Chrome TLS 1.3 no TLS resumption with not secure connections I am testing TLS 1.3 on a slower IoT device (120Mhz ARM). In my tests Chrome with TLS 1.3 will not allow TLS resumption (Session Tickets) when you have an not secure connection e.g. because of an user accepted self-signed certificate. Additionally you will see almost the doubled number of TCP connections when loading from the website that has an invalid certificate (wrong alternate name or root not trusted).

Has anybody an idea, if that is intended by Chrome? There is no TLS resumption problem with TLS 1.2, or Firefox TLS 1.3.

This is a typical behavior of Chrome if the certificate is not trusted but the user has just skipped the warning. Skipping warnings is a bad idea anyway so you better import the certificate explicitly as trusted.