Private set intersection, using a semi-trusted server Alice has a set $S$ of words.  Bob has a set $T$ of words.  They want to compute the intersection $S \cap T$ of their words, with the help of a semi-trusted third party Trent.  Trent runs a central server.  The server is normally well-intentioned and not malicious.  However, we are concerned about the risk of server compromise: a hacker might be able to break into the server, download all data stored on the server, and even control the server for a limited period of time.  Our primary security goal is to make sure that an attacker who manages to compromise the server cannot learn the set $S$ or $T$.  Also, neither Alice nor Bob should need to receive a copy of the other person's set (apart from the intersection).

I am aware of a super-simple protocol for this problem.  Trent picks a random symmetric key $k$ for a pseudorandom function (PRF).  Alice and Bob apply the PRF with key $k$ to each of their words and upload the result to Trent's server.  In other words, Alice computes the set $S^* = \{F_k(s) : s \in S\}$ locally and uploads $S^*$ to the server, and Bob uploads $T^* = \{F_k(t) : t \in T\}$ to the server.  Now the server can help them find the intersection: the server computes $S^* \cap T^*$ and sends it to Alice and Bob, and this will be enough for each of them to recover the intersection $S \cap T$.  This protocol is practical and has the benefit of being very easy to explain.  It is basically an application of (keyed) one-way hashing.  And, as long as the key $k$ is not stored on the central server, compromise of the central server does not lead to a violation of the confidentiality goals.

My question: Is this super-simple protocol approximately optimal?  Or is there some other protocol that provides even better security?  I'm familiar with all of the sophisticated protocols for private set intersection.  Do any of them offer any security advantages for this particular setting?  I'm most interested in practical benefits, rather than theoretical/foundational considerations.

This arises from a real-world problem involving data matching (matching of voter registration lists between multiple states, if that's relevant).

Your simple approach is not bad, but you might consider these modifications:

First, you don't need a PRF, any form of hashed key or a simple hash over the concatenation of a key and the element should be enough. Basically any one-way function over elements and some sort of key should do the trick, and you can optimize for speed.
The key is not chosen by Trend but Alice and Bob run a key exchange. There is no need for Trend to know the key at all. That means he can determine if two elements are equal but not get the element itself. With a keyed hash, even knowledge of the possible elements does not help if the server is compromised.
Both Alice and Bob send the hashed set to Trend, preferably already ordered to reduce the complexity of finding all equal hash values.
Trend sends the list of equal hash values back to both of them.
In a second step you can either use Trend again or leave it up to Alice and bob to make sure that they really have the same elements and not just the same hash value (different elements might have the same hash value). If you use Trend, Alice and Bob can run another key exchange and this time use symmetric encryption with this key and send the elements to Trend.


If a probabilistic encryption algorithm is used, how does decryption return the correct message? Given a key $k$ and a plaintext $p$, a deterministic encryption algorithm will return a ciphertext $c_1$. In a second trial, I run the same key and plaintext $p$ through the encryption algorithm and get ciphertext $c_2$ from the first trial. $c_1$ and $c_2$ are equivalent, so running the decryption algorithm on $c_1$ and $c_2$ both return $p$.

However, if a probabilistic encryption is used instead to encrypt $p$, the algorithm will run twice and return two different ciphertexts $c_1$ and $c_2$.

How does $Dec(c_1) = p$ and $Dec(c_2) = p$?? If $c_1$ and $c_2$ are different, should decryption return different results?

In a probabilistic encryption scheme, for every plaintext there is more than one possible ciphertext.

Here's an example—with lots of details not related to your question omitted, so don't take these scissors and try running with this at home!

The recipient knows the secret ~256-bit number $r$ of times that a base point $B$ must be added to itself to yield a public point $R = B + B + \cdots + B = [r]B$ on some standard elliptic curve, say Curve25519.  (There's a shortcut to computing $[r]B$ so you only have to do a few thousand arithmetic operations and not a mindbogglingly unimaginable number.)

To conceal a message $m$ using the public point $R$, the sender:

picks a secret ~256-bit number $s$ uniformly at random;
adds $B$ to itself $s$ times to obtain $S = [s]B$;
adds $R$ to itself $s$ times to obtain $[s]R$;
computes $k = H([s]R)$, a secret key;
computes $c = \operatorname{crypto\_secretbox\_xsalsa20poly1305}(k, 0, m)$, the authenticated ciphertext under the symmetric key $k$ and nonce 0; and
transmits $(S, c)$ to the recipient.

The recipient, on receipt of $(S, c)$, then:

computes $[r]S = [r\cdot s]B = [s\cdot r]B = [s]R$;
computes $k = H([r]S) = H([s]R)$, the same secret key as the sender derived;
computes $m = \operatorname{crypto\_secretbox\_xsalsa20poly1305\_open}(k, 0, c)$, or rejects if forged.

There are roughly $2^{256}$ possible sender secrets $s$ that could be used to encrypt the message, and they all work for any message $m$, so in this cryptosystem, for any message $m$ there are about $2^{256}$ distinct ciphertexts that have $m$ as the corresponding plaintext.

This is not simply an artificial example.  To meet the standard notion of security for public-key encryption, indistinguishability under adaptive chosen-ciphertext attack, there must be many ciphertexts for any given plaintext, randomly chosen by the sender.  Otherwise, an adversary without knowledge of the private decryption key can easily tell whether a challenge ciphertext conceals one of two (or three, or $n$) possible plaintexts by encrypting the candidate plaintexts and comparing the resulting ciphertexts to the challenge.  This implies that the minimum number of distinct ciphertexts for each plaintext must be around $2^{192}$ to give confidence in security against multi-target attacks.

There are also probabilistic symmetric ciphers, like AES-CBC with randomly chosen IVs affixed to the ciphertext, or crypto_secretbox_xsalsa20poly1305 with randomly chosen nonces affixed to the ciphertext.  In this case, the randomization serves to prevent the same message content at different times from leading to the same ciphertext and enabling an adversary to recognize repeated messages.

Randomization per se is not always necessary in the symmetric setting: it is sufficient to deterministically keep state for crypto_secretbox_xsalsa20poly1305 and transmit each successive message with a count of the number of messages sent so far, for instance.  But in some cases like AES-CBC it is obligatory—though of course you could use a secret pseudorandom function of the message sequence number, such as $\operatorname{AES}_k(\mathit{seqno})$, to choose the AES-CBC IV.


What is the probability of un-authenticated messages to go through CCM because of channel errors? Consider having the worst possible communications channel, where bits are flipped with probability 0.5.

Is there any probability that channel errors make the change in a frame go un-detected through CBC-MAC?

Is there any probability that channel errors make the change in a frame go un-detected through CBC-MAC?

For any Message Authentication Code, there is always a probability [1] that the modified message will just happen to verify against the modified tag.
In your extreme "worse possible case" scenario, it's quite simple to compute; your communication channel effectively replaces the message/tag with a completely random message/tag.  And, if we compute the MAC on a random message, the probability that it matches a random tag is $2^{-32}$ for a 32 bit tag.

[1]: Unless the errors are tightly constrained.  For example, with CBC-MAC with a full length tag, we will always detect any error if the error is constrained to be always within one block, with all the other blocks being transmitted correctly.  However, random errors (and active attackers) are generally not so accommodating with how they modify the message.


Distribution of hash values I was wondering if the uniform distribution of hash values is a generally required criteria for cryptographic hash functions.

The english wikipedia article only mentions four main properties. But it looks like the commonly used algorithms show a nearly perfect uniform distribution. So my question(s) would be:

Are hash functions supposed to have uniform distributed values?
(If so) Is it an explicit requirement or an implication of the second and last property mentioned by wikipedia (irreversibility + collision resistance)?
Are there any hash functions, currently used, that do not show such distribution?
Is there a scientific paper or article addressing this issue? (Unfortunately I was unable to find one)

The idea of a hash function is the idea of a random Oracle. For any given input, this Oracle should return a truly uniformly random output. This is ideal of how hash functions work, so any hash function that isn't uniformly random is not behaving the same way as a random Oracle. So yes, hash functions should have uniformly distributed values.

I don't believe it's necessarily an explicit requirement to be uniform, but not being uniform would certainly weaken the strength of the hash. For example, if the hash was a 'normal' distribution, certain outputs would be far more common than other. We could get collisions far easier then.

I'm unfamiliar of any cryptographic hashes attempting to reach a non-uniform distribution as I imagine they would be more vulnerable to collisions and preimage attacks. If you were so inclined, you could hash the values with a known uniform distribution use the output in a non-uniform distribution function.


Would the Intel SHA extensions help in creating SHA1 collisions? Would the Intel SHA extensions help in creating SHA1 collisions? AMD Ryzen and EPYC supports them.

If you break the attack into two phases, like in the SHAttered paper, it may help the first phase. The researchers say that they used a CPU cluster for the first phase; the more expensive second phase used a GPU cluster.

  ...from an attacker’s point of view, it may
  seem best to implement the attack on a CPU in order to be able to claim a better attack
  complexity. However, a GPU being far more powerful, it is actually much more efficient
  to run it on the latter: the attack of [18] takes only a bit more than four days to run on
  a single GTX 970, which is much less than the estimated 150 days it would take using a
  single quad-core CPU.

The trade-off is that GPUs may be more difficult to program, but on the plus side, they are more cost-effective.


ECDH/ECDSA key exchange on embedded devices Two devices are communicating only with each other and shall do this with AES encryption. Both devices are offline, have very limited storage and use a small cryptographic coprocessor which is able to perform AES/ECDH/ECDSA/RNG. Also keys and certificates can be stored in it. Any device must work with any other device, as they are not coupled in any way per default.
I planned on doing an ECDH key exchange to create random keys for the AES communication. Then I encountered the MITM problem, which makes ECDH alone invalid for creating random keys out of thin air without further validation.
If I wanted to use ECDSA I would need to store a certificate, which would be static for the entire life of the product, as I can't update it. It would also be the same for every device, as every device must be able to communicate with every other device. If the private key is compromised, so are all the devices.
I could also store a factory key in the devices and use that to transfer a randomly generated keys. For that I could directly use AES and ditch ECDH completely. The problem here is, that the factory key might get compromised, exposing all the other devices using the same key. As mentioned I could use a fixed public/private key pair, but I see no advantage in this case over simply using AES.
Then another problem: One device might stop working, which then needs a replacement. The new device would then have to exchange a new key with the old device. A function would be necessary, that makes the old device ditch its key and accept a new one. If an adversary knows the factory key, he could intercept the new key and listen to the communication.
I am looking for suggestions on how to approach this key exchange problem and make the system as secure as possible. Thanks in advance and BR.

You can assign each device its own unique certificate with a signature issued by the CA (for example, could be the manufacturer) on the certificate. So each device stores the following: its own unique certificate (its public key), its corresponding secret key, and the signature on its certificate issued by the CA. During key exchange, 2 devices would send each other their respective certificates plus the CA's signatures on those certificates, which can be verified using the CA's public key.


Can you get two unpredictable hashes from the same message with, e.g. SHA1? I'd like to create a database of questions and answers so that an attacker with access to the database can't obtain either the questions or the answers.

If H0 and H1 are secure hashes, looking up the answer to a question might proceed as follows:

lookup(H0(question)) -> value
H1(question) XOR value -> answer

Can this be done securely with a hash function such as SHA1?

I've looked at HMAC, which could be used to combine the message with additional strings. The additional strings wouldn't be secret. Would access to one MAC weaken the other?

Btw.: The answer would be the same size as the hash.

EDIT

To answer a question that was asked -- the application is unique. The database would be publicly accessible, and anyone could store a question, answer pair. The encryption would be done client-side, so the server would never see plaintext. You shouldn't be able to get any useful information from seeing the database itself.

I'd need to know precisely what the "lookup" operation does but I'm pretty worried already by that XOR. Let's remove the lookup operation for now and see what happens.

Suppose we have two hashes that hash to the same length ($L$) and we XOR their outputs. You've now got a much weaker hash that either of them.

Here's how to find a collision. Hash a message $m$ using $H_0(m) \oplus H_1(m)$ to produce an output $h$. We now wish to find a collision on $m$, such that $h=H_0(m') \oplus H_1(m')$

We now create a series of messages $m_i$ that are slightly different to $m$. The goal here is to find a message which has a xor of $H_0(m_i)$ and $H_1(m_i)$ equal to that of $H_0(m)$ and $H_1(m)$.

Let's assume that $H_0$ and $H_1$ behave like random oracles. In that case, the probability of this happening is approximately $2^{L\over2}$. Each oracle will take the message $m_i$ and produce a random bit string of length $L$. The probability that they collide will be $2^{L\over2}$ by the birthday paradox.

There's a slight difference here in that we're not after a precise collision but for them to have a fixed XOR. Even so, this event will happen with the same probability. We're just changing the meaning of the equality.

Note that this attack is not the typical birthday attack against a hash. The typical birthday attack finds a pair of message $m'$ and $m$ that hash to the same value. Here, I'm taking a known fixed hash value for one message and finding collision for it. That should normally take $2^{L-1}$ time but this attack demonstrates it in $2^{L/2}$ time. Thus, this scheme is completely unsafe.


Secret Sharing Scheme, with joining players, no central entity I am facing the the following problem:
Lets assume i have a secret, $S$, I want to share it to $N$ players so that $K$ of them can cooperate in order to obtain the secret ($K$,$N$ scheme).
Is there a scheme that supports the joining of a new player where a set of $K$ players can issue a new key without obtaining the secret itself resulting a $(K,N+1)$ scheme and with no central entity meaning there is no dealer after the first dealership.

This is a classic problem that can be solved with secure multiparty computation. When a new player joins, the $K$ parties who approve them joining run a secure computation protocol to generate their share. Concretely, if Shamir sharing is used, then the function computed is "reconstruct the polynomial $p$ from the $K$ shares input, and output the share $p(\alpha_{N+1})$, where $\alpha_1,\ldots,\alpha_{N+1}$ are field elements and $\alpha_i$ is associated with party $P_i$.


Why are there $ signs in my passwd file? I am trying to get access to my eReader and I managed to get the passwd file.

root:$1$hdhxObPx$TYFuTKsB9GGIgo53rF4bi1:0:0:root:/:/bin/sh
bin:*:1:1:bin:/bin:
daemon:*:2:2:daemon:/sbin:
nobody:*:99:99:Nobody:/:
s3c2440x::507:507:root:/:/bin/sh

I expected to see a standard hash string there or just "x" but this reminds me of something I have seen in MySQL databases, can anyone point me in the right direction please? What am I looking at?

Crypt based password hashes have several parts separated by $

The hash type, 1 in your case, this stands for MD5-crypt (this is not plain MD5)
The salt, hdhxObPx in your case
The actual hash TYFuTKsB9GGIgo53rF4bi1 in your case
Some schemes have additional parameters, such as a work-factor, but this does not apply to the scheme used in your example.

The MD5-Crypt scheme should be avoided, in favor of modern schemes, such as bcrypt (usually starting with $2a$). Not because MD5 is cryptographically broken, but because it has a constant work-factor, that's too small for the computational power modern attackers can field.

Check out crypt (C) on Wikipedia for further information.


Discrete Log with regard to a random base Suppose DL is hard in $G=\langle g \rangle$. For a uniformly random group element $r \in G$ (suppose $r=g^a$), is it hard to find $s$ given $r^s$ and $r$? Does the computational assumption have a well established name?

I can show it at least as hard as DDH, because if $\mathcal{A}$ can find $x$ given $g^y$ and $g^{xy}$, she can distinguish $(g^x,g^y,g^{xy})$ from $(g^x,g^y,z)$ where $z$ is a random group element.

You are asking if it is hard to find $s$ given $r^s$, but you do not mention if $r$ is also given.

If $r$ is not given, then the problem is: given some value $y$ find $r$ and $s$ such that $r^s=y$. This is an easy problem - just outputs $r=y$ and $s=1$.

If $r$ is given, then the problem is: given $(r,y)$ find $s$ such that $r^s=y$, where $r,s$ are randomly chosen. This is a form of the discrete log problem where the base is random. This makes it ``harder'' in the sense that the adversary cannot preprocess. I don't know if it has anything more established than this.


Verification of identity by certification authority I have question about how a user's identity is verified by a Certification Authority.

As I understand it, the process works as follows:

User generates his private key and (with the help of private key) generates his public key.
Now user want to register his public key. For this, he has to send the public key to CA.
User send Certificate request to the CA.

How will the CA know the user's identity for registration?

Can someone please explain it mathematically?

First of all, as already mentioned in the comments, there is absolutely no mathematics or cryptography involved.

Independent of the model used, i.e., public key cryptography, identity based cryptography, or certificateless public key cryptography (as i summed up in my answer here), the identity verification must be established by other means.

In the wild (currently) only public key cryptography is widely used and PKIX (PKI based on X.509 certificates) is the predominant "standard". Here, the user who generates the key pair sends a certificate signing request (including the public key, identity attributes - which should be included - and a proof that the user holds the corresponding private key - which is established by signing the request) is sent to the certification authority. As already noted in the comments, the "proof of possession" of the respective private key is required to be sure that the user does not come up with the public key of some other user (for which he does not possess the private key).

Then, how the identity verification is done before issuing the certificate mainly depends on the purpose of the certificate, i.e., the corresponding private key.

For instance, many countries, as widely encountered across Europe, have deployed national electronic identity (eID) solutions, where the respective private key can be used to sign documents, and such signatures are equivalent to handwritten signatures. There, you typically have an explicit verification of identity, e.g., by showing up with your smart card (which stores the private key) at a certified registration authority or by offering an online service for activation and the activation code is then send by traditional mail (which you can only receive by showing an official credential such as a passport).

However, this practice is quite different for SSL certificates (which makes up the biggest part) or software signing certificates.

Hopefully, this answers your question and I did not miss anything that should be said.


One time pad ciphers in emails In order to achieve very high security for privacy, would it be cryptographically secure to use one time pad ciphers in emails? The distribution of the keyword would pose no problems since I would distribute it to other people in person, therefore avoiding interception.

Just to avoid confusion, by keyword I mean a random string of bits as long as the message.

In order to achieve very high security for privacy, would it be cryptographically secure to use one time pad ciphers in emails?

OTP offers perfect secrecy, so if it's feasible to use it, it is secure.

However, OTP alone offers no authentication and leaves the message malleable. If Alice sends a message Y to Bob, standing for 'yes', Mallory can guess this and modify the message to say N instead (but he would garble the message if he thought it said something different).

You would need to add a MAC to get authentication as well.


How does ECDHE_RSA key exchange mechanism work? Using Wireshark, I found these data exchanged with google.com over TLS:

Client Hello

possible cipher suites and possible curve types (eg. secp256r1) sent

Server Hello

cipher suite selected

Certificate

RSA certificate signatures exchanged, etc. (hopefully, not important for me)

Client Key Exchange, Change Cipher Spec, Hello Request

ECDHE pubkey sent to server

New Session Ticket, Change Cipher Spec, Hello Request, Application Data

session ticket received, etc. (hopefully, not important for me)

Ok, and now my question: What I learned, I need curve equation, random point on it and the finite field size (for modulo operation) in order to apply ECC.

The only thing I found was the pubkey of size 520 bits, which should represent:

1st 8 bits - base 16 prefix
next 256 bits - X coordinate of the "random point"
last 256 bits - Y coordinate of the "random point"

Ok, I have the point, but what about the curve equation and the field size?

Does the curve secp256r1 define only one specific curve? (I suppose not, so where/how is it defined?)

What is and where to find the size of the field? (Or is there only one size for given standard? ...don't think so.)

Thank you for Your answer.

PS: This is how I understood the topic, if I'm wrong, please, correct me. :)

Curve secp256r1 is not a type of curve; it is a curve, and is standardized under that name by SECG, under the name P-256 by NIST, and under the name prime256v1 by ANSI. It also happens to be the by far the most common elliptic curve used in cryptography. The field size, curve equation, and generator point are all part of the curve spec; the point of having a standardized curve is that it takes time to generate elliptic curve parameters, and there's no need for different people to use different curves.

Incidentally, based on your not mentioning the generator point you might be a bit mistaken on how the "random point" in ECDH is created. An ECDH key doesn't just have a randomly selected point for a public key; rather, you randomly pick an integer $k$ as your private key, and then compute the public key as $kG$ for a known point $G$. Like the curve parameters, both parties must know $G$; like the curve parameters, there's no reason why everyone in the world can't use the same $G$. So, this generator point is also part of the curve spec.

You also missed a crucial step in ECDHE: the ServerKeyExchange message. This is a mandatory part of ECDHE exchanges, and comes after the Certificate message and before ServerHelloDone. This has the server's ephemeral ECDH public key; the ClientKeyExchange has the client's ephemeral key.


Worth taking performance hit of HMAC to gain additional security? It seems like SHA-512 truncated to 256 bits is usable as a MAC [1].  The advantage is that it's ~50% faster than HMAC-SHA-256 on 64-bit CPUs and ~50% faster than HMAC-SHA-512 on short inputs.  (My use case involves mostly short inputs.)

However, the HMAC construct provides an extra layer of protection in case of collisions in the underlying hash function [2].  This extra protection ended up being practically useful when weaknesses were found in MD5 and SHA-1.

Because of this, it seems better to use truncated HMAC-SHA-512 over truncated SHA-512.  Is that a reasonable (e.g. not-overly-paranoid) choice?

If we assume that 1 and 2 are true then HMAC-SHA-512 is a better choice.

For the time comparison, as stated Paul Uzsak, if there is no specific time relevant problem around ~50% faster shouldn't be considered. If more secure, then use it.

For your comment;

The shatter attack on SHA-1 requires a degree of freeness in the hashed data as in PDF's. This attack may or may not apply to other formats, but still, SHA-1 is considered broken and it is already non-standard, kick out.

With the identical-prefix collision attack probably you cannot forge the MAC with this method. We haven't seen any complicated attack that uses the shatter attack to break some other constructions, yet.

The output of SHA-1 is 160-bit and it is in the generic birthday-attack range for our computing powers, especially for a collective like bit-coin miners who reached $2^{91.6}$ SHA-256 hashes per year on 25 September 2018.

512-bit is not prone to generic collision attacks. This will require $2^{256}$ hashes to find a collision with probability 50%. For SHA-256, it is still impractical for today's standards $2^{128}$ and this is equal to brute-forcing AES-128 up to some constant.

When a new attack occurs for a hash function we have to look at it so that what the attack can be used when the hash function used in HMAC construction. However, as noted by the Forest

  In particular, an HMAC demands much weaker security guarantees from the hash function than many other applications it may have. It only requires weak collision resistance from the underlying hash.

For the security case You should be prepared to move into new standards. Even if there is not an attack to carry a collision attack into a HMAC construction, you should immediately move away from that hash function into more secure one.

note: Weak collision resistance is the second pre-image resistance:

it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given $x$, to find a 2nd-preimage $x' \neq x$ such that $h(x) = h(x')$.


How can I get the message which was encrypted before (when decrypting a product cipher) ? I want to make a product cipher containing s box and p box.
where message
$m = \{m_1, m_2, m_3, m_4\}$ where $m_i \in \{0, 1, \dots 25\}$ for $i=1,2,3,4$.
p-box: $P(x_1, x_2, x_3, x_4) = (x_1, x_3, x_2, x_4)$
S-box: $\mathbb{Z}^2 \rightarrow \mathbb{Z}^2$ where $\mathbb{Z} \in \{0, 1, \dots, 25\}$
$S(x,y)=(x+k_1 y \bmod 26, k_2 x + y \bmod 26)$
$K = (k_1, k_2)$ where $k_1, k_2 \in \{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}$

Encryption:

let key k = (k1, k2) = (3, 5)
Let M = {4, 8, 12, 13}
P - box: p(M) = {4, 12, 8, 13}
s - box: S(4, 12) = (4 + 12 × 3(mod 26), 5 × 12 + 12 (mod26)) = (14, 6)
         S(8, 13) = (8 + 13 × 3(mod 26), 5 × 8 + 13 (mod26)) = (21, 1)
cipher Text = {14, 6, 21, 1}

Decryption using S - box:

S(14, 6)
a + 3b(mod26) = 14
5a + b(mod26) = 6

and

S(21, 1)
a + 3b(mod26) = 21
5a + b(mod26) = 1

I am however unable to solve these equations.

Where I'm stuck

Solving for S(14, 6).

5a + b(mod26) = 6 multiplying this equation with 3 and then subtracting a + 3b(mod26) = 14.

We get 14a(mod26) = 4

To solve this I guess we need multiplicative inverse of 14 in Modulo 26 which does not exists. So we get multiple values for a and b.

So the message gets decrypted with multiple solutions. The original message plus some random messages.

How can I get exactly the message which was encrypted before?

You don't need 14. You need the inverse of 7 which is 15.

$$14 a  = 4 \mod 26$$

$$7 a = 2 \mod 26 $$

$$a = 2 * 15 \mod 26$$

$$a = 4$$


What is the fastest way to generate a truly random one-time pad without electrical or any other complicated device? I want to generate a truly random one-time pad as fast as possible, but without the use of any electrical or any other complicated device. What is the fastest way to do that?

We are going to generate a large number of truly random letters for use as a one-time pad (sometimes also referred to as Vernam Cipher).

Get your hands on about fifty six-sided dice--they are easy to order from a gaming company--and a shakeable box with a lid, and the box is about 30 centimeters square.

Build a random table: on a piece of paper, draw or print a table with six columns and six rows. Number the columns and rows, 1 to 6. Doing that sequentially should be fine. Put the dice in the box and shake, rattle, twist, and roll--use your own judgment. This step should not be short. Let the dice fall to one side of the bottom of the box and put them in rows of two.  Now start filling in your table according to the pairs of dice aligned in the box. Row/Column. 1/4 A, 4/3 B, 5/1 C, etc. Keep going until all letters of your alphabet have been entered.  If you are using a Russian alphabet, you will have three empty spaces.  If you are using an English alphabet, you will have ten empty spaces.

Generate your key: Shake, rattle, twist, and roll--consult the table to get your results:  5/1... C | 6/2... X | 1/1... P | etc. Repeat. Don't take any shortcuts.  Don't look at your results and say they are not random because there are too many of one number next to each other in the box. This is what it can sometimes look like. Don't introduce bias.

Secure your key: physical security is an important issue now.  You have to protect that key against compromise. If you can also share that key securely, then the traffic you create will at least have been enciphered with a real one-time pad.

Furthermore: you also have two additional problems--how will you authenticate your message, and will it have integrity?


Question about entity authentication Say party A wants to make sure they are communicating with party B, and not an eavesdropper E. Then they will use an authentication scheme to do this.

But what if there is an eavesdropper on the line, who waits until the authentication is complete, and then steps in a poses as party B when it is finished? Then A will still think she is communicating with B. How is this prevented?

This is prevented by:

by requiring authentication of B using a private key only known to B and a public key trusted by A;
by making sure that messages are protected by a message authentication code (MAC) / authentication tag, created using a session key only known to A & B.

Step 2 requires a key agreement step, e.g. Diffie-Hellman or the encryption of a secret by A to B using the public/private key pair of B.

I'm guessing that step 2: message authentication codes is what you're after. Message authentication codes provide integrity and authenticity for the messages they protect.

Note that you may also want to protect against replay attacks. Replay attacks however do not let E pose as B.


Can "(input * X) mod Y" with N iterations be computed in less than N operations? I think a simple question but here it goes (and sorry for my lack of math notation skills):
Given input I, a fixed factor X and fixed modulo Y and N iterations, does the process need to be performed consecutively in N steps, or can it be sped up?
I=12345
X=655573
Y=54321
for N=0; N < 10000; N++ {
    I=(I*Y)%X
}

This algorithm is computing $$I'=I\cdot Y^N\bmod X$$. Using a standard square and multiply algorithm you need at most $\lceil 2\log_2(N)\rceil+1$ modular multiplications to compute $I'$.  This is about 33 multiplications for the given example of $N=10,000$ which probably counts as this algorithm being "predictable".


Can I use the same key pair for authentication and Diffie-Hellman? Assume Alice has a key pair $(A, a)$ and Bob has a key pair $(B, b)$, where $A = Ga$ and $B = Gb$. In general, the basic rule of crypto says that we should not use the same key for different operations, like in signing and encryption, but I wonder whether in my use case it would be actually possible to use it. Below, I describe the simplified version of my use case.
So Alice and Bob are communicating over an anonymous network, like for example Tor. Also, Alice and Bob from time to time publish (independently of course) some data signed with their private keys.
Alice doesn't know Bob, and Bob doesn't know Alice. They only are aware of their advertised identity keys A and B. Alice when sending the message $m$ to Bob uses Diffie Hellman to derive a shared key. First, for each new message, she generates a new ephemeral key $x$ and computes the key shared with Bob as $k = KDF(B^x)$ (alternatively, maybe she could first apply some Hash function on B, i.e., h = H(B) and compute $k = KDF(h^x)$, not sure? ). Next, Alice encrypts $m$ as $c = AES_k(m)$. She concatenates $g^x$ and $c$ as $v = g^x || c$ and sends it to Bob.
So, in my use case, Alice doesn't reveal any information about herself due to the freshly generated ephemeral key and the anonymous channel (which I assume is secure). She doesn't learn anything about Bob others done his identity public key $B$. Also, as long as Bob's secret key is kept safely no one should be able to decrypt the content of $c$ except for Alice and Bob, which is crucial.
So, is there anything that can go wrong here? If for example Bob published let's say a document signed with his private key $b$, does this allow anyone to infer any information about $m$? In general, my question is whether I'm missing any attack which might compromise the confidentiality of the communication between Alice and Bob? Many thanks in advance!

While it's technically not (probably) an issue, you should definitely avoid sharing keys between different purposes. RSA uses separate keys for signing and encryption, for example, since an encrypted-and-signed message would cancel out. RSA only signs a hash of the original message, negating this issue, but it still avoids sharing keys because it's simply better not to use the same keys for different purposes.


Encrypt symmetric session key with asymmetric or symmetric master key? Every day, I must backup my server's files, encrypt the backup, and upload it to untrusted cloud storage (dropbox, s3, etc.)

I've spent time on security.stackexchange where I discovered the typical approach is:

encrypt the backup with random one-time symmetric key ("session" key), for speed
encrypt the session key with an asymmetric key ("master" key: the public key in a public/private keypair)
upload the encrypted backup and encrypted session key to cloud storage

But I don't understand: why not use another symmetric key as the master key? Put another way: there is no key exchange here, as I am both "sender" and "receiver" - so how do I benefit from using an asymmetric key as master?

(For example, I'm using gpg, so my server could store a symmetric key with a 100-char passphrase, and use it to encrypt the daily session keys.)

Symmetric cryptography could well work here, to be honest.

The main advantage of public cryptography in this setting is that you can encrypt by just using a public key. So you'd get the following operations:

Setup:

create public / private key pair;
encrypt private key with password.

Encryption:

create random session key;
encrypt session key using public key;
encrypt data with session key and random nonce.

For decryption:

decrypt password-encrypted private key;
decrypt session key using private key;
decrypt data with session key using random nonce.

In other words, during encryption you  don't need access to the private key and therefore you don't need a password either. You just need to make sure that you don't leak your temporary session key.

This seems to be particularly useful for backups where backing up is frequent and commonly automated, while the restoration is commonly manual and infrequent.

Notes:

the private key may also be otherwise protected, e.g. stored on a USB-stick or generated within a smart card (exporting the public key after key pair generation);
instead of deriving a key per session you might also want to generate a symmetric key per file - beware that some modes such as GCM have clear restrictions about the amount of data that can be processed by one key;
restoration is often too infrequent, don't forget to test your restoration initially and frequently thereafter.


Timing attack on modular exponentiation It is known that computing $a^x \bmod N$ takes $O(|x| + \mathrm{pop}(x))$ multiplications modulo $N$, where $|x|$ is the number of bits of $x$ and $\mathrm{pop}(x)$ is the number of $1$ bits (Hamming weight). This suggests a side channel attack by measuring the run time of the exponentiation.

Can the number of $1$ bits be derived from the run time, and can it somehow speed up finding of $x$ if $a$ and $N$ are known (assuming no countermeasures are used)?

Which countermeasures can be done?

Timing attacks against a function $f_k$ generally require two things:

The attacker might observe the target perform $f_k(x)$ for a large number of sufficiently diversified known inputs $x$.
For each $k$, there are inputs $x$ and $x'$ such that $f_k(x)$ and $f_k(x')$ are expected to execute at different speed.

Now, let's assume $f_k$ is the private key operation of Diffie-Hellman or RSA, that $k$ is the (fixed) private exponent of the target, and that the inputs are, say, 2048 bit integer values. Normally, the implementation of the operation $f_k(x) = x^k \mod p$ is such that it executes the exact same number of CPU instructions regardless of the value of $x$, so there will be no timing difference to observe (presuming the CPU performs e.g. a MUL or DIV at a fixed number of clock cycles).

There are however things to watch out for. If some $x$ is significantly smaller than the maximum size of 2048 bits and the implementation of modular multiplication is optimized to account for that, some of the least or most significant bits of $k$ might leak, depending on if the exponentiation implementation iterates the bits of the exponent from right to left or the other way around. Since the intermediate result grows exponentially, this will only reveal at most 11 bits of the exponent in the most unfavorable case of $x=2$.

To prevent this leak (again assuming the CPU performs a MUL instruction etc at a fixed number of cycles independently of the value of the operands), all that is needed to prevent such leaks is to justify the size of all inputs to the size of the modulus at the beginning of the exponentiation function implementation.

Now, next case, suppose the attacker is able to repeatedly slow down the system, at a time that averages out at the moment the target will either perform a modular multiplication because the corresponding bit of the private exponent $k$ is $1$, or not perform a modular multiplication because the bit is $0$. It suffices to say that if the modular exponentiation is e.g. performed by the CPU in a multi-threaded application, this can be done with some statistical accuracy, if the attacker somehow might control what else is executed by the CPU, either passively or actively.

One trivial way to blind the private key even in such cases, would be to always generate a fresh random integer $z$ that is invertible $\mod q$ where $q$ is a multiple of the order of $x$ (e.g. $p-1$ if the order is not known). Instead of calculating $f_k(x) = x^k \mod p$, you would calculate

$k' = kz \mod q$
$y = x^{k'} \mod p$
$w = y^{z^{-1}\mod q} \mod p$
return $f_k(x) = w$

The only step here that depends on the private exponent is the first, which has to be assumed to not vary in performance time depending on the value of $k$. The overhead of this method is on average a factor of 2, presuming modular inverses in $Z_q$ can be calculated in negligible time.

Another technique would be to make the number of modular multiplication completely independent of the bits of the private exponent, e.g. by using a sliding window technique. This means that a table of $2^m$ integers is built, and one of these values is picked for every $m$ bits of the binary representation of the private exponent. It should however be noted that this technique might make matters worse, e.g. if the time for picking one of the integers from the table depends on the index of that element.

It should also be noted, that while it has been advocated to blind the input value $x$ to-be-raised, instead of the private exponent, this will have no effect on a CPU that executes MUL independently of the value of the operand, and have no effect at all against both passive and active timing attacks that measure the timing differences relative to which bit position in the exponent is being processed.


Design question for a service that signs messages on behalf of a user I'm working on a messaging service that lets users author messages and have them signed with an RSA key. The key is used for identity purposes only and can be revoked, so compromising the private key is annoying, but does not expose proprietary information.

Still, in order for a service to sign on behalf of a user, that user must either provide the key's passphrase (or even the key and passphrase) and have it go over the wire on each signing, or the key is stored by the service without the user's passphrase.

In either case the service itself must be trusted since at some point they will have access to the key in an unprotected form.

So the question is, what is the better design (other than "don't do it"): require the passphrase on each signing event, or rely on the service to store the key without the original passphrase and require them to ensure safe keeping (using their own passphrase, encrypt it otherwise, etc). Or is there a third way by which the service can sign on behalf of the user without exposing the private key at all?

Clarification: The idea is that the user maintains portability of their identity, i.e. they could use their key to sign and publish messages themselves or provide the key to a new authoring service they pick instead, i.e. the key follows the user, not the service.

Store the key encrypted. Send the encrypted key to the user and have them decrypt it and sign the message. Whatever your objections are to this scheme, they are most likely either misguided or can be addressed by the implementation of the scheme.


Why is the point at infinity on Edwards Curve different to Weierstrass curves? If I understand correctly, the identity point on all elliptic curves is the point at infinity.
But on the Edwards curve, this can be written in Affine form?

Does this have something to do with the fact that Edwards curve formulas are complete?

What would the point (0,1) be on the Weierstrass curve signify? If b=1, then we can represent this point on the Weierstrass curve?

It still has not clicked with me, the fact that the point at infinity is in the group, yet it cannot be represented? But somehow it can b represented on the Projected form, which is another form of the same curve? Whereas Montgomery is a different curve entirely?

In mathematics, every group need and identity element. The points on the elliptic curves forms a group. Therefore they need an identity element, too.
The identity element is determined by the addition law of the curve. Some curves need a point at infinity $\mathcal{O}$ as the identity element (neutral element).
In the Edwards curve, the neutral element is chosen as $(0,1)$ and this can be represented in the affine coordinates. Other coordinate like $(0,-1)$ can be identity, however, this requires different formulas.

If I understand correctly, the identity point on all elliptic curves is the point at infinity.

No not necessarily. Edwards curves doesn't need a point at infinity.

But on the Edwards curve, this can be written in Affine form?

Yes, it is $(0,1)$

Does this have something to do with the fact that Edwards curve formulas are complete?

No, it is just by the equation of the curve and the defined addition law. This is very similar to the analogous to clock

What would the point (0,1) be on the Weierstrass curve signify? If b=1, then we can represent this point on the Weierstrass curve?

Converting formulas exist like this one

Fast Algorithm for Converting Ordinary Elliptic Curves into Binary
Edward Form

it still has not clicked with me, the fact that the point at infinity is in the group, yet it cannot be represented? But somehow it can b represented on the Projected form, which is another form of the same curve? Whereas Montgomery is a different curve entirely?

An birationally equivalence doesn't say about the representation of the elements. Consider the isomorphism of two group, they are same but they can be completely defined over different sets.
The the neutral element can be defined but you force it to be defined over the affine coordinates. Some curves need the protective coordinates so that every element can be represented with some coordinates.


How does Dragonfly key exchange work, in non-white-paper terms? I'm trying to understand WPA3, whose Simultaneous Authentication of Equals is supposedly similar to Dragonfly Key Exchange.

Dragonfly is resistant to dictionary attacks, meaning that rather than an attacker being able to identify the use of a password in their dictionary with passive computation, they are forced to interact with one of the parties to make guesses.

I'm having trouble understanding the description of Dragonfly in the link, which is the only one I can find. How do Dragonfly's properties arise from the arithmetic? Is it some property of the "hunting-and-pecking" that only the non-attacker parties can perform the computation?

Dragonfly is resistant to dictionary attacks, meaning that rather than an attacker being able to identify the use of a password in their dictionary with passive computation, they are forced to interact with one of the parties to make guesses.

Actually, the goals are a bit more than that; even if you have an active attacker that can either modify the exchanges taking place, or can impersonate one of the end points (and attempt to negotiate with someone who does know the password), the best they can do from $N$ exchanges is to test $N$ entries from their dictionary.
We know that such an adversary can do at least that much; with a single exchange, they can take an entry from the dictionary, and (assuming that entry is the password) perform the exchange honestly with the valid endpoint, and see if the exchange fails or not.  The goal of a PAKE (such as Dragonfly) is that they can't do any better than that generic attack.

How do Dragonfly's properties arise from the arithmetic? Is it some property of the "hunting-and-pecking" that only the non-attacker parties can perform the computation?

No, the hunting-and-pecking procedure $P = \text{HuntAndPeck}(\text{Password})$ is a public method of mapping a password to a 'group element' so that:

The group element $P$ generates a prime sized subgroup; that is (using Finite Field terminology) the values $P^x \bmod p$ (for various values of $x$) can take up exactly $q$ values (where $q$ is a large prime).

For two different passwords $\text{Password1}$ and $\text{Password2}$, the two values $P1 = \text{HuntAndPeck}(\text{Password1})$ and $P2 = \text{HuntAndPeck}(\text{Password2})$ are unrelated; that is, no one knows the value $x$ for which $P1^x \equiv P2 \pmod p$.

Instead, the PAKE properties arise from the actual protocol.
The RFC format is a horrid way to describe cryptography, and so here is the protocol in a nutshell in the honest case (still using the Finite-Field terminology, and eliminating sanity tests both sides run):
Alice and Bob run the Hunt-and-Peck procedure to convert their password into a group member $P$ (and since this is the honest case, we'll assume they have the same password).  Then, Alice picks random values $p, m$, and transmits the values $s = p + m \bmod q$ and $E = P^{-m}$, and sends those to Bob.  Bob also selects values $p', m'$ and sends $s' = p' + m' \bmod q$ and $E' = P^{-m'}$ to Alice.
Alice then computes $(E' \times P^{s'})^p$; this is $(P^{-m'} \times P^{p' + m'})^p = P^{p p'}$.  Bob does the same computation, and gets $P^{p' p}$, which is the same value, and so we have our shared secret.
Now, why is this secure?  The attacker is allowed to submit any $s', E'$ value it wants to Alice (subject to the sanity test that Alice runs); however (because of how the hunt-and-peck procedure works), he does not know a value $E'$ where he knows the values $x, y$ for $E' = P1^x$ and $E' = P2^y$ for two different passwords; hence if he can predict the value $(E' \times P1^{s'})^p$ for $P1$, he cannot know the value $(E' \times P2^{s;})^p$, and so he is effectively limited to testing one password (which we know he can do).
One final note: reviewing the Dragonfly RFC, I see that it would (as written) leak some information if you run in on an elliptic curve that doesn't have a prime number of points (that is, has a cofactor $h > 1$).  If you're using (say) the NIST curves, that's not an issue; if you try to adapt it to run over (say) Curve25519, that would need to be addressed...


Multi-key decryption Let's assume I want to send a secret message to $N$ recipients in an asymmetric way.

My message could be encrypted with $N$ different public keys $p_i$ one after another and send to each user individually. In practice only a symmetric key $k$ is sent in an asymmetric way I guess, but that's not the point.

Even direct symmetric encryption comes into mind where the key $k$ is encrypted with each $p_i$ once and attached to message body afterwards. Of course the message length grows with rising $N$.

So I wonder if there is an encryption function having $N$ public keys as input.
This fixed length encrypted message should be decrypted by corresponding private keys only. Is this possible?

By the way: Is this concept similar to TV channel encryption?

The problem you described is addressed and solved in different way by the Broadcast Encryption: roughly the problem is how to encrypt a message intended to more than one recipient.
You described a naive approach to the problem, your solution is, indeed, probably the simplest one.

The Broadcast Encryption concept was formalized and defined by Fiat and Naor in their seminal paper Broadcast Encryption. Their solution is based on a binary tree where recipient are leafs of this tree and owns a key for every node from them to the root ($2^n$ leafs, $n-1$ keys per user): a ciphertext is encrypted using the minimal set of nodes covering the set of intended recipient.

Other solutions have been published, using both public and symmetric key cryptography. These attack different deficiencies of solutions to the problem: size of the ciphertext, size of the user keyring, revocation without re-keying, privacy preserving schemes, ...

Two kinds of broadcast encryption exist: one where you name the intended recipients and the other one where you ban a subset of all potential recipients. This first is similar to pay TV (you pay so you can decrypt the broadcast), the second to DVD encryption (all players can play a DVD unless they are banned). The Fiat and Naor solution is of the first kind.

Note that usually public-key encryption is used with the KEM/DEM paradigm, so the plaintext to be encrypted to multiple recipients is a random key for a symmetric algorithm.


OT extension question about base-OT Recently, I am learning the Oblivious Transfer (OT) Protocol. I have some questions about the OT extension. In ALSZ13, we know that $m\times OT_l$ can be reduced to $\kappa\times OT_\kappa$, where $\kappa$ is a security parameter, $l$ is secret's bit length. So my question is:

How can I implement $\kappa\times OT_\kappa$? Is it run $OT_\kappa^1$ protocol $\kappa$ times? If yes, is $OT_\kappa^1$ same to NP01 Protocol 3.1 says that $OT_1^N$?

How can I implement $\kappa\times OT_\kappa$?

You pick your favourite public-key based OT protocol. Usually these will allow you to input a choice bit and learn exactly one out of two $r$ bit values in return.
Then you input two random $r$-bit values into that protocol and use the $\kappa$-bit hashes as output. This is your $OT_\kappa$ protocol.
Next, you execute $\kappa$ (e.g. 128) instances of that protocol in parallel with independently random choice bits. This is what is usually done for these OT-extension protocols.
As for building a $OT_\kappa$ from $OT_1$s, you can indeed run $\kappa$ such protocols in parallel with the same choice bit (which is only immediately secure in a semi-honest model).


Is it possible to obtain the value committed to by Pedersen commitment given the blinding key? I know that the purpose of the blinding key is to make it difficult to obtain the hidden value.
More formally: the Pedersen commitment is comprised of the blinding key $\alpha$, two generators $H$ and $G$ and the value we wish to commit to $v$.

I am familiar with two versions of the Pedersen commitment, the "regular" version where the commitment is $P=G^\alpha+H^v$, and the Eliptic curve version where $P = \alpha\cdot G + v\cdot H$.
In both versions, assuming I obtained the blinding key $\alpha$, can I obtain $v$ ($H$ and $G$ are publicly known) in an efficient way?

For the regular commitment I can see that it is a hard problem (under the CDH assumption) so I assume there is no efficient way.
However, for the version over eliptic curve, it seems that it is possible to obtain $v$ efficiently, but I am uncertain about it.

Recovering $v$ from $\alpha$, $G$, $H$ and $P=\alpha\cdot G + v\cdot H$ requires solving the discrete log problem to find $v$. Specifically, note that $v\cdot H = P - \alpha\cdot G$ so you need to find the discrete log of this value with base $H$. As such, if $v$ is small then you can find it.

It is crucial to understand that although it is hard to find $v$ in general, it does not mean that revealing $\alpha$ is OK and $v$ is still securely committed. This is because some part of $v$ may be revealed by $v\cdot H$. Thus, this is neither a secure commitment, nor possible to obtain $v$ efficiently.

On the note of working modulo $p$ or over Elliptic curves, this makes no different essentially.


Is this a good way of splitting a private key into a 2 of 3 scheme? Basically the idea is to split a key into three parts ($key_a, key_b, key_c$) of which any 2 of the 3 parts can be used to recreate the original key

$key_a$: a random number smaller then our original key
$key_b$: another number which when added to $key_a$ will result in the original key
$key_c$: two components:

$xor_a$: xor of the original key and $key_a$
$xor_b$: xor of the original key and $key_b$

Is this a good way of splitting a private key into a 2 of 3 scheme?

Here's a Github gist showing a Python example of what I described above.

The proposed sharing scheme does allow reconstruction of key $K$ from any two of the three shares $K_A$, $K_B$, $K_C=(X_A,X_B)$, because:

$K=K_A+K_B$ from $K_A$ and $K_B$
$K=K_A\oplus X_A$ from $K_A$ and $K_C$
$K=K_B\oplus X_B$ from $K_B$ and $K_C$

Problem is, the scheme leaks information about key $K$: always less than 1 bit worth to participants $A$ and $B$; but over 1 bit to participant $C$, growing up to the whole of $K$ if there is enough redundancy in $K$ (see below). While the proposed sharing scheme might leak acceptably little information about the private exponent of an RSA or ECDSA key, which are close enough to uniformly random, it is not recommendable in general.

As an extreme example, if it is shared a key $K$ of a single bit, that is $K\in\{0,1\}$, then:

if $K=0$ then $K_A=0$, $K_B=0$, $K_C=(X_A,X_B)=(0,0)$
if $K=1$ then either

$K_A=0$, $K_B=1$, $K_C=(X_A,X_B)=(1,0)$
$K_A=1$, $K_B=0$, $K_C=(X_A,X_B)=(0,1)$

It follows that $C$ always learns $K=X_A\oplus X_B$, and $A$ or $B$ seeing its $K_i=1$ learns $K$; also, if $K$ is uniform, $A$ and/or $B$ seeing its $K_i=0$ can bet that $K=0$ with better than even odds.

For large $K$, $A$ and $B$ learn some information about the order of magnitude of $K$ (less than 1 bit worth on average, regardless of the distribution of $K$).

But $C$ gains more information about $K$. The low-order bit of $X_A\oplus X_B$ is always the low-order bit of $K$, and the high order bit of $X_A\oplus X_B$ tends to match the corresponding bit in $K$ for uniform distribution of $K$.

Worse, redundancy known to exist in $K$ allows $C$ to gain even more information about $K$. For example, if it is known that the representation of $K$ consists entirely of the digits 0 and 1 in some base $2^j$ with $j\ge3$ including hexadecimal or octal, then $C$ can fully reconstruct $M$ by computing $(X_A+X_B)\oplus(2(X_A+X_B))$ and masking to keep the bits that could be set in $K$.

A simple scheme that works and leaks no information is to share each bit $k$ of $K$ by assigning a uniformly random integer $x$ in $\{0,1,2\}$ to $A$ ; $x+k\bmod3$ to $B$ ; $x+2k\bmod3$ to $C$. If two parties have the same value assigned, then $k=0$, otherwise $k=1$.

Further, by writing $K$ in base three, thus with $k\in\{0,1,2\}$ , and with the parties knowing who received $x$, $x+k\bmod3$, or $x+2k\bmod3$, the capacity of the scheme is increased and each of the three shares has the same size as $K$.

Of course, the generic method is Shamir's secret sharing, which allows a flexible number of shares and threshold for reconstructing $K$.


How should k2 be produced in the RC4A stream cipher (A modification of RC4)? RC4A is a slight modification of the simple RC4 stream cipher designed to strengthen it against a number of attacks. Here's that paper.

However in the paper, the second key k2 is only mentioned twice and provides only a loose description of what it should be:

  We take one randomly chosen key k1.
  Another key k2 is also generated from a pseudorandom bit generator (e.g. RC4) using k1 as the seed.
  Applying the Key Scheduling Algorithm, as described in Fig. 1, we construct two S-boxes S1
  and S2 using the keys k1 and k2 respectively.

The main thing here is that k2 is "generated from a pseudorandom bit generator (e.g. RC4) using k1 as the seed", and S1 and S2 are constructed "using the keys k1 and k2 respectively".

In source code implementations of RC4A I have come across two different ways of handling S2, none of which use a PRBG to produce k2. This results in different output for the same input:

S-boxes S1 and S2 are exactly the same (using k1 for both).
All 256 values of S-box S1 constitute the key k2 for S2.

In a cryptography course, it is suggested to use a "nonce" for k2, which has the same length of k1 but doesn't explain how it is calculated from k1 as a seed (which is understood to be how k2 is produced).

Finally, another article appears to show that k2 is produced by feeding a number of bytes from S1 into the original RC4 PRGA, producing a keystream:

  To be more specific, in KSA of RC4, the array S1 is initialized, using the secret key K.
  WK, 16 bytes of keystream, are generated from the array S1 in PRGA of RC4.
  Then, the array S2 is initialized in KSA of RC4, using WK.

I am assuming K refers to k1 and WK refers to k2 in the original article.

Related pseudo-code:

RC4_KSA(K, S1)
For i = 0 … l – 1
WK[i] = RC4_PRGA(S1)
RC4_KSA(WK, S2)

One problem with this approach is that when calculating k2, the RC4 PRGA would swap values in S1, altering it. S1 is used in the RC4A PRGA and would produce a different keystream than if it had not been altered. This can be avoided by using a second copy of S1 for RC4 PRGA, leaving the original unaltered.

So there is ambiguity in how the second key for S2 is produced, with implementations differing in output keystream for same input.

A few questions:

Do the two differing implementations in practice undermine RC4A's
security claims by not using a PRBG/PRGA to produce k2?
Does it matter what k2 is, how it's produced, or if it's the same as k1?
What is the proper way to produce k2 that all implementations should follow?

Thank you!

Do the two differing implementations in practice undermine RC4A's security claims by not using a PRBG/PRGA to produce k2?

I wouldn't think so.  I get the impression that the authors just intend k2 to be derived from k1.  They have not amended the algorithm so much as to use a different key schedule for k1.  That leads to the requirement to create a second permutation using the existing key scheduling algorithm, thus a different key has to be found from somewhere.  The truth of this is proven by the fact that different implementations use different techniques.

Frankly it's a little disappointing that the authors didn't address k2's generation more specifically.

  Does it matter what k2 is, how it's produced, or if it's the same as k1?

From a cursory inspection of fig.3, it appears that each alternate output comes from each state permutation. There doesn't seem to be any interaction between them. I posit that if k1 = k2 then the outputs would be identical pairs. This seems consistent with the authors' comments regarding improved security by having more variables. A  PRNG is as good a way as any, but.  Ideally the inner state of the PRNG should be equivalent to the length of the key, but since a RC4 key can technically be 2048 bits, that's a problem.  Few smallish XOR shift or LFSR PRNGs have such a large state.  See below.

  What is the proper way to produce k2 that all implementations should follow?

Again, the fact that differing implementations use differing ways of generating k2 proves that there is no proper way to produce it.  Proper would just be that k1 ≠ k2.  My personal choice would be a simple 256 byte randomly generated S box.  Note: it is confusing that the authors use the term S box to refer to the internal state array.  I'm suggesting a real S box so that k2 = SBOX[k1] for all bytes.

There is a wonderful  alternative solution to both initial key stream bias and generation of the two states.  Two fully widened Pearson hashes can be used.  One derangement makes k1, and a second independent derangement makes k2. Since this is a new variant of RC4, there cannot be any backward compatibility  for passwords anyway.   This means that the entire key scheduling algorithm can be scrapped.  And it's a perfect fit as a fully widened Pearson hash output is exactly 2048 bits.  Yes the maximum state size of such a hash is only 1684 bits, but who uses passwords that have 210 bytes of entropy anyway?

Opinion on the paper

I find section 5 very poor.  Every (even amateur) cryptographer knows that RC4's Achilles heel is bias.  Indeed the authors' motivation is to improve RC4's security.  This must mean bias reduction.  So how can they possibly put forward an RC4 derivative without a bias assessment?  What is the point of section 2 if they then just forget about possible biases of their own creation?

"Diminished" from section 5.3 is not good enough.  It means nothing that their baby passes randomness tests.  The original RC4 did too.  This speaks to the vagueness and generality of current test suites, but also forms a  cop out for the authors.  I don't know if this is intentional.  If they wanted a quick and dirty solution, all they had to do was add a von Neumann extractor after the PRNG component and RC4 becomes bias free.

As pointed out in the comments to you, RC4A can be distinguished now via observation of 2^23 outputs.  The author's began their paper saying that the original RC4 could be distinguished after 2^25 outputs.  They seem to have gone backwards, although in fairness attacks improve with time.


Authenticated Encryption Sheme with Random Access and proven security? I am searching for an authenticated encryption sheme with random access and a good performance.
The exact requirements are:
Data to protect: data = data_block_0 || ... || data_block_n
Every data_block has a size of n bytes, 512 for example and the complete data can have a size of many gigabytes.
I search for an authenticated encrypted sheme, which makes it possible to change a data block and update a authentication tag with a good performace.
All authenticated encryption shemes I found (e.g. AEGIS, AES-GCM, Deoxys) uses a chain from data_block_0 to data_block_n to compute the authentication tag. In consequence if I change block_i, I must re computate all blocks with j>i.
A simple approach to realize integrity of the data:
mac_i = MAC(K, blocknumber || block_i || block_length in bytes)
enc_mac_i = Enc(K, mac_i, IV = blocknumber)
mac = Enc( K, enc_mac_0 xor ... xor enc_mac_n xor mac(k, complete length), IV)
This example should demonstrate the requirement, which I need. This approach has many weaknesses.
If I change block_i I must remove the old enc_mac_i from the complete mac with xor and add the new mac with xor. This is possible with a good performance.
Knows anybody an authenticated encrypted sheme, that fullfills this requirment with proven security?

First, authenticated encryptions based on universal MACs (UMACs) can have their tags computed from blocks of message in random order. This is because UMACs are often based on integer or binary polynomial addition and multiplication, which are associative and commutative operations. Based on this, AES-GCM and ChaCha20-Poly1305 may satisfy your needs.
For these algorithms, recomputing the hash state for 1 block requires some addition, multiplication, and exponentiation, where the exponentiation can be done using square-and-multiply approach.
Second, authenticated encryptions are supposed to operate on whole messages. From your description I sensibly believe this may be some type of XY problem, and you may need to disclose your application blueprint so that we may tell if better solutions to your ultimate problem exist.


Breaking a modified version of Diffie Hellmann Protocol I'm modifying the Diffie Hellman protocol as follows: We are given a large prime number $p$ and exponent $x$ such that $0 \lt x \lt p-1$ and $\mathrm{gcd}(x, p-1) = 1$. Also we pick $g$ such as $1 \lt g \lt p-1$.

We are also given $y = (g^x) \bmod{p}$. Essentially, we know about the prime $p$, the exponent $x$ and the result $y$. But $g$ is kept secret.

This is similar to Diffie Hellman protocol except that exponent $x$ is made public while $g$ is kept secret. So I'm trying to find if there's an efficient way to determine the secret $g$ or is this also a discrete logarithm problem?

Yes, there's an easy way to recover $g$:

$$g = y^{x^{-1} \bmod p-1} \bmod p$$

This works because the multiplicative group $\mathbb{Z}_p^*$ has order $p-1$, and hence $g = g^{x \cdot x^{-1}} = (g^x)^{x^{-1}} = y^{x^{-1}}$


How to make a document truly read only How is it possibile to cryptographically make a document truly read only? As in read only I imply that the user can obviously view it which can be achieved by coding which pixels have which colors. But how is it done in the industry? and what's more important is it possibile to password-protect it too?
I have considered a few solutions but I would like input from someone who has more knowledge than I in cryptography and security.

Cryptography studies properties of information. Information, at least in discrete form (a sequence of bits) can inherently be duplicated. Inasmuch as a document conveys meaning, it can be expressed as a sequence of bits. If someone obtains a copy of the document, they can duplicate the sequence of bits and make other copies. It is impossible to prevent the copying of a document by cryptographic means alone.

It's also impossible to prevent making modified copies of a document. It is however possible to detect whether a copy of a document is pristine: this property is called authenticity, and it's one of the basic security properties that cryptography studies. Authenticity can be guaranteed by including a signature (which can be produced only by entities who know a particular private key and can be verified by anyone knowing corresponding the public key) or a MAC (which can be verified by entities who know the secret key that was used to produce the MAC).

While copies cannot be prevented, they can be made detectable through watermarking. Unlike authenticity, for which robust, generic solutions exist, watermark techniques are inherently tied to a particular medium (e.g. sound or video) and tend to be broken.

Protection against copying can be achieved by physical means (optionally in combination with cryptography). This is not always easy to achieve. In order to prevent copying, the information has to stay within systems that are under the control of the information holder. Properties such as “this information may not be copied outside a certain system” are known as digital rights management (DRM).

As soon as the information needs to be communicated to a human, it has to leave the controlled system. This is an analog hole, and cannot be prevented by physical means alone. There are two ways to mitigate the analog hole:

By physical means: the analog hole implies a quality degradation for some types of documents (e.g. filming a video in a cinema produces a lower-quality video — but technology is improving rapidly). Fundamentally, the analog hole represents a limit on the rate at which the information leak out of the controlled system.
By legal means: show the document only to people who have signed a contract whereby they guarantee that they will not make copies. In effect, legal means can make the human part of the controlled system.

In practice, DRM works (inasmuch as it works at all) by arranging to make the computer that a user bought remain under the control of the content provider: your computer is not your computer, you only paid for it, and you can only use software that is approved by the content provider. If DRM-protected content escapes computers that are under the control of a content provider (for example, if it's visible on a PC), it is no longer protected.

As long as the document is on systems under your control, you can configure your systems to require a password to view it. If the document leaks, then you can enforce confidentiality by encryption, making the document only readable only to holders of a key. Someone who doesn't have the key can tell that the document is there and (at least approximately) how large it is but not what it contains. It is possible to derive a key from a password, so that only entities who know the password can read the document.


What Diffie-Hellman parameters should I use? After reading this article, I started wondering how should I approach the problem of choosing p and g params in 1024-bit Diffie-Hellman key exchange.

In my project, I am going to establish keys between many users. Should I create different p and g for every one or e.g. every 100? Is there any tool that would generate me random and good p and g params (g to be generator of p group) which are considered cryptographically safe? Or is switching to 2048-bit the best solution?

I recommend avoiding Diffie-Hellman parameter generation.  Instead, use a standardized DH group with a sufficiently large modulus (2048-bit or larger).  For example, group #14 or #15 from RFC3526 (see sections 3 and 4) would be a good choice.  Alternatively, switch to the elliptic curve variant of Diffie-Hellman and use Curve25519.

The article you linked to is based on a great paper that surveys a variety of problems with how Diffie-Hellman is used in the real-world.  One part of the paper (section 4.2) describes how a well-funded attacker could feasibly break a 1024-bit Diffie-Hellman group.  At a high-level, the attack works as follows:

The attacker chooses one Diffie-Hellman group.
The attacker performs some massive computation for that group.
The attacker uses the results of that computation to break any key exchanges made using that group.

The authors point out that a large portion of the web sites that support TLS with DHE use one of only five 1024-bit DH groups.  They thus conclude that if a well-funded adversary performed five massive computations (one for each of the popular groups), the adversary could crack TLS Diffie-Hellman key exchanges cheaply and at a massive scale.  This lead many to believe that standardized DH groups are a bad idea, and that we should be generating a new group whenever possible.

I think this is misguided for a number of reasons.  First, group generation is hard to get right and can easily lead to much more disastrous vulnerabilities.  That same paper discusses "weak and misconfigured groups", and points out that "failure to generate Diffie-Hellman primes according to best practices can result in devastating attacks".

Second, the attack they describe on 1024-bit DH groups can still be applied to randomly generated 1024-bit groups.  The hope is that whatever key exchanges performed using your DH group just aren't interesting enough for anyone to bother spending the millions of USD required to break the group.  This isn't much comfort though.  In cryptography, we generally don't like "secure, except against rich people".  We aim for a higher standard: "secure against the combined resources of the human race for the foreseeable future".  DH groups with a large modulus can meet this higher standard, and it's OK if everyone uses the same large prime.

Note for TLS/SSL users: Use either ECDHE or DHE cipher suites (since these support forward secrecy).  With DHE, follow the above advice on groups.  With ECDHE, use the NIST P-256 curve (secp256r1), since Curve25519 is not yet supported.


How to prove that a function is not pseudorandom? I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I'm struggling with the exercies which ask for proofs, like the following one:

  Let G(k) be a PRG with |k| = n, and G'(k) the output of G(k) truncated to the first n bits. Prove that $F_k(x) = G'(k) \oplus x$ is not pseudorandom.

The only thing I can say is that $F_k()$ has a very specific structure, not chosen randomly from $1/2^n$.

Any hints?

Before answering the actual question, I will offer some general advice.

It is important to pay attention, both in class and to the textbook you are reading. If learning how to solve such exercises is a key goal of the course, such solutions have very probably been discussed at length in class. Moreover, your textbook also has proof examples, and in this case it has one which is conceptually identical to the one you have given here (where $G'(k)$ is replaced by $k$).
It is crucial to know and understand your definitions. Here, you want to show that a certain family of functions is not pseudorandom (i.e., does not satisfy the definition of a pseudorandom family of functions), but it is not clear that you understand what this means (you do not articulate it in your question). You must understand this definition if you want to be able to show that a certain construction does or does not satisfy it.
Broadly speaking, you seem to lack what is commonly known as mathematical maturity, which is not knowledge of any specific mathematics, but rather the ability to see how to connect the dots in a mathematical argument between the hypotheses and the conclusion. Indeed, a telltale sign of someone who is not "mathematically mature" is that they balk at the mere sight of the word "proof" and seem unable to make any progress beyond stating the hypotheses. Unfortunately, cryptography is not the best of places to "get your feet wet" in writing proofs because it is a very complicated business (most results in cryptography aim to prove that it is impossible to do something), and you can feel overwhelmed pretty quickly. For this reason, abstract algebra or real analysis are better training grounds, even if you have no intention of studying them for their on sake.

To turn to the main question, we first need to know and undertand the definition of a pseudorandom family of functions. We consider a function $F$ which maps each pair of strings $(k,x)$ of equal length to a third string $y$ of the same length as $k$ and $x$. For any string $k$ of length $n$, we note $F_k$ the function which maps the $n$-bit string $x$ to the $n$-bit string $y$ (i.e., $F_k(x) = F(k,x)$. The string $k$ is called the key. I only state the definition of a pseudorandom function without a lengthy discussion (which can be found in the book).

  The function $F$ defined above is pseudorandom if it satisfies the following two conditions.

  Easy to compute. There is a deterministic polynomial-time algorithm $C$ such that $C(k,x) = F_k(x)$ for any strings $k$ and $x$ of equal length.
  Pseudorandom. For every probabilistic polynomial-time algorithm $D$, every polynomial $p$ and all sufficiently large $n$, we have
  $$\left|\mathrm{Pr}[k \gets \{0,1\}^n : D^{F_k}(1^n) = 1] -
          \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right|
< \frac{1}{p(n)}.$$

My notation is as follows:

$\{0,1\}^n$ is the set of all strings of length $n$.
$\mathrm{Func}_n$ is the set of all functions from $\{0,1\}^n$ to itself.
$k \gets X$, where $X$ is a finite set, means that $k$ is randomly and uniformly chosen from $X$.
$D^f$ denotes the algorithm $D$ when given oracle access to the function $f$. That is, $D^f$ can obtain $f(x)$, for any $x$ of its choice, at the cost of only one operation.
$\mathrm{Pr}[A : P(x)]$ denotes the probability that $P(x)$ holds after the execution of $A$.

Here, you want to prove that the given function is not pseudorandom, meaning that it does not satisfy the definition above. In other words, that it satisfies its logical negation. Since the logical negation of the definition is not entirely trivial, it is best stated explicitly. Typically, the "easy to compute" condition will be satisfied, so we only give the negation of the pseudorandomness condition.

  A function $F$ as above which is easy to compute is not pseudorandom if there exists a probabilistic polynomial-time algorithm $D$ and a polynomial $p$ such that for infinitely many $n$, we have
  $$\left|\mathrm{Pr}[k \gets \{0,1\}^n : D^{F_k}(1^n) = 1] -
          \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right|
\ge \frac{1}{p(n)}.$$

We can finally define the algorithm $D$ (we denote by $\mathcal{O}$ the function computed by the oracle). On input $1^n$, it proceeds as follows.

Compute $y_0 = \mathcal{O}(0^n)$.
Compute $y_1 = \mathcal{O}(1^n)$.
If $y_0 \oplus y_1 = 1^n$, output $1$. Otherwise, output $0$.

We must determine the probability that $D$ outputs $1$ in each case: when $\mathcal{O}$ is $F_k$ for a uniformly chosen $k$, and when it is a uniformly chosen $f$.

In the first case, regardless of what $k$ is, we have $y_0 = G'(k) \oplus 0^n = G'(K)$ and $y_1 = G'(K) \oplus 1^n$. Hence we have $y_0 \oplus y_1 = G'(k) \oplus G'(k) \oplus 1^n = 1^n$, and $D$ ouputs $1$ with probability $1$.
For the second case, we note that $D$ outputs $1$ if and only if $y_1 = y_0 \oplus 1^n$. If $f$ is a totally random function, $y_1$ is chosen among all $2^n$ strings of length $n$ uniformly and independently of $y_0$, and so it will equal $y_0 \oplus 1^n$ with probability $1/2^n$.

Hence finally we see that for all $n$, the value of the big probability expression in the definition equals $1-\frac{1}{2^n}$. If $n > 0$ this is at least $\frac{1}{2}$, and so we can take $p$ to be the constant polynomial $2$.


Can one claim that AES is a perfect cipher? I'm taking a crypto class this semester and after learning the definition of a perfect cipher. I started wondering how this definition applies to AES.

Obviously AES isn't a perfect cipher, since the key length is only 256 bit at the maximum. But when talking about messages of sizes 128 bits to 256 bits, can one claim that AES is a perfect cipher?

Meaning, how can I prove that $\mathbb P(P|C) = \mathbb P(P)$, where $P$ is plaintext and $C$ is ciphertext ($\mathbb P(x)$ is probability of $x$)?

Short version: I don't think AES restricted to key-size messages is a perfect cipher, and I'm quite sure it can't be proven without breaking AES.

Long version:

A perfect cipher means that an attacker has the same chance to guess the plaintext if he has the ciphertext or he has no ciphertext at all, i.e. the ciphertext gives no information to someone who doesn't have the key (even with infinite computation resources).

AES itself is a 128-bit block cipher. To use it for longer messages, you need a mode of operation, and the probabilities in this statement will likely depend on the chosen mode. To avoid the complications, let's assume we have a 128 bit message encrypted with ECB mode (i.e. directly application of the block cipher), and the key is not reused for any other message.

$\newcommand\Enc{\operatorname{Enc}}\newcommand\P{\mathbb P}$Then we have a probability distribution $\P$ of the plaintext $P$ (this distribution is assumed to be known to the attacker), and on the (secret) key $K$ (which is assumed to be a uniform distribution). This induces a probability distribution of the ciphertext $C = \Enc_K(P)$ by
$$\P(c=C) = \sum_{k} \P( K = k \text{ and } \Enc_k(P) = c) = \frac{1}{2^\text{key size}} \sum_k \P(\Enc_k(P) = c)$$
The conditional probability $\P(P=p|C=c)$ is defined as $$ \P(P=p|C=c) = \dfrac{\P(P = p \text{ and } C = c)}{\P(C = c) },$$
and for a perfect cipher we want that this is equal to $\P(P=p)$ for all $c$ and $p$.

In effect, this means at least that for each pair of 128-bit-blocks $(c, p)$ there must be an equal number of keys $k$ with $\Enc_k(p) = c$. With 128-bit keys, this would mean that each key maps a given plaintext on a different ciphertext, and all ciphertext blocks can be hit this way.

While this sounds like a reasonable property for a block cipher, most block ciphers (including AES) instead are trying to approximate a random permutation, where each key's actions are independent from each other – which includes the possibility that there are plaintexts $c$ and pairs of keys $k_1, k_2$ with $\Enc_{k_1}(c) = \Enc_{k_2}(c)$.

A proof that this is not possible could possibly (depending on the proof) provide a way to retrieve the key in a known-plaintext attack, which would mean that AES is broken for all practical uses (with more than one use of each key).

(This is similar for the one-time pad: correctly used, it is a prefect cipher, but using the same key twice, it is totally broken.)

AES doesn't look like easily broken, so we can assume that this is not possible.


How do i manage encryption keys with a cloud provider? I would like to provision services from a Software as a Service (SaaS) provider. This is multitenant environment (multiple companies will be using a single instance of the application, with a single database, running on the same hardware and same OS).

Our company has a requirement to encrypt our data at rest (e.g. file stores, databases, backups).

Most of the guidance I have read states that the key should be kept with the customer or a third party and not with the cloud provider.

If I have the key; then every user in my company will need the key to access the file store once logged in? How would this work practically? Will the key be binded with my a users Username and Password?

Other option is to store the key in a configuration file on the cloud platform and managed by the cloud provider. But this creates another problem of securing the config file and the risk of having our key on a shared platform.

Where can the cloud provider store the key securely so that only I and my employees can use it?

What is best practice in terms of key management when having encrypted data on the cloud?

Best practice from my research states the following:

• Store the key with the customer or 3rd party

• Only authorised persons to access the key.

• Do not store the key on the same platform as the data.

One approach to doing this is using end-to-end encryption, where the provider never has access to the keys. A system that uses proxy re-encryption (PRE) can allow each user to have her own keys, but admins can manage a group that represents the users for your company, so it is not necessary to re-encrypt all the files the company can access every time a new user is added or a user is removed.

A paper that describes this in detail is available here (this directs through my company's website to the ACM digital library - sorry for the extra hop, but it avoids the need to have ACM Digital Library access to get the paper). In summary, proxy re-encryption is a scheme originally designed to allow the delegation of encryption from one person to another. PRE schemes are based on public key cryptography, and they allow someone (the delegator) who has her own private key plus the public key of another person (the delegatee) to compute a re-encryption key. This key will allow ciphertexts encrypted to the delegator to be re-encrypted or transformed so that they can be decrypted using the delegatee's private key. This process does not allow the proxy or individual doing the transformation to decrypt the ciphertext.

If the delegator is an abstract entity that represents your company, and system administrators control access to that entity's private key, they can generate re-encryption keys to different users within the company. Revoking access is achieved by removing the re-encryption key between the company and an individual user.


OMAC/CMAC constant for different block sizes OMAC/CMAC only specifies constants for 64-bit (0x1B) and 128-bit (0x87) block size. I would like to know how to get constants for other block sizes.

http://en.wikipedia.org/wiki/CMAC says it "is the non-leading coefficients of the lexicographically first irreducible degree-b binary polynomial with the minimal number of ones.", but I'm not good at math and I don't know how to implement that.

So does anybody know how to implement that?

Thanks.

The identification of the lexicographically first irreducible degree-b binary polynomial with the minimal number of ones can be implemented by testing reducibility (second algorithm) of those

polynomials in order until you get to the first irreducible polynomial in that order.

Alternatively, you could look them up.

The constant itself is then derived from the polynomial by discarding the leading (block size) term and evaluating the remainder for $x = 2$.

e.g. for 256-bit block size:

first polynomial is $x^{256} + x^{10} + x^5 + x^2 + 1$
Note this is is 256,10,5,2 in the linked report, which discards the $+1$ term.
discarding first term and evaluating for $x = 2$ gives $2^{10} + 2^5 + 2^2 + 1 = 0x425$


Is there distinguisher? Are these distributions computationally indistinguishable ?

$f:\{0,1\}^n \to \{0,1\}^n $

$\{X_n\}_{n\in N}$ : uniform distribution for function which $f(0^n)=0^n$  and for other function probability is zero.

$\{Y_n\}_{n\in N}$ : uniform distribution for function which $f(0^n) \neq 0^n$  and for other function probability is zero.

It looks like you're asking the following:

Consider the following families of distributions over functions from $\{0,1\}^{n} \to \{0,1\}^{n}$:

$\{X_n\}, \text{ where } X_n \text{ is the uniform distribution over the set of functions } f : \{0,1\}^{n} \to \{0,1\}^{n} \text{ such that } f(0^{n}) = 0^{n} $

$\{Y_n\}, \text{ where } X_n \text{ is the uniform distribution over the set of functions } f : \{0,1\}^{n} \to \{0,1\}^{n} \text{ such that } f(0^{n}) \neq 0^{n} $

Are these families of distributions computationally indistinguishable?

I claim they are computationally distinguishable, assuming that each function can be evaluated on input $0^{n}$ efficiently. Consider the following distinguisher, which on input $f$ computes $f(0^{n})$ and outputs $X$ if $f(0^{n}) = 0^{n}$ and $Y$ otherwise. By the definition of $\{X_n\}$, if $f$ is drawn from this family, this distinguisher will output $X$. By the definition of $\{Y_n\}$, if $f$ is drawn from this family, this distinguisher will output $Y$.


Is RSA in decline across the board? From what I gather from the internet (source), the recommended practice for 2019 and beyond is to avoid RSA and use ECDH and ECDSA.

Is this the general case?

RSA for key exchange is declining rapidly and is not recommended because it does not provide forward secrecy. Without forward secrecy, if someone breaks into the server and obtains the private key, they will be able to fully retroactively decrypt all recorded traffic encrypted under that key. ECDH does not have that problem because the private and public keys are generated on-the-fly, and discarded after use. This is possible because ECDH (and DH) key generation is light and easy on the CPU, whereas RSA is not. Generating a new RSA key pair for each key exchange would be absolutely prohibitive.

RSA for certificates, on the other hand, is still alive and well, and is still considered industry standard. There are some benefits that ECDSA has, though, such as smaller public key and signature sizes, which equates to reduced network usage, but verification with ECDSA is a little slower than with RSA.


How are salt values more secure? If a database stores password encrypted by using salt values, how are they stored?

I read somewhere, it uses timestamps.
So is the timestamp also stored?

How about when a user tries to login next time, then how are timestamps considered?

Salts are generally stored in the database with the password.

They shouldn't be timestamps, salts should be random values of 128 bits or more (though this may vary depending on the hashing scheme used.)

Salts improve security by making brute force attempts single-use: a password of "password" is likely going to be used many, many times. If it's hashed without a salt, then an attacker will instantly know which users used "password" as their password when they hash it. By hashing it with a per-user random salt an attacker will need to try at least one guess for each user, and hopefully several guesses. So salts help protect users who reuse passwords (there aren't that many hashing schemes) and users who choose bad passwords (attackers have to try all the bad passwords with each salt, instead of just trying them once.)


Strength of MD5 in finding duplicate files Why are there a lot of duplicate file finder applications which are using MD5 Algorithm? What is the strength of MD5 in terms of searching duplicate files in hard disk or flash driver or any other storage device?

MD5 is ok here as usual cryptographic attacks do not apply in this scenario.
The probability of accidental MD5 collision is much less than usual probability for soft error. For details read more.

MD5 is currently considered too weak to work as a cryptographic hash. However, for all traditional (i.e. non-cryptographic) hash uses MD5 is often perfectly fine.

MD5 has one important benefit above SHA1, SHA2, and upcoming SHA3: many platforms allow faster implementation of MD5 than other hashes. The performance in this use case varies highly according to used hash function.

The practical attacks against MD5 are mostly against collision resistance. If these are not an issue, MD5 can be fairly ok. (See earlier question Is a second pre image attack on MD5 feasible?.) For instance, where MD5 is considered fine by many is HMAC-MD5.

To get back to this question. It can be assumed that find duplicate files is not something where collision resistance is such of an issue (you likely do not have $2^{64}$ files), so chances of collision are much smaller than in many cryptographic uses where it is assumed adversary tries to find collisions.

Thus, for usual hash uses, the space of MD5 (128 bits) is large enough. The probability of collision in usual situations is small enough, it is much larger probability to for example, detect false duplicates due to random hardware failure (like soft error).

For more accurate mathematics, see earlier question What is the probability of md5 collision if I pass in 2^32 sets of string?. This is applicable in scenario where user has less than four billion files, and you may use the formula for other values. One million files gives $2^{-89}$, which I would consider very small.

Even more efficient for duplicate file finding than MD5 is to consider all file sizes. Files which are not the same size are not duplicates. Only files that have size which is not unique need hashing. If file duplicate program using hashing wants to be safe from MD5 hash collision, the program may want to perform byte-per-byte comparison to ensure files are unique.


Getting the Encryption Function From the Decryption Function + Decryption Key + Encrypted Item Is it mathematically possible to always be able to get the encryption algorithm used to encrypt a certain item (file, number, text, ...etc.) by knowing the decryption algorithm that will be used to decrypt that item, the encryption key (i.e. private key), and (of course) the encrypted item itself? I.e. are all encryption algorithms reversible and have this hypothetical equality hold (going to left decryption, while going to right is encryption), while still being able to get the method to go either way (right or left) if I know the other way: encrypted item + key <=> decrypted item?  I am referring to reverse engineering an encryption/decryption algorithm from knowing the other one in both symmetric and asymmetric encryption/decryption algorithms.

Every encryption is reversible, that's why most security relies on hashing in place of encryption.


Theoretical attack on RSA The high security of RSA is granted, because it is very hard to factorize
$$
N = p * q
$$

Nevertheless, there is actually no need of factorizing $N$, in order to generate the $Private$ $Key$, but the need of knowing
$$Φ (N) = (p - 1) * (q - 1) = N - (p + q-1)$$
If we think of $N$ as a rectangle with the width $p$ and the height $q$, we are able to find this geometrical coherence

That means, if there is an efficient way to find pairs of square numbers with a distance of $4*N$, RSA would be broken.

Please leave opinions on that.

Ricky's link answers your main question in the comments (that knowing the private key is equivalent to knowing the factorization of $N$). But your "attack" is unfortunately part of a class of properties which might appear insightful at first, but which eventually boil down to something like this: "find integers $(m,k)$ such that $m+kn$ is a perfect square" (with sufficiently powerful conditions on $m$). These kinds of questions are known to be difficult, and we simply do not know of an efficient way of answering them for general composites of unknown factorization.

Reformulating the problem geometrically does not appear to be helpful in this case (for instance, you need to know $p + q$ to know the side length of the square, and, of course, if you know $pq= N$ and $p + q$ then you can already factor $N$ efficiently without further techniques necessary).

As an aside, it is striking that we should not be able to answer questions about the behaviour of a simple function over the integers like $f(x) = x^2 \bmod{N}$, but recall that modular arithmetic is intrinsically linear: two integers $x$ and $y$ are congruent modulo $N$ if and only if $x - y = kn$ for some integer $k$. If you come from a programming background, it is a bit like mixing addition/multiplication and XOR/OR/AND in your algorithms - as long as you stick to one or the other, math it easy (standard algebra for the first, boolean logic/De Morgan's laws and so on for the other) and you can easily rearrange things around and so on, but as soon as you use both, even the simplest functions become very hard to understand and work with (a fact often used in symmetric cryptography). As an another example, mixing continuous functions like $\sin(x)$ with discrete functions like $\lfloor x \rfloor$. Same with mixing modular arithmetic and nonlinear functions like squaring. We do know how to work with these - to some extent - modulo primes or prime powers, a surprising result of number theory (for instance, it is easy to take square roots modulo a prime), and the Chinese remainder theorem [which, by the way, essentially borrows ideas from linear algebra] lets us extend these results to any integer whose factorization is known. But if the factorization is not known, there does not appear to be an easy shortcut in the general case (yet, of course, it is not proven that none exist).

As a result it is not surprising that most* of the current most efficient general purpose factorization algorithms use linear algebra techniques at their core to find a factorization of $N$ - it's about the only thing we can do if we know nothing about $N$ or it doesn't have any special structure (for instance, a prime factor with a smooth multiplicative order over some group that's easy to compute in, e.g. integers/elliptic curve). This is not to say that these algorithms are trivial. The fastest one (the number field sieve) uses powerful and nontrivial results from the theory of finite fields, but still builds on the same structural framework as the quadratic sieve and other sieving algorithms.

* The ECM algorithm is kind of in a class of its own, since it can be considered general purpose, yet uses group-theoretic ideas to find factors of $N$ while remaining rather competitive up to a certain input size - if you are interested in integer factorization, it is well worth your time to read all you can about this algorithm, and its predecessors the $p - 1$ and $p + 1$ algorithms (which are all conceptually similar but approach the problem in different and insightful directions)