Is there a problem with this specific RSA protocol? So a protocol uses two random primes $P$ and $Q$ with the equivalent bit length of around 2048 bits, multiplies to form $N$. The encryption function in detail is:
$m^e \bmod\ N$
$(\text{512-bit-random-key})^{65537}\bmod\ \text{4096-bit-modulus}$
Now there are a few attacks that can be performed if the message length is too short. For that reason, the message length is a fixed 512 bit. Are there any other theoretical/practical weaknesses from the information shown?

The proposed system is close to the safe RSA-KEM, with some exceptions:

The condition $\gcd(P-1,e)=1$ and $\gcd(Q-1,e)=1$ is missing. This must be checked when generating $P$ and $Q$. In the case of prime $e$ (as in the question) this simplifies to $P\bmod e\ne1$ and $Q\bmod e\ne1$.
The random key is 512‑bit, when in RSA-KEM it is typically drawn in $[0,P\,Q)$, thus about 4096‑bit. This is believed (without formal proof) to be without dire consequences since $512\,e\gg4096$. It would however be a total disaster with $e=3$, because taking the $e^\text{th}$ root of the ciphertext would reveal the secret; and I would not caution it blindly for $e=5$.
The random key reportedly is directly used as the encryption/decryption key for some symmetric cipher, without going thru some Key Derivation Function as customary. That's probably OK for most practical ciphers, but in theory we should worry about interactions with properties of the cipher. For example, with an hypothetical cipher where a key and the same shifted by some number of bits give related decryptions, an attacker could take advantage of that to force the legitimate receiver to decipher under a related key.
The generation and uses of $P$ and $Q$ must leave them (and secret derived quantities, such as $\varphi(P\,Q)$, $\lambda(P\,Q)$, any private exponent $d$…) secret, which is easier stated than done.

Assuming $e=2^{(2^4)}+1$ as apparent in the question: ignoring 1 would lead to problem in practice for about one key in $2^{15}$. We'd get away with 2. We'd likely get away with 3, but there's not enough context to affirm it. 4 is standard in RSA crypto.
As usual: for a real system, it's unwise to devise one's crypto.


Hill Cipher question Recently, I was given three ciphers to crack for my cryptography class. At this point, I have guessed that one of them is likely a Hill cipher (probably 3x3, as that is the most complex we have done so far).

I have made a fairly good guess of two options for the first seven characters in the cipher, but I found myself unable to figure out the key matrix. So far, I have $\bigl(\begin{smallmatrix}
a&b&c\\ d&e&f\\ g&h&i
\end{smallmatrix} \bigr)$ x $\bigl(\begin{smallmatrix}
14\\ 13\\ 0
\end{smallmatrix} \bigr)$ = $\bigl(\begin{smallmatrix}
10\\ 4\\ 12
\end{smallmatrix} \bigr)$, but since the matrix is modulo 26 there could technically be infinite values for variables a-i (for instance, $14a + 13b + 0c = 10$ could actually be 35, 60, etc.). Is there something that I'm missing?

You would need (at least) 3 pairs of vectors in order to determine the 3*3 matrix.


Is there any hash function that relies on integer exponentiation instead of XOR? I'm trying to implement a hash function in an esoteric language that has no 32-bit or 64-bit operations. Keccak, for example, is too slow in that language. I'd need a design that minimizes the number of 1-bit operations. Alternatively, I could also use a hash function that relies on integer exponentiation, which is not expensive on this language. Is there any hash function like that?

You can use the discrete log-based hash given by $H(x,y) = g^x h^y$, where $g$ and $h$ are two randomly chosen group elements. If your group has known prime order $p$, then this function is collision-resistant if and only if discrete logarithm is hard in your group. In particular, if you find a collision, $g^x h^y = g^{x'} h^{y'}$, then you get $g^{x-x'} = h^{y'-y}$. This means that $x - x' = \log_g h \cdot (y' - y) \mod p$. Since $p$ is prime and $y \neq y'$, we can invert $y'-y$ modulo $p$ to compute the logarithm.

This is assuming that you want a collision-resistant hash function. If you want something stronger, then this might not be suitable for you. E.g., this obviously has the property that $H(x+1,y) = g \cdot H(x,y)$, which could be really bad in some applications.


How does PBKDF1 work? I need some basic guideline on Password Based Key Derivation Function. PBKDF1 generates a key from password and salt using Hashing algorithm (like SHA1, SHA256, MD5).

What is the step behind this?

PBKDF1 as specified in PKCS#5 and RFC 2898 provides Key Derivation and Key Strengthening. The parameters of the function are a hash function (such as SHA-1), a password, a salt (sometimes called nonce, depending on context), an iteration count and the length of the derived key to be returned. The standard PBKDF1 will just calculate the hash of password concatenated with salt, and then hash the hash value that is returned by the previous step iteration count minus one times:

$$ K = H(H(...H(P||S)...))$$

If you only need key derivation but not key strengthening, use an iteration count of one. The purpose of the key strengthening is to increase the complexity of the key derivation, making certain attacks that exploit weak passwords more time consuming.

There are related key derivation functions that also provide Key Stretching, such as PBKDF2 and the .NET PasswordDeriveBytes function. Key Stretching is a feature that allows derived keys of any length to be returned, instead of being limited by the output length of the hash function.


Is there any such thing as "proof of location"? I'm looking for a way for someone to prove to me their geographical location without a trusted third-party. Imagine wanting to prove to someone you're actually physically in a specific place. I'd imagine you'd need something like perhaps a receiver of some kind to triangulate the location of a satellite that could perhaps only be calculated in that spot?

Is this possible?

A clear cut answer to your question is NO for now. In the literature there is no an accurate and reliable scheme that can determine geolocation of the data. They are basically timing-based schemes and the problem with timing (in this case) is that many factors can affect it. Also they usually assume that there are some reliable landmarks around the world that can help determining data location.

I think some internet infrastructures are needed to be improved to support such capability. See below for some paper in this area.

However, securing outsourced data might be a solution in hand rather than finding its location (I entourage you to think/read about why data location may matter).

1-GeoProof: Proofs of Geographic Location for Cloud
Computing Environment:http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6258199

2-Do You Know Where Your Cloud Files Are? :
http://dl.acm.org/citation.cfm?id=2046677

3-Geolocation of Data in the Cloud:
http://znjp.com/papers/gondree-codaspy13.pdf


Curve25519 Key Validation According to the original paper of Bernstein, there is no key validation needed when using Curve25519 for Diffie-Hellman Key Exchange. However, where does this property come from?
Is there any proof or argumentation available in order to understand this really practical property of Curve25519?
Does this mean that each $x$ coordinate could belong to a point $P=(x,y)$ from Curve25519? Is that even possible?

The responsibility of the user of Curve25519 for DHKE is Section 3;

The legitimate users are assumed to generate independent uniform random secret keys. A user can, for example, generate 32
uniform random bytes, clear bits 0, 1, 2 of the first byte, clear bit 7 of the last byte, and set bit 6 of the last byte.

This is a guarantee that the legitimate users are not in the small subgroup.  Remember the cofactor ($h = \#E(k)/n$) of the curve Curve25519 is $h=8$ which means that there are small subgroups of Curve25519. The order of the subgroups are  $2,4,8,n,2n,4n,8n$.
Now, the attacker may choose one of the small sub-group to use the Lim–Lee active small-subgroup attacks. This attack is very effective if the co-factor has many small factors. Then, the attackers can use CRT to combine the results.
The attacker will choose a $P$ which has a small order where the discrete logarithm is easy. During the protocol, the legitimate user will reveal $[a]P$ to the attacker. Now, how much information can the attacker learn about $a$ from $[a]P$?

The answer is given as information revealed by $[a]P$ is at most $\lceil log_2 h\rceil$ bits.

If the responsible users select their secret $a \equiv 0 \bmod h$ then $[a]P = \mathcal{O}$ for any small order, so they will expose nothing!
If you don't take responsibility then you need validation! During DHKE, for every public key you have to look at $[8]P \stackrel{?}{=} \mathcal{O}$. This has a cost of 3 doubling; $[8]P = [2]([2]([2]P))$. And, finally, to make sure that $P$ has order check $[n]P = \mathcal{O}$ with a cost of $\mathcal{O}(
log_2 n)$ by the double-and-add algorithm.
Which one is better? Of course, obeying the suggestion, no need for validation and no leak of information about the secret.

The validation can be hard for some curves, There is an article about this;

2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone
They defined a point is valid if

$P \neq \mathcal{O}$
The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
$P$ satisfies the curve equation ( the twist attack )
Check $[n]P = \mathcal{O}$ for prime curves ($h=1$) and check $[h]P \neq \mathcal{O}$ for non-prime curves ($h>1$).

Twist attack
An attacker, instead of sending a valid point $P$ as a public key, can choose to send a point on the quadratic twist of the curve where the group order is low. If the receiver doesn't check this (3. case) then it may be vulnerable to this. Curve25519 is also secure against this attack if the user takes responsibility during the key generation;

The twist of Curve25519 has an order $4p_2$ where prime $p_2 = 2^{253} − 55484635554744707071703875581767296995$. Therefore. Its small subgroups are $2,4$ and with the choice of the secret key, the user secure against these, too.

Why do we need uniform random secret keys?
There we some protocols [1] [2] that used fixed byte of the key, or low hamming weighted key for performance ( named restricted exponents 3.59 of HoAC). If the Hamming weight is $t$ of $k$ bit than there are $\binom{k}{t}$ such keys, the Shank's baby-step giant step can be modified to search in $\binom{k}{n/2}$-time. This is investigated by Heiman in 1993.

Does this mean that each $x$ coordinate could belong to a point $P=(x,y)$ from Curve25519? Is that even possible?

A point $P$ is in either on the Curve25519 or on its quadratic twist. A point $(x,y)$ is on the curve iff its satisfies the curve equation $$y^2 = x^3 + 486662 x^2 + x \text{ over } \mathbb{Z}/(2^{255} - 19)\mathbb{Z}$$


Break El Gamal for Elliptic Curves There  is  an  elliptic  curve  El  Gamal  digital  signature  scheme. Alice fixes an elliptic curve $E$, a prime $p$, a point $A$ on $E$, a secret integer $a$, and computes $B = aA$.  She makes $(E, p, A, B)$ public. To sign a message m (which is an integer), she computes a point $R = (x, y)$ on $E$ and an integer $s$, and sends $(m, R, s)$. The verification is $xB + sR = mA$.
Eve chooses $R1 = B − A = (x1, y1)$.
How do I find an integer $s1$ and message $m1$ so that $(m1, R1, s1)$ is a valid signature?
I referred to this to relate the normal El Gamal to the one on the Elliptic curve, but am not able to do so. Also, why is hashing required in such situations to prevent such forgery?

Well, one obvious method (which assumes that either there's a point on the elliptic curve with $x=0$, or the verifier doesn't check if $R$ is on the curve) is:
$$m1 = 0$$
$$R1 = (0, y)$$
$$s1 = 0$$
This satisfies the verification equation...


Reusing characters from plaintext in salt I'm curious about the security implications of reusing characters from the plaintext as salt.e.g.

$salted_plaintext = $plaintext[1] . $plaintext[7] . $plaintext;

My gut feeling is that it increases security through obscurity, though not as much as a proper salt, as existing rainbow tables wouldn't be applicable and would have to be re-made with this "salt" in place.

Since I'm sure someone will ask: the hash is for comparison of some sensitive data against a list of stored hashes.

My gut feeling is that it increases security through obscurity [...]

Security through obscurity is the name of an antipattern, for good reason.  Generally, the way we analyze security measures is by trying to give the attacker as much power as we can get away with.

So we just assume that the attacker knows your construction:

$salted_plaintext = $plaintext[1] . $plaintext[7] . $plaintext;

...and then we can observe that since the salt is a function of the password, two users who use the same password will get the same salt and thus the same hashed password, meaning that for each password guess the attacker is able to test every user's password entry.  Same as with unsalted password hashes.

  [...] existing rainbow tables wouldn't be applicable and would have to be re-made with this "salt" in place.

The proper answer to that is "meh."  GPU password cracking is so fast these days that an attacker might not even consider rainbow tables.  See Troy Hunt's article on GPU password cracking, where he demonstrates how he cracked 24,710 out of 40,000 salted SHA-1 hashed passwords in 45 minutes with a $500 GPU and a cracking dictionary he downloaded.

You really ought to read the Information Security Stack Exchange's site popular entry on how to securely hash passwords, particularly the top answer.


Paillier paper: Number Theoretic Lemma doesn't seem to work I'm reading the original Paillier paper.

I've reached Lemma 3: If the order of $g$ is a nonzero multiple of $n$, then $\varepsilon_g(x,y) = g^x y^n \mod n^2$ is a bijection, where $x \in \mathbb{Z}_n$ and $y \in \mathbb{Z}_n^*$.

Take for example $n=6$, $n^2=36, \mathbb{Z}_6^* = \{1, 5\}$.

Let $g=5$. The order of $5$ modulo $36$ is $6$ (see WolframAlpha), which is a multiple of $6$, so $\varepsilon_g$ should be a bijection.

Let $(x_1, y_1) = (1, 1)$ and $(x_2, y_2) = (1, 5)$. Then:

$y_1, y_2 \in \mathbb{Z}_6^*$ as required.
$\varepsilon(x_1, y_1) = 5^1 \cdot 1^6 = 5$
$\varepsilon(x_2, y_2) = 5^1 \cdot 5^6 = 5$ (assuming operations are modulo $36$.)

So... It's not a bijection. Am I missing something?

Short answer: This appears to be an error in the paper, but it's not a problem in practice.

The proof of Lemma 3 uses the following implication:

  Since $\gcd(\lambda,n)=1$, $x_2-x_1$ is necessarily a multiple of $n$. Consequently, $x_2-x_1=0\bmod n$ and $(y_2/y_1)^n=1\bmod n^2$, which leads to the unique solution $y_2/y_1=1$ over $\mathbb Z_n^\ast$.

As your example shows, the assertion $\gcd(\lambda,n)=1$ is wrong in general: $n=2\cdot 3$, hence $\lambda=(2-1)\cdot(3-1)=2$, and $\gcd(\lambda,n)=2\neq1$. Structurally, this becomes manifest in the fact that the ring $\mathbb Z/n^2$ contains nontrivial $n$th roots of unity — in your case the element $5$ — which voids the uniqueness claim.

It is not hard to prove that for $n=pq$ a product of two primes, this phenomenon occurs if and only if $p=2$ or $q=2kp+1$ for some $k\in\mathbb N$. (Modulo reordering of $p$ and $q$.)
The chance of this happening is negligible for any realistically-sized and randomly generated pair of primes $(p,q)$, hence this is not going to be an issue in practice.


How can I create pre-determined encrypted results? I want my encryption results to be the lyrics to Star Spangled Banner.
The original text I'm encrypting would be, for instance, the menu to a local pizza place.
I know what I want my passphrase to be.

How can I determine how to do this if I want to require a particular passphrase for its decryption? Obviously, I don't want something simple like ROT. I want to use cascade ciphers to accomplish this, something like AES, Serpent or Twofish.

What's asked is not possible if we add three constraints:

There exists a decryption method that given only the encryption results and the passphrase, outputs the original text.
The encryption/decryption method is not highly specific to a particular input (a particular menu to a local pizza place) or desired output (the lyrics to Star Spangled Banner).
In "I want my encryption results to be the lyrics to Star Spangled Banner", what's meant is that the full encryption results is exactly equal to prescribed data rendering as the lyrics to Star Spangled Banner.

Proof: suppose what's asked is possible with these three constraints. Using the same passphrase, encipher a variant of the menu to that local pizza place, in the same hypothetical method that gives the prescribed data rendering as the lyrics to Star Spangled Banner. The deciphering program of 1 has no way to decide which of the two menus it should output.

If we remove any of these constraints, what's asked is easy.

Argument for 1: Consider a decryption program that uses the help of an online server to retrieve the original text stored there, using the desired output as key.

Argument for 2: Consider a program that outputs the lyrics to Star Spangled Banner whenever the original text is a specific menu to a local pizza place, and otherwise performs as a normal encryption program; add a few easy technicalities.

Argument for 3: Consider an encryption program that accepts as additional input a text file with the desired output; and outputs a PDF or JPEG file that shows the text of that desired output, but contains in a comment field (not rendered by a PDF or JPEG viewer) the result of the encryption of the original text under the passphrase, per some standard encryption method. The decryption program will first extract the comment field, then use the standard decryption method. We can perfect the illusion by replacing the passphrase with the SHA-256 hash of the passphrase followed by the PDF or JPEG output file less its comment field.

There are countless ways to work around requirement 3; some even use a standard method modified in a detail. For example, with AES-CBC, it is easy to specially chose an IV such that a given 16-byte plaintext block enciphers to a given 16-byte ciphertext block under a given key, with no change to the decryption program. That's apparently how the idea illustrated in Angecryption started.

An entropy argument gives us a limit to how far we can go while meeting requirements 1 and 2: regardless of how clever we are in working around 3, the ciphertext is bound to be at least as big as we can losslessly compress the combination of the input and desired output, minus the entropy in the passphrase.


How to sign a large file for random-access reading? I need to write an "Authoring" application which produces large files. These files must be signed so that the "Consuming" application knows that it was authored with a matching key.
The consuming application must access the signed files read-only, with random access. This means it will not read the full file but still must check that the read bytes are signed.

I have thought cutting the data into 64k blocks and sign these blocks individually using a RSA private key with Crypto++.

Is there a RSA scheme which produces fixed size signatures?
The last block can be as small as 1 byte. Is there any cryptographical risk doing this?
Is this globally a good idea?

Is there a RSA scheme which produces fixed size signatures?

Normally RSA signatures are fixed size. Depending on encoding and the details included, the length may vary by at least a few bytes, though. There is usually a known maximum at least.

  The last block can be as small as 1 byte. Is there any cryptographical risk doing this?

No. As long as a good signature scheme (including a secure hash and proper padding in the case of RSA) is used the length of the data signed does not matter.

  Is this globally a good idea?

Firstly, signing each block individually does not allow verifying that their order is correct – an attacker could reorder the blocks and the corresponding signatures. You would need to add at least an index of the block to the signed data to verify that. (You likely also need to sign the file identity and length to prevent moving blocks between files or leaving data off the end.)

It also seems somewhat inefficient — RSA signatures are quite long and computing them is relatively time-consuming. But you know best whether the performance is sufficient or the space usage a problem in your use case.

Signing a hash list or hash tree of the data would allow storing a shorter signature and verifying blocks faster — you only need to verify a signature of the hashes once, then it suffices to check that each block hashes to the correct value. It would also take care of verifying the ordering. However, it would require reading and verifying a length-dependent list/tree of hashes before reading the actual data, which may be a problem.


My encryption message system & question about security I made this small tool for make & read easily an encrypted message without nothing to install, just a simple private key like a word or a couple of words to share. (Without say it directly of course but with a guess, like a place gone together with the correspondent, renembered).
I think the result message and the system is not bad to run safely for my (basics) needs, anyway an expert view could be great!
Please note i am just someone who like learning new things, really not an expert into coding or cryptography!

I used this tools:

Cryptoxi is the primary script
jcryption for aes256 browser encryption
Mcrypt for serpent256 server encryption
Tinymce
Base64 drag &drop
jq
jq-mobile
(..)

Here is the routing process:

Client connect, send an automatic unique hash generated by javascript, server respond a main and unique key based on the previous hash. This is used for
encrypt all
       future GET and POST requests with aes256 into browser by javascript.
Client input a private key, write his message with pictures if need, validate for convert into html and base64 for
pictures.
Client send this trough the AES tunnel to server.
Server decrypt aes, encrypt into serpent-256 & re-send it encrypted to client trough aes tunnel again,so final message is encrypted into serpent256 only. Then client send it by their own tools, like mail or sms.
Receiver do the same process on the other side by pasting or just click the generated url with the encrypted hash (Whith ?bin=... php variable on it) and of course by writing the private key.
When both user quit or refresh the page, keys and internals data are destroyed.

Here the site, sorry it's French, hope this is not a too big problem!
http://cryptop.at/m_.php. Also a YouTube video description (also in French).

So the question is, Do you see some kind of security hole?

Of course the main problem looks like if the primary hash is intercepted, but this allow only one connection, one time, so I think it's just impossible to catch & use this hash for reed the second user private key, or I am wrong?

Based on the details given in the question and the comments, it appears your protocol does nothing to protect the key exchange. The client sends a hash to the server, the server uses that hash to generate a key which it then sends back to the client. Client and server then use that key for future encryption.

Thus, anyone snooping on the key exchange will see the key and can then use it to decrypt and modify future messages. This is a major vulnerability.


Digital Signing algorithm for a fixed set of private and public keys in broadcasting like system? I have a broadcast kind of system. Where sender knows what to send and receivers will know what sender has sent. Now the sender will sign the message with his own private key and receivers will verify with the provided public key.

Now, all the receivers will have the same public key and the sender will have one protected private key that is being used for signing of the messages.

Keys are not going to be changed for a very long long time. So the senders and receivers will end up having same keys for eternity.

Which cryptographic approach would be suitable for this use case to make sure no one else can sign the message and send to the receivers?

There is a lot of confusion in the question:

message encryption is performed to achieve confidentiality, it is performed using the public key of the receiver's key pair (the public key needs to be trusted by the sender);
message signing is performed to achieve authentication and integrity of messages, it is performed with the private key of the sender's key pair (the public key needs to be trusted by the receiver);

Now you are missing the receiver's key pair in your question. This makes it impossible to encrypt messages for the receiver, as you cannot establish the identity of the entity that is trying to contact you. You could still use Diffie-Hellman key agreement to establish a secret key to prevent passive attacks, but the scheme would not be secure against active attacks.

Public keys are usually not protected against attack. For instance, an RSA public key exponent is usually set to 65537 so anybody that also processes the modulus can guess the public key using only a single guess. Public key operations are usually not protected against leaking the public key either. So any scheme that requires the public key to be secret is build on quicksand.

You need to provide the receiver with a shared secret key or a key pair with a trusted public key to create a secure scheme.

[UPDATE] After the update only message authentication and integrity seem to be requested. This can be performed using any secure digital signature format. RSA with a large key size and PKCS#1 v2.1 PSS padding would likely be the best choice.

Although key rotation is always preferable, a large enough key pair is likely to be secure enough unless quantum computers start to scale really well. Currently QC secure algorithms are not standardized all to well, so it's not like you have much of a choice in that regard. ECDSA could also be used.

It's probably best to use an existing container format for this. Usually CMS would be recommended as protocol.


AES file encryption with PBKDF2. Safe parameters? I'm developing an application that will use public key authentication to contact some webservice. So the user has his keypair on his computer, and I want that file to be encrypted using AES with a key derived from a user's password.

I'm wondering if I'm using relatively "safe" parameters and way of writing the file.

Here are the PBKDF2 and AES parameters:

PBKDF2 Iterations : 1024
PBKDF2 Hash function : SHA256
PBFDF2 Salt size : 256 bits
PBKDF2 Derived key size : 256 bits
AES Cipher mode : CFB

Here is how the file is written:

Salt (Hex encoded)
Return line
IV (Hex encoded)
Return line
Encrypted file content (Hex encoded, encrypted using AES in CFB mode and the key derived from the user's password)

Maybe what's missing here is a HMAC (with SHA256, for example) to "guarantee" that the file hasn't been tampered with. Here's how probably I'd append it to the file, after "Encrypted file content":

Return line
HMAC-SHA256 with the content's encryption key

Thanks in advance.

As this question is still on the list of "questions without answers", I'll quickly answer it (Basically repeating all of the above comments).

Increase iteration count to something larger (1 Million?)
You don't want to attach your HMAC of the plain-text after the contents. Rather authenticate either the ciphertext or (even better) use CCM/EAX/GCM mode.
Store the PBKDF's params in the header of the file.
Don't use PBKDF2 if possible. Rather use scrypt (best choice currently, for the next weeks), bcrypt (if no other option) or some of the PHC finalists.


Factoring Anderson's RSA backdoor In 1993, Anderson [1] proposed a backdoor to the RSA key generation algorithm. This backdoor requires that a backdoor key (prime) $A$ be implanted within the key generation portion of the RSA algorithm.
Instead of the usual way, primes $P$ and $Q$ are generated using the following algorithm:
First define a backdoor prime $A$ and two smaller random primes $P'$ and $Q'$.
Let $k=1$
$ \text{If} \ \ isprime(A\cdot k + P'):\\
\quad P = A\cdot k + P' \\
\text{else}: k = k+1$
The analog is performed for $Q$ using $Q'$.
This algorithm was also described here Is there any more information on this RSA backdoor?
This backdoor allows to calculate $N′= N \mod A$ and then factor $N′$ into $P′$ and $Q′$. Still $N'$ needs to be factored, but this is now a much easier problem as $N'$ is only about a fourth in size of $N$.
Please note that in my algorithm above I used $k=1$, the original implementation by Anderson suggests starting value $k=P'$ and iteratively increasing $k$ by one until $P$ is prime. In my algorithm I start with $k=1$.
My questions are:

does starting the iteration from $k=1$ instead of $k=P'$ make a difference?
in the way $N'$ is generated, what is the best way to factor $N'$ given the information how it is generated? Is there a certain factoring algorithm that makes factoring $N'$ very easy?

[1] Ross Anderson. Practical RSA Trapdoor. Electronic Letters. 29(11): 995,
1993.

does starting the iteration from $k=1$ instead of $k=P'$ make a difference?

If you start iteration from $k=P'$ then you get;
$$P = A\cdot (P'+i) + P'$$
where $ i = 0,1,2,\ldots$. Take modulo $A$
$$P  = A\cdot (P'+i) + P' \pmod A$$
$$P  =  P' \pmod A$$
Therefore it will still work to reveal the $P'$

in the way $N'$ is generated, what is the best way to factor $N'$ given the information how it is generated? Is there a certain factoring algorithm that makes factoring $N'$ very easy?

The current factoring record in the open literature is 829-bit, however, the recommended key size is at least 2048, i.e each factor has 1024-bits. Therefore the size of $A$ must be around $1024$-bit. Once you set $A$, then you can seek $P = A\,k_1 + P'$ where $P$ is prime.
There is nothing that prevents one to generate small primes for $P'$  and $Q'$. The $P'$ and $Q'$ doesn't add much to $P = A\,k_1 + P'$ since they are added. The $A$ and $k_1$ is important.
Therefore you can choose $P'$ and $Q'$ as below as $829$-bits.
You can use the CADO-NFS to factor the $P'\cdot Q'$. Here some notes about it, too.


Do Partially Homomorphic Encryption schemes also suffer from noise overflow? Do PHE schemes in general also suffer from noise overflow problem?

If by PHE you mean systems such as Paillier, then the answer is no. They don't have noise as in FHE and SWHE.


How practical are side-channel attacks and how much of a concern are they? I see a lot of research in very sophisticated side-channel attacks on crypto systems. Most (but definitely not all) seem to follow a trend, namely, the crypto system does something very dumb like decrypt any block given to it with no IV or nonce (so usually ECB mode).

That said, there have been practical attacks against smart cards and timing attacks against RSA.

So, when building a system which uses cryptography (be it public or symmetric key), how practical of a concern are such attacks? And, what guidelines can be followed to determine if your systems needs protections (be they power analysis protections, emissions, timing, etc)?

Yes, side-channel attacks are practical and a real concern, if the past is indicative of the future.
I've been professionally involved with Smart Cards since the mid eighties, and have repeatedly witnessed deployed systems vulnerable to many forms of side-channel attacks; examples (I personally did 1 and 3):

RAM buffer not cleared at reset, readable (with standard command Get Response), leaking state of previous PIN comparison, even if incrementing the PIN presentation counter had been inhibited (by hardware reset or/and removing EPROM programming voltage); that allowed recovering the 4-digit pins with expected 5000 attempts.
Timing dependency where the duration of PIN presentation with permanent-memory writes inhibited leaks if the PIN is correct or not, to the same effect.
Timing dependency where the duration of a comparison between values leaks the index of the first incorrect byte, allowing finding an $n$-byte value with expected $n\cdot2^7$ attempts instead of $2^{8\cdot n-1}$.
Return to manufacturer test mode (by a software exploit, hardware modification or upset), allowing extraction of permanent memory content, including secrets (variant: normal software can be coerced to read the wrong location).
Micro-probing to spy on bus lanes, leaking all kind of secret information.
Simple Power Analysis directly leaking bits of exponent in RSA.
Simple Power Analysis leaking activity (e.g. start programming of permanent memory), which combined with timing measurement leaks sensitive information (e.g. good or bad PIN, before that is recorded).
Differential Power Analysis, allowing key recovery.
Fault Injections (often considered side-channel attacks).

I have seen this causing great embarrassment to the suppliers of the vulnerable Smart Cards, and believe multiple reports that in the (distant) past, such vulnerabilities occasionally have been exploited on a large scale, especially in the field of Pay-TV with Smart Card.
More generally, when a device using cryptography is broken, this is often by means better described as a side channel attack than a cryptographic attack.
Addition: check this introductory article's part1 (alt.), part2 (alt.), part3; and this 2012 paper showing remote SPA and DPA attacks on Smart Phones and PDA.

If a cryptographic device/system can get in the hands of the adversary or otherwise become accessible enough (timing/Tempest/DEMA/SPA/DPA attacks can be remote to some degree), and it contains any information which confidentiality or even integrity matters (such as secret/private keys, authenticators, counters..), then one needs to pay close attention to side-channel attacks.


Benefits of signing RSA-encrypted data? I recently came across this (PDF) journal article, which describes what it calls "A New Design Of A Hybrid Encryption Algorithm" (which I must say, doesn't sound very novel, even in 2014!):

An AES key K is chosen
Encrypt message M using AES and key K

eM = AES-encryption(M)
AES key K is encrypted using RSA with the public key of the receiver

eK = RSA-encryption (K)
The cipher text eM is fed to SHA1, which generates a 160-bit message digest

mD = SHA1 (eM)
The message digest is signed using RSA with the private key of the sender

DS = RSA-sign (mD)
The encrypted message eM, digital signature DS and AES encrypted key eK are transmitted to the user over a network

So, basically standard AES-RSA hybrid encryption, but with the additional of an RSA signature (a signed message digest) that is intended to provide message authentication.

My question is whether signing the ciphertext actually provides any extra security (i.e. integrity or authentication) - doesn't encrypting the AES key with the receiver's RSA public key effectively provide message authentication?

Yes, signing the ciphertext does provide extra security, and yes, that would be integrity and authenticity of the message.

Encrypting with a public key does not provide integrity / authenticity against active attacks. That's kind of obvious: an adversary can simply encrypt another message with the public key - it is public after all.

The scheme however uses asymmetric encrypt-then-sign. This is dangerous as an adversary could strip off the signature to replace it with its own. That way it looks like the adversary has signed / send the message. However, this is only possible if the public key of the adversary is trusted within the system. More details are (indeed) here.

It will also be impossible to verify the message afterwards (unless you keep the ciphertext message as well, and make sure that the plaintext message and ciphertext message are irreversibly linked).

So when used correctly this kind of scheme provides integrity / authenticity. But it also has known limitations; that is: known to the cryptographic community, not the authors.

These kind of papers are used by the writers to get their degrees or progress within their studies. They provide zero insight and contain clear issues:

no mode of operation is defined for the symmetric cipher, no IV handling is performed;
the padding modes of RSA are not specified, not for encryption nor for signature generation ... there is only a limited description of the textbook RSA operation;
the hashing is not thought of to be part of the signature generation function;
the use of SHA-1 and the references to MD5 and blowfish, years and years after SHA-2 has been standardized.

And quite obviously there is no security analysis at all, which makes the entire paper a waste of bits and - worse - time.

The given "protocol" (and the quotes are needed here) could easily be extended with a message nonce and sender/recipient, making it more secure.


How can a collision be generated in this hash function by inverting the encryption? This is from Joan Daeman's Doctoral thesis
Per page 64 (or PDF page 79)

4.7.1 Our approach
Our goal is the design of simple and portable unkeyed and keyed
cryptographic hash functions that are hermetic.The basic principle of
our approach is derived from the compression function of an early
version of MD4.  The operation of this compression function can be
described as encrypting in an invertible way the 128-bit chaining
state $d^{i−1}$ to $d^i$ with $m^i$ as a key,or
(4.4): $d^i = f_{MD4}(d^{i−1}, m^i)$
In a later version this compression function was modified by adding
$d^{i−1}$ to the "encryption result" :

(4.5): $d^i = d^{i−1} + f_{MD4}(d^{i−1}, m^i) \bmod 2^{128}$
It can be seen that for the compression function (4.4) collisions can
be generated by simply inverting the encryption

2 Questions

What does hermetic mean in this context?

How exactly can you generate a collision by inverting the encryption?

4.4

Merkle–Damgård construction requires a one-way compression function and the common way is to use a block cipher. If you initiate with the simple way;
$$d^i = f_{MD4}(d^{i−1}, m^i)$$ then the message is the key.
Now, consider that we want to find a collision. Take an arbitrary $h$ as the output of the hash function, take two arbitrary but different message blocks $m^2_1$ and $m^2_2$, and decrypts the $h$ for each;
$$ m_1^1 = f_{MD4}^{-1}(h, m_1^2)$$
$$ m_2^1 = f_{MD4}^{-1}(h, m_2^2)$$
Since we used a block-cipher and that is a permutation and each key is select a different permutation from all possible permutations we expect that $m_1^1 \neq m_2^1$ with high probability. Then we find two inputs that have the same hash value. Note that we can find meaningful messages with this approach. If the $m_1^1 = m_2^1$ the choose another $h$ value to begin.

4.5

$$d^i = d^{i−1} + f_{MD4}(d^{i−1}, m^i) \bmod 2^{128}$$
This is the Davies-Mayer construction and its security is proven under the ideal cipher model. SHA-1 and SHA-2 are using this construction.
This construction has a problem with the block cipher, too that one can find a fixed point; that is $h = E(h,m)$ by setting $h=0$. There is no practical attack on this, though.
Block ciphers can have related keys that don't make a problem during the encryption since we are expected to select uniformly random keys. In the hash function, though, this makes a problem and therefore we use a special block cipher for those like SHACAL-1 for SHA-1 and SHACAL-2 for SHA-2 series.

Ideal-cipher model: Consider the set $\mathcal{B}$ as all possible $k$-bit key and $n$-bit block-sized block-ciphers. Then, in the Ideal-cipher model, a block-cipher $E \stackrel{R}{\leftarrow}\mathcal{B}$ is being chosen uniformly from $\mathcal{B}$. For each key, there are $2^n!$ permutations. Each key defines a permutation therefore there are ${2^n!}^{2^k}$ possible block ciphers. When we instantiate our black box, it becomes some particular block-cipher. Consider the AES-128 is one choose from $2^{2^263}$ that one can choose. Note that in 2005 Black showed that "a blockcipher-based hash function that is provably-secure in the ideal-cipher model but trivially insecure when instantiated by any blockcipher".


Fairness and guaranteed output delivery Why for achieving the fairness and guaranteed output delivery, less than a half of the parties should be corrupted? ($t < m/2$, where $t$ is the number of corrupted parties and $m$ is the total number of the involved parties)

Would you please prove it intuitively?

Intuitively anything the honest minority can do the dishonest majority can do as well. So if the minority can force a correct outcome the majority can force an incorrect outcome.

Side note:The question is ill-defined, not mentioning a specific problem where these requirements are to be held, is this a computation? who has the input? In some situations we can deal with a dishonest majority such as limiting them to no more than failing the process.


Can RSA-PSS signing be made deterministic without loss of security? Is it possible to make RSA-PSS signing deterministic without loss of security?

Specifically, I would use Blake2b of the key and message to generate the salt.

Any probabilistic signature scheme can be made deterministic without any loss of security. The generic transformation is as follows:

Let $(pk,sk)$ be the key-pair of the original signature scheme
Choose a random key $k$ for a pseudorandom function $F$ (you can use HMAC or CMAC), where the output of $F$ is enough randomness used to sign. This key is part of the secret key.
In order to sign on a message $m$: First compute $r=F_k(m)$. Then, sign on message $m$ using randomness $r$.

It is not difficult to prove that the scheme is secure, as long as the probabilistic scheme is secure and $F$ is a PRF. (The bounds of the probabilistic scheme stay the same as well; the only difference is that you add the probability of breaking the PRF, which is insignificant.) In practice, this can be very efficient, by using HMAC or CMAC and then stretching the output to the required length using the result as a key to AES-CTR, or using HKDF or something of the sort.

In fact, it is very unfortunate that this is not the standard way of deploying dSA and ECDSA, since that would resolve the major weakness which is that if the same randomness is used for different messages, then the secret key is revealed.


How can homomorphic encryption be probabilistic while allowing for math to be conducted? I've been playing with some homomorphic encryption libraries. It's given me a greater appreciation for probabilistic encryption. These two answers were instrumental in leading to this question, but don't contain an answer for this question by themselves:

If a probabilistic encryption algorithm is used, how does decryption return the correct message?
Partially Homomorphic Cryptographic Schemes - Deterministic vs Probabilistic
Homomorphic & Functional encryption: Mapping unencrypted outputs to encrypted outputs using existing data

For those who don't know, in probabilistic encryption:

A piece of data is anonymized by appending a time-dependent random string to its beginning
This means the same data (or "plaintext") can have a different value each time it's encrypted
When a user with the key decrypts the data, they  then remove this leading string to get back the original plaintext
A single "bit" of data can be a very long string in the HE space. This means HE encrypted strings contain more 'information' than regular bits. What this information contains is a mystery to me.

As you can tell I (think I) understand probabilistic encryption. But I don't understand how you can possibly retain homomorphism within a probabilistic space.

If each piece of data has a different leading random string, how does the algorithm know which parts of the encrypted data contains the true value? How can you add and subtract two encrypted datas that have different leading strings?

Obviously, the person performing math on the encrypted data can't know the key used to decrypt it. So HE somehow uses different leading random strings to encrypt each data,  but these datas can still be added and subtracted together? How can this possibly be true?

Probabilistic encryption is a necessity for ANY public-key encryption scheme. The reason is that in such schemes anybody can perform the encryption, thus if the encryption was deterministic, that would allow to check a guess of the plaintext. That would be a total disaster in a lot of applications: enciphering a coin toss, a name on the class roll, a price, a bulletin vote, a credit card number or SSN, a password..

There's a tantalizingly simple but somewhat oversimplified explanation to:

  If a probabilistic encryption algorithm is used, how does decryption return the correct message?

That explanation says that encryption takes the message, combines it with randomness, then enciphers; and decryption deciphers, then remove randomness to get the original message. That's exactly how it is done in RSA encryption with random padding, where combines sometime is as simple as appending randomness and fixed bits to the message (see e.g. RSAES-PKCS1-V1_5).

However, that simple explanation falls short of the goals of homomorphic encryption, because (as noted in the question) it does not yield a method to perform arithmetic on the encrypted message without holding the decryption key. That's why RSA encryption with random padding is not homomorphic, when RSA without padding is (multiplicatively, modulo the public modulus).

Secure homomorphic encryptions schemes do combine the message and the randomness as in the oversimplified explanation, but that combination is not by concatenation. For homomorphic randomized encryption to work, the combination of randomness and message must be by a method precisely matching the rest of the scheme.

The Paillier cryptosystem is one of the simplest example of randomness combination giving both security and homomorphicity.

As for a normal public-key encryption system, encryption requires the public key of the entity that will ultimately decipher. But (as the name implies) that public key is not secret. In Pailler, it is $(n,g)$ with large $n$ difficult to factor (similar to RSA) and choice of $g$ with $g^n\bmod n^2=1$ (typically $g=n+1$). Pailler encrypts message $m$ with $0\le m<n$ into $$E(m)=g^m\,r^n\bmod n^2\quad=c$$ where $r$ is a fresh random with $0<r<n$ and $\gcd(r,n)=1$.

Efficient decryption is possible knowing the factorization of $n$, with $D(E(m))=m$ for all valid $m$ and $r$.

That way of combining message $m$, randomness $r$, and public key $(n,g)$ is such that we have a homomorphic property:
$$\begin{array}{llll}
E(m_0)E(m_1)\bmod n^2&=g^{m_0}\,{r_0}^n&g^{m_1}\,{r_1}^n&\bmod n^2\\
&=g^{m_0+m_1}&{(r_0\,r_1)}^n&\bmod n^2\\
&=g^{(m_0+m_1\bmod n)+w\,n}&((r_0\,r_1\bmod n)+x\,n)^n&\bmod n^2\\
&=g^{m_0+m_1\bmod n}\,{(g^n)}^w&{(r_0\,r_1\bmod n)}^n&\bmod n^2\\
&=g^{m_0+m_1\bmod n}&{(r_0\,r_1\bmod n)}^n&\bmod n^2
\end{array}$$
$w$ and $x$ are integers bound to exist, that disappear later in the calculation. On the left side, that's by choice of $g$. On the right side, that's because the polynomial in $x$ raised to the power $n$ has all non-constant terms multiple of $n^2$.

We see that $E(m_0)E(m_1)\bmod n^2$ is identical to what the encryption of $m=m_0+m_1\bmod n$ could have been for choice of randomness $r=r_0\,r_1\bmod n$ .
Notice that the requirements $0\le m<n$ , $0<r<n$ and $\gcd(r,n)=1$ are met.

For a working decryption, we must thus have
$$D(E(m_0)\,E(m_1)\bmod n^2)=m_0+m_1\bmod n$$
or, for regular addition: if $0\le m_0<n/2$ and $0\le m_1<n/2$ then
$$D(E(m_0)\,E(m_1)\bmod n^2)=m_0+m_1$$

To produce a cryptogram per that homomorphic property, one needs

at least one ciphertext $c_0=E(m_0)$ for an unknown message $m_0$, typically prepared by someone else (otherwise why use homomorphic encryption?)
either

A second similar $c_1=E(m_1)$, so as to be able to compute the ordinary product $c_0\, c_1=c$
A new $m_1$ to combine, and the public key, which allows to compute $c_1$ and be back to the previous option.

Typically at least, the public key (specifically, it's component $n$), to allows reduction of $c_1\,c_2$ modulo $n$, for two reasons

concealing if a particular $c_i$ was involved in preparation of the ciphertext (otherwise determinable by testing if $c_i$ divides $c$)
the reduced $c\bmod n^2$ is shorter than $c$ by a factor about 2.


Proving security of an encryption scheme I have an encryption scheme $Enc(pk, m)$ which outputs ciphertext of the form $c_1 = (pk)^r, c_2 = g^r \cdot m$; where $pk$ is the public key of the form $g^a$, $a$ being the corresponding secret key.

Is this secure?

If you are working in an order $p$ prime order group which is generated by $g$, and $a$ as well as $r$ are drawn uniformly random from $\mathbb{Z}_p$, you can prove this secure under the decisional Diffie-Hellman (DDH) assumption (what you sketch here, is often referred to as modified ElGamal in the literature).

Informally speaking, under DDH you can show that $c_1$ looks like a random value. Now, once you have shown that $c_1$ looks random, you can view $g^r$ like a one-time pad on the message.

See Section 3 of this paper for an excellent formal treatment.


How to calculate if probability is negligible or not If i have probability $Q = 2C(A\times B)$ where $A$ and $B$ are unknown probabilities and $C$ is a non-negligible probability, what can i speculate about probability $Q$ and how can i calculate bounds on probabilities $A$ and $B$ in order to make this value non-negligible?

First of all, keep in mind that all meaningful probabilities must be between $0$ and $1$.  In particular, this means that, if $X$ and $Y$ are probabilities, $0 \le XY \le \min(X, Y)$.

In cryptography, a probability is considered "negligible" if it is very small.  What actually counts as "negligible" depends on context, but typically, we're talking about probabilities on the order of $1/2^{128}$ or less.

Conversely, a "non-negligible" probability may be high, perhaps even close to $1$.  In fact, since we typically want probabilities (of an attack succeeding) to be small, we may safely assume that, in the worst case, all non-negligible probabilities are $\approx 1$.  This leads to the following "rules":

The product of two negligible probabilities is (always) negligible.
The product of a negligible and a non-negligible probability is also (always) negligible.
The product of two non-negligible probabilities is (usually) not negligible.

Corollary: For the product of several probabilities to be negligible, at least one of them must (usually) be negligible.

Multiplying a probability by a constant $\approx 1$ (say, between $1/2^{16}$ and $2^{16}$) does not (usually) change its negligibility.
The sum of two negligible probabilities is (usually) negligible.
The sum of a negligible and a non-negligible probability (or of two non-negligible probabilities) is never negligible (and might not always, strictly speaking, be a probability).

Thus, without knowing anything about $A$ and $B$, except that they are probabilities, the most we can say about $Q = 2C(AB)$ is that it is somewhere between $0$ and $2C$.  Furthermore if $C$ is not negligible, then $2C$ is definitely not negligible; thus, for $Q$ to be negligible, $AB$ must (generally) be negligible.

For $AB$ to be negligible, it's sufficient for either $A$ or $B$ to be negligible.  If neither $A$ nor $B$ is negligible, their product cannot be assumed to be negligible either — although it's possible for $AB$ to be negligible (e.g. $AB \approx 1/2^{128}$) even if both $A$ and $B$ are only "nearly negligible" (e.g. $A \approx B \approx 1/2^{64}$).

Conversely, for $Q = 2C(AB)$ not to be negligible, neither $A$ nor $B$ may be negligible.  (Strictly speaking, for any specific threshold of negligibility, the factor of $2 > 1$ could bump a probability just below the line to just above it; but the whole point of using terms like "negligible" is to note that we're speaking loosely and usually ignoring such factors of $\approx 1$.)  It's still possible for all of $A$, $B$ and $C$ to be above our negligibility threshold, but for their product to be below it (if two or more of them are "almost negligible"), but we cannot assume this without knowing their values more precisely.


Can AES in CCM or GCM counter mode interoperate with AES in "plain" counter mode (CTR)? I am exploring the use of Windows CNG to replace some OpenSSL-based code that takes advantage of AES in counter mode. From the outside, everything should look the same after the switch.

The section BCRYPT_CHAINING_MODE in this piece of CNG documentation gives me the impression that the only counter modes supported are BCRYPT_CHAIN_MODE_CCM, which sets the algorithm's chaining mode to counter with CBC-MAC mode (CCM) and BCRYPT_CHAIN_MODE_GCM, which sets the algorithm's chaining mode to Galois/counter mode (GCM)

I have no experience with CCM or GCM and would like to understand whether it is possible to use them in such a way that it can interoperate with CTR, by "disabling" the authentication part or in any other way. I did not find any indication that that is possible indeed, but on the other hand, I would be surprised if CNG does not support AES-CTR.

Maybe my question should have been "does Windows CNG support AES-CTR" to get a more direct answer :-)

Update: On another Microsoft webpage, in the section Cryptographic Algorithms, the table called "Table 12 – Advanced Encryption Standard (AES)" mentions "CTR( int only; 128 , 192 , 256 )", which I suppose means that it is internal functionality only.

I think this question is related: What is wrong with AES-CTR-HMAC-SHA256 - or why is it not in TLS?

A message encrypted with AES-GCM can be decrypted with an AES-CTR library IF the authentication tag is stripped from the message.
If you are encrypting with AES-GCM and then adding an HMAC tag, you need to strip the HMAC and the GTAG off the message in order to decrypt it, assuming the IV section of the message is in the correct location for each library to handle.
edit:
Thanks to Maarten Bodewes for pointing out that the initial counter value is used in GCM to create the Galois hash key, and thus would need to be incremented by 1 in order to read the message data properly.


Weak and Strong Collision Resistance, again Weak collision resistance (CR), or second-preimage resistance, is the property that given $x$ and $h(x)$ ($h$ a hash function) it's difficult to find $x' \neq x$ such that $h(x') = h(x)$.
Strong CR, or just collision resistance, is the property that it's difficult to find any two $x,x'$ with the same hash value.

The latter is easier than the former; the former is the "hash function analogue" of "same birthday as me" and the latter the analogue of "any two persons sharing a birthday".

Now then, what would a collision attack look like? I don't understand when it would be of relevance that it's relatively easy to find a pair $x,x'$ with the same hash value; isn't an adversary typically confronted with a given hash value that he has to "work with"? I.e., $x$ and $h(x)$ are given, if he can find a collision pair $(y,y')$, well, what does that help him?

Also, how does one actually find "any two" inputs with the same hash value? Seems to me that you must always first choose one input $x$, and then compare against that, at which point we're back to finding second preimages, right?

There are many situations where collision resistance is exactly the property that you need. For example, assume that I want to get a certificate from a CA with the URL www.google.com so that I can play a fishing attack against Google. Assume that I manage to find two certificates with the same hash; one has URL that is www.google.com and the other has something else (e.g., www.yehudalindell.com). Then, the CA will happily sign on the certificate for the latter URL, and due to the collision I will now have a valid certificate for google. Another example is code signing: if I can construct two pieces of code where one is malicious and the other is perfectly valid but both have the same hash, then I can get my valid code accepted to Apple Store or something like that, but then get people to download my malicious code.

It is really important to understand that birthday attacks on hash functions are just the generic way of finding collisions when nothing better is known. However, advanced cryptanalysis can do amazing things and find really valid collisions. For example, using advanced techniques and MD5 collisions, a rogue certificate signing certificate was obtained. The Flame virus also propagated by using an MD5 collision. So, this is not there, but reality!

Weak collision resistance, or more exactly, target resistance or 2nd-preimage resistance is important when a collision must be found with a given hash. But this is often not the case.


Why can't we construct a PRG from a one-way function and hc, but only one-way permutation From Katz & Lindell's book, theorem 7.19:

Let f be a one way permutation with hard-core predicate hc.
Then the algorithm $G(s)=f(s)||hc(s)$ is a PRG with expansion factor $\ell(n)=n+1$.

But what about if we use a one-way function? I know that there could be $f(x)=f(x^{'})$ when $x\neq x^{'}$, we lost some entropy here, but what breaks the theorem actually?

The proof of Theorem 7.19 explicitly uses that $f(r)$ for a uniformly random bitstring $r$ is distributed like $r$ when $f$ is a permutation*. I don't have the energy to reprint the proof here to show exactly how the distribution of $f(r)$ is used, but it should be clear that it can be useful to know this about $f(r)$ when arguing that $G$ is a PRG.

If you want a counterexample when $f$ is not a permutation you can see this answer.

*This is the part of the proof that says

  using the fact that  $f$ is a permutation for the second equality

for those who have access to the book.


Encryption that can only be decrypted once? I want to encrypt a message so that it can only be decrypted once. I know that we can use nonces to do this when we exchange data over a communication channel, but in my case the cipher text will be stored on a disc.

Is there any way to do so?

If I understand your query correctly then you mean that if the decryption is successful then the original message should be destroyed. That said you can do this in such a way that once the password entered is correct the Plain Text should be displayed and the cipher text should be altered beyond recovery. You can write a program to do that. There are some companies which employs such techniques e.g. you can install some features from a CD only once.

If this is a research question then read ahead.
The computing which we do on our computers is called classical computing. A classical computers is independent of the path it chooses to produce the result. However a quantum computer is dependent on how it produced result i.e. the paths available and the paths chosen affects result. So what could have happened but did not heavily affects the outcome. In a quantum system once we take any measurement the state of the system is disturbed. So if you have a ciphertext which is in a quantum system then if you make an observation the system gets disturbed and the original message is lost.
I hope the firs part answered the question but if it did not then I have an upsetting information for you, the quantum cryptography is a theoretical model which has not been fully practically realized(as far as I know).


Elliptic curve point addition with $Z_1 = Z_2 = 1$ Elliptic curve point addition and point doubling operations using Projective and Jacobian coordinates require fewer field multiplication operations when considering $Z$ coordinates of input points equal to one ($Z_1=Z_2=1$). Is there any drawback of this strategy?

This question was answered in the comments:

If you add two points with $Z_1=Z_2=1$, the resulting point will (in general) have $Z_3\neq1$. Given that we typically do a full addition chain, and not just add two points together, what is your stategy when it comes time to do the second addition? – poncho
In other words, the drawback is that it only works when $Z_1=Z_2=1$. :) And of course you must normalize the resulting $(X_3,Y_3,Z_3)$ if you want the $(x_3,y_3)$ coordinates that point. – Chris


Should I use SHA256 or Blake2 to checksum and sign scrypt headers? I use scrypt as a key derivation function (not to store passwords). To pass around the detached key header I use the standard encoding as implemented in Colin Percival's scrypt implementation (scryptenc.c#L224).

The original scrypt key header encoding

binary encodes an algorithm identifier ("scrypt\0"), logN, r, p and salt into a 48 bytes header
checksums these bytes using SHA-256 and appends the first 16 bytes of the checksum to the header
signs the concatenated work factors and checksum using HMAC SHA-256, appending the signature to the header

The resulting 96 bytes form the key header.

My requirements

I rarely need to derive keys, probably a dozen times per day.
Keys are derived from human-generated passwords
My application runs on both 32-bit systems (e.g. smartphones) and 64-bit desktops.
My project is in Go which supports both SHA-256 and Blake2
the Go implementations of Blake2s and Blake2b don't provide 128bit checksums

Would it make any difference for me to use Blake2 for checksums and signing instead of SHA-256? Is there any difference in security?

If I use Blake2-256, would I cut off 16 bytes for the checksum (this seems to be not recommended), use 32 bytes or just keep it as is using SHA-256?

Thanks!

Note that Blake2's security goals are a superset of those of SHA-256:

SHA-256 is conjectured to be collision resistant, preimage resistant and second preimage resistant.
Blake2 is conjectured to be random oracle indifferentiable, a stronger property that SHA-256 doesn't have, and which implies the three classic hash function properties.

So yes, this substitution should be safe if Blake2 is safe.  One thing to note is that for this step:

  signs the concatenated work factors and checksum using HMAC SHA-256, appending the signature to the header

...you wouldn't want to use HMAC, since Blake2 has a built in optional keyed mode with the same MAC/PRF goals as HMAC.  (HMAC-Blake2 is not unsafe—it's just not the canonical way of using Blake2 as a MAC.)

  If I use Blake2-256, would I cut off 16 bytes for the checksum (this seems to be not recommended), use 32 bytes or just keep it as is using SHA-256?

The answer you linked doesn't say that truncating a Blake2 is always unsafe.  The gist of it is that:

It's generally wiser and safer to stick to well-trodden paths than to improvise your own; if there's a well-understood, standard way of achieving X, then that should generally be your default choice.  (Note that this implies you should stick to SHA-256 for the application you describe!)
When hashing to a custom output size, it's sometimes safer to make the hash output depend on the desired output size, to close off attacks where somebody is able to trick a system into hashing the same input in different contexts but truncated to different lengths.  (More generally, whether truncating a hash function is safe or not depends on how it's used.)

In your situation, I would go back to the fact that you're taking an already designed protocol and replacing its use of SHA-256 with Blake2.  This means that if the protocol is secure, then your substitution should be secure as well, because if Blake2 is secure then it should have all the properties that the protocol expects from SHA-256.  So if the original protocol truncates the output of SHA-256, then it should be no worse to truncate the output of Blake2.


Encryption for continuous, real-time data over an unreliable connection I have a continuous stream of real-time data. It must be consumed immediately or discarded, so I'm using UDP for transmission without ACK or retransmission (the connection is unreliable).

The packets I'm sending are of the same length, and one packet is sent per transmission (each next packet invalidates the previous one).

Is it insecure to use AES for encryption, reinitializing the AES context with the same key for each packet?

The AES key is pre-shared over a known wired secure channel.

On AES per packet: Generally it depends, but if you write there so few details, then I would bet you would implement it insecurely (no offense). There are several reasons:

You need to use a specific mode of operation, but you don't mention any. The mode of operation can have substantial impact on security.
You don't mention initialization vectors / nonces. Wrong handling of them (e.g., using a constant IV) can have bad impact on security, but the exact impact depends on mode of operation.
You don't mention any authentication. Not having any authentication can result in messages modified by attacker – for example, some modes of operation reflect bitflips in ciphertext to plaintext. Also, some other modes of operation can leak some data if used without authentication (see POODLE).
You don't mention any replay attack prevention. Without that, attacker can replay or reorder the messages.

I suggest not to implement it yourself and rather use something existing. DLTS seems to be designed for such case.

There are also some additional concerns that probably need to be handled per application:

In some realtime systems, you might want to have a special handling for delayed packets – some might be pretty outdated at the time of arrival and it might be bad to process them.
In some realtime systems, you might want to add a special reaction to situation when you receive no fresh data for some time, regardless it is accidental or due to an attack.


Difference between computational and statistical indistinguishabilities What is the difference between the two notions of computational and statistical indistinguishability?

Computationally indistinguishable typically means that your adversary is computationally bounded and that because of this they cannot distinguish between, for example, two messages.

For example, say you encrypt (with proper padding) the messages $0$ and $1$ using RSA and send them to the adversary. We would not want the adversary to be able to distinguish which encrypts the $0$ and which encrypts the $1$. If the adversary is not computationally bounded, however, they can break RSA via factoring, recover the private key, and decrypt each ciphertext to get the plaintext. Then they would be able to distinguish.

Statistical indistinguishability is when the adversary is not computationally bounded. They should still not be able to tell the difference between, for example, two ciphertexts. An example of this would be the one-time-pad. Encrypt a message of all 1's with one pad and a message of all 0's with a different pad. The adversary, no matter how powerful, can not distinguish between the two.


Secure multi-party random number generation This question is actually continuation of my previous one.

Secure multi-party computation for digital signature

to implement solution there, I have to generate random data for padding (I will use PSS).

There are N parties. Up to M are malicious adversaries (were trusted, but got taken over silently). I will be happy with solution for any N and M = 1.
Parties should send to each other some random data d[i] and each party based on all d[1..N] should generate some final random value R.

From one side, value should be one and the same for all parties, i.e. calculation should be a fixed predictable process and all parties should get one and the same value R. From another side, malicious adversary party should not be able to affect randomness of R[i], i.e. even malicious adversary should not be able to generate d[m] to get specific R.

Looks like I can achieve this by simply hashing all d[i] values in predictable order. For instance sort d[i] and calculate hash of "well-known-secure-prefix" + d[1..N] + "well-known-secure-suffix".

Am I missing anything?

Looks like I can achieve this by simply hashing all d[i] values in predictable order.

That doesn't quite work; the issue is that the last one to contribute their d[i] value has seen all the previous ones, and can then quickly test candidate d[i] values, looking for one when produces the random padding they like.  This is probably not a huge vulnerability (if the protocol expects a d[i] value within a few seconds, an implementation might be able to test a few million to billions of candidate values (depending on attacker resources) before having to select one); however it is something.

The fix for that is for to have everyone submit commitments to their shares before revealing them.  For example, party i first publishes $\text{hash}( d[i] || r_i )$ to everyone, and not until everyone has published their commitments, everyone then publishes their $d[i]$ and $r_i$ values (and everyone can check that their revealed values matches their commitments).  Then, everyone can combine all the $d[i]$ values, and you then get a hash value that no one has control over.

The best an attacker can do is arrange to be the last person to reveal their $d[i], r_i$ values, and then, if the combined value isn't what they like, just refuse (or misopen their commitment).  This does allow the attacker a veto over the randomness; however for the attacker to use their veto, they have to give a hint that they are the malicious party.  You could try to avoid this by using a function that is hard to compute quickly (e.g. Argon2 with appropriate parameters); I'm not sure if it's worth the trouble...


Character frequency graph for cipher text I have studied about the mono-alphabetic substitution cipher. With Character frequency graph, the encrypted text can be decoded. I am wondering how can be happen?

In each language there is an expected distribution of characters so you can use this to make reasonable estimate as to characters.
For example, E is by far the most common letter in English words, followed by T, then A then O etc. So in your substitution ciphertext, the most common letter is probably E.
From pi.math.cornell.edu:


Berlekamp-Massey to construct minimal LFSR Given the sequence 0010001111 (or any other, not homework, but exam practice), how do you use the Berlekamp-Massey algorithm to construct a minimal LFSR?

I have read several definitions of how Berlekamp-Massey works, but I'm missing some simple example that actually demonstrates the algorithm in use.

Trying to use the following http://en.wikipedia.org/wiki/Berlekamp-Massey#The_algorithm_for_the_binary_field this is how far (or short) I get:

Let $s_0, s_1, \dots, s_9$ be the bits 0,0,1,0,0,0,1,1,1,1.
Let the arrays b and c, each of length 10, be: b = {1,0,0,0,0,0,0,0,0,0}, c = {1,0,0,0,0,0,0,0,0,0}
Let L = 0, m = -1
Iterate 10 times:

Iteration 0:

$$d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9}$$

Already at this first iteration (0) I run into problems. What are these negative subscript s variables?

I'm using the formula on Wikipedia, which is:

$$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$

Is there a fault in this formula? Earlier at step 3, the algorithm states L = 0, hence the final term with:

$$c_Ls_{N-L}$$

makes no intuitive sense if it is taken literally? I assume that the subscript of this s variable should keep decreasing and for c it should keep increasing? If taken as the formula states it, these would be just 0?

But regardless, there is this problem with the negative s variables.

There are no issues with negative indices, even the first (or zero-th depending
on how you want to count them) iteration.

The quantity $d$ is called the discrepancy. During the $N$-th iteration,
$d$ is the difference between $s_N$, the $N$-th bit of the given sequence for
which you are finding the LFSR, and the bit computed by the LFSR that you
have synthesized thus far.  If $d=0$, the bit produced by the LFSR is
the same as the bit in the given sequence and so the current LFSR, which
is guaranteed to produce $s_0, s_1, \ldots, s_{N-1}$, need not be changed:
it is producing $s_N$ also.  On the other hand, if $d \neq 0$, then the
current LFSR needs to be updated, that is, you need to find the shortest
LFSR that produces not just $s_0, s_1, \ldots, s_{N-1}$ but also $s_N$.
How to go about doing this is the crux of the Berlekamp-Massey algorithm.
Note that it is easy to find an LFSR that will produce
$s_0, s_1, \ldots, s_{N}$:
the trick lies in finding the shortest LFSR that will do so.

With that as background, and the further information that $L$ is
an upper bound on the number of stages in the current LFSR, consider
the discrepancy calculation
$$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$
which really ought to be expressed as
$$d = c_0s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$
but the simpler version works because $c_0 = 1$ always (see the
initialization).  Now, we begin with $c_0 = 1$ and all other $c_i = 0$,
that is, a trivial LFSR with no stages that will produce $0$s for
all eternity if you ask it to.
In the very first calculation when
$L=0$ and $N=0$, we have
$$d = c_0 s_0 = s_0.$$
If you want to use the full-fledged form
$$d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9}$$
that is fine, as long as you remember that $c_1=c_2=\cdots=c_9 = 0$,
and the values you choose to
ascribe to $s_{-1}, s_{-2}, \ldots, s_{-9}$ don't affect the computation
at all.  But more realistically, you should note that $L=0$ and $N=0$, and so
the term $c_Ls_{N-L}$ that makes no sense to you is just $c_0s_{0-0}=c_0s_0=s_0$,
just it ought to be.

In the form
$$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$
correctly interpreted, you never run out of bits because
$c_{L+1}, c_{L+2}, \ldots$ are all guaranteed to be $0$ and
$L$ is upper bounded by $N$ and so $s_{N-L}$ can reach down
to $s_0$, the leading bit of the given sequence, but no farther.

  There are no negative subscripts on $s$ (or $c$) that we ever need
  to worry about.


Creating a license system based on asymmetric encryption (RSA or ECDSA) I’ve spent a couple of days researching the topic of creating a license system for my desktop software. While I fully understand that there’s no perfect copy protection, this approach seems to have the best balance for me.
There are a couple of details that I can’t fully get my head around before starting with the implementation. I’d really appreciate if you could share your thoughts on the following topics:

1. Encrypt or Sign? (answered -> sign)

In my understanding both encrypting and signing the license information on my server-side with my private key would work. The desktop client would either have to decrypt or verify the signature of the license text-file with the embedded public key. The only difference I see is that in the latter case the content of the license file is humanly readable while the encrypted version is not.
Would you rather encrypt or sign the license file? Why?

2. Hash or directly encrypt/sign the License? (answered -> signing automatically hashes it)

Let’s say the license information text consists of about 300 bytes. Would you recommend to sign/encrypt it directly, or hash it and then sign/encrypt the hash? I’m asking this because I’ve read different statements that asymmetric encryption isn’t suitable for large data. But what’s the limit?

3. Revoke a License?

What’s the best way to revoke an already issued license? I understand that having an online blacklist is probably the most accurate solution, however I don’t want the software to be dependent on an Internet connection and the reliability of my server. So I guess the alternative is to have black-listed licenses within the application being maintained with new releases? In that case what exactly would I create a list of? The signed/encrypted license (probably too big with a growing list)? A hash of it? Something completely different?

Edit:
Combining the replies so far I guess the first two questions can be combined to "Sign it and don't care about the content length".

The third question however remains unclear to me. I'd like to point out that I don't want to have a dependance on an online server for not bothering honest customers. After all forced online connections bring more annoyance than security.
So there needs to be kind of an "offline solution", even if less secure. Please reconsider question #3 under this aspect.

Actually I'd even like to extend question #3 by the following scenario:

4. Replace stolen/hacked private key
In a worst case scenario the private key might get stolen or somehow hacked, so the attacker is able to create a license generator himself. What would I have to do in this case? I can't blacklist some licenses like in #3, so instead I'd have to replace the key pair, wouldn't I? However in my understanding that would also mean that all customers would require to receive new licenses when updating to a new version with the replaced public key. Is there some clever solution for only blacklisting licenses with the old key pair that have been created after a certain date so the already created licenses before some date stay intact? I understand that it'd require some kind of timestamp system that an attacker can't fake. Is there such a thing?

Thank you!

Sign the license text.  There's nothing confidential in the license text, so you don't need confidentiality.

If possible, include some kind of customer ID or something in the license that links it to a particular customer.

Standard digital signature schemes can easily sign arbitrary-length messages.  Don't worry about the length of the message.  (Internally, they hash the message with a collision-resistant cryptographic hash, then sign the hash, roughly speaking, which is how they can handle arbitrary-length messages efficiently.  But you shouldn't need to know that, if you are using a standard implementation of a well-vetted crypto algorithm.)

One approach to revocation is to have your client software contact a central server for periodic download of the revocation list.  The alternative is to have your server issue short-lived signed authorizations, and require the client to periodically contact the server when each one expires to get a new one (and the server can withhold providing any new authorizations once you revoke that customer).  In either case, make sure that the client can continue to use your software for some set period while they are offline without destroying their access to the software, or your customers might become very mad at you.

There is no purely offline solution to revocation.  If the customer has no network connectivity, there's no way to revoke their software license early.  If in the absence of revocation their software license would be valid until time $T$, and at time $t<T$ you want to revoke them, you can't.  Consider: from the client's perspective, there is nothing that lets them distinguish between whether they are revoked or not, if they don't have any communication whatsoever with the server or anyone else.  So if you expect clients to be offline, it becomes a tradeoff between "the lifetime of a license" (how long before it expires?) vs "speed of revocation" (how long before revocation takes effect?).  If you issue licenses that are good for one year, then revocation won't take effect until that year is up -- if clients are offline.

What you can do is refuse to provide software upgrades to clients whose software has been upgraded.  This won't prevent them from continuing to use the older version of the software, though, for as long as their license is valid.  Optionally, you could also have the client software try to connect to the Internet whenever possible, and if the client goes for a certain time period without having being able to reach the server, you could have the client disable itself; whether this is acceptable will depend upon how you expect your legitimate customers will use your software.

If your private signing key is stolen, you are hosed.  There's nothing you can do to prevent whoever holds that signing key from generating illegitimate licenses that the existing version of your software will accept as valid.  All you can do is change the public key that's hardcoded into the software, in the next software update (so people won't be able to use that newer version of software using licenses signed by the old stolen key) -- but this won't stop people from using the older version of your software.  So try to not let your signing key get stolen.

Finally, remember that these licensing schemes provide a speedbump, not strong security.  They exist to keep honest people honest, but they will not be effective at deterring or stopping dedicated malicious people from bypassing your copy protection system.  Therefore, whatever you do, try to ensure that your license system doesn't inconvenience honest users too much.  Don't drive them to download pirated copies because they're less annoying than the actual paid-up copy.


Does RSASSAPSS use RSA signature I just need to know is it correct to classify the RSASSAPSS scheme and sha[256 | 512 | 1]WithRSAEncryption all under RSA signature?

Yeah, of course, your RFC has references:

  PSS Algorithm

  Although there are no known defects with the PKCS #1 v1.5 [P1v1.5]
     signature algorithm, RSASSA-PSS [P1v2.1] was developed in an effort
     to have more mathematically provable security.  PKCS #1 v1.5
     signatures were developed in an ad hoc manner; RSASSA-PSS was
     developed based on mathematical foundations.

If you follow that link you find that it was defined in RFC 3447, which is called the "Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1". So these are the official standards from RSA Laboratories, except in RFC form. There is also v2.2 which just defines a different set of hash functions, of which only SHA-224 is moderately interesting in the given setting.

In full, the algorithm name is RSA (Rivest, Shamir, Adleman, after the team that thought it out), Signature Scheme with Appendix for SSA, and finally Probabilistic Signature Scheme for PSS. Commonly we just call it RSA-PSS or just PSS though.


Is there a lower cost cryptography than elliptic-curves based cryptography? ECC requires less CPU power, less memory and shorter keys than RSA or any other asymmetric cryptography I came across in the literature (correct me if I am wrong).

Is there a lower cost asymmetric cryptography than elliptic-curves based cryptography?

In fact, for public-key operation (message encryption and signature verification, as opposed to message decryption and signature generation), RSA and, even more, the Rabin cryptosystem, outperform ECC. This may matter to, for instance, low-power embedded systems that try to connect to a powerful server with a TLS-like protocol.

In the domain of signatures, signature size can also be an important parameter. A plain signature based on elliptic curves (ECDSA, EdDSA) will use about 512 bits (64 bytes) for the customary "128-bit" security level. The BLS scheme does twice better (256-bit signatures) through the use of pairing-friendly curves, which are a very special kind of curve with complicated mathematics, and a substantially higher computational cost. Some multivariate cryptographic schemes can conceptually yield both even shorter signatures and faster operations.

For asymmetric encryption, it is known that the McEliece cryptosystem offers really fast operations (but public and private keys are much larger).

There is currently a flurry of activity with "post-quantum schemes" that offer various additional performance trade-offs; notably, some Ring-LWE schemes have public-key operations that outperform even RSA.

Asymmetric cryptography performance is not a simple metric; many features are amenable to measurement, such as speed of public-key operations, speed of private-key operations, signature size/overhead, encryption overhead, public key size, private key size, implementation RAM and ROM usage,... Classic elliptic curve cryptography tends to perform well in each of these, but for each category, there are other algorithms that outperform them.


How are new coins minted in Proof of Stake systems I've been trying to understand Proof Of Stake cryptocurrency systems, but I don't see how new coins are made using the Proof Of Stake system.
My current understanding of Proof Of Stake

People put up a certain amount of cryptocurrency they already hold for a chance to be the entity that creates the next block.  This is the Stake.

Whoever is chosen to write the next block verifies the transactions and as a reward gets to keep all the transaction fees.  If you're not chosen, you get your Stake back.

The Stake of the new block writer is held in escrow (i.e. not allowed to be spent) until several new blocks are added.

If they are found to be cheating they loose their Stake.

I don't see where new coins are being added.  It seems like the coin supply is set and it just moves around as people pay transaction fees.
In Bitcoin, and other Proof Of Work systems, I would buy a computer and become a miner.  I'd keep solving hash problems until I mined a coin, then I could spend the coin.  I do not need to have Bitcoin to mine it.  With Proof of Stake it appears I have to have currency to get more - it's a chicken and egg problem.
In a Proof Of Stake system, how do I go from 0 coins to 1 coin?  For example, I invent a Proof Of Stake cryptocurrency.  How do people besides me get coins to spend?

In a purely Proof-Of-Stake cryptocurrency the number of coins is fixed
And so are most government back currencies.  Interest in Proof-Of-Stake seems to be driven by the rise of 51% attacks, Ethereum Classic has been attacked multiple times, which significantly drove down value.
Unless you're BitCoin, the network of miners is simply not big enough to protect your blockchain once your coins start getting valuable.  Each Ethereum coin is worth about $1,500, which is enticing for attackers.  You can hoard coins, spend thousands on a 51% attack and still come out ahead.
Because of repeated 51% attacks, Ethereum released Ethereum 2.0, which swapped from a Proof-Of-Work, like BitCoin, to Proof-Of-Stake.  There were already plenty of coins and a healthy user base, so not adding new coins wasn't that big a deal.
By switching to Proof-Of-Stake Ethereum 2.0 forces any attacker to put up coins they won't get back quickly.  51% attacks work by overwhelming the network for a short time and cashing out.  Now any attacker would have to control 51% of the network for a long time in order to cheat and get the Stake back.
But where do the Proof-of-Stake coins come from
Ethereum started as a Proof-of-Work cryptocurrency and swapped over to Proof-of-Stake to stop attacks.  Most of the Proof-Of-Stake cryptocurrencies started out as Proof-Of-Work then switched over to Proof-Of-Stake after they had plenty of coins to go around and a good eco-system of users.
Proof-Of-Stake is a way for smaller cryptocurrencies to protect their blockchains.  BitCoin doesn't have to worry as much about a 51% attack since it is the largest cryptocurrency by far.  For reference each BitCoin is worth 48,850 USD while each Ethereum coin is worth 1,500 USD.
How I figured this out
Reading and re-reading the Ethereum 2.0 website
This reddit thread ask a similar question, which lead me to this article.


What to do with a last chunk of 503 bits in SHA1? I was trying to implement a SHA1 algorithm last night, and I got stuck at preprocessing the chunks in SHA1.

As I have understood it, the message that has to be hashed, has to be broken into chunks of 512 bits, and if the last chunk is not equal to 512 bits, a 1 is appended to the bits, followed by '0', and at the end the number of bits of the last chunk of message is appended. So an example:

abc = 97 98 99
abc = 01100001 01100010 01100011
chunk = 0110000101100010011000111... ( 482 x 0) ...11000

But what would happen if the last chunk is 504 bits? Then 9 bits (2^9 = 512), should be used to describe the length of the message, but that does not fit, because there are only 512 - 504 - 1 = 7 bits left to describe the length.

I've looked into Wikipedia and the SHA documentation, but could not find my answer in there.

The answer is in both sources you linked.

Pseudocode from the Wikipedia article:

  append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
  append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
  is congruent to −64 ≡ 448 (mod 512)
  append ml, the original message length, as a 64-bit big-endian integer. Thus, the total length is a multiple of 512 bits.

From the SHA documenation:

  Suppose  that  the  length  of  the  message, $M$,  is $l$ bits. Append the bit "$1$" to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $l+1+k\equiv 448 \mod 512$.

In both instances, the number is the smallest non-negative solution to the same congruency, just noted slightly differently. If you have an example where $-1$ would be a solution to the congruency, then the actual value of $k$ is $511$.


Are there any misuse-resistant asymmetric encryption schemes? The notion of misuse-resistant authenticated encryption (MRAE) was defined in the symmetric setting by Rogaway and Shrimpton, along with the SIV mode that achieves it. The idea being that modern authenticated encryption cipher modes require a unique nonce and fail more or less catastrophically if a nonce is reused. An MRAE cipher mode maintains a strong definition of security even in this case, although not semantic security.

If we look at digital signatures, then there are also unique values that must be used. This has been a classic vulnerability in ECDSA, e.g., in the Playstation 3 hack or the attacks on Android Bitcoin wallets. The Ed25519 signature scheme is deterministic to avoid these problems, replacing the random value with a hash/PRF over the secret key and the message. RFC 6979 proposes a deterministic variant of ECDSA that is along similar lines. Both seem close in spirit to the SIV construction: replacing a random/unique value with a psuedorandom one generated from the message and a secret key.

But what about asymmetric encryption? For RSA it is common to use either PKCS#1 v1.5 or OAEP padding. Both require random elements for security, and it seems to me that both would not achieve semantic security (IND-CPA) if these repeat as RSA is otherwise deterministic. But it is not clear to me to what extent security is lost in this case. While the deterministic authenticated encryption (DAE) that SIV ensures in this case is not appropriate for public key encryption, does RSA-OAEP achieve the notion of deterministic privacy described in Appendix B of http://web.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf? If not, has anyone ever considered an SIV-like construction for RSA? On the face of it, it would seem you could do the same trick and replace the random seed value in OAEP with the output of a PRF calculated over the message and the private key (and potentially a random nonce too). Would this be secure?

Both require random elements for security, and it seems to me that both would not achieve semantic security (IND-CPA) if these repeat as RSA is otherwise deterministic.

Actually, that would be true of any potentially misuse resistant system.  As long as you don't fold in fresh randomness, and as long as you don't update long term state during the encryption, then encrypting the same message a second time will result in the same ciphertext.

Doing an SIV-like trick wouldn't help; if you encrypt the same message with the same private key, the PRF would generate the same nonce, and everything becomes deterministic.

What the PRF would help you if there are weak nonces (for example, in ECDSA, if you use the same nonce twice for two different messages, you leak the private key).  If there was a similar weakness in the public key encryption scheme, that would help.

On the other hand, I don't believe RSA-OAEP has such a weakness; hence the PRF idea doesn't make anything better


Password generation/storage scheme How bad is the following strategy for a password manager on a local machine?

The user wants to sign up for somesite.com where he needs a password.
The user has previously generated a secret key K which he remembers and isn't stored anywhere. Now using a good hash function the site's URL somesite.com is hashed together with K to form the password used for the site.
This way passwords are never stored and can be recalled on a per-site basis from the secret key.

For the sake of this answer I shall suppose that the domain of "somesite.com" is used as the salt to some password-based key derivation function.

Now this has the usual problems of deterministic password managers: As soon as one site is breached, you need a different password for that site meaning either the site needs to change their URL (unlikely) or you need to remember an additional piece of information to derive the password for this particular site or you need to change your master password which will also force you to change passwords on all other sites you use, including those you no longer remember you actively use but still do from time to time where you're locked out with the new master password.

If you want more information why deterministic password management might not be a smart idea, have a look at this blog post.