Securely send public key from client to server in RSA? I have a client and a server communicating with messages encrypted using RSA.

Initially, the client knows server's public key, but the server does not know the client's public key. Is it possible to securely receive the client's public key over a network (i.e. without a man in the middle intercepting and changing the public key the client is trying to send with their own).

I was thinking that the client can generate a random secret and then send it to the server using the server's public key for encryption. Then the server can decrypt the secret, use it as a key for AES, and echo it back (this time encrypted with AES). The client then verifies that the decrypted secret is the same as the one it sent.

I'm scratching my head trying to figure out if this is secure, and how I should incorporate hashing to verify the integrity of the data.. Would this even work?

In this protocol:

client draws a random AES key $K_\text{SES}$ (I'll make it 128-bit);
client enciphers $K_\text{SES}$ using the server's RSA publickey $K_\text{PUB}$, and sends the result $\text{RSAES}_{K_\text{PUB}}(K_\text{SES})$ (note: RSAES designates RSA encryption with some unspecified padding e.g. per one of the two fine encryption schemes defined in PKCS#1);
server receives the alleged $\text{RSAES}_{K_\text{PUB}}(K_\text{SES})$ and deciphers it into the alleged $K_\text{SES}$, using the server's RSA private key $K_\text{PRI}$; servers stops if that fail;
server enciphers $K_\text{SES}$ using AES key $K_\text{SES}$, and sends the result $\text{AESENC}_{K_\text{SES}}(K_\text{SES})$;
client receives the alleged $X=\text{AESENC}_{K_\text{SES}}(K_\text{SES})$, deciphers it using the original AES key $K_\text{SES}$, and aborts if $\text{AESDEC}_{K_\text{SES}}(X)\ne K_\text{SES}$;
presumably, $K_\text{SES}$ is then used as a session key; I'll assume as key to some unspecified mode of AES for confidentiality, and perhaps something (not even suggested) for authentication; at least the client's public key is sent using that encrypted channel.

A 5-minute non-exhaustive analysis reveals various serious issues, limitations, and risks with this protocol:

there is no explicit protection against replay of a session to the server; in many circumstances this is a gapping hole!! (clarification: replay to the server is simply sending the messages sent by a genuine client and recorded in an earlier session, including any IV, and would work in the absence of some challenge-response from the server, which is currently not described);
it was imprecisely specified (it still is, in particular regarding error handling and time-outs), making a detailed analysis impossible;
it is not peer-reviewed, thus must be presumed unsafe;
as any protocol starting without secret credentials on the client side, it can not authenticate the client;
as any known non-quantum protocol, it can not prevent Eve-in-the-middle from intercepting or/and relaying the messages, but that is not by itself a security issue;
there is no protection against denial of service of the server by multiple connections, replayed or not;
there are Bleichenbacher padding oracle attacks on some bad implementations of step 3. on the server side (typically when using RSAES-PKCS1-V1_5), that in the worst case could leak $K_\text{SES}$, and then the sky is the limit;
if somewhat Eve-in-the-middle manage to abuse the implementation of step 6. on either the client or server side as a decryption oracle, then the possibility exists that she can obtain the decryption of $X=\text{AESENC}_{K_\text{SES}}(K_\text{SES})$ using the active key $K_\text{SES}$, giving her $K_\text{SES}$, with similarly devastating effect (clarification: if the encryption uses CBC, the attack could consist is replacing one genuine ciphertext block with with $X$ obtained from step 4. and somehow obtain the corresponding plaintext block, that would yield $K_\text{SES}$ after an exclusive-or with the previous ciphertext block ; that should not be possible in an authenticated link, but not enough details about that are given);
if $K_\text{PRI}$ ever leaks, the protocol is entirely insecure after the leak with no stated provision to recover from that;
if $K_\text{PRI}$ ever leaks, the confidentiality of past recorded communications is compromised; contrast that with protocols offering forward secrecy;
update: there is no stated safeguard to reduce the risks resulting from a poorly seeded or otherwise bad RNG being used at step 1., which times and times has occurred on the field;
update: at step 6. the client's public key is sent enciphered, when we really need authentication, not really described.

If clients authentication is no necessary, then this protocol looks safe.
But I have got couple suggestions.
Use RSA-OAEP padding scheme, for making communication between client and server more secure.  This scheme could  prevent MITM changing message without decryption.
Another way to make your protocol more secure is adding to server response digital signature, to confirm that received message exactly from server.


How was the 5 digit random number in the VIC cipher generated? Knowing that VIC was a "spy cipher" it is unlikely that the agents used a cryptographic device to genreate the 5 digit number but how did they do it?

In the VIC cipher, that significant five-digit number was created by the user when doing the encryption. It was surely made on the spur of the moment without equipment. As you remarked, these people were spies, and they would not have wanted to get caught with some strange device.
The CIA's online library does not mention the five-digit number as a value that the user had to memorize. The agent already had four mnemonic keys stored in his or her mind:
 1. a date (in Russian this would be day/month/year; six digits)
 2. a snippet of a popular Russian song        (20 characters long)
 3. the user's personal identification number
 4. a Russian word (e.g., the word for "snowfall")

I do not know for sure, but I think it is most likely that agents came up with their own "random" number out of their own heads. One, admittedly thin, piece of evidence might be that the Russians were generating "one-time pads" at that time out of their own heads by pecking at a typewriter--and keys generated in such manner were considered "random" enough to encrypt important traffic.

Write the numbers 0 to 9 on slips of paper and draw them from a hat.


Are common cryptographic hashes bijective when hashing a single block of the same size as the output? It's been said that CRC-64 is bijective for a 64-bit block.

It the corresponding statement true for typical cryptographic hashes, like MD5, SHA-1, SHA-2 or SHA-3?

For example, would SHA-512 be bijective when hashing a single 512 bit block?

It would be very freakish if it turned out to be true. It is not an expected property of SHA-512 to have such bijectivity. It would be worrisome, even, because that's a kind of structure that should not appear in a proper cryptographic hash function.

Actually proving that SHA-512, for 512-bit blocks, is not bijective, would already be a kind of a problem. We do not expect to be able to prove such things without breaking the function.

One "simple" way to prove this would be a single collision (on short inputs), which in theory could be found by chance. But for finding such, we expect to have to calculate about $2^{256}$ hashes (and store/compare them to the other values) to have a non-neglible probability to find a collision.

For example, if I have one zettabyte of fast accessible storage (which would be more than half of humanity's currently stored data), I can store about $2^{62}$ SHA-512 hashes. The probability that between these is at least one duplicate would be about $2^{-389} \approx 10^{-117}$. If every human (around $2^{33}$ in some years) repeats this experiment about once a week (i.e. $2^6$ times a year) with $2^{62}$ new hashes, humanity each year has a chance of $2^{-351}$ of finding a collision. Assuming that humanity  will work on this for 10 times as long as the universe already existed (i.e. 130 billions of years), we get a chance of $2^{-314} \approx 10^{-94}$. For comparison, the probability that a ticket wins the main prize in the German weekly lottery (6/49) is around $2^{-27}$, so the probability that humanity will ever find a collision (in the scenario outlined above) is lower than the probability of me winning the main prize each week, for 11 weeks in sequence (with one ticket per week).

So we can expect collisions to stay hidden until the end of times.

No.

Proof :

Let A be an object represented by a string of bits of length N "10001010110101100 ..."

Let H be the Hash of A , SHA256(A) = H ,H is of 256 bits length

How many possibilities of H are there ? the answer is 2 to the power of 256

And how many possible values of A we got ? the answer is 2 to th power of N

So if N>256 than our hashs are impossible to be unique , in that case , there would be too much possible values to assign hashs to. therefore , we will certainly have duplicated hash, at least 2 to the power of N-256 duplicated hashs

if SHA256 was bijective , than why dont we just use it as a perfect compression algorithm , that can put gigabytes in 256 bits ? ;)
you can find answers for such questions in the information science .

( SHA256 hashs are unique for objects of size <= 256 bits )


Can AES ans SHA-2 algorithms be implemented in parallel? As I understood AES GCM mode of operation gets good performance result because parallel execution of both encryption and hashing part.

Why AES and SHA-2 computation cannot be pipelined ?

They can be computed in parallel.

But what would still make AES-GCM faster than AES-SHA2 is GCM itself.

GCM is a universal hash function: it can be very fast, especially on CPUs supporting carry-less multiplications.
But it doesn't satisfy the same properties as a hash function such as SHA2. In particular, not encrypting its output would have catastrophic implications. It's fast because it is a simple and specialized function.

Even with Intel and ARM SHA extensions, I doubt it would be faster than GCM.

With AESNI and CLMUL, AES-GCM is about 0.65 cpb. SHA256 alone using Intel extension is about 3.8 cpb.

AES and GCM are both encryption algorithms meant to protect the contents of whatever the input is with a provided secret key from the user. AES can certainly be deciphered given the same key if the receiving party also has it.

SHA-2 is a hashing algorithm that is meant to serve a one-way purpose. This means it is not meant to be un-hashed. So Technically you would want to encrypt and hash in parallel which is not a very easy thing to do. The more rational approach (if you want to use both AES and SHA-2) would be to either encrypt using AES then hash, or hash, then encrypt.


An alternative hashing method, how does it compare? Say that I have good, collision resistant hash function H. Given a message M, the typical usage is h=H(M) to get it's hash.

Now, I want to propose two alternative methods of using this hash function, and compare them to the original function. First, I split my message M into equally sized chunks M1, M2, ..., Mn.

First method: the hash would be h=H(M1)⊕h(M2)⊕...⊕h(Mn) (⊕ is XOR).

Second method: the hash would be h=H(M1,1)⊕h(M2,2)⊕...⊕h(Mn,n), where comma means concatenation.

Now, it's obvious that the first hashing method is poor - I can shuffle the chunks around, and add two equal chunks without changing the resulting hash. But what about the second method? Are there any attack vectors? How does it compare to the original hash function?

Isn't the second method reducing the hash's target space because it is only 2 x 'chunk size' (which is less than the original size if number of chunks > 2)? If the target hash space is smaller then collisions are likely to be higher and the resulting hash use is therefore weaker on that basis (although this isn't the most important factor with reasonable size target spaces).

Obviously this is a simplistic analysis comment and not a full crypto analysis - for that you need to have a solid grounding in cryptography mathematics.


Deriving HMAC key and cipher key from passphrase? I'm encrypting a file with AES-256 in CBC mode. I needed to add an HMAC for authentication and validation of the file contents and passphrase, so I used a SHA-256 HMAC over chunks of my file cumulatively.

My main question is how to derive both an HMAC key and my AES key from an input passphrase. I'm currently taking the SHA-512 hash of the input passphrase, passing that to bcrypt/PBKDF2 with a salt and high rounds, and then using the SHA-256 hash to supply my AES cipher password. For deriving an HMAC key in addition to my cipher key, I was thinking of doing one of the following things:

SHA-512 the output from the strong hash method and split the result in half, using the first half as the cipher passphrase and the second half as the HMAC passphrase.
Store an additional salt in my header, and after generating the passphrase using SHA-256 after the strong hash, run the result through SHA-256 again with the salt for the HMAC passphrase.
Same as #2, but without a salt.

Which of these ways is the best way to generate a HMAC password in addition to my cipher password from the same input passphrase?

If you are doing authenticated encryption with an AES and HMAC combination, the security of your scheme depends on the key for encryption and the key for message authentication being independent. The general idea is that you might generate two independent keys from a single master key, by proper usage of a $PRF$. The most performance effective solution is therefore to modify your first suggestion in either of two ways:

Let $K$ be the output from the PBKDF2.

Alt 1. Derive the encryption key $K_e$ and authentication key $K_a$ using one call each to
$K_n = PRF_K(label_n)$. The input $label_n$ might e.g. be the single char "e" and "a" respectively.
Alt 2. Derive $K' = K_e||K_a$ using a single call to $PRF_K$ to generate a 512 bit derived key.

Please note SHA-512 is not a pseudo random function, but might be used to create one. For instance, you could use HMAC-SHA-512 as your PRF.

It greatly depends on whether or not your system is closed or opened, how many users you will have, what kind, how and where the software will be run, etc.

As a general rule, you should store only true random data in your cyphertexts (rather than hashes). Your solution #2 is the closest to that goal.

Just keep in mind that as SHA has been designed for speed, it might be a two-sided sword, allowing opponents to brute-force things easier (or worse, if they are competent).

In this regard, if security is really a concern, you should build your own variable-based hashing method (be very creative - the least conventional the best it will be) to make sure that the hashing method is changing with the input data.

Then, test it for collisions to make sure you are not defeating the purpose of using hashing in the first place.


What is a cryptographic "salt"? I'm a beginner to cryptography and looking to understand in very simple terms what a cryptographic "salt" is, when I might need to use it, and why I should or should not use it.
Can I get a very simple and clear (beginner level) explanation?
If you know of any references on the topic, those would also be useful.

The reason that salts are used is that people tend to choose the same passwords, and not at all randomly. Many used passwords out there are short real words, to make it easy to remember, but this also enables for an attack.

As you may know, passwords are generally not stored in cleartext, but rather hashed. If you are unsure of the purpose of a hash-function, please read up on that first.

Now, what the attackers can do is to simply generate a list of common passwords and their corresponding hashes. Comparing the hashes that a site has stored with the table will, if common passwords are being used, reveal the passwords to the attacker.

A salt is simply added to make a password hash output unique even for users adopting common passwords. Its purpose is to make pre-computation based attacks unhelpful. If your password is stored with a unique salt then any pre-computed password-hash table targeting unsalted password hashes or targeting an account with a different salt will not aid in cracking your account's password. A long randomly generated salt (using /dev/urandom) is expected to be globally unique. Thus salts can be used to make pre-computation attacks totally ineffective.

The simplest way to combine the salt and the password is to simply concatenate them, i.e. the stored hash value is Hash(salt||password). The common password password1 now magically becomes, e.g., 6$dK,3gCA%Jpassword1 which is unlikely to be found in a password cracker's table.

The salt can be stored completely in the clear in the database, next to the hashed value. Once the attacker has the database and wants to find the passwords, he needs to generate the pre-calculated table for each salt individually, a costly operation.

Another way to help defend against offline password cracking is to perform password stretching, ie. making a password hash slower to compute for any person, including the log-in service and password crackers. One method used to stretch passwords is achieved by iterating the hash-function many times, i.e. storing Hash(Hash(Hash(Hash…(Hash(salt||password)))…).

Another common idea related to salting is called a pepper. That is, another random value concatenated to the password, such that the stored value is Hash(pepper||salt||password). The pepper is then not stored at all. Both the login server and password cracker need to brute force the unknown pepper value, slowing password hash comparisons for both parties.

From 2013 to 2015 a password hashing competition was held to search for a better password-stretching algorithm. The winner was the Argon2 algorithm. Programmers are recommended to use Argon2 instead of implementing their own algorithm.

A salt is a random number that is needed to access the encrypted data, along with the password.

If an attacker does not know the password, and is trying to guess it with a brute-force attack, then every password he tries has to be tried with each salt value.

So, for a one-bit salt (0 or 1), this makes the encryption twice as hard to break in this way. A two bit salt makes it four times as hard, a three bit salt eight times as hard, etc. You can imagine how difficult it is to crack passwords with encryption that uses a 32-bit salt!


Cracking WWII-era codes - code found on a pigeon's leg in Surrey A recent BBC article entitled WWII code 'may never be cracked' posted a code:

AOAKN HVPKD FNFJW YIDDC
RQXSR DJHFP GOVFN MIAPX
PABUZ WYYNP CMPNW HJRZH
NLXKG MEMKK ONOIB AKEEQ
WAOTA RBQRH DJOFM TPZEH
LKXGH RGGHT JRZCQ FNKTQ
KLDTS FQIRW AOAKN 27 1525/6

According to the article the code was found on the leg of a pigeon in a chimney in Surrey a few weeks ago.

Do we have enough information about WWII-era codes (presuming that is when it comes from), such as the one above, to figure out what these long-forgotten codes might say?

EDIT: This was discussed on slashdot.

A problem with this message is that the image in a press release from GCHQ differs slightly from one in a New York Times article, although the paper, with its tears looks the same.

The image below shows the two side by side, the one on the left from the NY Times and the right from GCHQ. There is a slight difference in the style of writing, i.e. more sloping to the right in the GCHQ image. There are also some word differences: word 7 is GOVFN from GCHQ and FOVFN in the other.

That the message was found in Bletch***ing***ley, Surrey may be a bigger clue.

NOTHING IS UNCRACKABLE! It may take a mind a thousand years, or a computer 500. But as long as there are people with curiosity, this will be cracked.


Indistinguishability in the presence of an eavesdropper attack scenario The property of Indistinguishability in the presence of an eavesdropper
as described in the following experiment:

(tract from: Introduction to Modern Cryptography)

It must be interpreted as a scenario of  Ciphertext-only attack or Known-plaintext attack?
Thanks

It's CTO, you are trying to figure out the plaintext given two ciphertexts. M1 and M0 are just bits of either 1 or 0.


Hash function as secure as one-time pad? We know that the one-time pad is provably secure as a cipher to encrypt some data. Is there an algorithm which does the same just as a hash function? Can we get a provably secure hash function? Maybe with some ridiculous properties like the one-time pad got them (really big key length, fully random key)?

OTP requires 1) random key material as long as the message to be encrypted 2) no reuse of the key material or any part, ever 3) secure transmission of the key material between communicants 4) no key material becomes known to anyone ever.
And even then, OTP only guarantees that no other encryption will be harder to break. NOT that a message can't ever be recovered.

1) random -- for crypto purposes, random is very very hard, and very very tricky. We don't know how to do it, though we think some schemes are pretty good. There are many tests, but there are more ways to be non-random than there can be tests.

2) no reuse -- reuse makes an OTP worthless. The Russians did a little reuse in WWII and NSA was eventually able to read some of the traffic encrypted with reused key material. See Venona Project.

3) secure transmission -- NO ONE has solved the secure transmission of arbitrarily long material between nodes. There are Xerox machines, disk copiers, thumb drive copiers, ... Plus burglary (which can sometimes be covered up, leaving the sender making a very bad and completely insecure assumption),

4) no exposure of key material ever -- this requires a degree of fail safe control of the security of stuff well into the future. Humans aren't really compatible with this sort of thing.

But, good hash algorithms (and we are not SURE any of ours are good enough, there's been a poor track record) can be claimed to produce an unpredictable (and so random) string when fed with a suitable input. Sadly, they are deterministic.  Feed a hash algorithm abcd... more than once and you'll get out the same hash. Which means that the unpredictability of hash algorithms is dependent on unpredictability in their inputs.  Not a good thing, people being people. But, if you use some CSRNG for the inputs, why bother with the hash algorithm? If the CSRNG is defective, so will be the randomness of the hashes you produce.

But even if you, foolishly, hand wave away these issues, nearly all hash algorithms produce a shortish bit string.  Say, 128 bits, or 256, or some such. So you could send a message, using one of these hashes as the OTP key material, 128 or 256 bits long.

I wouldn't bother in practice, and wouldn't touch it with a ten foot pole for a theoretical study.  Too much contingency, too much dependence on things athat are out of anyone's control, ....


Asymmetric keys (e.g. RSA) must be so much longer than symmetric keys (e.g. AES). Why? I have been reading that RSA has to do with math (prime numbers), while symmetric key encryption deals with blocks of data and modifying the blocks with replacements and remappings, but I still don't understand why asymmetric encryption has to have longer keys because of that, or whether that's even the reason.

Asymmetric algorithms

Asymmetric algorithms rely on mathematical structure. Keys for asymmetric algorithms typically have some kind of structure, as opposed to being uniformly random bit strings. This structure can be exploited to reduce the cost of breaking the system.

Additionally, with asymmetric cryptography, there is more information to work with; The public key has some known relation to the private key, and everyone has the public key. This is in addition to the usual information that you might have from what the system is used for, e.g. plaintext-ciphertext pairs or message-signature pairs.

Symmetric algorithms

Keys for symmetric algorithms do not have structure - They are simply a uniformly random block of bits.

Other than plaintext-ciphertext pairs, you typically do not have any more information about the key. The relation of the key to the bits of the plaintext/ciphertext are extremely complex with no regular or helpful structure to speak of.

Of course, you could have a cipher with a 256-bit key that is vulnerable to an attack that recovers the key in negligible time from a single ciphertext.

Key size

Key size isn't really what is relevant. What is important is the cost of the best attack to break the system.

With a strong symmetric algorithm, the best attack will be brute force guessing the key. So the size of the key more or less directly controls the cost of the best attack against the system.

The structure used by asymmetric algorithms typically results in the existence of attacks better than brute force guessing the key. So the key size has to be increased to compensate. This is visible in RSA as each prime $p, q$ is much much larger than the size required to prevent brute force guessing; Brute force guessing is not the best attack, so the keys are not scaled against the cost estimate that brute force would have.

Note

The above are generalizations that are only approximately true - it is possible to design symmetric algorithms that have structure - But those are not what people usually mean when they say "symmetric encryption".

Additionally, it's also possible to generate at random an AES key that happens to be the product of two somewhat sizable primes; But that won't tend to help cryptanalysis of AES much because that structure doesn't appear to be helpful.

Suppose you use for symmetric encryption a key of 256 bit. Any of 256-bit numbers can be used as a password. That's why there are 2^256 password candidates that an attacker has to test in a brute force attack.

Where as for RSA not every number can be used. RSA keys are based on prime numbers with special properties. In any given range only a small part of numbers fit these criteria, all others can be easily filtered out before brute force attack. For instance, out of all 256-bit numbers only 2^47 can be used for RSA. This is essentially less than in case of symmetric encryption.

That's why for RSA to get the same number of password candidates you have to use a bigger range. For instance, to get 2^256 candidates for RSA you have to use bigger range, about 13500 bits.

You can find more details here:
Security strength of RSA in relation with the modulus size


Negative exponents in Shoup's threshold RSA? I'm trying to implement threshold RSA operations, starting with decryption based on

  Peeters, R., Nikova, S., & Preneel, B. (2008). Practical RSA Threshold Decryption for Things That Think. Retrieved from http://www.cosic.esat.kuleuven.be/publications/article-1178.pdf

and running into problems where it seems I would have to raise by a negative exponent. The formula is on page 9:

$$
w = \prod_{j\in S} x_j^{\lambda_{0,j}^S}
$$

Peeters et al. reference

  Shoup, V. (2000). Practical threshold signatures. Advances in Cryptology—EUROCRYPT 2000, 207–220. Retrieved from http://link.springer.com/content/pdf/10.1007/3-540-45539-6_15.pdf

for definitions, which to me seems to have the same issue. I'll quote Shoup page 212:

  Let $\Delta=l!$. For any subset $S$ of $k$ points in $\{0, \ldots, l\}$, and for any $i \in \{0, \ldots, l\} \setminus S$, and $j \in S$, we can define $$ \lambda_{i,j}^S = \Delta\frac{\prod_{j^\prime \in S\setminus\{j\} }(i-j^\prime)}{\prod_{j^\prime \in S\setminus\{j\} }(j-j^\prime)} \in \mathbf{Z} $$

(which Shoup defines as equation (2), but I couldn't get the embedded LaTeX to do that)

Shoup uses $\lambda$ on page 214:
$$w = x_{i_1}^{2\lambda_{0,i_1}^S} \dots x_{i_k}^{2\lambda_{0,i_k}^S}$$

(where $x_i$ were previously calculated to be in $Q_n$, e.g. the subgroup of squares in $\mathbf{Z}_n^*$, n being the RSA modulus, though I'm a little bit out of my depth as to what consequences this has. In any case, Peeters et al. don't use the subgroup of squares.)

My problem is: $\lambda_{0,j}^S$ is negative quite often. Simple example $l=3, k=2, S=\{1,2\}, \Delta = l! = 6$.

For $j=1$: $\lambda_{0,1}^S = \Delta \frac{ (0-2) }{ (1-2) } = 6 \cdot 2$

For $j=2$: $\lambda_{0,2}^S = \Delta \frac{ (0-1) }{ (2-1) } = 6 \cdot -1$

How am I supposed to use that in an exponent?

There is nothing wrong with any negative exponent $\lambda$, just modular division for $(-\lambda)$, modulo $n$. That is, one would calculate modular exponentiation for positive $(-\lambda)$ first and modular inverse (division) next.


Randomness in Public Key Encryption For a scheme to be at least CPA secure, one has to randomize the scheme. In case of a secret key encryption scheme, the used randomness will typically become part of the cipher text as in the case of an IV and is "public" (This is not a necessary requirement but how most algorithms work).

Now, if I switch to public key encryption schemes, the randomness will typically not be "public". The decryption algorithm simply removes it without necessarily really knowing it, like for example in the case of LWE or McEliece.

Now my question is: Is this a necessary requirement for public key encryption schemes that at least some of the randomness is not explicitly given as part of the cipher text?

Moreover, might it even be the case that all randomness that effects security has to be non-public? To be more precise, does all randomness that I cannot replace with a public constant value, without harming the security of the scheme have to be private.

(As a motivating example of randomness that can not effect security: I can always add randomness by first XORing the plaintext with a random bit string and adding this bit string to the cipher text but the scheme would be as secure as if I XORed the all zero string instead. Hence, this randomness could be omitted without harming the security.)

A public-key encryption algorithm cannot rely exclusively on "public" randomness.  The reason comes down to the fact that encryption is a public algorithm that can be run by anyone. If the algorithm's output included all the random coins that it used, then an adversary could determine the message from the ciphertext, by running the encryption algorithm with the (given) coins and each of the two candidate messages from the IND-CPA experiment. The true message (and only that message) would yield the target ciphertext.

In some cryptosystems, the decryption algorithm recovers all of the encryption randomness. Examples include encryption schemes based on injective trapdoor functions like RSA. There's no contradiction with security here because one needs the secret key to recover the randomness.

For your second question, we can't go so far as to say that all publicly recoverable randomness is non-security influencing, i.e., replaceable by a fixed public constant (which is the contrapositive of your question).  For example, consider a PRG that uses some random public parameter along with a secret random seed (e.g., an LWE-based PRG).  Now consider an encryption algorithm that chooses both a public parameter and a seed for the generator, to produce a pseudorandom string for the "real" encryption, and outputs the parameter as part of the ciphertext. This would be secure, but might not be if we fixed the public parameter to be, say, all zeros.

Even non-public randomness may be fatal.

For example, RSA public keys are calculated as p*q, where p and q are two random primes. If you have lots of two keys, you can work out if they have any common factors (which would be either p or q) and what it is. Once you have this, you can work out the other, and you can then recalculate the private key.

This was used as an actual attack. It was made easier by the fact that, if you multiplied two public keys together, you could test a third key against both of the first two keys. If you don't get a match, multiply by the third key to test the next candidate against all three keys.

This means that, if p or q are used more than once in different keys, attacker knowing only the public key can calculate BOTH private keys trivially.

  As a "sanity check", Arjen Lenstra et al. tried a gcd-calculating trick out on several million real keys [..] and cracked about 13000 of them. This led to a New York Times report emphasizing that this could be a serious flaw in the way RSA is used: about 0.2% of all keys seen on the Internet seem to be vulnerable.

from http://www.loyalty.org/~schoen/rsa/, referring to http://eprint.iacr.org/2012/064.pdf

Note that this applies to RSA specifically; other encryption schemes will not have this specific issue, this does not mean that they don't have other (comperable?) issues.


Is it possible to check if a number is the product of two primes without factorizing it? I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox).

I have started to run a factorization algorithm on it, and after a few hours it still has not found any factors. But I wouldn't want to keep the algorithm running for a couple more days (or pay for a few EC2 instances to run the factorization on) only to find out that it is simply the product of three or more somewhat large prime numbers.

So, I was wondering if there was a way (even theoretical!) to check if that number was indeed the product of two prime numbers without actually having to factorize it.

Given a 613-bit integer, it is easy to check that it is composite (and we assume that's been done). It can be hard to factor, but that's feasible with GNFS, including with ready-made tools (see Luke Valenta, Shaanan Cohney, Alex Liao, Joshua Fried, Satya Bodduluri, Nadia Heninger's Factoring as a Service), and that's one sure way to demonstrate how many factors it has.

We can do better! We can use Lenstra's ECM repeatedly, with parameters and runtime tuned to find factors less than about 205 bits. That's within reach of the best current implementations, see Paul Zimmermann's list of ECM factoring records. If that fails, then it is a very strong indication that there is no factor 205-bit or less, thus there must be only two factors (for the product of three or more 205-bit integers has at least 613 bits). If that succeeds, we can test the primality and/or factor the rest.

I believe the tool of choice is GMP-ECM.

Edit: That is not generalizable to much larger integers. Starting about 800 bits, it becomes quite hard to tell apart those with two factors, and those with three factors of about equal size.

You can test whether the number is composite without knowing its factors by using Fermat's Lesser Theorem:  If $p$ is prime, $a^{p-1} \equiv 1 \bmod N$, so if $a^{p-1} \not\equiv 1$, you know the number is composite.

Here's an example.

https://youtu.be/keXQRT4aB1E?list=PLKXdxQAT3tCssgaWOy5vKXAR4WTPpRVYK

Some posters noted that this only tells you if it's composite,  not whether it's the product of two primes, which is true.   But note that you don't need a RSA modulus to be a product of two primes, and there are good reasons for using the product of three or more primes for a RSA modulus.


Why SHA-512/256 when we already have SHA-384? Both of them are just SHA-512 with different IV's and truncation. What's the point of having 2 of them? (Actually we have 3 of them as SHA-512/224 is the exact same thing.)

The truncated versions of SHA2 are introduced in 2005 and in the Cryptographic hash Workshop, in 2005, Kelsey listed the reasons as;

Interoperability and security reasons
Need drop-in replacement for SHA1 (MD5)
Have unbroken hashes of wrong size

ECDSA/DSA key sizes
File and protocol formats

Though not mentioned by Kelsey or any other NIST document, the truncation also helps to mitigate from the length extension attack of the SHA series that is due to the Merkle-Damgård construction's architecture problem.
Using different IV enables the domain separation that enables us to have two different random oracles *. It makes sure that the truncated versions have different results. With the domain separation  $$\operatorname{SHA-224}(m) \neq \operatorname{SHA-256}(m)|_{224}$$ where $|_{224}$ is the truncation

What's the point of having 2 of them

If you have an already implementation that uses SHA-256 and you want to mitigate from the length extension attack then SHA512/256 is a good choice. Also, it possibly may increase attack strength.

Also, when you need only 256 but hash output, if you use the SHA512/384 you need to trim that yourself. Not a good idea in the case of programming and in the case of security since you are using the same random oracle.

The ECDSA/DSA key sizes: ECDSA-384 signing SHA512/384 is a good choice especially for 64-bit devices since SHA512 is designed for 64-bit.

Someone tried to use SHA512 and has problems with TLS 1.2. if you are adopting ECDSA-384 signing SHA512/384 is a good choice as above.

For SHA512/224 and simply for 224-bit usage is due to the Triple-DES security, $112 \cdot 2 = 224$. There is a very extensive answer for this by Fgrieu SHA-224 Purpose.

*A random oracle is like a kind of hash function and the same concept applies to hash functions.


Interpretation of (NIST) Non Overlapping Template Matching Test Regarding the Non-Overlapping Template test, this test normally gives us a bunch of p-values (148 values). I would like to ask that how do we interpret those values into a single p-value for presenting in an academic report. I have seen many papers illustrate as only a single p-value. For example,

Cao et.al, Phys.Rev X 6, 2016

In this work the p-value of Non-Overlapping Template test is shown as a single value. I have tried using fisher method to combine all of the p-values but by it's characteristic, the p-value after a combination drops exponentially.
Is there any simple way to interpret ?

Thank you in advance.

First, Fisher's method is a way to combine several independent statistical tests with known distributions under the null hypothesis into a single statistical test with a known distribution under the null hypothesis.  If you would have raised an alarm for certain outcomes of the individual statistical tests with a known false alarm rate, then you can use the same criteria to raise an alarm for the composite test with a known false alarm rate.

Another way to look at this is: Fisher's method is a way to combine several independent d20 rolls into a single d20 roll, so that if you're given a black box that prints d20 outcomes, you can't tell whether a gremlin inside is doing several statistical tests and applying Fisher's method to them and rounding the result, or just rolling a d20.

If you would have raised an alarm when one of the statistical d20 tests rolled a 1 for the standard false alarm rate of 0.05, then you can raise an alarm when the Fisher composite statistical d20 rolls a 1 for the standard false alarm rate of 0.05.
Another way to look at this is:

With one statistical test, you lay out the possible test outcomes ($p$-values) uniformly on a line segment from $[0,1]$ and raise an alarm for any data that gives a $p$-value in $[0, 0.05]$.
With two statistical tests, you have a grid of outcomes on the unit square $[0,1] \times [0,1]$.  On what subspace of the unit square do you raise an alarm?

Fisher's method is a particular choice of which subspace of the unit square raises alarms.  There's some good illustrations of this—and comparisons to an alternative method of combining $p$-values—in the answers to a question about Fisher's method on stats.se.

There are other methods too for combining a collection of $n$ values $\{p_i\}_{i=1}^n$ into a single test statistic with a known distribution:

The arithmetic mean $\sum_i p_i/n$, as discussed in the stats.se answers, and known as Edgington's method.
The root-mean-square, $\sqrt{\sum_i p_i^2/n}$.
The geometric mean $\prod_i {p_i}^{1/n}$, which turns out to be tantamount to Fisher's method—just take the log.
Pearson's complementary geometric mean, $1 - \prod_i (1 - p_i)^{1/n}$.
The minimum $\min_i p_i$.
$p_1$, ignoring $p_2, p_3, \dots, p_n$ altogether.

Why should you prefer one of these over the others?  They all give rise to statistical tests that have any prescribed false alarm rate you want, so they must all be good, right?  Well, there's an elephant in the room.

Why raise an alarm when you roll a 1, rather than, say, a 7, on your d20—i.e., why do we care about $p < 0.05$?  What's really interesting is the alternative hypotheses.  The null hypothesis is that the device is working correctly as intended (and perhaps that working correctly means a perfect uniform distribution).  But the test is valuable insofar as it raises alarms at a substantially higher rate for plausible deviations from the null hypothesis—for instance, a significantly higher number of one bits than zero bits, which can happen in samples under the null hypothesis but only with low probability.  What plausible deviations might there be?

Study the physics or engineering of the system—don't just discard them as waste byproducts of the process that led you to a good NIST test result.

What do you know about the physics that might let you predict the result better than flipping a coin?
What manufacturing flaws and failure modes could the engineered system have that might change the distribution?

Many of these deviations or failure modes will not be detected by generic statistical tests.  As an extreme case, if your device chooses $k$ uniformly at random and produces $\operatorname{AES}_k(0) \mathbin\| \operatorname{AES}_k(1) \mathbin\| \operatorname{AES}_k(2) \mathbin\| \cdots$, except when it's broken and always chooses $k = 0$, generic statistical tests will never detect that broken case.

What matters for security is showing that the smartest, best-funded physicists in the world can't do better than a certain advantage at predicting what the outcome is, and that if the device fails in some way then you will detect that failure and stop relying on it.

The $p$-values of NIST statistical tests on samples you took during development?  These are more like the waste byproducts of a process that led you to a good hardware RNG.

As you're dealing with randomness, the test results have randomness within them too. So combinatoric tests have to be statistically based. I've never seen Fisher used for this in the common  randomness tests.  By definition, $p$ is uniformally distributed 0 to 1 for the null hypothesis, ie. data is properly random.  A common      technique is for a Kolmogorov–Smirnov (KS) test against the expected uniform distribution. The test then outputs a single $p$ value for uniformity and thus data randomness. Hope for $p > 0.01$.

I only ever generate enough data for Diehard testing, but you see this approach used therein.  For example, the 3D Spheres test consolidates 20 $p$ values into one:-

 ::              THE 3DSPHERES TEST                               ::
 :: Choose  4000 random points in a cube of edge 1000.  At each   ::
 :: point, center a sphere large enough to reach the next closest ::
 :: point. Then the volume of the smallest such sphere is (very   ::
 :: close to) exponentially distributed with mean 120pi/3.  Thus  ::
 :: the radius cubed is exponential with mean 30. (The mean is    ::
 :: obtained by extensive simulation).  The 3DSPHERES test gener- ::
 :: ates 4000 such spheres 20 times.  Each min radius cubed leads ::
 :: to a uniform variable by means of 1-exp(-r^3/30.), then a     ::
 ::  KSTEST is done on the 20 p-values.                           ::
     ^^^^^^

You can also see it being used in the following NIST results snippet taken from a NIST random excursion results Q & A which is talking about their interpretation:-

  9   3   6   5  10   8   7   7   8   8  0.808725     70/71      RandomExcursionsVariant
  6   5   5   8  10   8   7   9   5   8  0.901761     69/71      RandomExcursionsVariant
  3   9   5  12   6   6   6  10   8   6  0.437274     71/71      RandomExcursionsVariant
  3   6   7   2  10  11   6  10   7   9  0.238562     71/71      RandomExcursionsVariant
  4  10   6  12   3  13   4   4   5  10  0.033552     71/71      RandomExcursionsVariant

The decimal number (e.g. 0.808725) is a KS test performed over 9   3   6   5  10   8   7   7   8 individual scores where one failed with $p$ < 0.01. The  NIST SP 800-22 software does this amalgamation automatically.

You should be able to adapt this technique to the 148 values of your NIST Template test if the program didn't produced them already. Spreadsheets and standard programming libraries can help.


The security proof for Key Policy Attribute Based Encryption My question relates to the original KP-ABE paper:

http://research.microsoft.com/en-us/um/people/vipul/abe.pdf

I'm having trouble understanding the proof (pages 10–13) that the scheme is secure in the Selective Set Model:

  Proof: Suppose there exists a polynomial-time adversary A, that can attack our scheme
  in the Selective-Set model with advantage $\epsilon$. We build a simulator B that can play the Decisional BDH game with advantage $\epsilon/2$. The simulation proceeds as follows:

  We first let the challenger set the groups G1 and G2 with an efficient bilinear map, e
  and generator g. The challenger fips a fair binary coin $\mu$, outside of B's view. If $\mu = 0$, the challenger sets $(A, B, C, Z) = (g^a,g^b,g^c,e(g,g)^{abc})$, otherwise it sets $(A, B, C, Z) =(g^a, g^b, g^c, e(g,g)^z)$ for random $a, b, c, z$. We assume the universe, U is defined.

  ...

  Phase 1 A adaptively makes requests for the keys corresponding to any access structures T such that the challenge set $\gamma$ does not satisfy T . Suppose A makes a request for the secret key for an access structure T where $T(\gamma) = 0$. To generate the secret key, B needs to assign a polynomial $Q_x$ of degree $d_x$ for every node in the access tree T .

  We first define the following two procedures: PolySat and PolyUnsat.

  PolySat$(T_x,\gamma,{\lambda_x})$ : ....

  PolyUnsat$(T_x,\gamma, g^{\lambda_x})$: This procedure sets up the polynomials for the nodes of an access tree with unsatisfied root node, that is, $T_x(\gamma) = 0$. The procedure takes an access tree $T_x$ (with root node x) as input along with a set of attributes $\gamma$ and an element $g^{\lambda_x} \in G1$ (where $\lambda_x \in Z_p$).
  It first defines a polynomial $q_x$ of degree $d_x$ for the root node $x$ such that $q_x(0) = \lambda_x$. Because $T_x(\gamma) = 0$, no more than $d_x$ children of $x$ are satisfied. Let $h_x \leq d_x$ be the number of satisfied children of $x$. For each satisfied child $x'$ of $x$, the procedure chooses a random point $\lambda_{x'} \in Z_p$ and sets $q_x(index(x')) = \lambda_{x'}$. It then fixes the remaining $d_x - h_x$ points of $q_x$ randomly to completely define $q_x$.

  ...

  To give keys for access structure $T$, simulator first run PolyUnsat$(T,\gamma,A)$ to define a polynomial $q_x$ for each node $x$ of $T$.

  ...

My question is relating to the last (bold) paragraph: How is it possible to define such $q_x$, since the simulator cannot learn $\lambda_{x}$ from $g^{\lambda_x}$ unless he can compute discrete log?

Because the simulator picked   $\gamma$ to generate $g^\gamma$.  He acts as an ABE authority for an attacker who breaks the Selective Set Model security game so he can use the attacker to solve the   Decisional Bilinear Diffie-Hellman problem .

As a result of being  the ABE authority, the simulator  knows  the master secrets and all other secrets created by the ABE authority. Remember, that for normal ABE, the authority knows everything, including user's private keys (attributes).

  Proof: Suppose there exists a polynomial-time adversary A, that can attack our scheme
  in the Selective-Set model with advantage $\epsilon$. We build a simulator B that can play the Decisional BDH game with advantage $\frac{\epsilon}{2}$. The simulation proceeds as follows:

  We first let the challenger set the groups G1 and G2 with an efcient bilinear map, e
  and generator g. The challenger flips a fair binary coin $\mu$, outside of B's view. If $\mu$ = 0,
  the challenger sets $(A; B; C; Z) = (g^a, g^b, g^c, e(g, g)^{abc} )$ otherwise it sets
  $(A; B, C,Z) =
(g^a, g^b,g^c, e(g, g)^z)$
   for random $a, b, c, z$. We assume the universe, $U$ is defined.

The simulator, then, gets to set up an ABE system so he can use the attacker

  The simulator B runs A. A chooses the set of attributes $\gamma$ it wishes to be challenged upon

$\gamma$ has nothing to do with the DBLDH assumption.

I have managed to figure out the answer to my own question, so I thought I would share it here, in case someone else would encounter the same problem.
The set-up of the simulator $B$ is so that it simulates a challenger in the game with $A$, in which the challenger has the master secret $ab$, where $g^a, g^b$ are given as inputs of the BDDH game. Now of course $B$ cannot learn $a$, $b$, or $ab$, but it can construct private key for an access tree $T$ that implicitly shares the secret $ab$.
The PolyUnsat$(T_x,\gamma,g^a)$ is called to split the secret $a$ to shares such that their combination that satisifies $T_x$ will recover $a$. Notice that $T_x(\gamma)=0$.

It first defines a polynomial $q_x$ of degree $d_x$ for the root node x such that $q_x(0)=a$

Now that is easy, because $g^{q_x(0)}=g^a$ which is given as input. To completely define $q_x$, it needs another $d_x$ points. It can do that by assigning:
$g^{q_x(i)}=g^{\alpha_i}$ for a random $\alpha_i \in Z_q$. Notice that $B$ does not knows $q_x$, but defining it this way makes sure that it can compute $g^{q_x(j)}$ for any $j$ (using Lagrange interpolation), and that $g^{q_x(0)} = g^a$. So implicitly, it has split the secret $a$ (unknown to itself) to shares so that they can be combined to recover $g^a$.

For each child node $x'$ which is not a satisfied node, the algorithm calls $PolyUnsat(T_{x'},\gamma,g^{q_x(index(x'))})$

Now this can be easily done, because $g^{q_x(index(x'))}$ can be computed from $\{g^a, g^{q_x(0)}, g^{q_x(1)}, ..\}$ using interpolation.

The key corresponding the each leaf node is given using its polynomial as follows:
$D_x = g^{b.q_x(0)/r_i}$ if $x \in \gamma$

In this case, $B$ knows $q_x(0)$ but does not know $b$. However, $D_x = (g^b)^{q_x(0)/r_i}$ can be computed because $g^b$ is given and that $q_x(0)/r_i$ is known since $1/r_i$ is known in $Z_q$.

$D_x = g^{q_x(0)/\beta_i}$ if $x \notin \gamma$

This is also computable, since $g^{q_x(0)}$ is known (not $q_x(0)$), and so is $1/\beta_i$.
These share are valid, because for any secret $s$, we can have the following valid ciphertext: $E = \langle\gamma, E' = m.e(g^a,g^b)^s, \{E_i = g^{s.r_i} | i \in \gamma\} \ \cup \ \{E_i = (g^b)^{s.\beta_i} | i \notin \gamma\}\rangle$. Furthermore, all $D_x$ are uniformly distributed, so they have the same distribution as in the original game.
Finally, to simulate the BDDH game, upon a challenge $\{m_0,m_1\}$, the simulator will toss the coin and set $E' = g^h, \{E_i = (g^c)^{r_i}\}$. If $A$ guesses it correctly, then $g^h = g^{abc}$, and the simulator wins the BDDH game.


What's wrong with this digital signature scheme? With regards to user authentication...

The server sends Alice a randomly chosen number.
Alice signs the number and sends the signature back to the server.
The server checks the signature using Alice's public key. If it's valid, the server accepts her connection request.

Suppose that Alice uses the same private key to log in to the server and sign her emails. The authentication mechanism signs the bare challenge without hashing, while Alice signs the hash of the email message.

Apparently, the server can forge emails from Alice under this scheme? If so, how could this be prevented?

Regardless of the possible answers here, which probably focus on some technical difference between the signature scheme for authentication vs the signature scheme for non-repudiation, the practical way to prevent this is to have at least two key pairs for the different use cases.

Alice would have a private key and matching certificate to perform the authentication. Preferably she would even have multiple ones for each use case, with access conditions matching the use case. Although this scheme uses signatures, it uses them just to authenticate Alice at a particular time and the signatures do not need to last.

Alice would have another private key and matching certificate to perform the signatures for non-repudiation. Non-repudiation is used for documents to show that a specific person has signed it; that person nor others cannot repute the signature: it must have been set by somebody who has access to the private key. These signatures are stored with the document so that they can be accessed later.

The private keys for non-repudiation generally need higher security than those for authentication. Signatures are stored, so the key size needs to be future proof. This difference is reflected in the certificate, which may for instance have to adhere to an established Certificate Practice Statement to be accepted - a self signed certificate created on your computer cannot be used to buy a house.

Old style Government ID cards commonly have three private keys and matching certificates on them: one key for authentication (to the OS, TLS or applications), one key for non-repudiation (a digital signature to replace the written signature you are used to) and one for decryption (to keep messages send to you confidential).

This is a kind of blind signatures. Most of the context of blind signatures are unsecure, but there are few interesting use cases. For you case, Alice can just hash the random server challenge before signing and the server hashes as well the challenge during verification/authentication.


RSA Proof of Correctness Can anyone provide an extended (and well explained) proof of correctness of the RSA Algorithm?

And why is it needed?

I can't say that this or this helped me much, I'd like a more detailed and newbie like explanation, if you don't mind too much... ;)

After a couple of hours of detailed study I've come to an answer.

As we all know the RSA algorithm works as follows:

Choose two prime numbers $p$ and $q$,
Compute the modulus in which the arithmetic will be done: $N = pq$,
Pick a public encryption key $e \in Z_n$,
Compute the private decryption key as $d$ such that $ed = 1 \bmod{\phi(N)}$,
Encryption of message $m$: $c = m^e \bmod{N}$,
Decryption of crypto message $c$: $m = c^d \bmod{N}$.

While these statements and equations can stand true for some fixed values of $p$, $q$, $m$, $e$, $d$ in order to define the RSA as a general cryptographic algorithm we must prove their generality for any message $m$ we wish to encrypt.

This is therefore the reason why the proof of the correctness of the RSA algorithm is needed.

Getting to the proof we can formalise it as follows:

Hypothesis:

$\gcd(p,q) = 1$
$N = pq$
$ed = 1 \bmod{\phi(N)}$

Thesis:

$ (m^e)^d = m \bmod{N}$, for all $m \in Z_n$

  NOTE:The important part is ^^^^^^^^^ the for all part...

Proof:

Being $m \in Z_n$ there are only two possible cases to analyse:

  1) $\gcd(m, N) = 1$

In this case Euler's Theorem stands true, assessing that
$$ m^{\phi(N)} = 1 \bmod{N}\text{.}$$

As for the Thesis to prove, because of Hypothesis number 3, we can write:

$$(m^e)^d = m^{ed} = m^{1 + k\phi(N)}\text{,}$$

furthermore

$$ m^{1 + k\phi(N)} = m\cdot m^{k\phi(N)} = m \cdot (m^{\phi(N)})^k,$$

and for Euler's Theorem

$$m \cdot (m^{\phi(N)})^k = m \bmod{N}$$

Proving that the thesis stands in this case.

  2) $\gcd(m, N) \neq 1$

In this case Euler's Theorem does not stand true any more.

For a result of the Chinese Remainder Theorem (check this SO question - Chinese Remainder Theorem and RSA - or just wiki it) it is true that if $\gcd(p,q) = 1$ then:

$$ x = y \pmod{p} \land x = y \pmod{q} \Rightarrow x = y \pmod{pq}$$

So by proving the following two statements we would have finished:

$ (m^e)^d = m \bmod{p}$
$ (m^e)^d = m \bmod{q}$

Because $\gcd(m, N) \neq 1$ one between $\gcd(m, N) = p$, and $\gcd(m, N) = q$ must stand true. I will demonstrate that both the above statements stand true in the case $\gcd(m, N) = p$, being it absolutely identical (by switching letters) to prove it for $\gcd(m, N) = q$ as well.

So let it be $\gcd(m, N) = p$, this implies that $m = kp$ for some $k > 0$ which means that $m \bmod{p} = 0$. By concerning the first statement we also have

$$ (m^e)^d = ((kp)^e)^d$$

which therefore results to be a multiple of $p$, and so it is equal to zero.

So the first statement becomes $0 = 0$ and is proven to be satisfied.

Concerning the second statement we have that Euler's Theorem results to be proved in $Z_q$, since $\gcd(m,q) = 1$, so:

$$ m^{\phi(q)} = 1 \bmod{q}\text{.}$$

This implies that we can write:

$$\begin{align}
 (m^{e})^d &= m^{ed} \\
&= m^{ed - 1}m\\
&= m^{h(p-1)(q-1)}m\\
&= (m^{q-1})^{h(p-1)}m\\
&= 1^{h(p-1)}m = m \bmod{q}.
\end{align}
$$

which definitively proves the second statement and theorem.

Here is a blog post link: tominology

For a sketch of proof using Fermat's little theorem and a simplified JavaScript implementation


Using a block cipher with timestamp instead of counter I have a system where machine A sends updates to machine B. The updates are sent over the internet, where each update is a single UDP datagram. Machine A sends a local timestamp in each update (we can assume that the timestamp increments for each message). Messages can vary in length, but there is a maximum size (consider it <1kb).

I would like to secure this communication. Specifically I require that:

Machine B can verify that an update is from machine A, and no tampering has occurred.
An attacker cannot decrypt the updates.
The implementation on machine A is simple and lightweight.

It's okay for an attacker to drop, reorder and replay the updates. (The timestamp in the update mitigates such attacks.)

I can arrange for both machines to share a symmetric key.

My initial thought is to encrypt each message with a block cipher in ECB mode, where each message fits in a single block. I believe the timestamp in the message mitigates the problems with ECB, performing a similar function to the incrementing counter in CTR mode. Are there problems with substituting a timestamp in place of a counter?

One problem here is that the messages are larger than most cipher block sizes. I could instead use a stream cipher, but I'm not sure of the consequences of doing so. Alternatively, there are apparently constructions to make a block cipher with a larger block size, but I'm not sure how they work either.

A timestamp in the message won't fix the problem with ECB mode. ECB mode uses the same key for each block, so you will leak the fact that blocks are the same within the same message, and if you use the same key static key for every update, between different messages as well.

Consider a higher level library such as libsodium or spiped from tarsnap to avoid worrying about these details.

It sounds like what you are looking for is essentially a (possibly lightweight) Authenticated Encryption scheme. AE schemes are the focus of a lot of academic interest at this moment. With the CAESAR competition many new efficient and secure schemes have been proposed to be adopted as standards. If you want an earlier example of a very good Authenticated Encryption scheme, look at GCM (Galois/Counter Mode), as mentioned by Lery above.

Unless you are a specialised researcher yourself, it would probably be more advisable to choose a scheme endorsed by the Crypto community (which translates to being around for a while enjoying some publicity without being broken, like the third-round CAESAR candidates), rather than designing your own.

As for you questions regarding timestamps and counters, there's not enough information to answer those. If you have some concrete constructions in mind, I suggest you add more details (and preferably a diagram).


Why should the RSA private exponent have the same size as the modulus? Consider the generation of an RSA key pair with a given modulus size $n$ and a known, small public exponent $e$ (typically $e = 3$ or $e = 65537$). A common method is to generate two random primes numbers of size $n/2$ (or very close), and check at least that they are probable primes and that $\mathrm{gcd}(e, (p-1)(q-1)) = 1$. Once $p$ and $q$ have been vetted, from what I've seen, the other parameters (the private exponent $d$, or the CRT parameters if desired) are computed but not subject to any extra check.

I have met an extra requirement whose purpose I don't understand. In the Référentiel Général de Sécurité (something like the French equivalent of FIPS), annex B1 §2.2.1.1, a rule states:

  [RègleFact-3] Private exponents must have the same size as the modulus.

What is the purpose of this rule? I know that small private exponents are bad, but here small means something like $d \lt N^{0.5}$. Even allowing for a security margin, this is a far cry from requiring $d \gt N/2$. What can go wrong if the size of $d$ is not verified (so the probability that $d \lt a N$ is close to $a$)?

Well, first off, it appears that these requirements are a bit confused.  If the requirement is that for a given modulus $N$ and public exponent $e$, that the corresponding private exponent $d$ satisfies $d > N\!/2$, that rules out all public keys (!).  You can see that from the necessary and sufficient relation $de = 1 \mod \operatorname{lcm}( p-1, q-1 )$, and so if $d$ exists (which it will of $e$ is relatively prime to $\operatorname{lcm}(p-1,q-1)$), then there exists a $d > 0$ with

$$d < \operatorname{lcm}(p-1, q-1) = (p-1)(q-1) / \!\operatorname{gcd}(p-1, q-1) \\ \le (p-1)(q-1) / 2 < N\!/2.$$

So, what other interpretation can we give to this rule?  Well, one alternative is that you must use a private exponent $d > N\!/2$, even though it is not the smallest possible.  However, as such a $d$ always exists, that actually mandates no requirements whatsoever on either $N$ or $e$ or the generated signatures or encrypted messages, and so cannot affect the security of a generated public key.  In any case, when you're doing the RSA private operation, you generally use the CRT optimization, and so you don't actually use the value $d$ directly (and a larger than necessary value of $d$ would give you exactly the same CRT parameters).

The bottom line is that if you need to conform to these requirements, you'll need clarification on what the requirements actually are; the literal interpretation doesn't make sense.

Now, for your actual question: what is the purpose of this rule?  Well, the document does go on to give this justification (if I remember my French correctly):

  "Using specific private exponents (for example, small private exponents) to improve performance is forbidden because of practical published attacks in this area"

It appears that they are indeed worried about the published attacks against $d < N^{0.5}$, and possible refinements on that attack that might work for larger $d$.

As for the probability that a random public key will yield a small value of $d$, well, it turns out to be quite unlikely (if $e$ wasn't chosen specifically to make $d$ small).  The easiest way to see this is to assume a modest $e$ (for example, 65537), and note that

$$d \cdot e > \operatorname{lcm}(p-1, q-1)$$

and hence

$$d > \operatorname{lcm}(p-1, q-1)/e \approx \frac{N}{e \cdot \gcd(p-1, q-1)}.$$

Hence, $d$ cannot be small unless $\gcd(p-1, q-1)$ is large; that is, if $p-1$ and $q-1$ share a large common factor.  Because the probability of $\gcd(p-1, q-1) > k$ is $O(1/k)$, this means that in practice, a small $d$ never happens by chance.

Lastly, it isn't quite true that with other standards, there's no check on the value of $d$.  For example, FIPS 186-3 does have the requirement that $d > 2^{\mathit{nlen}/2}$.

In academic mathematical french, numbers do not have a size. They are values. Only the representation of numbers can have a size (e.g. 357 has a size of 3 digits in base-10 representation).
Checking d > N/2 is a check of the value of d.
Checking d fills a 256-byte buffer is about the size.
lcm(p-1, q-1) = ((p-1)*(q-1))/gcd(p-1, q-1) and can be much smaller than n=p*q
In practice, p-1 and q-1 could have some common factors, and d is computed mod lcm(...). Then it is usual to have the value of d much smaller than n=p*q.
The size of the binary representation of d could be smaller than the size of the binary representation of n by many bits. | log2(n) - log2(d) | > 20 is very frequent.
It is known that some attacks will succeed if approximately log2(d) < log2(n)/3. Many authors, many bounds.
You can't get d > n/2, even if gcd(p-1, q-1) == 2  (smallest possible common factor)
Unfortunately 1/e mod ((p-1)*(q-1)/2) is always < n/2
The French document you mention is using the word "taille" (size). Later the document is about p and q "la meme taille" (same size). The correct recommendation about values is p*p > 2^2048/2, q*q > 2^2048/2  . "La meme taille", in base 10 representation, can be different for numbers p, q you would accept as valid, reversely, 13 and 17 are the "same size"
Let us not be too picky, and consider "the position of the most significant bit in a base 2 representation" as a synonym for "the same size"?
The bureaucratic paradox in civil servant scripting, you can't solve it : d < n/2 by definition, no way to make them the "same size".
In a "courtelinesque" style, you should ask for a government change, so the author of the document will disappear, and the new prime minister will change the politics and decrees about "d".


Identification of correct plaintext after decryption in Rabin cryptosystem In the Rabin cryptosystem, decrypting a message can produce four different outputs, of which only one is the correct plaintext.  How can one know which of the outputs is the correct one?

This is a solution that should work with very high probability, but possibly can fail. As a bonus it also resists tampering with the ciphertext.

As encrypter generate a random key (say a 128-bit key for AES128-CTR) and encrypt the plaintext using that key. Then compute a MAC over the ciphertext (for example using HMAC-SHA1) using the same key. Finally you encrypt the randomly generated key using the Rabin cryptosystem. You then send $encrypted\_key || MAC || ciphertext$ to the receiver.

The receiver first decrypts the encrypted key to get 4 potential keys. For each key he computes the MAC over the ciphertext and see if it equals the sent MAC. If yes he proceeds to decrypt the ciphertext using that key.

Another bonus of this system is authentication. If you have a shared secret/token of sufficient cryptographic length (say 128 bits) between sender and receiver you can use that as the key for the MAC instead of the randomly generated key.

Decoding produces three false results in addition to the correct one,
  so that the correct result must be guessed. This is the major
  disadvantage of the Rabin cryptosystem and one of the factors which
  have prevented it from finding widespread practical use.

That's straight from the Wikipedia page.  It goes on to discuss that guessing the answer is easier with something like a text-based message, but obviously much more difficult if you're decrypting a number.  Or imagine if you double-encrypted your result, meaning you'd have to perform decryption 5 times (first time results in 4; then one more for each of those) and result in 16 possible outcomes.

There may be use for this type of cryptosystem, but for most applications it seems this flaw is pretty major.


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.


Can SRP be used with Elliptic Curves? I'm sure it can, because SRP (secure remote protocol) can be implemented everywhere where Diffie-Hellman works, but I need a proof to put this aspect into Wikipedia.

Edit: ok, can it be at least partially moved to elliptic curves?

SRP needs more than a group, it requires a field. See the specification: second user sends $B = v + g^b$. This requires two operations, addition and multiplication. You cannot trivially slap that onto a group which provides only one operation, such as elliptic curves.

Variants of SRP which use elliptic curves have been proposed, but do not seem to have reached wide acceptance or even substantial scrutiny yet. See for instance this proposal. Also, this article gives some details (e.g. it claims to break a previous proposal for an EC-based SRP variant).

The DH operations in the SRP algorithm cannot simply be replaced with 'equivalent' ECDH operations.

In DH, we generate a public key A from a private key a like so:

A=pow(g, a, n)

where pow(g, a, n) is g^a mod N, and g and N are known constants

In ECDH, we generate a public key A from a private key a like so:

A=point_mult(a, g)

where point_mult represents EC point multiplication, a is a scalar, and g is a known generator point on the elliptical curve.

Let's see what happens if we simply try to replace every instance of DH A=pow(g, a, n) in the SRP algorithm with ECDH A=point_mult(a, g).

In the SRP algorithm, the server generates the server session key as follows:

S_s = pow(A * pow(v, u, N), b, N)

where A was previously calculated as A=pow(g, a, n), and v was previously calculated as v=g^x.  So the above equation could be written as:

S_s = pow(pow(g, a, n) * pow(g^x, u, N), b, N)

or

S_s = pow(pow(g, a, n) * pow(g, u*x, N), b, N)

Focusing on just pow(g, a, n) * pow(g, u*x, N) from the above equation, if we replace the DH operations in this expression with their 'equivalent' ECDH operations, we would have:

point_mult(a, g) * point_mult(ux * g)

And, therein lies the problem.  The above expression is the product of two points on an elliptical curve.  But, in elliptical curve math, there is no way to multiply two points.  We can add two points, and we can multiply a point by a scalar - but we cannot multiply a point by another point.


Relationship between PRF/KDF/MAC? It seems that not every MAC is a KDF. But would any PRF also work as both KDF and MAC? Could someone explain the relationship between these 3 definitions?

A key derivation function (KDF) takes in some secret keying material, which may or may not be uniformly distributed, and where the adversary may also have some auxiliary information about the keying material or its distribution, and outputs a uniformly distributed bit string. See definitions 5, 6, and 7, here.

Intuitively, a KDF's job is to take in some keying material which has some minimum entropy, but which might not be uniform as a bit string (or not be a bit string at all!), and output a "smooth" bit string of essentially the same entropy as the original input. A classic use case is a Diffie-Hellman (DH) secret obtained from a key exchange protocol. This secret is not a bit string, but rather a group element. Moreover, when encoded as a bit string, this group element will not be uniformly distributed over all bit strings of the corresponding length. However, it does have high entropy, and a KDF can then be used to extract from the secret DH group element a nice and uniformly distributed bit string (i.e., a symmetric key).

The security definition of a KDF (Def. 7 in the link above), is essentially that it should behave like a random function when evaluated on the secret keying material and some arbitrary additional input (there are some additional bells and whistles in Def. 7 provided in the link, but what I said contains the gist of it).
A pseudorandom function (PRF) takes in a secret key and a message, and outputs a bit string. The security requirement for a PRF (see Def. 5.6, here) is that it should behave like a random function when evaluated on arbitrary messages---provided the secret key is uniformly distributed.

Notice that PRFs and KDFs are quite similar, but that a PRF has a much more stringent requirement on its secret key. Essentially, a non-uniformly distributed secret key voids all security guarantees of a PRF.
A message authentication code (MAC) takes in a secret key and a message, and outputs a tag. There is also a corresponding verification algorithm that on input the secret key, a message, and a tag, outputs either VALID/NOT-VALID. The security requirement of a MAC is that for someone not knowing the secret key, it should be hard to come up with a message and a tag, such that the verification algorithm outputs VALID. (Note that this is a very weak form of MAC security, and usually we require something stronger called EUF-CMA security, see Def. 9.1 and Def. 9.2 here).

As for the relationships between them, it follows from what I wrote above that KDF $\implies$ PRF $\implies$ MAC. That is, since a KDF is supposed to behave like a random function even when given a non-uniform secret key, it of course also behaves like a random function when the secret key is uniformly distributed. That a PRF allows you to build a MAC is shown in Section 9.6 here.

In the other direction none of the implications hold generally. That is, it is not the case that all secure MACs are secure PRFs (can you think of a counterexample?), and not all secure PRFs are secure KDFs.

About any MAC is a KDF you can find answer here: Can any MAC be used as a KDF?
And there is HKDF which based on HMAC (https://en.wikipedia.org/wiki/HKDF).

MAC is used to confirm that the message came from the stated sender and has not been changed.

KDF is used to strengthen the security of the symmetric key after DH (Diffie-Hellman).

I am not sure, but in TLS 1.2 PRF is used for Key Calculation. You can read more details from RFC 5246:

https://tools.ietf.org/html/rfc5246#section-5
https://tools.ietf.org/html/rfc5246#section-6.3

Clarification needed in TLS 1.2 key derivation process also have answer about MAC and PRF.


Use a SHA256 as a key for AES256 Is it safe to use the SHA256 of a hard-to-bruteforce string as the key to encrypt data with AES256?

Yes, it is safe. The answer of @kelalaka (the first part, before update) it not correct.

The OP is saying that the password is a strong string which is hard to bruteforce. That's why the answer of @kelalaka the attacker, firstly, will try to brute-force is not relevant to the question. Everything @kelalaka is saying about password stretching is correct, but it is not relevant to this particular question.

I am curious why would you want to use SHA256 instead of password, if your password is complex and is hard to bruteforce. But this is another story.

I would suppose that some readers who didn't read the question attentively will vote  my answer down. Some people don't think much and just apply patterns that they have in their minds, like Password? --> hashing is bad --> use stretching instead But guys, read the question once again.

SHA256 Hash Generator will allow you to check the sha256 hash of any string.


Is there any open-source white-box implementation of AES or DES? I googled it, but got no result.  There is a binary executable of a white-box implementation of DES (scroll down), but no source code is provided.

The same page also links various papers about white-box cryptography, but these don't contain the implementation.

I want to study such an implementation to learn about the techniques used there.

I add my whitebox AES implementation on GitHub in:

C++
Java

C++ version implements both Chow's (mixing bijections, input/output encodings, external encodings) and Karroumi's (dual AES in each column) whitebox AES scheme plus Billet's key recovery attack on both schemes.
Java implements Chow's scheme only.
PS: Due to low reputation I post links to schemes to the comment below.

I'm not sure I get your Q? but do these links help

http://people.csail.mit.edu/rivest/crypto-security.html#Software
(Eric Young's DES implementation)
http://www.tero.co.uk/des/
http://www.opensource.apple.com/source/OpenSSL/OpenSSL-26/openssl/crypto/aes/
http://www.opensource.apple.com/source/OpenSSL/OpenSSL-26/openssl/crypto/des/


Is it possible to verify and relay an encryption key with a trusted but transparent third party? I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?):

Bob has an encryption key. Alice has the encrypted data and wants to buy the key from Bob.
Bob sends the key to the smart contract (SC).
Alice sends some ether (and perhaps the encrypted data or some function on it) to the SC.
The SC verifies that the key decrypts the data properly. If it doesn't, it halts.
The SC sends Bob the ether, and Alice the key.

The main issues I'm finding when I'm trying to think of a solution are:

How does the third party verify a decryption is correct?
Is it possible for the third party to verify this decryption without revealing it, since it is transparent? I know of zero knowledge proofs, but am not sure of how they could apply here.

Thank you!

I'm not sure what you mean by transparent.
With a trusted third party what you ask is trivial. But with etherium I believe you can't, the key would become public there is nothing secret on the blockchain.

If we wanted our own distributed third party this can be done. You can perform secret sharing and send part of the key to each member of the distributed escrow. They can then perform shared computing to verify the secret without revealing the secret.

How about hash checksum?
Bob sends the key and the hash checksum to SC
SC decrypts the data and hash the result, see if it matches with the checksum


plaintext distribution ,perfect secrecy cryptosystem I have been trying to solve the next problem:
let pi be a perfect secrecy cryptosystem with specific plaintext probability distribution.
How to prove pi will have perfect secrecy for all other possible plaintext probability distributions?

Perfect scheme \Pi defined such that for every distribution over M and every $c\in C$ it holds that:  $Pr[C=c|M=m]=Pr[C=c]$ which means that probability to get a cipher text $c$ is independent of the message been encrypted, thus independent of the distribution over the message space M.


Quality of randomness on a Linux system with haveged Has anyone checked if using haveged, a Linux daemon which uses the HAVEGE algorithm, changes the non-deterministic properties of the random data from /dev/random in any negative ways?

TL;DR: do not use HAVEGE, it was flawed. It's evolution HAVEGED (notice the additional D) has improvements, but this answer is about HAVEGE, because the original question was.

I do not buy some of HAVEGE, specifically the claim made here "tens of thousands of unpredictable bits can be gathered per operating system call in average", and the methodology used to support that claim, as found here.

Entropy gathering is described by this pseudocode:

where HARDTICK() is a function that reads a hardware clock counter. An experimental evaluation of the entropy gathered was made as follows:

  We determined the threshold for NMININT above which the content of
  Entrop array can be CONSISTENTLY considered as random, i.e. it cannot
  be distinguished by our battery of tests from truly random numbers
  (i.e DieHard + ent + FIPS 140 +NIST suite).

(Emphasis using bold is mine)

The data gathered in Entrop is built using a Pseudo-Random Number Generator, complete with repeated rotation by 5 bit of each 32-bit word of Entrop, combination by XOR with one bit of the least recently modified word of Entrop, and combination by XOR with the actual source of entropy, HARDTICK() (or rather, the delta between successive HARDTICK() which is to closest to the actual source of entropy). See HAVEGE's paper for more details.

The entropy at the output of that PRNG has been evaluated using an experimental test (not designed specifically against this PRNG). That's a cardinal mistake: any half-decent PRNG will pass this test, even if fed very little actual entropy in its input, which makes its output highly predictable.

While this does not constitute a practical break of HAVEGE, it shows that the justification of its entropy-gathering part is flawed. My recommendation is thus not to use HAVEGE.

The above is advice about HAVEGE, as in the original question, based on references from 2003. In it's successor HAVEGED (notice the additional D) of the 201x, there was some effort made towards a sound methodology, in particular checking the entropy at input of the PRNG, leading to the conclusion: "Most samples failed all tests!". It is acknowledged that theoretical analysis of the source of entropy to build a model suitable to support a demonstration of security "were not sufficient to constitute such a model". This at least is quite believable.

The haveged program provides a viable additional source of entropy, preferably not as the only source. However, haveged is a product that produces results we surely need in computers starved of random bits including mobile markets.

The CPU/GPU configured so can obviously create logical and not so perfectly entropic results. We have to ask ourselves: do we need random filled with a viable source available to all? The answer is obvious yes.

Haveged produces a data far superior to just the user input. Furthermore the tasks running on the computer and or within the system improve the output.

As the necessity to use haveged increases, then most likely the user will be running more tasks that need to use it and hence there will be better results and more of them.

A true TRNG is a state of peace in the true security advocates heart but there is always room for an improved haveged; both on Windows, on Mac and other operating systems.

http://esa-space.blogspot.com/2017/04/rng-and-random-web.html

http://esa-space.blogspot.com/


Calculate all possible keys for AES 128 encryption to exploit hardware encryption Some background: I am using the MicroChip ATAES132a for hardware encryption/decryption. The ATAES132a is very configurable and can be misconfigured in such a way that the encryption/decryption will be performed using the same nonce. In theory, if the nonce is known I can do an encryption of the plain text and get the same ciphered text result. Based on this, I could possibly try to encrypt the same plain text with the known nonce and compare to the generated ciphered text until I get a match.

For example, in theory my target key could be some thing like this (see below). I would need to calculate every possible key, use the known nonce and the same plain text until I get the same ciphered text result.

const uint8_t g_key0[] = { 0x01, 0x08, 0x0E, 0x91, 0xe2, 0x64, 0x8f, 0x49, 0x0c, 0xe9, 0x80, 0x45, 0x38, 0xb5, 0x85, 0x3f };

This would exploit how the device was configured incorrectly. The ATAES132a does all its encryption with AES in CCM mode. I can perform the attack either on the ATAES132a or on any PC using any standard AES library.

Is this attack plausible using a modern PC?

Is this attack plausible using a modern PC?

No. For AES-128 (or any secure 128-bit symmetric cipher for that matter), there are $2^{128}$ possible keys. You would have to try on average half of those keys before finding the right one, which is $2^{128}/2=2^{127}$. At $100,000,000$ attempts per second (or around $2^{26}$), it would take around $2^{101}$ second. The universe is around 13.7 billion years old (about $2^{59}$ seconds). So the amount of time it would take you is $2^{42}$ times the age of the universe.

There are other ways you can calculate this, but the end result is the same. See How much would it cost in U.S. dollars to brute force a 256 bit key in a year?.

Finally, the relevant XKCD:

in a universe of combinations you can give luck and find the correct one in 1 minute. It is not mandatory to scroll through the range to find the correct key. But you can't get luck too :-)


Proving a secret is known without revealing it Let's say Alice wants to prove to Bob that she knows a secret S that Bob is also supposed to know. Alice can't be sure Bob is really who he pretends to be, so she needs to make sure Bob can't deduce S from their interaction. Additionally, S could be weak (e.g. "abc123"), so she can't simply send a hash of S to Bob, or any f(S) really since that could be brute-forced.

What are your thoughts on this? Is this even possible?

What you want is the https://en.wikipedia.org/wiki/Socialist_millionaires
Problem.
This problem is orignally phrased as two people want to verify if they have the same amount of money without revealing anything more.
Alice has a value $A$ and Bob has value $B$ and they want to verify $A =? B$
without either side revealing anything more than the result of the check.
See the wiki page for algorithm description.

You have the answer. It's hashing. Even if S is weak, it's not possible to determine S from the hash value if the algorithm used is secure enough.
Alice can send a SHA-256 hash of S to Bob. If Bob knows S, he can confirm it and Alice has convinced him. Else, we know it's just someone pretending to be Bob.


Are really, really long passwords any more secure than short ones? Just for fun, I want to encrypt a message that will take about 10 or so years to decrypt. My idea is to encrypt a message with AES-512 with a password one million decimal digits long.

Knowing not much about cryptography, is this any more difficult to decrypt than a shorter password? (I'm trying to prevent brute-forcing, until computing power becomes so high that it is irrelevant).

There is no AES-512; AES takes keys of 128, 192 or 256 bits.

When encrypting with a password, there are two steps: first the password is converted into a key for the symmetric encryption, then the encryption is applied. Brute force can be applied either on the password (enumerating all possible passwords until a match is found) or on the key itself (enumerating all possible keys until a match is found).

A 128-bit key is large enough to defeat brute force for long period of times. You can use a larger key for display purposes (larger figures impress managers, and some people apparently believe that key length correlates with manhood -- in the same way as big cars).

The same applies to a password with 128 bits of entropy -- which is a way of saying that there are 2128 possible passwords, and you chose one at random among them. You can lower the entropy requirements on the password by using a slow hashing process; roughly speaking, if the function which converts the password into a key has the cost of 220 elementary encryption operations (that's about one million, and will be done in a fraction of a second with a basic PC) then you can be content with 108 bits of password entropy.

If your passwords are random sequences of alphanumeric characters (uppercase letters, lowercase letters, digits), then 19 characters are enough (because you use 62 distinct signs, and 6219 is greater than 2108). More characters are useless. Note that "random" is an important word: I am certainly not talking about choosing the password with your head ! Human brains are definitely bad at randomness. Use a coin, dice, or a computer with /dev/urandom.

All of the above is about making sure that the message will not be decrypted within the next 10 years. A much harder problem is to also ensure that the message will be more or less easily decrypted in year 2022, but not before. I suggest entrusting the key to a notary, with instructions to reveal it at a specific future date.

According to Gibson Research's Password Haystacks website 23 digits would take 35 years at 100 trillion guesses per second.


What is the intuition for ECDSA? I understand DH and ElGamal and RSA encryption/signatures.  But when I look at ECDSA (or plain DSA), it seems like the formulas are just pulled out of thin air.  I can verify that the algebra used in the verification formula does in fact work out, but I have no clue why forgeries are hard, why these formulas were used, why something simpler wouldn't work, and where the inventor(s) got all this stuff.  Can someone explain the intuition behind ECDSA?

It is possible to view DSA/ECDSA as an identification scheme (like Schnorr) but with a different variant of Fiat-Shamir. This gives the intuition that you are perhaps looking for. I will include an excerpt from Intro to Modern Cryptography 2nd edition (Section 12.5.2) which gives this explanation:

Begin Excerpt -- Section 12.5.2 DSA and ECDSA

The Digital Signature Algorithm (DSA)
and Elliptic Curve Digital Signature Algorithm
(ECDSA) are based on the discrete-logarithm problem in different
classes of groups.
They have been around in some form since 1991, and
are both included in the current Digital Signature Standard (DSS)
issued by NIST.

Both schemes follow a common template and can be viewed as being constructed
from an underlying identification scheme
(see the previous section).
Let $ \mathbb{G}$ be a cyclic group of prime order $q$ with generator $g$.
Consider
the following identification scheme in which the prover's
private key is $x$ and public key is $( \mathbb{G}, q, g, y)$ with $y=g^x$:

The prover chooses uniform $k \in \mathbb{Z}_{q}^*$ and sends
$I:=g^k$.
The verifier chooses and sends uniform $\alpha, r \in \mathbb{Z}_{q}$ as the
challenge.
The prover sends $s:=[k^{-1} \cdot (\alpha+xr) \bmod q]$ as the
response.
The verifier accepts if $s\neq 0$ and $g^{\alpha s^{-1}} \!\cdot
    y^{r s^{-1}}=I$.

Note $s \neq 0$ unless $\alpha=-xr \bmod q$, which occurs with negligible
probability. Assuming $s \neq 0$, the inverse $s^{-1} \bmod q$ exists and
$$
g^{\alpha s^{-1}} \! \cdot y^{r s^{-1}}
 = g^{\alpha s^{-1}} \! \cdot g^{xrs^{-1}}
  = g^{(\alpha+xr) \cdot s^{-1}}
   = g^{(\alpha+xr) \cdot k \cdot (\alpha+xr)^{-1}} = I.
$$
We thus see that correctness holds with all but negligible probability.

One can show that this identification scheme is secure if the discrete-logarithm
problem is hard in the group. We merely sketch the argument, assuming
familiarity with the results of the previous section (i.e., Schnorr and identification schemes).
First of all, transcripts of honest executions can be simulated:
to do so, simply choose uniform $\alpha, r \in \mathbb{Z}_{q}$
and $s \in \mathbb{Z}_{q}^*$, and then set $I:=g^{\alpha s^{-1}} \!\cdot y^{r s^{-1}}$.
(This no longer gives a perfect simulation, but it is close enough.)
Moreover, if an attacker outputs an initial message $I$ for which it can give
correct responses $s_1, s_2 \in \mathbb{Z}_{q}^*$ to distinct challenges $(\alpha, r_1),
(\alpha, r_2)$ then
$$
g^{\alpha s_1^{-1}} \!\cdot y^{r_1 s_1^{-1}} = I = g^{\alpha s_2^{-1}} \!\cdot y^{r_2 s_2^{-1}},
$$
and so $g^{\alpha (s_1^{-1} - s_2^{-1})} = h^{r_1s_1^{-1} - r_2s_2^{-1}}$ and
$\log_g h$ can be computed as in the previous section. The same holds if the attacker
gives correct responses to
distinct challenges $(\alpha_1, r), (\alpha_2, r)$.

The DSA/ECDSA signature schemes are constructed by ``collapsing'' the above identification
scheme into a non-interactive algorithm run by the signer. In contrast
to the Fiat--Shamir transform, however, the transformation here is carried out
as follows:

Set $\alpha:=H(m)$, where $m$ is the message being signed and $H$ is
a cryptographic hash function.
Set $r:=F(I)$ for a (specified) function $F: \mathbb{G}\rightarrow
   \mathbb{Z}_{q}$. Here, $F$ is a ``simple'' function that is not
intended to  act like a random oracle.

The function $F$ depends on the group $ \mathbb{G}$, which in turn depends on the scheme.
In DSA,
$ \mathbb{G}$ is taken to be an order-$q$ subgroup of $\mathbb{Z}_{p}^*$, for $p$ prime, and
$F(I) =[I \bmod q]$.
In ECDSA, $ \mathbb{G}$ is an order-$q$ subgroup of
an elliptic-curve group $E({\mathbb Z}_p)$, for $p$ prime. (ECDSA also allows elliptic curves
over other fields.)
Any element of such a group can be represented as a pair
$(x, y) \in {\mathbb Z}_p \times {\mathbb Z}_p$. The function $F$
in this case is defined as $F((x,y)) = [x \bmod q]$.

DSA and ECDSA - abstractly:
Let $\cal G$ be a group -generator algorithm.

$\sf gen$: on input $1^n$, run ${\cal G}(1^n)$ to obtain $( \mathbb{G},
   q, g)$. Choose uniform $x \in \mathbb{Z}_{q}$ and set $y:=g^x$. The
public key is $(\mathbb{G}, q, g, y)$ and the private key is
$x$.

As part of key generation, two functions $H: \{0,1\}^* \rightarrow
   \mathbb{Z}_{q}$ and $F:  \mathbb{G}\rightarrow \mathbb{Z}_{q}$ are
specified, but we leave this implicit.
$\sf sign$: on input the private key $x$ and a message $m \in
   \{0,1\}^*$, choose uniform $k \in \mathbb{Z}_{q}^*$ and set
$r:=F(g^k)$. Then compute $s:= [k^{-1} \cdot (H(m) + xr) \bmod q]$.
(If $r=0$ or $s=0$ then start again with a fresh choice of $k$.)
Output the signature \mbox{$(r, s)$}.
$\sf vrfy$: on input a public key $(\mathbb{G}, q, g, y)$, a message
$m \in \{0,1\}^*$, and a signature $(r,s)$ with $r, s \neq 0 \bmod
   q$,  output 1 if  and only if  $$ r = F\left(g^{H(m) \cdot s^{-1}}
   y^{r \cdot s^{-1}}\right). $$

Assuming hardness of the discrete-logarithm problem,
DSA and ECDSA can be proven secure if $H$ and $F$ are modeled as random oracles.
As we have discussed above, however,
while the random-oracle model may be reasonable for $H$,
it is not an appropriate model for $F$. No proofs of security are known for the specific
choices of $F$ in the standard. Nevertheless, DSA and ECDSA
have been used and studied for decades without any attacks being found.

Proper generation of $k$.
The DSA/ECDSA schemes specify that the signer should choose a uniform $k \in \mathbb{Z}_{q}^*$
when computing a signature. Failure to choose $k$ properly (e.g., due
to poor random-number generation) can lead to catastrophic results.
For starters, if an attacker can predict the value of $k$ used to compute a
signature $(r, s)$ on a message $m$, then they can compute the signer's private key.
This is true because
$s = k^{-1} \cdot (H(m)+xr) \bmod q$, and if $k$ is known then the only unknown is the
private key $x$.

Even if $k$ is unpredictable, the attacker can compute the signer's private key
if the same $k$ is ever used to generate two different signatures. The
attacker can easily tell when this happens because then $r$ repeats as well.
Say $(r, s_1)$ and $(r, s_2)$ are signatures
on messages $m_1$ and $m_2$,
respectively. Then
\begin{eqnarray*}
s_1 & = & k^{-1} \cdot (H(m_1)+ x r) \bmod q \\
s_2 & = & k^{-1} \cdot (H(m_2) + x r) \bmod q.
\end{eqnarray*}
Subtracting gives $s_1-s_2 = k^{-1} \left(H(m_1)-H(m_2)\right) \bmod q$, from which $k$
can be computed; given $k$, the attacker can determine the private key $x$ as
in the previous paragraph.
This very attack was used by hackers to extract the master private key
from the Sony PlayStation (PS3) in 2010.

EC-Schnorr or ECDSA, there is no important difference. The addition of $k$ (Schnorr) or the muliplication with $k^{-1}$ an can be seen as encryption of message and private key. That's why it's secure.