Is Rabin's cryptosystem secure against known-plaintext attacks? I've bee learning about Rabin's cryptosystem, and I already know that Rabin's cryptosystem  is vulnerable to a chosen-ciphertext attack, but I was wondering, is it also vulnerable against known-plaintext attacks? I think it's not, but I'm not sure. I would appreciate if someone could clear this up for me.

Both Rabin and RSA rely on padding for security. Proper padding prevents chosen-ciphertext attacks since modified ciphertext has a negligible chance of producing valid padding.

If you claim Rabin (or RSA) is vulnerable to CCA attacks, you should limit that to the unpadded/textbook variants. Most deployed implementations use padding, though some paddings are still vulnerable (e.g. PKCS#1v1.5 padding for RSA).

Another important property of padding is randomization to prevent plaintext guessing attacks, which would otherwise break low entropy messages.

=> Rabin without padding is only a building block, not something that should be used directly as secure encryption.
The most basic property asymmetric encryption needs to provide is security against chosen plaintext attacks, since the attacker can encrypt arbitrary plaintexts. Security against chosen plaintext attacks trivially implies security against known plaintext attacks.

=> Any secure asymmetric encryption is secure against known plaintext attacks, this includes Rabin.


RSA Key generation Public exponent too big I'm currently writing a paper about RSA (a self-chosen subject).
I'm writing about the key-generation in RSA, and I have problem finding the public exponent e.

I have chosen p = 61 and q = 53.

Then I determined my modulus n = p ⋅ q = 3233

and my phi(n) = (p-1)(q-1) = 3120.

What bothers me is that when I try to generate the public exponent e using CrypTool (given the same parameters), it gives me e = 2^16+1 = 65537 BUT I thought e had to be less that phi(n) = (p-1)(q-1) (according to this source).
Why is it OK to break this rule? Or is the CrypTool faulty?

The $2^{16} + 1$ exponent is really meant for use in real life systems, in which public keys are expected to be considerably larger than that. I guess CrypTool assumes this is the case, as you would expect, really.

That said, if $\gcd{(e, \varphi{(n)})} = 1$, then $gcd{(e ~ \mathrm{mod} ~ \varphi{(n)}, \varphi{(n)})} = 1$ by definition, so such an $e$ will still work regardless, as noted by fgrieu in the comments.


Weak Stream Cipher cryptanalysis Hi I have a stream cipher which uses a keystream of:

F(r) || F(r+1) || F(r+2) || ...

Suppose F(r) is the RSA encryption algorithm:

F(r) = r^e mod p where e and p are known , e = 3

My question is:
If we know F(r), F(r+1) and F(r+2), how can we calculate the subsequent key sequence?

Is there some obvious relation between F(r+3) and F(r),F(r+1),F(r+2) I don't  see?

I'll expand my comments into a full answer.

Start by examining that you know the value of $r^3$ - this is just $F(r)$.

You know you can express $F(r+1)$ and $F(r+2)$ symbolically. You can do this for any term in the key sequence, but it will be useful to write down $F(r+3)$. Forget any constant terms in the computations because they can be added in at the end.

Do you notice anything about the coefficients of $r^2$ and $r$ in the expressions for $F(r+1)$ and $F(r+2)$? Do they look like the coefficients of any subsequent terms in the key sequence?


Is computing majority element while doing secure two party computation for inner products ( input of the two parties ) an attack on the protocol? This was told to be an attack.

However, we can create a simulator in the ideal world which sends all 1s to the trusted party and receives the number of ones of the honest party. Is this simulation correct?

As shown in the attack you described, computing the majority bit is not an attack in the malicious model. However, it is an attack in the semi-honest model.


How does the cyclic attack on RSA work? I am trying to get the idea of cyclic attacks againts assymetric RSA encryption.
Taken from Handbook of applied cryptography .

Let $k$ be a positive integer such that $$c^{(e^{k})} = c\mod n  \tag{1}.$$
There for
$k-1$ it holds that $$c^{(e^{k-1})} = m \mod n  \tag 2$$ where $m$ is the message for encryption $n$ is the modulus and $c$ is the ciphertext.

I can't understand why equation (2) must hold?

We start with the definition of textbook RSA encryption: $c = m^e \bmod n$. From your first equation

$$c^{e^k} = c \pmod{n},$$ we have that if $c^{e^k} = c \pmod{n}$, then $e^k = 1 \pmod{\phi(n)}$ (Euler's theorem). Dividing both sides by $e$, we get

$$e^{k-1} = e^{-1} \pmod{\phi(n)}.$$

By definition, $d = e^{-1} \pmod{\phi(n)}$. Thus, $$c^{e^{k-1}} = c^d = m \pmod{n}.$$


How to attack Oblivious Transfer from a malicious sender that can deviate from the protocol I am looking at at the $1–2 \space \text{oblivious transfer}$ that is described here: https://en.wikipedia.org/wiki/Oblivious_transfer#:~:text=In%20cryptography%2C%20an%20oblivious%20transfer,Rabin.
I want to show that a malicious sender (Alice) can attack this protocol if it can deviate from it, namely, send a wrong RSA key pair, and learn the secret bit $b$.
If the sender (Alice) sends $e$ such that $gcd(e, \phi(N)) \neq 1$, then the RSA key is not valid, but the receiver (Bob) can't efficiently know this without the factorization of $N$.
However, I don't exactly understand how sending such an invalid input $e$ helps.
Since $e$ and $\phi(N)$ aren't coprime, then $k^e$ from the protocol that the receiver sends is not exactly random. But how does it help to understand who is $b$?
Help would be appreciated.

I want to show that a malicious sender (Alice) can attack this protocol if it can deviate from it, namely, send a wrong RSA key pair, and learn the secret bit $b$.

You can, in fact, show this (or, rather, the OT would require a ZK proof by Alice that $\gcd(e, \phi(N)) = 1$)

However, I don't exactly understand how sending such an invalid input $e$ helps.

If $\gcd(e, \phi(N)) > 1$, then not all values $z$ have $e$th roots, that is, sometimes there won't be a value $y$ with $y^e = z$.  And, if you know the factorization, this is easy to test.
So, when Alice gets the value $v = (x_b + k^e) \bmod N$, she can compute $v - x_0$ and $v - x_1$.  The correct one will be an $e$th root; the wrong one will likely not be - if it is not, then she will then know $b$.
One issue that Alice will run into is that, in this case, she would not be able to unambiguously recover $k$; this would prevent her from being able to complete the protocol. However, the damage has already been done.


What are the advantages of a static ECDH key? What are the advantages of using "static-ephemeral ECDH" over "ephemeral-ephemeral ECDH"?

Well, the advantages of static-ephemeral ECDH (and, they apply to DH as well):

You get one-way authentication for free.  That is, if Bob has Alice's public ECDH key, and uses it to talk to someone, Bob knows that that someone is Alice, without doing any further checks.  Now, Alice has no idea who she's talking to; on the other hand, for some scenarios, Alice really doesn't care.
You don't need a reply from Alice to get her ECDH public value; you already know it.  This may allow you to use one fewer protocol round (depending on what else needs to be done on the protocol).  In fact, if all Bob wants to do is share a symmetric key so he can send Alice a message, he doesn't need any replies from Alice at all; he can generate his public value, and the message encrypted and authenticated with a key derived from the shared secret.  Doing this is actually known as the Integrated Encryption Scheme; if this is what you're doing, you might want to look at the standards (as people have thought through the details)

Of course, there are some downsides:

It means that Bob has to get Alice's public key in a way that is authenticated.  If that means that Bob has Alice's key in a database, well, there are some practical questions with that (such as when Alice creates a fresh key, how does Bob hear about it).
If Alice does care who she is talking to, that means Bob needs to authenticate himself.  If you need to do this, you lose some (but not all) of the advantages you get from preconfigured keys in the first place.
You lose the Perfect Forward Secrecy properties that are normally associated with DH; you may or may not care depending on your security assumptions.  That is, if someone gets their hands on Alice's private key, then they can not only impersonate Alice, they can go back and decrypt previous sessions.


Message length limit induced by block counter size Wikipedia reports the following information about the ChaCha20 algorithm:

  An implementation reference for ChaCha20 has been published in RFC
  7539. The IETF's implementation modified Bernstein's published algorithm by changing 64-bit nonce and 64-bit block counter to 96-bit
  nonce and 32-bit block counter[34]. The name was not changed when the
  algorithm was modified and it could be the source of confusion for
  developers. Because of the reduced block counter, maximum message
  length that can be safely encrypted by the IETF's variant is 2^(32)-1
  blocks of 64 bytes (about 256 GiB). For usages where this is not
  enough, such as file or disk encryption, RFC 7539 proposes using the
  original algorithm with 64-bit nonce.

My questions are:

In this sentence

  ... maximum message length that can be safely encrypted ... is
  2^(32)-1 blocks of 64 bytes (about 256 GiB)

I've got the following related questions about this:

Is it being implied that that using the same block counter repeatedly is a risk?
How is that risk calculated? What is the formula for the risk?
If it is a question of repeating blocks counters, then shouldn't the block size be the same as the nonce? 96 bits = 12 bytes?
If it is not repeating block counters that is the source of risk, then is the risk just based on the total length of encoded data?  What is the formula for that risk?

From the RFC you can see that a ChaCha20 block is constructed as follows:

state = constants | key | counter | nonce

Which is then processed in a number of rounds. So lets keep that in mind for the following Q/As.

1. Is it being implied that that using the same block counter repeatedly is a risk?

Yes. If you use a 32 bit counter then it is presumed to be used in modular fashion, using modulo $2^{32}$ calculations. That means $\operatorname{inc}(2^{32} - 1) = 0 \mod 2^{32}$. I.e. it overflows and resets to the initial counter 0.

That would mean that the state would get the same value (none of the other components changes for the same nonce), which means that the key stream starts to repeat itself. The processing of the state is otherwise deterministic, so you would get the same key stream block.

2. How is that risk calculated? What is the formula for the risk?

In the calculations below $P_x$ is a block of the plaintext message, $S_x$ is a block of the key stream generated by processing the state with the ChaCha20 rounds and $C_x$ are the blocks of the ciphertext (where the last block may be a partial block depending on the size of the message). $x$ is the position of the block within the plaintext / key stream / ciphertext.

This is basically a so called many-time-pad. If you have two blocks of the message $P_0$ and $P_{2^{32}}$ then you would have $C_0 = P_0 \oplus S_0$ and $C_{2^{32}} = P_{2^{32}} \oplus S_{2^{32}}$. But because $S_0 = S_{2^{32}}$ you can see rewrite that to $C_{2^{32}} = P_{2^{32}} \oplus (C_0 \oplus P_0)$ or, after a bit of rearrangement $P_0 \oplus P_{2^{32}} = C_0 \oplus C_{2^{32}}$, i.e. you leak the XOR of two plaintext blocks of the message by XORing the ciphertext at the same position.

This risk is 100%. How much information is leaked depends on the contents of the blocks of the message. Note that much more information becomes available if the same limit is crossed multiple times, as you can now XOR multiple blocks together in a pairwise fashion.

3. If it is a question of repeating blocks counters, then shouldn't the block size be the same as the nonce? 96 bits = 12 bytes?

That would not fit in the state; ChaCha20 is specified with a specific state size where state consists of sixteen 32 bit words, or 512 bits.

4. If it is not repeating block counters that is the source of risk, then is the risk just based on the total length of encoded data?  What is the formula for that risk?

This is about repeating counters, so this question is not applicable.

Note that a correct implementation should fail rather than overflow. Unfortunately for online implementations, where the size of the plaintext message is not known in advance, that would be after encrypting $2^{32}$ blocks.


Understanding calculation of collisions in hash-functions I am going through some of my notes from class (About Information Security) and I'm stuck understanding how my teacher got this result. The question is:

  How many collisions would you expect to find in the following cases?

  a) Your hash function generates a 12-bit output and you hash 1024 randomly selected messages.

  b) Your hash function generates an n-bit output and you hash m randomly selected messages.

The teacher's only answered a) like so:

  We expect to find one collision every $2^{n/2}$ hashes. There are $2^{(n/2) * 2} = 2^n$ comparisons. Since the output is 12-bit the answer is $2^{10 * 2}/2 ^{12} = 2^{8} = 256$ collisions.

However I don't quite understand how he got this?

I get that the expected number of collision after n hashes would be $2^{n/2}$. But the rest doesn't make sense to me. I mean if the output is 12 bits (4096 arrangements), why would we expect to get 256 collision after only hashing 1024 messages (1/4 of the possible outputs)?

I suspect you are misrepresenting what your professor actually said.

Since I'm not certain exactly what he said, here is how I would explain it:

With 1024 outputs, there are $\binom{1024}{2} \approx 1024^2/2$ pairs of outputs.
For each pair of output, that pair has a $2^{-12}$ probability of being a collision (that is, those two outputs being exactly the same).
Hence, the expected number of collisions would be about $1024^2/2 \times 2^{-12} = 128$

The exact expected number would depend how you count a multiway collision (where 3 or more outputs have the same value); it turns out that, if you count it right, $\binom{1024}{2} 2^{-12}$ is the correct answer.


Attacking a hardware AES implementation if it leaks the intermediate round states Let's say that we have a hardware AES implementation that, on request, will encrypt or decrypt a 16-byte block of data in ECB mode using a fixed key, but refuses to reveal its fixed key.  In other words, an oracle.

This oracle has a flaw: if you read the hardware's output registers before the device says that its output is ready, it will return the result of the intermediate rounds rather than only the 10th (final) round.

Is it possible to attack this system to go after the embedded key?  I suppose that this means my question is about chosen-plaintext attacks against reduced-round variants of Rijndael-128.

If you can read the intermediate states of the encryption algorithm you could recover, one by one all the round keys.
Given a AES round, all the operation between the two AddRoundKey (at the beginning and the ond of the round) are invertible.

Take for example round 1:
you get the internal state before AddRoundKey (of round 2), you get back at the beginning of round 1, and you get the plaintext XORed with the first round key.

Finally, recovering all round keys is equivalent to recover the master key.


Which encryption is recommended for own messenger I wrote my own messaging-app and now I would like to encrypt the data transfer between my client (app) and my server. What kind of encryption is easy to implement and can be recommended? I am very very knew to the whole encryption thing. I would love to get some hints or ideas as input.

I use TCP/IP for delivering the messages.

TLS, without a doubt. Note that TLS does not imply HTTP, so you can use it with whatever TCP protocol you have.

For UDP you can use DTLS, which I believe forces the use of CTR mode to combat packet loss.


How to formally prove that a given hash construction is collision resistant or not? Is there a precise procedure or strategy to follow in order to prove in a formal way the (not) collision-resistance of a certain given hash construction? I.e. let $H_1$ and $H_2$ be two hash functions, then define the following construction $H(x) = H_1(x)||H_2(x)$. How could one formally prove that such construction does not yield any collision, given that at least one of $H_1$ and $H_2$ is collision resistant?
I know, in this case, the concatenation of a sequence of hash functions is collision resistant if at least one of the hash functions in the sequence is collision resistant. But, my question here is if there's any formal way of proving it.

Proof by contradiction is easy in this case.

Assume the construction is not collision resistant. Then there's an adversary who can efficiently find a pair $H(x) = H(x')$. However, that also gives them $H_1(x) = H_1(x')$ and $H_2(x) = H_2(x')$, so neither hash function is collision resistant, which contradicts the assumption.


What Cipher Suite in this list is the worst to use I have a list of cipher suites I captured using Wireshark. Which one of these cipher suites would possibly be the worst to use. Here is the list.

In my opinion, I choose the:

TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA

to be the worst because it uses a 128 bit key and uses CBC instead of GCM cipher mode. Is there any cipher suite that would be less secure here compared to others in the list?

Assuming you are actually asking whether any cipher suite is objectively worse than the others, the answer is clear:

TLS_RSA_WITH_3DES_EDE_CBC_SHA. Why? Well, this cipher suite suffers from 3 "major" problems, at least one of which is remedied by any of the other cipher suites:

Lack of forward secrecy. This cipher suite doesn't use any form of (EC)DHE key exchange, thus if the private RSA key is leaked (eg through a server compromise), all passively captured past data exchanges can be decrypted.
Use of CBC. TLS has a history of having (somewhat practically exploitable) issues with its padding used for CBC, e.g. POODLE or with IV selection, e.g. BEAST. Also notable here is Lucky13, which apparently is somewhat hard to mitigate if you want to use CBC. The CBC padding issues are  available to attackers because AES-CBC is used in a mac-then-encrypt situation where the padding is removed before the message is authenticated.
Use of a cipher with a small block size. If you use a block cipher with a $n$-bit block cipher, you expect to see a collision in the CBC ciphertext after about $2^{n/2}$ blocks. With AES, this is $2^{64}$, but with 3DES this is $2^{32}$ blocks (due to its 64-bit blocksize) which gave reason for the Sweet32 attack.

You may also want to note that technically the security margin of three key 3DES is 112-bit, as opposed to AES' 128-bit, so it's worse off even there, but it's a matter of "meh, can't brute-force" vs "meh, can't brute-force".


Fastest multiplication algorithm for efficient exponentiation in C++? First I apologize if this question is better tailored for SO, but since I'm using the method for crypto stuff, I thought I'd ask anybody that might know here. Karatsuba algorithm does a pretty good job, but maybe there is something that works better.

It depends on the length of the inputs and characteristics of the target platform:

If inputs are short (at most around a thousand bits), try a Comba multiplication.
If inputs are short and your platform has a lot of registers, try a hybrid Comba multiplication.
If you have a multiply-accumulate instruction, give a shot at Schoolbook multiplication.
If inputs are larger, divide-and-conquer approaches (Karatsuba, Toom-Cook) start to become faster.


Probability of generating same master secret key in Identity-based Encryption Suppose multiple servers use same IBE domain parameters (I mean same curve description parameters and field) for master secret key setup. Is there any possibility for generating the same system parameters?

Yes, it is possible, but extremely improbable.

Take for example the BasicIdent IBE scheme, by Boneh and Franklin. Let us assume that the curve, pairing and groups are fixed. During the Setup step, one has to select a random generator $P \in \mathbb G_1$ and a random master key $s \in \mathbb Z_q^*$. We can assume that these parameters are sampled uniformly.

The probability of selecting the same parameters in a different domain mostly depends on selecting the same $P$ and $s$. The order of both $\mathbb G_1$ and $Z_q^*$ is $q$, so the probability of generating the same system parameters is $\frac{1}{q} \cdot \frac{1}{q} = \frac{1}{q^2}$, which is negligible.


OpenSSL TLSv1.3 record padding OpenSSL supports TLSv1.3 record padding:
https://www.openssl.org/docs/man1.1.1/man3/SSL_CONF_cmd.html
but I'm not sure if it works like I think it does. If I would choose a factor of 2 it would make the record (=packet/payload length???) twice the original size. Is that correct? If so, wouldn't random padding be better? Otherwise you could just divide the packet by 2,3,4 ... to get to the real value?

If I would choose a factor of 2 it would make the record (=packet/payload length???) twice the original size. Is that correct?

No; if you set a factor of 2, then the encrypted record size would always be even (that is, if it would have been odd, a padding byte would be added).
In general, a factor of $x$ would increase the size of the encrypted record from 0 to $x-1$ bytes.


I didn't get the hash length extension attacks I was trying to solve a cryptography challenge and the problem was about "hash length key extension". After some reading in different topics, I don't know why I still didn't solve the challenge.

I read this page. From what I understood, we have the MAC which is $\mathrm{md5}(\mathrm{secret}||\mathrm{data})$.  We want to append some string at the end, so we will have the new hash $\mathrm{md5}(\mathrm{secret}||\mathrm{data}||\mathrm{append})$.

When I run $\mathrm{md5}(\mathtt{secretdata})$, I get 6036708eba0d11f6ef52ad44e8b74d5b like in the tutorial.
But when I compute $\mathrm{md5}(\mathtt{secretdataappend})$, I get 81efe001a23d41765fa7323d22861558. However, the tutorial says it should be 6ee582a1669ce442f3719c47430dadee.

In other tutorials it is the same hash value, so I am probably doing something wrong. My instinct is that I have to guess the value of $\mathrm{secret}||\mathrm{data}||\mathrm{append}$, without knowing $\mathrm{secret}$. I only know the length of $\mathrm{secret}$.

Why do I get the wrong hash when trying to perform this attack?

OK, so the general idea of MD5 and SHA-1 and SHA-2 is that they process the data in blocks. For the last block the algorithms first append a padding to the plaintext data and the encoding of the length to create the final block. If the padding and length do not fit then an additional block is used.

Now the problem with these algorithms is that the intermediate state, that is: the state after a block encrypt is directly used as the output for the final block. So if you have three blocks then the value of the last block operation is used as output. So if you have a message that consists of the first block and then two blocks that mimic the last part of the message, padding and length indication then the intermediate value between block 3 and block 4 will be identical to the output of the previous calculation. After that you can add any data and keep processing as usual.

Let's put this in a scheme, ignoring the secret for now:

| message_b1 | message_b2 | message_p3 | padding_p3 | length__p3 |
| process_b1 | process_b2 |              process_p3              |
| h_state_b1 | h_state_b2 |              h_state_p3              |

can be extended using

| message_b1 | message_b2 | message_b3 | message_p4 | padding_p4 | length__p4 |
| process_b1 | process_b2 | process_p3 |              process_p4              |
| h_state_b1 | h_state_b2 | h_state_p3'|              h_state_p4              |

For this to happen message_b3 must of course consist of message_p3 | padding_p3 | length__p3 otherwise h_state_p3' will be different from h_state_h3 and therefore h_state_p4 the final output will be invalid.

If the secret is (part of) message_b1 then the verifier will automatically prefix the secret for you. So you just need to provide the message itself, but it must consist of the special format.

SHA-3 post processes the hash, so the length extension is not possible anymore as the final hash cannot be an intermediate value of another hash calculation.


What are the standard procedures in cryptanalysis to analyze unknown ciphertext? What are the "standard procedures in cryptanalysis" to analyze unknown ciphertext?

In other words: Are there any protocols, officially acknowledged checklists or something like that which represent a "standard" approach in cryptanalysis to analyze unidentified ciphertext? If yes, which ones would that be and what would be the path to follow?

Clarification

I am well aware of cryptanalytic procedures like detecting algorythms etc. My question was: is there any “officially acknowledged protocol” in cryptography to follow when doing cryptanalysis?

To get one point very clear before anyone goes down the wrong road: this has nothing to do with "only a bad guy would ask something like this…." since the situation is actually the other way around. That's why I asked for "officially acknowledged protocols" as in "legally accepted by authorities as evidence and/or proof". Think "whitepaper", not "reverse engineering".

The goal is the "capturing and identification of digital evidence coming from communication streams" to then forward that information to authorities in a way they will accept it. I know how to gain the rough information I want to pass on (like the identification of the crypto-algorithm used), but I want to follow the correct path/order/procedures which authorities accept as "correctly collected digital evidence".

There has to be some protocol that governments, (security) companies, and institutions follow. When it comes to "evidence", there's always a "specific way to do it". Question is: which one would that be when it comes to analyzing unknown ciphertext?

So, to wrap it up: I'm not asking how to analyze unidentified ciphertext, I'm asking what protocol to follow when doing so because I need to pass on the collected evidence later on!

I think my comment-reply to @mikeazo wraps up my question rather perfectly:

  Collected evidence was captured in internal company network. We secured full access logs and identified source and target of transmission. Currently, source denies it's anything else but random text. Doing a quick analysis of copies of the captured data shows different encryption algorithms. As proof it's not random text I would like to add my findings to the other evidence collected. Do do so, I want to be sure they accept the way I identify the algorithms etc. That's why I would like to know if there's an "official protocol" to follow that's "officially accepted" (by authorities).

Addendum to the accepted answer

After getting a tip via twitter, it turns out that there are several pointers in publications from the National Institute of Justice (NIJ):

Electronic Crime Scene Investigation: A Guide for First Responders, Second Edition
(April 2008, NCJ 219941)
Forensic Examination of Digital Evidence: A Guide for Law Enforcement
(April 2004, NCJ 199408)
Digital Evidence in the Courtroom: A Guide for Law Enforcement and Prosecutors
(January 2007, NCJ 211314)

Those provide some hints, but even those don't really handle the details of standard procedures to follow in cryptanalysis. Like the accepted answer already implied, cryptanalysis obviously isn't enjoying any standard protocols (yet).

Unfortunately Crypto.SE probably has very few lawyers, law enforcement officers, public policy experts, etc. Furthermore, Legal.SE doesn't exist yet. To further complicate the situation (at least in the US) the answer will probably vary from state to state.

So, I'm going to do the best I can, but you are probably best off either calling police or a lawyer in your jurisdiction.

Here is the deal, it is hard to prove a negative. Thus, I don't feel sufficiently knowledgeable to say no such protocol/procedure exists. That said, I don't know of one. I did find this flowchart for collecting digital evidence if you are in the US. Step one seems to imply that some knowledge of local/agency policies must be followed. But this deals more with evidence collection and not analysis.

My guess is that (at least in US), once you have the relevant network traffic and logs, your job is done. This is especially true if you have any motive/interest in seeing the offending party get in trouble.

So, assuming evidence is collected properly (since that is beyond the scope of your question) my guess is that the prosecuting attorney will hire an expert witness to examine the evidence and give testimony at a trial. They would probably also call you up to testify as to the collection procedures, etc.

Some added thoughts
The answer probably also depends on the exact protocols/software used. For example, if after an expert analyzes the ciphertext, they can determine that PGP or some other piece of software was used in which a long-term secret is used for encryption, a judge could order the defendant to disclose the encryption password or long-term secrets. At this point, no additional cryptanalysis would be needed. This would become more difficult if say TLS is used as the client often has no long-term secrets. I suppose a judge could force the party owning the server to reveal long-term secrets so decryption could take place (assuming the initial handshake was captured). If TLS, or whatever protocol used, is used in such a way that ephemeral keys are used, then even this would not work.


Arbitrary key size in RC4 Is it possible using RC4 that for e.g. a 17-bit long plaintext i can get a 17-bit long ciphertext?

From my understanding, for this example i need a 17-bit long key to do the XOR operation for encryption. However in the normal algorithm of the RC4 only keylengths of 1 to 256 bytes are permitted.

Can i use 3 bytes = 24 bits as keylength and discard 7 bits in the generation of the random bytes K which i use for encryption?

Or is there another workaround which i am missing?

This is about a misunderstanding. RC4 is a stream cipher. That means that it takes an (input) key and generates a key stream. The bits of this key stream are then XOR'ed with the plaintext. The size of the key stream is not dependent on the size of the (input) key. The input key is not XOR'ed with the plaintext.

Generally RC4 implementations only handle bytes. That's OK, you can just give any input key you want between 40–2048 bits in steps of 8 bits.

Then you can encrypt with the resulting key stream, which means the XOR'ing with the key stream. You can just use 3 bytes / 24 bits of plaintext: say one byte with the least significant bit set (the other bits can have any value) followed by  two bytes with the rest of the 16 bits. Then you encrypt those bytes.

Finally you retrieve back the 17 bits at the same position. Now you've encrypted 17 bits; the other 7 bits can be ignored or removed. When XOR'ing the bits of each byte are fully independent of each other, so the other bits are not needed.

Decryption is identical, so you can just ignore the same 7 bits again.

As indicated by others, RC4 is not considered secure. There are plenty of stream ciphers to choose from that are secure. You could also use AES in counter mode, although AES-CTR obviously does have specific input key sizes; the key stream will however work as expected.


Pedersen commitment in elliptic curves I try to understand Pedersen commitment in elliptic curves over finite fields. I could use some clarification.

Let's say we have two generators $G$ and $H$.

Is that required that $G$ and $H$ are two different generators of the same group?

Pedersen Commitment $C$ will look like that.

$$C = aG + bH$$

$C$ is a point on the curve, right?

Now in the situation when $a=0$ we have

$$C = 0G + bH = bH$$

How do I know that $bH$ is generated by $H$ without revealing $b$?
How do I know that $bH$ is not generated by $G$?

Is that required that $G$ and $H$ are two different generators of the same group?

Yes. Pedersen commitment uses random public generators $G$ and $H$ of a suitable large group where the Discrete Logarithm is hard, thus $G$ and $H$ can safely be assumed distinct. Also, that condition implies no integer $w$ such that $G=w\,H$ can be found by anyone. These facts are assumed or stated.

  $C=a\,G+b\,H$ is a point on the curve

Yes, though at some implementation level, it is a bitstring describing a point on the curve.

  How do I know that $b\,H$ is generated by $H$ without revealing $b$?

Anyone given a bitstring alleged to describe a point generated by $H$ can check that assertion, simply by checking that the bitstring indeed describes a point on the curve (which is feasible since the curve's equation and bitstring convention is public). Being generated by $H$ follows, since all points on the curve are generated by any generator (by definition of a generator), and $H$ is a generator.

Also: since the first-person locutor in this question cares about not revealing $b$, s/he knows $b$, thus can compute $b\,H$, which by construction is generated by $H$. If s/he makes that computation privately, that's an alternate way of making the verification without disclosing $b$.

  How do I know that $b\,H$ is not generated by $G$?

Point $b\,H$ is generated by $G$, even though it may not have been obtained by computation of $x\,G$ for some integer $x$. Obtaining integer $x$ such that $x\,G=b\,H$ not knowing random $b$ would be as hard as the discrete logarithm problem for $G$.

My guess is that the intended question 3 is:

  How do I know that the alleged $C=b\,H$ was obtained by computation of $b\,H$ without being revealed $b$?

As a verifier in a Pedersen commitment, you don't know that the alleged $C=b\,H$ was obtained by computation of $b\,H$ until being given $b$ by the prover, which is how s/he demonstrates $a=0$.

As rightly pointed in an other answer, there are different interactive protocols (when Pedersen commitment is not) allowing a prover to demonstrate knowledge of integer $b$ such that $b\,H$ is a certain public point, without revealing $b$. Schnorr protocol does so, as:

prover generates random integer $r$, computes and sends point $T\gets r\,H$
verifier generates and sends random integer $i$
prover computes and sends integer $s\gets i\,b+r\bmod n$, where $n$ is the (public) order of the curve
verifier knowing point $b\,H$ computes point $i\,(b\,H)$, then point $i\,(b\,H)+T$; computes point $s\,H$; and ensures $i\,(b\,H)+T=s\,H$.


Is it safe to use the CBC-MAC as a Initial Vector and Key Check Value in deterministic encryption? I want to deterministically encrypt a short message <50 bytes with AES-128 CBC. I also want to be able to detect if the correct key is being used.
Ciphertext and IV integrity will be guaranteed by a higher layer of software, so its impossible to tamper with the ciphertext, IV or additional data. The encryption key is widely known also by malicious parties, except by one server. The encryption is only used for plausible deniability for this server, so a malicious party is allowed to read everything. The server should be able to group equal messages blindly hence the deterministic encryption.
Since the message size is small, I want to minimize overhead next to the ciphertext. I've read a key check value can be used to detect if the correct key is applied for decryption. This can be done by adding one block of zeros or another constant in front of the message before encrypting with AES.
I was wondering if I can use a 128 bit CBC-MAC of the plaintext as this constant, and use it simultaneously as IV for the encryption of the message. This to prevent only equal first bytes of the messages to result in equal first bytes in the ciphertext.
Basically the idea boils down to concatenating twice the plaintext, apply AES-CBC with an IV of zero. Using the output of the last AES block of the first half as IV and the whole second half as ciphertext. After decryption the receiver can CBC-MAC the decrypted plaintext to see if it matches the used IV and thus the correct key was used.
Note that the CBC-MAC is only used for creating a deterministic IV. Its not needed for all the properties a MAC is intended for.
Am I thinking correctly and will an malicious user (which has access to encryption keys) not (or very hard) be able to generate a collision in my IV-ciphertext combination so that the server is grouping unequal messages together?

Am I thinking correctly and will an malicious user (which has access to encryption keys) not (or very hard) be able to generate a collision in my IV-ciphertext combination so that the server is grouping unequal messages together?

If the server checks all the bytes in the IV-ciphertext (and declares a collision only every byte for two encrypted messages are identical), and if you can decrypt it (and a decryption of an encrypted message will always output the original message), then it is obviously impossible to generate for two distinct messages to be declared as colliding (and you don't have to worry about the details of the encryption method except for these two facts).
Consider two distinct plaintext messages $M \ne M'$, they will be encrypted into ciphertext messages(which includes the IVs) $C = E(M)$ and $C' = E(M')$.  Now, the decryption process is a function of the ciphertext and the keys (and nothing else; that's why I counted the IVs as part of the ciphertext).  If we had $C = C'$, then what would this common ciphertext decrypt to?  If it is $M$, then we have a message $M'$ that, after encryption, could not be decrypted properly (hence violating the assumption that decryption of an encrypted value always gave back the original plaintext).
Hence, a malicious user cannot generate a message that the server would confuse with another message.


Why do cryptographic hashes need to be fixed length? Why do cryptographic hashes need to have a fixed length output?

I know that the shallow answer is that an output that varies by key size or file size can leak information somehow, leading to cryptanalysis, but I would like some more intuition as to why this is the case.

In the case of using an HMAC, like HMAC-SHA256 or HMAC-SHA1, is it still the hash (SHA256 or SHA1) which is ensuring that the output is of a fixed length? Or does the HMAC algorithm come into play as well?

They don't, and in fact the sponge construction used in Keccak (SHA-3) allows for variable length output.

In other hashes the Merkle-Damgård construction was used which has a fixed output length due to the nature of its design. But there is no reason to not allow for variable output length other than ease of development or use.


How to prove a symmetric encryption scheme provides perfect secrecy? I learned in class that in order to achieve perfect secrecy, the source of the plaintext $\mathcal{P}$ needs to be independent from the source of the encryption key $\mathcal{K}$. We also learned that this is always the case for independent sources: $H(\mathcal{P}) \le H(\mathcal{K})$, but that it shouldn't be used as an exhaustive proof, because in the case where you have a high-entropy key but it is badly designed (such as having different lengths for each code word), you could still derive a lot of information from attempted decryption.

We saw an example where someone used a coin to determine a random key composed of 16 bits to mask a plaintext composed of 4 digits coded into 4 bits each (using xor logic). In this case, $H(\mathcal{P}) = 13.2877$ (there are 10000 possible combinations of digits), and $H(\mathcal{K}) = 16$, so the inequality holds.

Suppose now that 8 bits of the key are generated randomly, and then just copied over for the remaining 8 bits. The key source and the plaintext source now become dependent, however only if the "hacker" knows that the key was copied twice over (because it is technically a possible outcome). The inequality doesn't hold anymore either because $H(\mathcal{K}) = 8$. I'm assuming that this encryption scheme fails to provide perfect secrecy, but I remain unconvinced because of my previous argument of the conditional state of this "copied" key. In this case, is there a better way to provide a proof other than the two methods mentioned above?

Xor-ing the first half of the encrypted message with the second gives the same result as xor-ing the first and second half of the original message. (When the key is duplicated). This contradicts perfect secrecy as some information can be obtained from the cyphertext.


Basic Vigenere Cipher I'm taking my first cryptography course and having trouble deciphering some Vigenere encrypted text.

I was able to crack the first one:

I'm having difficulty with the other two. I think the solution to #2 and #3 lies in the wording of the question. It says that the "message format" is the same as the first one, but what does that actually mean? Are the numbers arranged in the same way (i.e. first number is 3 chars long, second is four chars, third is four chars, etc)? I've been trying out a bunch of approaches but i'm not getting anywhere. Please help!

Same format means they are numbers. So you have to try the combinations to match. In other words, you are performing an attack on limited message space. Produce combinations of numbers.

ONEONEONEONE...
ONEONEONETWO..
...
NINENINENINE

Before this applying Kasiski test to determine the key length may be helpfull to reduce the string lengths.

Good luck!


Can I create a random access CSPRNG from a hash? Can I use a keyed hash of a counter as a secure CSPRNG?
E.g. 4th random block is Hash(4, seed)

If not, what are the possible attacks?

There is a name for "random access PRG" : it's called a pseudorandom function (PRF). Any block cipher is a pseudorandom function (that's more-or-less the definition of what it means to be a secure block cipher), so you can use, say, AES directly. If all you have is a hash function, then the HMAC construction also gives you a PRF.


Is OpenSSL HMAC vulnerable to length extesion attacks when using MD5 as hash algorithm? Given that a valid hash for a specific payload is known, would some C code like this be vulnerable to a length extension attack?

#include <openssl/hmac.h>
...
unsigned char *calculated_hash = HMAC(EVP_md5(), &key,sizeof(key) - 1, payload, payload_len, NULL, NULL);
...
    if(memcmp(calculated_hash, received_hash, 16) == 0){
        dprintf(client_fd, "Payload Valid\n");
        exit(0);
    } else {
        dprintf(client_fd, "Payload Invalid\n");
        exit(1);
    }

HMAC-MD5 is not vulnerable to length-extension attacks, period.

If that's what your code computes, then your code is not vulnerable to length-extension attacks.  That said:

Length-extension attacks are a part of the protocol, not an implementation of the protocol.  It doesn't matter whether you use OpenSSL or something else to implement the same protocol.

You should have a concise description of your protocol and generate test vectors, e.g. with Python or Go, to confirm that your C code is computing the cryptography you intend in the protocol.  You should also have a clear statement in a design document of what your protocol accomplishes, without reference to the cryptography it uses; and a clear statement in a separate section of the design document of what security goals your protocol aims for.
Your code has another problem: it has a side channel leak that could be exploited to forge messages, because you're comparing secrets with memcmp.  In OpenSSL, you should use CRYPTO_memcmp instead.


What is an extendable output function? The standardization of SHA-3 included the specification of two functions, SHAKE128 and SHAKE256. Both SHAKEs are referred to as extendable output functions, but what makes a function an extendable output function?

As defined in FIPS 202, whereas SHA3-256 is a function mapping an arbitrary-length bit string to a string of 256 bits, the extendable output function SHAKE256 is a function mapping an arbitrary-length bit string to a string of infinitely many bits.

In both cases, the conjectured cost of computing a preimage or second preimage for a given $\ell$-bit output ($\ell = 256$ for SHA3-256, arbitrary for SHAKE256) is about $2^{\min\{256,\ell\}}$ bit operations, and the conjectured cost of computing a collision is about $2^{\min\{256,\ell/2\}}$ bit operations.  For SHAKE128, it's rather $2^{\min\{128,\ell\}}$ for (second) preimages or $2^{\min\{128,\ell/2\}}$ for collisions.

For an adversary with a quantum computer, the exponents for preimage and second preimage attacks are halved for qubit operations due to Grover's algorithm: for SHAKE256, $2^{\min\{256,\ell\}/2}$, etc.  (The costs of quantum collision search are sometimes reported to divide the exponent by three, but this is not really an accurate measure of the cost; I'd rattle off some citations but I have other work to do right now.  Patches welcome!)

Note that while SHA3-256 is usually treated as an independent random oracle from SHA3-512, and while the derivative of another SHA-3 candidate BLAKE2b-256 is also usually treated as an independent random oracle from BLAKE2b-512, in contrast the functions SHAKE256-$\ell$ for all $\ell$ are dependent because they are all just $n$-bit truncations of the same SHAKE256 function.  This also means that the length of the output need not be known ahead of time before computing SHAKE256.


What is the canonical way of creating Merkle tree branches? I'm currently looking into creating some compact Merkle tree branches to prove that a given hash was included in a given Merkle root. My initial thought was to list the leaf, the Merkle root and all of the hashes that the given leaf was combined with to make the Merkle root.

So in this example:

I would state

Leaf:  12c5
Root:  2f9c
Nodes: [d187, a8b5, 1328, d063]

However, since the order of nodes matter for creating the Merkle root, I would also need to list whether the node was on the left or right side.

I'm wondering if is there a canonical way of listing this information to create the Merkle branches?

If you have the index of the leaf, it describes the path from it to the root.

Specifically, the binary representation is a series of left (0) and right (1) turns from the root. If you're working your way up, the least significant bit says if the leaf is a left (0) or right (1) child, the next bit refers to the leaf's parent, etc.

This illustration makes it obvious:

The numbers on each node are the binary representation of that node's index in its layer.

So just listing the index of the leaf whose membership is being proven provides enough information to validate the proof.

Here's some simple pseudocode for validating a proof:

func isValidProof(leaf, index, nodes, root):
  currentNode = leaf
  for node in nodes:
    if index mod 2 == 0:
      currentNode = hash(currentNode, node)
    else:
      currentNode = hash(node, currentNode)
    index = index >> 1 // shift 1 right is essentially like dividing by 2, ignoring the remainder
  return currentNode == root


Largest message size for XChaCha20-Poly1305 libsodium documentation says that XChaCha20-Poly1305 can encrypt a message of arbitrary size.

However, the only specification available (still a draft) explains that under the hood the IETF version of ChaCha20-Poly1305 is used (in combination with HChaCha20 for key derivation), which implies at the very least a hard limit of 256GB because of the 32 bit counter.

Who is right, and how large can a message be at most to be safely encrypted with XChaCha20-Poly1305?

And what about the authenticated data?

You should email the libsodium maintainers and the internet-draft author and ask them to talk to each other to work out what they mean, and to clearly document the limits in the internet-draft.  (They sometimes post here but not often.)

In principle, XChaCha provides $2^{256}$ 512-bit blocks of output under a single key, indexed by a 256-bit input.  The only question is how they are carved up for messages vs. blocks within a message.

For the XSalsa20 stream cipher, the message number is 192 bits, and the block number is the remaining 64 bits, so the theoretical limit on the number of blocks per message is $2^{64}$, or $2^{70}$ bytes.
For the Salsa20 stream cipher as in eSTREAM and as in NaCl, and for the related ChaCha stream cipher, the message number is 64 bits and the block number is the remaining 64 bits, so again the limit on blocks per message is $2^{64}$.
For the IETF ChaCha stream cipher of RFC 7539, the message number is 96 bits and the block number is 32 bits, so messages are limited to 256 GB.
The current XChaCha-Poly1305 internet-draft, draft-arciszewski-xchacha-03, is defined in terms of the IETF ChaCha-Poly1305 AEAD of RFC 7539 as a subroutine, in §2, p. 3, but it follows the XSalsa20 API, so the message number—which is a parameter to the API—is 192 bits, but the block number—which is managed internally by the API—is 32 bits; the remaining 32 bits of the internal ChaCha input are fixed to zero.
In what libsodium seems to implement for crypto_aead_xchacha20poly1305_ietf, according to the XChaCha20-Poly1305 construction page (archived 2019-05-30) and the AEAD limitations table (archived 2018-11-07), the message number is 192 bits and the block number is 64 bits, like XSalsa20.

If the byte order of the block number is chosen appropriately, this should be compatible with draft-arciszewski-xchacha-03 in the sense that it can correctly implement any protocol following the internet-draft, but it also allows much larger messages that are not allowed by the internet-draft.
It is also possible that the block number encoding is mismatched so that libsodium's crypto_aead_xchacha20poly1305_ietf is incompatible with draft-arciszewski-xchacha-03—I haven't checked.

All that said, the distinction between a 32-bit block number and a 64-bit block number is essentially academic: the largest message any implementation is willing to receive is the largest amount of memory that an adversary waste in a denial of service before you can drop the message on the floor.  It is hard to imagine applications for which this amount should reasonably be beyond a few megabytes, let alone 256 GB—larger messages can simply be broken up into smaller pieces at negligible additional cost since the per-piece overhead is at most a few dozen bytes, even if you include the 192-bit nonce and some formatting metadata.


AES Cipher Block Chaining 128 bit message I understand that for AES CBC you need to split the plaintext up into blocks and perform XOR'ing using the previous blocks calculations etc.

However, if your message is exactly 128 bits long, do you only perform the XOR with the IV and the encryption with the key once? Or is there a way to split up a 128 bit message so that you can perform the cipher block chaining method as intended.

Thanks.

However, if your message is exactly 128 bits long, do you only perform the XOR with the IV and the encryption with the key once? Or is there a way to split up a 128 bit message so that you can perform the cipher block chaining method as intended.

This is a non-starter, as there is nothing wrong with performing a single block encrypt in CBC mode. For 128 bits messages you don't need any padding method, even for CBC mode, but generally we try and apply PKCS#7 padding for compatibility reasons.

The XOR of the unpredictable IV with the plaintext is required, otherwise your cipher would not be able to handle identical messages without leaking information. If your 128 bit messages are unique by itself they you could just use a single block encrypt of the block cipher (the attacker would only know that no repetition is present in the messages).


Public key in fully homomorphic encryption over the integers I'm reading “Fully Homomorphic Encryption over the Integers” by van Dijk et al.

I wonder why $x_0$, which is a component of the public key, should be an odd number?

(even number mod even number) is always even number and (odd number mod even number) is always odd number. If $m=0$, the result of modular $x_0$ will be always even number. If $m=1$, the result will be odd number. So $x_0$ should be a odd number.


A hash functin based on XOR and matrix multiplication Imagine an $n$ bit to $n$ bit hash function defined as follows: Let $K$ and $K'$ be two random predetermined $n\times n$ matrices. Then the hash function $h$ of an $n$ bit number $a$ would be:

$$h(a)=K\cdot a\oplus K'\cdot \bar{a}$$

Note that addition in matrix multiplication is done on one bit, so it's equivalent to $\oplus$ operation, Now my question is that if this function is reversible.

First note that the following holds:

$$h(a)=K\cdot a+K'\cdot \bar a=K\cdot a+K'\cdot(a+1^n)=\underbrace{(K+K')}_M\cdot a+\underbrace{K'\cdot 1^n}_c=M\cdot a+c$$

Also note that $h(a)=M\cdot a$ is an universal hash function for $n$-bit input and $m$-bit output, as $\Pr\left[h(x)=h(y)\right]=2^{-m}$ with the randomness being over the choice of $M$. Clearly in this case $M=K+K'$ both of which are random matrices so this clearly holds. Now note that adding $c$ is essentially just a permutation over the bit values which doesn't change the collision properties, so it preserves the universality.

Also note that the first observation means that given $n+1$ chosen input-output pairs you can fully recover a description of $h$ and recover all information that you could from $Ma$ about $a$ when given $h(a)$. The strategy to the recovery would be to request $0^n$ and get $c$ this way. Then request $0^n$ with the $i$-th bit set for all $n$ values of $i$ to learn all the columns / rows of the $M$ matrix.


Can you explain to me how permuted congruential generator XSL-RR-RR works? I found note about XSL-RR-RR on wikipedia:
https://en.wikipedia.org/wiki/Permuted_congruential_generator
But I don't understand what this means:

count = (int)(x >> 122)
low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)
high64 = rotr((uint64_t)(x >> 64), low64 & 63)
return (uint128_t)high64 << 64 | low64

What is difference between rotr and rotr64? What is "int"? Is rotr64((uint64_t)(x ^ (x >> 64)), count) doing rotr64 by count steps (am I understand it right)? What is "|"? And what is "uint64_t"? At least I understand "^", "&" and ">>".
Is XSL-RR-RR eliminate low bits periods known from typical LCG? As I understand that's why it was invented.

I have read a bit about C syntax and I seem to understand what this generator does.

count = (int)(x >> 122)

>> is the right bitshift operator, shifting all the bits to the right a specified number. So initial number $x$ is shifted by $122$ bits. It means count is number consist of first $6$ most signifficant bits of $x$. Type of this data is int, because it could be every $0$-bit, $1$-bit, $2$-bit, $4$-bit, $5$-bit, $6$-bit number.

low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)

^ is just XOR operation. After xoring we can get every $128$-bit number, that's why there is introduced type uint64_t. It means we have to cut our result to first $64$ least signifficant bits. Rotr64 rotates the bits $x$ to the right by $n$ places around a $64$-bit boundary, which means we rotate (uint64_t)(x ^ (x >> 64) by count places.

high64 = rotr64((uint64_t)(x >> 64), low64 & 63)

Here we have the same operations like above except & which is the logical AND operator.

return (uint128_t)high64 << 64 | low64

In the end we get $128$-bit number (uint128_t). high64 bits are shifting on most signifficant bits positions and | is the logical OR operator. All $64$ least signifficant bits after << 64 will be equal to $0$. So OR operator just copy all $1$ and $0$ of low64 to $64$ least signifficant bits in our final $128$-bit number.
And $x$ is just number taken from typical linear congruential generator modulo $2^{n}$. Author specified in the documentation two multipliers and increments, which we can use:
$m=2549297995355413924$, $i=4865540595714422341$
and
$m=6364136223846793005$, $i=1442695040888963407$


Counter mode with $\operatorname{AES}_k(m)$ vs $\operatorname{AES}_m(k)$ In theory, for an ideal cipher $E_k: \{0,1\}^{128} \to \{0,1\}^{128}$, it would be completely fine to use the key and the input interchangeably, but obviously AES is not perfect. For AES128, the key size and the block size are the same. What would the security implications of using the key in place of the input block and vise versa be? I understand that it would be quite inefficient as the key schedule would need to be re-calculated for every block, but would it make cryptanalysis easier?

Encryption and decryption would be possible by putting the cipher in a modified counter mode. Where $n$ is the nonce, $i$ is the counter/position of the block, $C$ is ciphertext, and $P$ is plaintext:

\begin{align*}
C_i &= E_{n \mathbin\| i}(k) \oplus P_i\\
P_i &= E_{n \mathbin\| i}(k) \oplus C_i
\end{align*}

Actual counter mode is:

\begin{align*}
C_i &= E_k(n \mathbin\| i) \oplus P_i\\
P_i &= E_k(n \mathbin\| i) \oplus C_i
\end{align*}

This is a purely hypothetical question and I have no intention of doing something so silly.

I understand that it would be quite inefficient as the key schedule would need to be re-calculated for every block, but would it make cryptanalysis easier?

It would make cryptanalysis trivial.

If the attacker knows that

$$P_i \oplus C_i = E_{n \mathbin\| i}(k)$$

and he knows $n, i, C_i$ and has a guess for $P_i$, he can recover $k$, and use that to decrypt everything else.

This works because, with AES, $E_k$ has an inverse $E^{-1}_k$ that's efficiently computable, assuming you know $k$.  There's no corresponding "inverse" corresponding to the message block, and so the "message block" and the "key" inputs to AES are not interchangable from a security standpoint.


Pseudocode for constant time modular exponentiation I'm looking to implement modular exponentiation (for RSA) in constant time, but most of the examples I've found are more mathematical descriptions of the operations. Are there any references with descriptions in psuedo-code, which are understandable (and implementable!) by someone without much of a math background?

No.  If you don't have a strong math background, implementing RSA yourself is a  bad idea (and perhaps even if you do).  There are many ways to go wrong, which can open up subtle security weaknesses.

Instead, you should use a well-vetted RSA implementation from a standard crypto library, and a well-vetted protocol -- or hire a cryptographer who does understand the mathematics, if you don't think you can trust any existing implementation or need help selecting one that is suitable.


Is it possible to derive an asymmetric algorithm from a symmetric one? Given the advancements in quantum computing, there's a lot of incentive to move away from the usual asymmetric cryptography. Is there a way to turn a symmetric algorithm (e.g. AES) into an asymmetric one?

Besides the hash based signature constructions mentioned by @CodesInChaos in the comments, it is entirely possible to build an asymmetric cryptosystem from a secret key one. Granted, the secret key ciphers in question are not typical, such as AES, but ones that support homomorphic operations on ciphertexts.

Homomorphic Encryption

A cipher supports a homomorphic operation on ciphertexts if $D(E(m1) * E(m2)) \equiv m1 * m2$, where $*$ is some operation such as addition or multiplication.

Note that the operation performed on the ciphertexts does not necessarily have to be the "plaintext" operation: For example, the Paillier cryptosystem utilizes multiplication on ciphertexts to compute the addition of plaintexts.

Additionally, some such ciphers also offer the following property: $D(E(m1) + m2) \equiv m1 + m2$.

These properties can be used to create public key encryption systems.

An example

One example is provided in Fully Homomorphic Encryption Over The Integers:

A public key consists of many secret-key encryptions of 0
Random elements of the public key are summed together to form a ciphertext, and the message is added to the ciphertext

$ciphertext := pb_{r_0} + pb_{r1} + pb_{r2} + ... + pb_{rn} + m$

Decryption applies the decryption operation of the secret key cipher to obtain the plaintext message

In the above example, inverting a public key ciphertext without the private key is equivalent to solving a subset sum problem.

Acquiring the private key from the public key requires analyzing the secret key cipher that is used to instantiate the scheme. In the above design, they base the hardness of their secret key cipher on the Approximate Greatest Common Divisor problem.

However, you can instantiate such a scheme with any cipher that can perform the specified operations.

Now, the security of the constructed schemes is another question. But the mechanisms can be constructed. Additionally, many such schemes are not nearly as efficient as they would need to be in order to be utilized in practice: The ciphertexts and public keys can get huge.

More examples

Merkle's original knapsack cryptosystem can be deconstructed similarly.
Aside from encryptions of 0, you can also release encryptions of $1, 2, 3, ... N$ and sum elements randomly, with a final adjustment to set the message equal to your plaintext. (This requires a modular reduction step in order to function)
Or, there is another encoding still: release encryptions of powers of 2, as well as some 0s. Then, sum together some 0s randomly, then combine appropriate powers-of-2 such that the plaintext equivalent is equal to the message. (Powers of 2 are weight-1 words; They consist of a single set bit)
The last scheme that I know of is to release some encryptions of 0. Then, to encrypt, multiply each element of the public key by a large random (plaintext) integer, sum the results, then add the message to the ciphertext. This one seems to offer the prospect of smaller public keys then the alternatives.

$pb_0 r_0 + pb_1 r_1 + pb_2 r_2 + ... + m$

I have yet to encounter such a scheme that is built using multiplication as the homomorphic operation; All of the above require only addition. By that I do not mean such schemes do not exist, I just don't know of any.

(Note: multiplication by plaintext is supported when ciphertexts support addition: $E(m) + E(m) \equiv E(m) * 2$

Why doesn't AES work with any of these?

"Normal" symmetric primitives are designed to destroy any semblance of structure. It's just a lot easier and faster to drown the information in impossibly complicated equations then it is to formulate something simple enough to provide the required properties while still providing security. Since the constructions need to be simple, it usually means the numbers need to be big, and this comes with a cost.


Authentication and integrity I was trying to solve this problem:

Sometimes Alice needs to send a file to Bob, guaranteeing her identity and the file integrity (no confidentiality
required); the two parties are sharing a secret w and make use of a hash function $H$ that outputs 40-bit numbers and a symmetric encryption $E$.
Each time they use the following (pre-agreed) protocol.

A → B: $E_w(nA)$, where $nA$ is a nonce (Alice sends a challenge).

B → A: $E_w(nA+1)$ (Bob proves he knows the secret, providing response to challenge).

A → B: $(F, H(F),E_w(H(F)))$ (Bob, given $F$, computes $H(F)$ and $E_w(H(F))$, and then compare his results to data
actually received)

**1.Show how an attacker can act in place of Alice and send a file to Bob tricking him into
believing that the file is coming from Alice.

2.Fix the protocol without significantly perturbing it too.**

*My answer to 1:
The attacker can do Man in the middle attack.
Suppose Trudy impersonates Bob's network address.
1.Alice sends w{nA} to Trudy.
2.Trudy sends w{nA} to Bob.
3.Now Bob will send w{nA+1} to Trudy, which she will use it to send it to Alice.
4.After Trudy sends w{nA+1},
Alice will send (F, H(F),w{H(F)}) to Trudy, thinking she is Bob because she proved her that she is Bob.

Scheme:

A → T: $E_w(nA)$
T → B: $E_w(nA)$
B → T: $E_w(nA+1)$
T → A: $E_w(nA+1)$
A → T: $(F, H(F),E_w(H(F)))$

Is my answer to question 1 correct?
How do I solve the 2nd question?

Best Regards.

Q1 asks “Show how an attacker can act in place of Alice and send a file to Bob tricking him into believing that the file is coming from Alice.”

In your answer, Trudy simply relays the traffic to the two parties without doing anything else, thus this is not really an attack that achieves what is asked. Note that whatever Bob receives is truly coming from Alice in this session.

Hint for Q2: the problem in the protocol is that Bob cannot verify that the last message is fresh, and it can come from a previous session intercepted by Trudy (replay attack).


When NIST disallows the use of 1024-bit keys, what effect will that have on SHA-3 (with max. 512 bits)? Quoting the article Gone in 60 Months or Less:

  The National Institute of Standards and Technology (NIST) has disallowed the use of 1024-bit keys after 31 December 2013 because they are insecure. Rapid advances in computational power and cloud computing make it easy for cybercriminals to break 1024-bit keys. When a researcher from Ecole Polytechnique Fédérale de Lausanne (EPFL) in Switzerland cracked a 700-bit RSA key in 2007, he estimated that 1024-bit key lengths would be exploitable 5 to 10 years from then. Not even three years later, in 2010, researchers cracked a 1024-bit RSA key.

So, we're talking about a 512-bit "cryptographically secure" hash meeting cipher implementations where 1024-bit keys are not disallowed anymore by the end of the year 2013.

What does that mean for SHA-3, as the NIST submission sets the rate $r$ as 1152, 1088, 832, or 576 (144, 136, 104 and 72 bytes) for 224, 256, 384 and 512-bit hash sizes, respectively? Can we still think about using SHA-3 to hash passwords to the desired bit-length and comply to NIST rules on the long run, or do we need to expect NIST gradually starting to enforce that 1024-bit key rule across all protocols?

That's not the same kind of key.
Symmetric keys are a bunch of bits, such that any sequence of bits of the right size is a possible key. Such keys are subject to brute force attacks, with a cost of $2^n$ for an $n$-bit key. 128 bits are way beyond that which is brute-forceable today (and tomorrow as well). If a block cipher is "perfect," then enumerating all possible keys is the most efficient attack (i.e., "no shortcut").
RSA keys are mathematical objects with a lot of internal structure. In a 1024-bit RSA key, there is a 1024-bit integer value, called the modulus: this is a big integer whose value lies between $2^{1023}$ and $2^{1024}$. To break an RSA key, you "just" have to factor this modulus into its prime factors. There are relatively efficient algorithms for that, to the extent that factoring a 1024-bit RSA modulus is on the verge of the feasible. It has been estimated that the "cost" of factoring a 1024-bit RSA modulus is similar to the "cost" of brute-forcing a 77-bit symmetric key. Note that this is not the same kind of cost (you need a lot of fast RAM for factoring big integers, whereas enumerating many AES keys requires no RAM at all).
DSA and Diffie-Hellman keys are also mathematical objects, with again a lot of internal structure. There is also a modulus, but a prime one, so it is not about factorization, but something else, called discrete logarithm. It so happens that breaking discrete logarithm modulo an $n$-bit prime has a cost that is roughly similar to the cost of factoring an $n$-bit RSA modulus (the DL cost is, in fact, a bit higher). So a 1024-bit DSA or DH key is also similar in strength to a 77-bit symmetric key (or maybe an 80-bit symmetric key).
Elliptic curve cryptography yet again uses mathematical objects as keys, but with another structure that fits in fewer bits for a given security level. Basically, you get "$n$-bit security" (resistance similar to that of an $n$-bit symmetric key) with a $2n$-bit curve.
Hash functions have no keys. Yet there is a concept of resistance to various attacks (collisions, preimages, second preimages...) with costs that can be estimated depending on the function output size (assuming that the function is "perfect"). For a hash function with an $n$-bit output size, resistance to collisions is in $2^{n/2}$, resistance to preimages (and second preimages) is in $2^n$. (There are ongoing discussions about making SHA-3 faster by relaxing this latter value, i.e., having "only" 128-bit security against preimages with a 256-bit output length.)

See this site for lots of data on comparative strength estimates. In particular, these NIST recommendations illustrate their point of view:

1024-bit RSA/DSA/DH and 160-bit ECC are "as good" as an 80-bit symmetric key.
2048-bit RSA/DSA/DH and 224-bit ECC are "as good" as a 112-bit symmetric key.
3072-bit RSA/DSA/DH and 256-bit ECC are "as good" as a 128-bit symmetric key.
7680-bit RSA/DSA/DH and 384-bit ECC are "as good" as a 192-bit symmetric key.
15360-bit RSA/DSA/DH and 512-bit ECC are "as good" as a 256-bit symmetric key.

NIST also says that the "80-bit" security level should be shunned except when mandated for interoperability with legacy systems.
These five formal "security levels" are the reason why AES was defined with three key sizes (128, 192 and 256 bits -- the two lower levels mapping to 2DES and 3DES), and SHA-2 with four output sizes (SHA-224, SHA-256, SHA-384 and SHA-512, the "80-bit" level being used for SHA-1); and, similarly, SHA-3 is (was) meant to offer the four output sizes 224, 256, 384 and 512 bits.


Are there any signature schemes that protect against collusion by multiple parties? Say I want to verify the identity of Alice, but Alice could be colluding with Bob to fool me. Is there any way to verify Alice's identity and also be sure that Bob is not impersonating Alice, e.g. using her private key?

No, this is not a security feature provided by asymmetric signature schemes, the way the concept is usually understood.

You have Alice's public key. Typically, you got it in a certificate issued by Carol. Let's assume (for the sake of argument) that Carol has a very strict certificate issuance policy, and only issues certificates corresponding to hardware devices with 100% reliable biometric identification mechanisms. Hence, when you receive a signature that verifies OK with Alice's public key, you can be sure Alice was present when the signature was generated. However, the signature doesn't tell you whether Alice was on the phone with Bob when the signature was generated.

If you want a signature to proves that the signer had no out of band communication with anyone at the time of the signature generation, you must make sure that the private key is stored and used in such way that no such communication would have been physically possible. Say, Carol has a policy only to issue certificates of the kind you require for hardware that consists in a remotely monitored Faraday cage that only fits a single person.


Is it possible to decrypt a ciphertext with a different private key? In public key cryptosystem, there are often two keys (pub and pri) and two functions (Enc and Dec) such that:

Enc(pub, m) = c
Dec(pri, c) = m

Usually pub and pri are generated as a matching key pair and used together. However, given a ciphertext c, without knowing pri, is it possible to successfully decrypt it into the original plaintext m with a different private key pri' other than pri?

No, it's not possible. If it was possible it would have a devastating impact on asymmetric cryptography in general.

Most asymmetric cryptosystems rely on mathematically problems that cannot be solved in polynomial time (such as integer factorization, or discrete logarithm).

Let's look at RSA:
you choose your $K_{pub} = (n,e)$ and $k_{priv} = (d)$ with $e \in \{1,2,\dotsc , \Phi(n) - 1\}$ to fulfill  the following equations:

$$\Phi(n) = (p - 1) \cdot (q - 1)$$
$$\operatorname{gcd}(e, \Phi(n)) = 1$$
$$d \cdot e \equiv 1 \bmod \Phi(n)$$

Every element in a group can have one inverse element at maximum, you can not find a $d'$ for which:

$$d' \cdot e \not\equiv 1 \bmod \Phi(n)$$

So instead of:

$$d_{k_{priv}}(y) = d_{k_{priv}}(e_{k_{pub}}(x)) = (x^e)^d \equiv x^{de} \equiv x \bmod n$$

you will compute:

$$d_{k'_{priv}}(y) = d_{k'_{priv}}(e_{k_{pub}(x)}) = (x^e)^{d'} = x^{d'e} \equiv m' \not\equiv m \bmod n$$

So you will be able to compute the decryption with a different $d'$, but your result $m'$ will have nothing in common with the original $m$.


Is AES key and cipher distance measurable? Could this be translated into a cost function? Given a plain-text, two keys, and two cipher-texts:

p: plaintext
k: actual key and k': predicted key
c: actual cipher and c': AES(p, k')

Can you calculate the degree of incorrectness of k' in NP-deterministic/NP-easy time? Does err(k, k') or err(c, c') exist?

The impetus of this question is to develop a cost function in a deep learning algorithm. Currently, there is the possibility for only one cost function C(k, k')= (k != k) or C(c, c') = (c != c'). This function shows zero cost for a correct guess and full cost for an incorrect guess—this cost function will never improve the learning of the network...

Currently, there is the possibility for only one cost function $C(k, k')= (k \neq k)$ or $C(c, c') = (c \neq c')$. This function shows zero cost for a correct guess and full cost for an incorrect guess

Not quite. Hamming distance is an obvious candidate, as in the comments. Another candidate might be the compatibility of the two permutations $E_k$ and $E_{k'}$ or  $$\#\{x:E_k(x)=E_{k'}\}.$$ There are other distances on permutations such as Kendall tau, as well.

It's probably going to be difficult to do this except at a reduced scale, so I remain skeptical. Maybe try it on weaker or reduced round ciphers.


ECCS: Elliptic Curve Cryptography Cramer Shoup Introduction

I know how to do Cramer-Shoup with cyclic groups. But how do I do it in elliptic curve cryptography (ECC)?

Cramer-Shoup with cyclic groups

Following was taken from Wikipedia: https://en.wikipedia.org/wiki/Cramer%E2%80%93Shoup_cryptosystem

Key Generation

Alice generates an efficient description of a cyclic group $G$ of order $q$ with two distinct, random generators $g_1, g_2$.
Alice chooses five random values $({x}_{1}, {x}_{2}, {y}_{1}, {y}_{2}, z)$ from $\{0, \ldots, q-1\}$.
Alice computes $c = {g}_{1}^{x_1} g_{2}^{x_2}, d = {g}_{1}^{y_1} g_{2}^{y_2}, h = {g}_{1}^{z}$.
Alice publishes $(c, d, h)$, along with the description of $G, q, g_1, g_2$, as her public key.  Alice retains $(x_1, x_2, y_1, y_2, z)$ as her secret key. The group can be shared between users of the system.

Encryption

To encrypt a message $m$ to Alice under her public key $(G,q,g_1,g_2,c,d,h)$,

Bob converts $m$ into an element of $G$.
Bob chooses a random $k$ from $\{0, \ldots, q-1\}$, then calculates:

$u_1 = {g}_{1}^{k}, u_2 = {g}_{2}^{k}$
$e = h^k m$
$\alpha = H(u_1, u_2, e)$, where ''H''() is a universal one-way hash function (or a collision-resistant cryptographic hash function, which is a stronger requirement).
$v = c^k d^{k\alpha}$

Bob sends the ciphertext $(u_1, u_2, e, v)$ to Alice.

Decryption

To decrypt a ciphertext $(u_1, u_2, e, v)$ with Alice's secret key $(x_1, x_2, y_1, y_2, z)$,

Alice computes $\alpha = H(u_1, u_2, e) \,$ and verifies that ${u}_{1}^{x_1} u_{2}^{x_2} ({u}_{1}^{y_1} u_{2}^{y_2})^{\alpha} = v \,$.  If this test fails, further decryption is aborted and the output is rejected.
Otherwise, Alice computes the plaintext as $m = e / ({u}_{1}^{z}) \,$.

The decryption stage correctly decrypts any properly-formed ciphertext, since

$ {u}_{1}^{z} = {g}_{1}^{k z} = h^k \,$, and $m = e / h^k. \,$

If the space of possible messages is larger than the size of $G$, then Cramer–Shoup may be used in a hybrid cryptosystem to improve efficiency on long messages.

Questions

How to convert Cramer-Shoup into ECC?
How do I prove the security of ECC Cramer-Shoup?

Literature

Cramer, Ronald, and Victor Shoup (1998). “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack.” Advances in Cryptology—CRYPTO'98, Lecture Notes in Computer Science, vol. 1462, ed. Hugo Krawczyk. Springer-Verlag, Berlin, 13–25.

Crosspost: https://math.stackexchange.com/questions/3643951/elliptic-curve-public-key-encryption-schemes-cramer-shoup

How to convert Cramer-Shoup into ECC?

Because Cramer-Shoup restricts itself to using only group operations (and never using a single value as both a scalar and a group member), it can translate directly into elliptic curve group operations.  What you quoted are the operations listed in multiplicative form, and so:

When the protocol says to select a cyclic group $G$ of order $q$, you'd pick an elliptic curve, with $q$ being the order of the large prime subgroup.
When the protocol specifies $g^x$, this is the point multiplication of $g$ times the scalar $x$, that is, what is more typically written as $x \cdot g = \underbrace{g+g+...+g}_{x\text{ times}}$
When the protocol specifies $gh$, this is point addition of $g$ and $h$, which is more typically written as $g+h$
When the protocol specifies $g/h$, this is point subtraction of $g$ and $h$, which is more typically written as $g-h$

For example, the original has $c = g_1^{x_1} g_2^{x_2}$; this would be understood as (written in additive notation) $c = x_1\cdot g_1 + x_2 \cdot g_2$.  That is, you perform the point multiplication of the scalar $x_1$ with the point $g_1$, and you perform the point multiplication of $x_2$ with the point $g_2$, and then you add the two resulting points.

The hardest part would be the conversion of $m$ into an elliptic curve point.  Of course, you can avoid the issue entirely if you're doing hybrid crypto (just pick a valid point $m$ randomly, and then use $KDF(m)$ as the transmitted symmetric key).  If that doesn't work for your scenario, one alternative method is to encode the value $m$ into some of the bits of the $x$ coordinate, and they try random settings of the remaining bits until you get a valid $x$ coordinate (e.g. if you're using a Weierstrass curve with $p>3$, then $x^3 + ax + b$ is a quadratic residue); then, select the $y$ coordinate from the two possibilities randomly.

  How do I prove the security of ECC Cramer-Shoup?

The proof in the original Cramer-Shoup paper assumed that the Decisional Diffie-Hellman problem was hard in the group; as long as you select a curve where that is also hard (pairing friendly curves are not an option), the original proof would apply.


Testing hash functions for collision resistance I was hoping to implement a software that allows testing a user-defined hash function for cryptographic properties (Meant to pique interest in cryptographic hash function for a school showcase), as well as compare them with well-known hash function to identify their hash functions strong points & weak points. However the property collision-resistance got me into a bit of a pickle.

The first obvious thought that occurred to me was the Birthday Paradox Attack, where given that we only with to find an instance of a hash collision
(henceprob of hash collision should assumed to be 0.5 or above)
thus if the hash function finds a collision on 2^(n/2) operations consistently.

The second option that I considered was to count the length of the hash value & determine the size of the pool for all possible hash values. From there on we prepare a plaintext list of that size to check if the hash values are distributed evenly across the hash value space.

The problem with the two proposed solution I given was that given that the hash value length is significantly large (256 bits or more) this might prove to be an hassle given the large amount of brute force needed to thoroughly check for collisions. Also I was hoping for a more refined way to identify their hash functions flaws.

I am currently looking at length extension attack, the way it functions sounds like a type of differential cryptanalysis attack, I was hoping that I can use this to derive a collision using the padding exploit. (By understanding how they pad. maybe I can use the same type of trick to result in a collision, am still unsure of how exactly it works so I might be completely wrong here)

Other than the methods mentioned above, is there any other ways that I can accomplish this?

I think calculation of probability is not a good idea. Because your pool is gonna greater when you want to work with complex hash algorithms (for ex: sha256/512...)It may work just for md5 or sha1.
I suggest you to check out also Linear Cryptanalysis Attack to understand Differential Cryptanalysis deeply.

Good luck


One-time token to decrypt a local file I am trying to achieve the following:

Encrypted files are stored on users filesystem. The user uses my client to authenticate against a server. Once he is authenticated successfully he gets a token to decrypt the files.

Things I want to ensure: the user should not be able to cache the token for later use. like a one time token, so that he is no longer able to decrypt the files in some time in the future.

The client and server do only exist in my head, so anything that is possible can be applied to it. I am looking for algorithms/protocols to achieve my requirement.

I don't think that's possible, at least not without the kind of intrusive mechanisms you'd need for reliable DRM.

Basically, if the user gets a key that lets them decrypt the files, what's to stop them from just decrypting them all and keeping the decrypted versions?

The only way this could possibly work if you only allowed access to the files through a program you control, which would present them to the user in a way that makes them hard to copy (like rendering video directly to the screen).  Then you'd need to prevent the user from modifying the program or running it under a debugger, or finding some way to copy the data anyway as it's presented (e.g. through the "analog hole").

All that's easier said than done — and once you've done it (as well as you can), you may find out that it still won't stop a clever and determined user from copying the data, but that it will piss off ordinary users because all the restrictions make them feel like they're working in a straitjacket.


What MAC did SSLv3.0 use? How did it compare to HMAC in TLS 1.0 and above? According to Wikipedia:

TLS has a variety of security measures:
Using a message digest enhanced with a key (so only a key-holder can
check the MAC). The HMAC construction used by most TLS cipher suites
is specified in RFC 2104 (SSL 3.0 used a different hash-based MAC).

What hash-based MAC did SSLv3.0 use?  How does it compare to the ubiquitous HMAC that is used everywhere else today?

The key was concatenated in SSL 3.0:
    hash(MAC_write_secret + pad_2 +
         hash(MAC_write_secret + pad_1 + seq_num +
              SSLCompressed.type + SSLCompressed.length +
              SSLCompressed.fragment));

but XOR'ed in HMAC:
    H(K XOR opad, H(K XOR ipad, text))


Why was ISO10126 Padding Withdrawn? Wikipedia mentions ISO10126 Padding has been withdrawn, but doesn't say why. Also there were no news reports about this, as far as I can see.

Why was it withdrawn? Are there security flaws? Is there maybe a new version?

Indeed, ISO 10126-1:1991 and ISO 10126-2:1991 titled Banking -- Procedures for message encipherment (wholesale) have been withdrawn circa 2007.

The padding specified by ISO 10126 was adding random until the message has length 7 (mod 8) bytes, then adding a byte coding the number of bytes added (including that byte), making the length 0 (mod 8) and suitable for DEA/DES block encryption. The rationale for adding a little randomness is dubious at best; it creates a subliminal channel, for no clear advantage.

I conjecture that the rationale of the withdrawal is not the padding algorithm, but rather the use of single-DEA/DES (56 bit key), which is clearly obsolete and insecure; and availability of other standards for the same purpose.


Scheme that encrypt with $n$ pk that any sk of the pks can decrypt? Suppose there are $n$ users each with public/private key pair $(pk_i,sk_i)$ $i=1,\cdots,n$. Is there any scheme that I can encrypt $m$ using the set of public keys $(pk_1,\cdots,pk_n)$, and can decrypt it using any $sk_i$?
That is $C=Enc_{(pk_1,\cdots,pk_n)}(m)$ and $m=Dec_{any\ sk_i}(C)$.

This is meaningful when these $n$ users are just a small portion of a group of $N$ users. A bit like "ring encryption" (opposite to ring signature). Thank you!

This is in no way practical, but it's relatively easy to describe a scheme.

If the public key contains (or allow easy derivation of) a unique prime (just has to be unique among the recipients - If every recipient knows the public key of any other recipient, and public keys can be ordered, we can use the first $n$ primes.), say $r_i$, you can use:
$$
C=\prod_{i=1}^n r_i^{\operatorname{enc}_{pk_i}(m)}
$$
(where $\operatorname{enc}$ is the function for encrypting to one recipient).

Then for decryption you "just" need to determine factor $C$ and determine the highest power of $r_i$ that divides it, and put the exponent into the function for decryption to one recipient.

I haven't tried to prove that it isn't easier to break this than to break than to break the scheme it's based on. I can't see why it would be though, and given how impractical this is, I don't think it matters much.


Is there a simple zero knowledge proof of $x$ for $b=x^x\pmod p$? We have a multiplicative cyclic group $G$ which is a subgroup of $(\mathbb{Z}/n\mathbb{Z})∗$. There are two parties, Alice and Bob:

If:

Alice knows: $b$ and $x$ such that $x^x = b$;
Bob knows: $b$.

Then what's the easiest non-interactive way Alice can prove to Bob the knowledge of $x$ without leaking $x$?

The original question was:

Alice knows: $a,b$ and $x$ such that $a^{(x\cdot x)} = b$
Bob knows: $a,b$

and DrLecter referenced this paper (fixed the link), which covers the question.
Now, the question was changed to

Alice knows: $b$ and $x$ such that $x^x=b$;
Bob knows: $b$.

The given structure was:

... multiplicative group $G$ which is a subgroup of  $(\mathbb{Z}/n\mathbb{Z})$

And a sub-question in the comments was, if this is easy if $n$ is prime. The answer in this case is: "It depends".
As poncho pointed out, if $x>n$ is allowed, you can find a $x$, if you consider the exponent and the base independently (let's call the modulus $p$ for being prime):

$x=b$ mod $p$
$x=1$ mod $p-1$
Since $p$ is prime, we can apply the Chinese Remainder Theorem to get $x= p^2 - bp + b$.

So for $x$ without restrictions, there is no need for a ZKP, because it is easy to calculate the solution from $b$ and $p$ alone.
Now the tricky part: What if $x$ is limited to $x<p$?

In general, there is no solution, because there is no structure which would be preserved by a function $x\rightarrow x^x$. I can't even think of a way to check if for a given $y$ there exists a $x$, s.t. $x^x=y$.

But what we can prove is that there can be no such zero knowledge proof:

Bob knows $b$.
If $b=1$, the solution is $x=p-1$ or $x=1$, this means $x<p-1$.
If the modulus is prime, he can check if $b$ is a quadratic residue.
$x$ has a factorization in $\mathbb{Z}$, and for every prime factor $x_1$ of $x$, we know that $x^{(x/x_i)}$ has to exist, because $x^a$ is well-defined for every $0\leq a\leq x$, if $0<x<p$.
If $b$ is a quadratic nonresidue, then there exists no quare root, and we know that $x$ does not contain a factor $2$ (in $\mathbb{Z}$).

A similar approach can be made for every prime factor of $p-1$, because the according exponentiation with this factor is a non-injective function.
This is a contradiction to ZK already, because knowledge of $b$ reveals already some information about $x$.


What is the difference between authenticating and signing a document? Authenticating a document means to verify it is from the sender. But it seems like signing a document also verifies it’s from the sender. What exactly is the relationship or difference between “authenticating a document” and “signing a document”? Are they the same thing?

Authentication can either mean entity authentication or data authentication.

Data authentication is a means to demonstrate that some specific data originates from a specific source and has not been modified during transmission and/or upon storage. It can be achieved by the use of digital signatures in a public key, i.e., asymmetric, setting or message authentication codes (MACS) in a secret key, i.e., symmetric, setting. Digital signatures support public verifiability and thus using the respective public key (which is assumed to be known by anyone) given the signature and the data anyone can check if the data has been authenticated by the holder of the corresponding private key. In contrast, using MACs only support private verifiability, i.e., only parties holding the respective secret key can verify whether a given data has been authenticated by any of the other parties holding the respective secret key.

Entity authentication is a means to prove to someone else that the entity it is speaking to is indeed the entity it is claiming to be. This can be achieved by various means such as challenge response authentication protocols (which may be based on digital signatures).

Often this is not explicitly stated, but it should be clear from the context what type of authentication one is referring to.


Is the difference distribution table of AES S-box uniform? I am studying about various block ciphers and their weaknesses, so I have a doubt about AES S-boxes, Is the difference distribution table of AES uniform ?

The difference distribution table for the AES s-box contains mostly probability 2/256 differentials. However, there is a single probability 4/256 for each input/output difference. I uploaded a dump of the table here so that you can see.

The code used to produce this table can be found here. Disclaimer: This is my personal github.

If by "uniform", you mean all values equal, the case is no. If you meant "differential uniformity", that is a term with a precise meaning:

From this paper, they define differential uniformity as "A mapping is called differentially uniform if for every non-zero input difference and any output difference the number of possible inputs has a uniform upper bound".

The AES s-box is a differential 4 uniform function


Do all PAKE assume that all parties already have a password? I was looking for a means to perform a key exchange without relying on a PKI. I discovered Password Authenticated Key Exchange (PAKE) and after reading J-PAKE; I have the following questions:

Do PAKE assumes that involved parties already have a shared message?
 in J-PAKE, they used an extension of Diffie-Hellman Key agreement to establish the shared message. However, I don't understand how they prevent Man-in-the-Middle attacks.
 In general, how does PAKE prevent Man-in-the-Middle attacks?

Do PAKE assumes that involved parties already have a shared message?

Some do, some don't.  In general, there are two flavors of PAKEs; balanced (where both sides do know the password), and augmented (where only one side knows the password; the other side knows enough to recognize it).

J-PAKE is a balanced PAKE.

  in J-PAKE, they used an extension of Diffie-Hellman Key agreement to establish the shared message. However, I don't understand how they prevent Man-in-the-Middle attacks.

Going through it thoroughly would require going through a set of cases; however here's a nutshell: each side expects to receive (in successive messages) proof of knowledge of $x_2$ and $x_2 \cdot S$ (or $x_4$ and $x_4 \cdot S$); the MITM cannot fake both of those (without knowing $S$), and so those have to be forwarded untampered.  The adversary is them limited with tampering with $x_1$ and $x_3$; we can show that that doesn't give him an advantage either.

  In general, how does PAKE prevent Man-in-the-Middle attacks?

Well, with all PAKEs, if the attacker has a correct guess to the password, they can do MITM attacks or impersonation attacks (and because the password really is the only way the protocol has to perform authentication, we can't do better).  What a PAKE does try to do is make sure that the attacker is forced to test only one password per attempt (either MITM or impersonation); if he wants to test ten passwords, he needs to interact with a legitimate party ten times (for example, MITM ten separate exchanges).

How they to that varies, of course.  J-PAKE relies heavily on its proofs of knowledge; EKE encrypts the Diffie-Hellman keyshares (so that a MITM would need to guess a specific password for an attempt to work); CPACE uses a password-dependent DH base value (again, so you need to guess a specific password for an attempt to work); OPAQUE has the client and server do a multiparty computation on secrets that the client and the server has for the client to rederive the key needed to recover the private signature values (and the multiparty computation messages look completely random to a MITM).

It's fine that you're studying J-PAKE; just realize that other PAKEs work rather differently...