How to calculate the maximum output size for data encrypted with a RSA Private Key? I have an an encryption algorithm I am working with that looks like this:

prv_key_enc(sha1_hash(data))

Where, the RSA parameters are:

RSA/ECB/PKCS1Padding
1024 bit keysize

I have provided the RSA parameters as well as information on the data that will be encrypted (sha1 hashed value) because I do not know if those details will affect the size of the output (hence this question).

Question: Is it possible to calculate the maximum number of bytes that will be output by the RSA encryption?

NOTES:

The algorithm is fixed by a third party and can not be changed.

Encoding of the encrypted data

The output from the RSA encryption will be base64 encoded, so the above algorithm becomes this:

base64(prv_key_enc(sha1_hash(data)))

Therefore, the final output size will be:

ceil( num_bytes_from_enc / 3 ) * 4

prv_key_enc

I don't know how to express the algorithm for prv_key_enc except for providing an example implementation (including the base64 encoding) using Java:

Cipher c = Cipher.getInstance("RSA/ECB/PKCS1Padding");
c.init(Cipher.ENCRYPT_MODE, privateKey);
bytes outputData = org.apache.commons.codec.binary.Base64.encodeBase64(c.doFinal(data));

We do initially did not have the specification of prv_key_enc, thus we can could not answer with some level of certainty anything more than: the maximum size of its output, in bytes, is at least 128. Looks like the answer now is: the output is always exactly 128 bytes before Base64 encoding, making it exactly 172 bytes.

One thing is sure: the term prv_key_enc is grossly non-standard. Problem is not that Googling it is circular. The main issue is that in RSA, encryption is always with the public key, thus at least one of the following does not hold: prv is for private key, enc is for encryption and correctly describes the overall intend.

Confusing public with private is an even worse sin than confusing encryption with signature, so the best guess we can could make is that the question is about a signature, or rather the signature of a hash (which is functionally equivalent) if we trust the notation (the first step of signature in most practical schemes is hashing, but is part of the signature process, including unambiguously in PKCS#1, so the notation suggests the signature of a the result of sha1_hash that will get re-hashed; such double-hashing is sometime used in practice, e.g. in Global Platform).

Update (AGAIN): Even given the Java code, I am uncertain about what is really done. It could be some signature that is NOT one prescribed by PKCS#1: using RSAES-PKCS1-V1_5 encryption overs the hash of the message, except with the private key instead of the public key; this would be a randomized signature scheme; its security uh, would be an other question, depending to some degree on the verifying code, and perhaps the public exponent.

In any case, a PKCS#1 RSA cryptogram (resulting from one encryption or signature) with a key of $n$ bits is defined to be an octet-string of exactly $\lceil n/8\rceil$ octets, which is always enough to code $x^y\bmod N$ when $2^{n-1}<N<2^n$, where $y$ is the public exponent $e$ for encryption, and a private exponent $d$ for signature; and $x$ is a prescribed padding of the message to encipher, or of some hash of the message to sign. Under PKCS#1, encryption of a 20-octet SHA-1 hash with a 1024-bit key, and signature of any data of any size up to at least $2^{61}-1$ octets with any key, both result in a single RSA cryptogram. Thus for $n=1024$ the single cryptogram is exactly 128 octets (or bytes, that's synonymous on modern computers), including when the leading octet(s) are zero, assuming PKCS#1 is followed to the letter.

However the association of ECB (initials of Electronic Code Book) with PKCS1Padding is very uncommon, except as part of some crypto APIs trying to unify things that should not. Update: We are now told this is Java We are left uncertain about what ECB means. Especially if prv_key_enc did encryption as we are told it does, prv could designate some private hybrid encryption mode using ECB at some point, and who knows what the size of the cryptogram would then be, except that if it uses RSA per PKCS#1 it is going to be at least 128 octets, or won't be decipherable.

Also importantly, practice differ widely!! And we do not have any initially had no clue about practice in the mysterious prv_key_enc (we now have); in particular it is not uncommon that a PKCS#1 signature

is ASN.1 encoded, which always increases its maximum size by several bytes, but can make it of variable size (leading  bytes in the encoding of the integer can be suppressed, this is allowed but not required by at least some ASN.1 implementations, there is a complication with sign, leading to several different ASN.1 signatures valid for the same message even for deterministic signature schemes); (update: given the Java source, I would say this is not the case here);
or/and is expressed as a base-64 (or other base) character string of characters, which increases the size in bytes to some degree (update: given the Java source, base-64 is used here).


Read/Write speed of encrypted sparsebundle I'm in way over my head with even being on this website, let alone attempting to ask a question… but here's an attempt.

Basically, I want to have a password-protected folder on my Mac which is resizable as needed (sparsebundle seems to be best).  It's recommended by Disk Utility to go with 128-bit AES because 256 is "slower".

This got me thinking, how slow is 128?  Is this just while it's initially encrypting?  If so, I don't mind.  The problem is, I'll be storing session files for use with music software in this folder, which means constant reading and writing of files as I work.

Will the encryption slow me down?  I'm hoping that once I put my password in and "open it up", it "stays open" and read/write speeds are as if it isn't even encrypted, but I suspect this isn't the case.  I also don't want to create a speed bottleneck that renders my internal SSDs pointless.  Thanks so much for any thoughts on this situation, much appreciated.

It's recommended by Disk Utility to go with 128-bit AES because 256 is
  "slower"

Yes, AES-256 is 40% slower than AES-128, because it has 14 as opposed to 10 internal encryption rounds.

  This got me thinking, how slow is 128?

On a modern CPU, AES-256-CTR runs at about 1cpb (cycle per byte), meaning AES-128-CTR will roughly run at 0.75cpb (this assumes that the implementation is properly optimized). If you now have a CPU running at 3GHz you get about 4GB/s encryption throughput.

  Will the encryption slow me down?

That very much depends. It depends on the optimization quality of the AES implementation. It depends on the speed of your drive(s). It depends on the load on the CPU during the write / read operations except for the encryption. It depends on the specific CPU, ie whether it has ressources left for encryption.

Usual saying is that it will slow the PC down by a few per cent, so not much.

  Is this just while it's initially encrypting?

Initially it will encrypt the entire area you allocated so an attacker can't distinguish "empty space" from "meaningful data" when looking at it. During the normal usage, only the parts that need changing are changed, meaning you can use the actual size of the data you save / read for your timing calculations.


If the output size of SHAKE128/256 is variable, why is the security fixed at 128/256? The general idea is that the security strength of a good hash function is equal to half it's output length. The output length of SHAKE128 and SHAKE256 is variable, but their strengths are still said to be 128-bit and 256-bit, respectively. Why is that the case?

The inner functions have been specifically designed to only support 128 bit or 256 bit security: it's half of the capacity of 256 or 512 bits. The underlying functions or structure do not change.

You can see this from the following picture, taken from the Noekeon site about generic sponge constructions (SHA-3 / SHAKE / Keccak is a sponge construction):

the capacity is $c$ on the left hand side.

So the output is generated at the squeezing stage, while the capacity (as input for $f$ stays 256 or 512 bits).

This may not matter as much as you think, 256 bit security is considered enough to protect against analysis with a quantum computer. The security won't decrease even if large output is generated.

More information can be retrieved from the Noekeon site:

  When using a random sponge as a security reference, one considers the success of a particular attack. Such a success probability depends not only on the nature of the attack considered but also on the chosen parameters of the random sponge, i.e., its capacity, bitrate and whether it calls a random permutation or a random transformation. The flat sponge claim is a simplification in the sense that we consider only the worst-case success probability, determined by the upper bound on the random oracle differentiating advantage [Bertoni et al., Eurocrypt'08], which depends solely on the capacity of the random sponge. Hence, it flattens the claimed success probabilities of all attacks using a single parameter: the claimed capacity $c_{claim}$.

Later it is mentioned that $c_{claim} = c$.


HMAC of message hash If I have a message m and want its HMAC, I can simply do HMAC(k, m). But sometimes I am not given m but the hash of m: H(m). If I do HMAC(k, H(m)) instead of HMAC(k, m), does this make it more or less secure?

HMAC hashes m when it is longer than block size. So I guess this question is only meaningful when m is equal or shorter than block size.

We can assume the hash function on m is the same one used in HMAC.

It would depend on the hash function if this is more or less secure. If the hash is broken and allows collisions then the scheme is decidedly less secure.

For instance, if you'd use MD5 for the HMAC then you'd still be secure, as HMAC(k, m) doesn't rely on collision resistance of the underlying hash function. However HMAC(k, MD5(m)) certainly does rely on it. So this latter scheme would be considered broken: an attacker can come up with m and m' that would be verified by the same HMAC if H(m) = H(m') after all.

If - on the other hand - a secure hash function is used then it should be secure. Hash functions  are often stacked on top of each other, e.g. in a Merkle tree. That's a known good application of hash functions and I don't think that there is anything wrong with that.

I don't see how length extension attacks would apply to HMAC(k, H(m)). The key is not used in the hash calculation over the message, after all.

The security strength of the combination of HMAC and hash would very likely depend mostly on the hash. For sure, if HMAC uses SHA-256 and the hash uses SHA-256 then the security provided would top at 128 bits due to the collision resistance of the hash. Generally this would not pose an issue if the hash is strong enough, so I almost forgot to mention it.

Using SHA-512 or SHA3-512 instead of a weaker hash function may make a lot of sense...


Key Exchange and anonymity issue If Alice (sender) sends a private message embedded with public key of the Bob(recipient) through onion network, so in this key exchange, does Bob remains anonymous to Alice as Alice knows about the public key of Bob. So if we want to achieve mutual anonymity, how can we do that? Can we achieve mutual anonymity through this key exchange?

You could cheat and use different keys for each recipient. That would work assuming the recipients don't know each other (and cannot compare keys).

Mix networks are by design hard to trace so it depends on the network.

EDIT:
Sending a message to Bob implies Alice knows how to find Bob in the first place, or knows someone who knows where Bob is, without Bob having to directly reveal his location to Alice. The Tor network has implemented this through hidden services which guarantees that both Alice and Bob remain anonymous to each other. The webpage has some diagrams as well and explains how it works, but I won't go into much detail about it because your question isn't about Tor.

It is important to note that public key cryptography doesn't guarantee anonymity or privacy or protection from identification. It's not designed for it. It just protects a message. Tor has managed to do a decent job at protecting two parties who wish to talk to each other and is reasonably mature but mutual anonymity really depends on the (onion) network Alice and Bob are using - not on the PK scheme.


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

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

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

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

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

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

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


What are usable entropy sources in a headless machine without /dev/random or any cryptography API? If I have a headless machine (no mouse movements, no keyboard presses, or user input), without any cryptography CSPRNG APIs, where can I collect entropy from?

I believe that on any CPU that you should be able to find at least two sources of noise with physically proven behaviors to create a purely random number.  The first is through oscillator sampling, assuming that you have a fast clock and a slow clock.  The second assumes that you have DRAM, and through the two-way shot noise in the channel, you should be able extract random bit flips in DRAM if you can control the timing.

Clock Sampling

The clock in a system is not a precise as you'd hope.  Generally, you have a core clock that is generated through a PLL, and you also have some sort of realtime clock at 32.768kHz because that will overflow after bit-15 to give you a 1-second pulse.   By sampling the fast clock with the slow clock, you can generate a series of bits; however, there's a few caveats:

oscillator jitter alone is not enough to create randomness
you can actually degenerate the randomness by trying to make it random if you have a poor circuit model.

As an x86 was mentioned (I know the least about this CPU btw), the time stamp counter combined with a 8254 on older machines or HPET on newer machines will get you a fast and a slow clock source.   Michael S. McCorquodale dissertation should have a very good analysis on the clock jitter in both cases, or at least he did at this defense.

DRAM

If you can control the timing of the DRAM, you very likely could get a random noise source due to the fact that the noise in a semiconductor channel is a function two-way shot noise (and not classical Johnson Noise). Let's limit the scope to a single bit.  You would have to put charge on the DRAM capacitor and then gradually delay the timing until that bit gave you a 1 or 0.  The charge amplifier on the DRAM rows would also add to the noise, but I will ignore that component for now.  Carver Mead and Rahul Sarpeshkar both use shot-noise in their neuromorphic engineering papers as a source for entropy on silicon neurons, and circuits people can derive it but I really don't know where an external reference is.  The caveats:

DRAM timing control
assume that you are not near "freeze out" as the shot noise goes away.

I believe that either of these, combined with a hash, could be used as a means to generate a true random number as the noise sources are rooted in physics.  You'll need to grab a cryptographer to take what I described to the next step.


What asymmetric key exchange algorithms are known besides DH? On Wikipedia, a lot of the subjects that are said to be different key exchange methods are often just protocols that incorporate the Diffie-Hellman algorithm into them. The only other key exchange algorithm I know of besides DH is Algebraic Eraser, of which I don't know much about. Are there any others? And I don't mean key exchange schemes based on symmetric key primitives.

Using lattices/ring-LWE, there is Lattice Cryptography for the Internet (by me), which inherits from Ring-LWE encryption, and has been implemented by Bos et al. with further improvements by Alkim et al.

The underlying mechanism is conceptually DH-like, but uses completely different mathematics.  We start with a uniformly random $a \in R_q = R/qR$, which can be chosen by one of the parties or by a trusted third party.  Here $R$ is an appropriate choice of ring, e.g., $R=\mathbb{Z}[X]/(X^n+1)$ for power-of-two $n$ (in the few hundreds, for current security estimates).

The basic protocol works as follows (oversimplifying a bit): to establish a key, the first party chooses a "short" random $e \in R$, and announces $E \approx e \cdot a \in R_q$, where the approximation hides some short random error.  Similarly, the second party chooses a short $f \in R$, and announces $F \approx a \cdot f \in R_q$.  The first party can then compute $e \cdot F \approx e \cdot a \cdot f \in R_q$, and the second party can compute $E \cdot f \approx e \cdot a \cdot f \in R_q$.  The parties then use some kind of "reconciliation" mechanism to extract a common secret key from their shared "noisy" versions of $e \cdot a \cdot f$.

The above mechanism can be proved secure against passive eavesdroppers assuming the hardness of the corresponding Ring-LWE problem (which itself can be proved quantumly as hard as worst-case problems on ideal lattices, for appropriate parameters).  Of course, in reality we need authenticated key exchange and other properties; these can be obtained using additional techniques that originated in the DH setting (see the first link for details).


Bulletproofs range proof of value provided from trusted third party I'm really interested in range proofs, and bulletproof seems to be the most effective range proof.

I saw an example of usage of bulletproofs range proof: You can generate a proof that your age is greater than 18 without revealing your exact age.

That sounds cool, but what I don't understand is how I can prove that my age is verified. Say I'm 12, but while I generate a proof, I pretend that I'm 20 and generate a proof for 20 years. Clearly, I need a third trusted party to verify that my age is really greater than 18. How it can be done?

Maybe I should generate a proof, and then a trusted third party - for example my government - signs that it to make it a valid proof? Is there a better approach?

I think the example that you saw was just a simple example of how a range proof would work in theory.

Range proofs could be used for encrypting transactions in cryptocurrencies, specifically the amount of the transaction.

A very simplified mathematical notation would look like this:

$\text{E}(a) - \text{E}(b) = 0$

where $a$ is the amount of coins you "spend" and $b$ is the amount the receiver gets. $\text{E}$ indicates that the values are encrypted. This simple calculation here only indicates, that $a$ and $b$ are equal, so you didn't somehow create coins out of thin air.

Bulletproofs are a new addition to range proofs, they basically prove the same thing but bulletproofs can prove something with less overhead than a normal range proof, which again makes them desirable for cryptocurrencies. You can find more information in this PDF of the published paper.

Now to your actual question:

You can't really prove that your age is a certain number without a trusted party. Range proofs (and bulletproofs) just prove that the encrypted input is equal to the encrypted output.

You technically could do this with your government as you suggested. You would need to create a commitment. The commitment comes from anyone who is trusted by the verifier. So to prove your age, this value would have to come from a government issued ID.


Does SpongeWrap (from the Keccak team) absorb ciphertext or plaintext? I have been reading the Cryptographic sponge functions paper, but I'm still confused.

Does Keccak in authenticated encryption mode absorb ciphertext or plaintext?

Edit: Are there any test vectors to verify implementation of Keccak authenticated encryption?

The authenticated encryption mode devised by the Keccak team is the SpongeWrap method, and is first described in this paper — the paper you cite is an amalgamation of all their major sponge papers. The encryption method wrap is described in Algorithm 3, on page 10. In particular, lines 14–18 absorb-squeeze with respect to the ciphertext.

In practice it is probably simpler to think of it in the following way:

To implement this in terms of absorbing and squeezing, we have to use the squeezed output from the previous iteration (here called $s_r$, called $z$ in their algorithm) and xor this with the message, before absorbing in the message as part of the next call. In my mind absorbing / squeezing is a much less clear way of describing the process, but mathematically it is important since it clearly shows the object to be an instance of a Duplex Object, which is itself a series of sponges, and thus allows us to use their security proofs.

I do not know of any test vectors for SpongeWrap.


How to generate different hash values for same files/messages? I was generating HashValue for contents in the file. I want a different hash value every time I wanna generate even if the file is the same.
I am using SHA256. For the same files, the hash value I am getting is the same. Is there any way to generate different hash values?

You should use a cryptographic salt.
This is a single use number generated for each hash. The salt should be prepended to the file to be hashed before hashing. The salt and hash value can then be stored together. Now if you want to compare a file against a given hash you prepend the salt, hash and check against the stored value.
Provided that the salt values are unique, you should not get repeated values (subject to the birthday bound).


Cryptography XOR Question Recently I encountered an interview question related to XOR and I have no idea how to figure it out.
The question is as below:

The algorithm is: $A\oplus B$ (operation) $C = D$

We have the value of $A$, $B$ and $D$. Please figure out the value of $C$ and the (operation). The $C$ is being dump as per the interviewer.

Is there a way to figure out the value of $C$ and the operation as in the question?

First of all I'll have to disagree with fkraiem that there are many possibilities. In fact there are exactly four. I'm going to assume that $A$, $B$, $C$, and $D$ are bits. (Or equivalently I'm assuming that they are bit-strings and the operation we are looking for a is a bitwise boolean operation.)
Then I'll make my life a bit easier and define $E=A\oplus B$, since it does not matter what $E$ actually is.

Now, there are exactly 16 possible binary boolean operations. Not all of those actually have their own name, but they technically do exist and we could come up with a symbol for them. Assuming that we are supposed to find an operation and a description of $C$ in terms of $D$ and $E$ such that the equation is satisfied for all possible values of $E$ and $D$.

Then this leaves us with exactly 4 possibilities.

Namely

XOR as the operator and $C=E\oplus D$.
XNOR as the operator and $C= \neg(E\oplus D)$.
The operator that always evaluates to the second value and $C=D$.
The operator that always evaluates to the negation of the second value and $C=\neg D$.

The reason for this can be seen in the following table. For an operation to be viable, we need that it allows us to force any value of $D$ irrespective the value of $E$. This means we require that in the following table the operation has both a $0$ and a $1$ in each pair of columns in the following table. Otherwise there is always at least one combination of values for $E$ and $D$ that makes the equation unsatisfiable. It is easy to see that there are only 4 viable operations.


Quadratic residue problem on composite integers Its believed that the quadratic residue modulo $n=p·q$ for large primes $p$ and $q$ is intractable, which forms the basis of some cryptosystems.

However, it is solvable if the factors of $n$ are know, such that the problem modulo a prime is easy (we use the Chinese reminder theorem) to simultaneously solve the problem for each prime factor.

The question is, is there any proof of why the same method for prime number should not work for composites?

Or, what if the same technique for the prime number case is applied to the composite number? What flaw might we see in the result?

Obviously the output won't be correct, is there a specific thing that can be said on the result? For example, let us say we wanted to solve the problem for some integer $i$ which we think is a prime (but without our knowledge, it is a composite), is there any thing in the result that can be detected, so that we know the integer in which we thought is prime happens to be not?

The computation of square roots modulo a composite $N$ is hard, because a method for computing square roots can be turned into a factoring method in the following way:

Choose an element $a$ modulo $N$ uniformely at random and compute $A=a^2 \pmod{N}$
Apply the square root computation technique on $A$, get result $a'$
If $a'=\pm a$ retry, else $gcd(a-a',N)$ is a non-trivial factor of $N$

An important argument here is that the square root computation cannot systematically return $a$ because it has no way to know which of the possible square roots of $A$ you started from (they are all equiprobable since you choose $a$ uniformly and kept it secret).

If you are asking about deciding whether an element is a square modulo $N$, the situation is a bit different. First, an element $a$ is not a square modulo $N$ if its Jacobi symbol of $a$ and $N$ is not $1$. But if the Jacobi symbol is $1$, the problem of deciding whether a number is a square is believed to be hard. However, for the decision problem contrary to the computational version, I am not aware of reduction to factoring.


What are the minimum constraints on RSA parameters and why? The RSA cryptosystem only works if certain constraints are applied to its input parameters. Some of those constraints are made to make it "hard" to determine the private key whereas other constraints are there to make the mathematics work. I want to understand the latter category of constraints and why they exist.
Here is what I have so far....

The public exponent $e$ and the modulus $n$ should be $e<\phi(n)$. It can be larger but there is no benefit because $e$ is congruent $\mod\phi(n)$.
There are no other restrictions on $n$ (the use of $n$ with prime factors $p$ and $q$ is just to make the problem "hard").
The public exponent $e$ must be $0<e<n$.
In practice and because of the above, $n>1$.
$e$ does not need to be prime but it should be coprime with $\phi(n)$ (see next point). It does not need to be coprime with $n$ but it doesn't matter if it is. It is usual for $e$ to be chosen from the Fermat Primes, usually $65537$ in real applications.
$e$ and $\phi(n)$ must be coprime to satisfy, for the private key $d$, that $ed\equiv 1\pmod{\phi(n)}$ if, by Euler's Totient Theorem and Bezout's Identity, $ed+k\phi(n)=1$ (where $k$ is a quotient of no relevance and can be any integer; $k$ and $d$ are computed from $e$ and $\phi(n)$ by the Extended Euclidean Algorithm).
The message $m$ (both the plaintext and the ciphertext) must be coprime with $n$ so that, by Euler's Totient Theorem, $m^{\phi(n)}\equiv 1\pmod n$. However, $m$ does not need to be coprime with $\phi(n)$ but it doesn't matter if it is.

I have read elsewhere that any $m$ should work, like this question explains, but that contradicts the last constraint and I've experienced that the algorithm somtimes fails without this.
I have a little program that evaluates the algorithm with some small numbers ($n$ < 20 bits). I find it breaks occasionally and, when it does, I find that $m$ and $n$ are not coprime.
I believe the minimum constraints are those that I've listed above. I'd like to understand whether I have it right or if I'm missing anything. If it should work for all $m$ there must be a reason why I find to the contrary.
Update
$m$ does not need to be coprime with $n$ but $gcd(m,n)$ must be coprime with $n/(gcd(m,n)$ but I don't understand why this is the case.
Optimisations can be performed if the factors, $p$ and $q$, of $n$ are known. They aren't necessary but can help improve decryption performance where $d$ is large. They are:

The reduced totient $\lambda(n)$, or Carmichael Function, can be used instead of Euler's Totient so, in the above, $\phi(n)$ can be replaced with $\lambda(p,q)$. This gives a smaller value for $d$ (and demonstrates that there are multiple $d$ values for a given $e$).

It's possible to use the Chinese Remainder Theorem (CRT) to break the ciphertext into two smaller parts so that two smaller exponents can be computed instead of one based on a large $d$. A good explanation of this technique is here.

When generating the private key, the CRT coefficients $dp$, $dq$ and $qinv$ (the inverse of $q\mod p$) can be precomputed and would form part of the private key. They are then used in decryption instead of $d$.
I don't understand why $\lambda(p,q)$ works and I've found that CRT only works when $p>2$ and $q>2$. The reason for this isn't clear but I think it is because a CRT coefficients when $p$ or $q$ is 2 will be taken modulo 1 which is always zero.

One does not need  e < n .

One does not need $\;\; e\hspace{-0.03 in}\cdot \hspace{-0.03 in}d \: \equiv \: 1 \;\; \pmod{\phi(n)} \;\;\;\;\;$;

one just needs that congruence modulo λ(n).

(Being coprime with $\phi$(n) is equivalent to being coprime with λ(n).)

Neither the plaintext nor the ciphertext need to be coprime with n.

gcd(m,n) must be coprime with n/(gcd(m,n)).

That last condition will be automatic when n is square-free, since it's equivalent to

"If m≠0 then for every prime factor p of n, p's multiplicity as a

factor of m is either 0 or equal to p's multiplicity as a factor n.".

When the quote holds, for each maximal-prime-power factor q of n,

m's remainder mod q will be either 0 or a coprime to q.

When the former case applies, it will continue applying to all positive powers of m.

When the latter case applies:

By Fermat's Little Theorem, $\;\;\; m^{\hspace{.02 in}\phi(q)} \equiv 1 \: \pmod{q} \:\:\:\:$.

For all non-negative integers k,

$m^{(k\cdot \phi(q))\hspace{.02 in}+1} \: \equiv \: m^{\hspace{.02 in}k\cdot \phi(q)} \cdot m^1 \: = \: m^{\hspace{.02 in}\phi(q) \cdot k} \cdot m \: =$

$\left(\hspace{-0.03 in}m^{\hspace{.02 in}\phi(q)}\hspace{-0.06 in}\right)^k \cdot m \: \equiv \: 1^k \cdot m \: = \: 1\cdot m \: = \: m \;\;\; \pmod{q} \;\;\;\;\;\;\;\;$.

λ(n) is a positive integers multiple of $\phi$(q), so for all

non-negative integers $k$, $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{q} \:\:\:\:$.

Thus, when the quote holds, one will have $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{q}$

for each maximal-prime-power factor q of n and each non-negative integer k.

Therefore, by the Chinese Remainder Theorem, when the quote holds one

will have $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{n} \;\;\;$ for all non-negative integers k.


In RSA, why does Alice's $N$ need to be relatively prime to Bob's $N$? I was asked this by my professor and I didn't understand the reasoning behind it. If Alice has a the key pair $(p_a, n_a)$ and Bob has the key pair $(p_b, n_b)$, why do $n_a$ and $n_b$ have to be relatively prime?

In RSA, the modulus is computed as $n=pq$ where $p$ and $q$ are prime. Given two moduli, if they have no primes in common, then the GCD is $1$ and they are relatively prime. If they share a prime factor, then the GCD will reveal that prime factor. Therefore, anyone who knows the two public keys can factorize the moduli and break security.


Vigenere cipher with a shared resource I'm pretty new to all of this and I apologize in advance if (as, I'm sure it has) this question has been asked and answered a million times previous, but I couldn't find anything through searching (which might speak to my less than ideal google-fu).

I understand intuitively that the Vigenere cipher is insecure because the fact that the keyword is shorter than the plaintext will inevitably lead to repeated patterns and that probabilistically you can then crack the whole thing. Then, using Shannon's theorem, we know that the KEY must be at least just as long as the PLAINTEXT and therefore key-sharing gains us nothing.

But, what would be the problem with sharing some resource as our keyword. Like for instance, what if we agreed that our keyword would be Moby Dick? Then, we only need to share the TITLE of the book and then we have access to something that could be longer than the plaintext? Or, even more secure, what if we pick a de dicto key - something that picks out a changing element. For instance, if we choose "The Leftmost Column of the NY Times" - that changes on a day-to-day basis, but is always going to be secure?

I'm just a bystander curious about what he's missing and/or misunderstanding. Thanks.

Since your key is non repeating, you're essentially talking about one-time-pad, not a vigenere cipher.

There are two problems with what you propose:

The key is natural language. This means that the key acts like a second use of the pad. This is enough to recover the plaintext with few mistakes.

The one-time-pad doesn't just require a long enough key, the key must also be perfectly random.
The shared text is public knowledge, and thus presumably known to the attacker. So the attacker could simply test every text in their library against your ciphertext. This is quite feasible using computers, even for huge libraries.


Usage of Zero-knowledge proofs for NP-complete languages It is well known that if OWFs/PRGs exist, then there is a zero knowledge proof for any NP-complete language, say G3C (graph coloring in 3 colors). The zero-knowledge notion maintains that any malicious verifier that interacts with the prover can be simulated by a PPT algorithm (including the communication) and thus, doesn't gain any advantage from the prover's replies.

Yet, if a PPT algorithm can find a coloring in a graph with non-negligible probability (even without interacting with a prover), then the whole notion of zero-knowledge proofs for NP-Complete languages becomes useless!

Is there a distribution over graphs that enables generating graphs for which no PPT algorithm can find a 3-coloring in non-negligible probability?? (under the assumptions of P!=NP and OWF & PRGs exist). Or a distribution over graphs that enables generating graphs for which no PPT algorithm can determine if they are in G3C or not with non-negligible advantage?
 Otherwise I can't see how such a ZK proof can be beneficial.

If one-way functions exist, then there is a distribution over graphs (or SAT formulas, or ...) having the property you're asking for.  In short, just put the OWF through the Cook-Levin reduction.

In a little more detail, Cook-Levin transforms the NP witness-finding question "what is a preimage of $y = f(x)$?" (for random unknown $x$) into the NP witness-finding question "what is a 3-coloring of this graph $G$?", by converting $y$ into a graph $G$ such that any 3-coloring of $G$ can be efficiently converted back to a preimage of $y$ under $f$.


McEliece parameter tuple (n, k, t) through BouncyCastles (m, t, poly) I am using BouncyCastles Java API and want to use McEliece encryption. After browsing through various paper for finding good parameters (e.g. How to choose McEliece's parameters?) I am now having the problem, that I do not see a possibility to set these parameters with the BouncyCastle API.

In all papers, the parameter set is a 3-tuple: (n, k, t). But with BouncyCastle, I can only specify the 3-tuple (m, t, poly) for keypair generation.

How do they correspond to the (n, k, t) parameter set?

The parameters are specified in the parameters object. You give them normally in the constructor: new McElieceCCA2Parameters(m, t, poly). I am however not sure how they map to the canonical parameters of the crypto system.

Javadoc: http://bouncycastle.org/docs/docs1.5on/org/bouncycastle/pqc/crypto/mceliece/McElieceCCA2Parameters.html


SHA-256 Reversing A String of Equal Length I've done a lot of reading on how SHA-256, I've found that SHA-256 is irreversible because more data is fed into the hashed string than the hash string contains.  But, what if the data that was inputted was equal in size to the output string, a string of 64 characters is inputted a string of 64 characters is outputted.  Would it be possible to reverse the hashed data back to the original string?

SHA256 gives 256 bits, which is 32 bytes, not 64 "characters" (please use the well-defined bits and bytes). When written in hexadecimal notation, you need 64 characters from 0-9a-f, but the length of the hash is 256 bits.

Yes, you could invert the hash. Unfortunately, a straightforward lookup table would be too large to store, but you can still do brute force without memory. This would take you on average $2^{255}$ tries (that's many).

There have been papers, like "Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family" which discuss preimage resistance attacks on the SHA-2 family, but they're, as far as I know, all academical breaks (meaning they cannot really be exploited efficiently.


What weaknesses in Hash_DRBG did NIST find and fix? Matthew Green states in the Practical Kleptography presentation (video, at about 12:15) that Hash_DRBG (from SP800-90A) as originally proposed by NSA had potentially exploitable flaws or bugs and that NIST fixed it.

I've been unable to find how. This VCAT report only states that it was contributed by NSA and NIST "provided substantial comments".

Does anyone know how Hash_DRBG was broken and what fixes were made?

Please bear in mind that this information is all secondhand. I have not looked closely at the original drafts of Hash DRBG (although you might find a draft that's early enough if you peruse the FOIA results in [1]).

However, during conversations with folks at NIST I was told that there were certain weaknesses in early drafts of Hash DRBG that were very similar to known issues in the FIPS 186 (DSA) DRBG. Kelsey, Schneier, Wagner and Hall have at least one paper on this [2]. In particular, if an attacker is able to control some of the entropy inputs to the DRBG, they could force that DRBG to repeat output. I gather from these discussions that the original draft of Hash DRBG had similar issues. The version published in NIST SP 800-90A was modified to deal with these.

It's important to note that I'm not saying these flaws were deliberate. Quite frankly they just look like bugs. And they appear to have been fixed long before to the publication of NIST SP 800-90A. I also can't state with certainty that Hash DRBG was an NSA design, though I believe the NSA was involved in its design.

One more note: it's my understanding that Hash DRBG was eliminated in the ANSI standard because it was deemed redundant, but it was kept in NIST SP 800-90 (though in repaired form) because the NSA asserted that some partners had already implemented it. Hash DRBG was also included in ISO 18031, some portions of which I can probably dig up and add to this link later. It's not clear whether the ISO version includes the repairs.

Welcome to our crazy world!

[1] https://github.com/matthewdgreen/nistfoia
[2] https://www.schneier.com/paper-prngs.pdf


Creating ECDH using OpenSSL For academic reasons, I'm playing around with OpennSSL 1.0.2g.
I tested RSA encryption/decryption.
I created key exchange with DHKE.
But I'm struggling to find a way, to create ECDH, using only OpenSSL.
Is it possible to create such key exchange only using OpenSSL?

ECDH is included in the ciphersuites, so the only answer is: yes, this should be possible.

For your further research, it might help to know that Crypto.SE features a lot of Q&As related to “OpenSSL ECDH”.

Also see the related documentation at the OpenSSL wiki for practical code examples showing how to use ECDH in OpenSSL, how to use the low-level APIs to achieve the same, and infos about how to handle ECDH and Named Curves.


Prevent double-spending with decentralized digital currencies without all transactions being public? A recent approach to creating a decentralized online currency, called Bitcoin, has been generating some interest. The goal is to have a way to transfer currency without a central authority and without double spending or counterfeiting. Their approach is to have all the nodes in the network try to verify a transaction by doing a proof-of-work computation and then the transactions with the most verification are considered official. If an attacker wants to forge the official record (to reverse their first spending and use the coin again), then they must have the majority of the computing power in the network. The biggest downside is that in this scheme, the record of all transactions must be public, which the author of the Bitcoin paper assumes is a must:

The only way to confirm the absence of a transaction is to be aware of all transactions. In the mint based model, the mint was aware of all transactions and decided which arrived first.  To accomplish this without a trusted party, transactions must be publicly announced.

Is it obvious that all transactions must be publicly known in any such scheme?
It is known that schemes without a public-transcript can be implemented when you have a central authority/mint, but I am only interested if it is possible for a decentralized approach.
Notes
I originally asked this question on cstheory. Also, I am not familiar with the tagging on crypto.SE, so any help is appreciated!

For such a scheme to work, if I have some currency, I have to be able to give it to Abel and I have to be able to give it to Beth, but I have to be unable to give it to both Abel and Beth. This means that giving the currency to Abel has to somehow make me unable to give the currency to Beth even though I previously could do that.

There are three mechanisms by which this can be accomplished:

There can be a central authority. To give the coins to Abel, I must tell the central authority that I have done so. The central authority would then prohibit me from giving the coins to Beth. This means giving coins requires both approval from the central authority and reporting to the central authority.
There can be a distributed secure device. To give the coins to Abel, I must tell the instance of the secure device that holds the coins. The device will then prohibit me from giving the coins to Beth once it has given them to Abel. This means coins must be held in a physically-secure device. In practice, it also requires a central authority to load the devices and issue keys to them. (I need to prove a secure device was involved in the transaction, which requires the device to have a certificate, which requires some authority to issue such certificates.)
At least some aspect of all transactions can be public. Thus, if I give the coins to Abel, there will be a record Beth can easily find. Beth will know the coins are not mine to give.

Bitcoin chooses the third approach. This seems the best approach for cryptographic decentralized currencies. There is no fourth approach known.

Now, the only information about the transaction that needs to be public is enough information to prove I have the coins and prove that I didn't transfer them elsewhere. As it happens, the Bitcoin protocol leaks much more information than this (for example, the account I transferred the coins to). The protocol could have been designed to make less information public if that was desired.

The coins need be traceable back to their origin. But whether or not you can track the particular accounts they passed through is an implementation decision.

For example, a hypothetical coin could use the following mechanism: Alice wants to send some coins to Bob. She knows Bob's public key. She generates a random private key just for this transaction and encrypts it with Bob's public key. She then publishes a transaction transferring coins to the public corresponding to the random private key she generated along with the encrypted version of that same key that she encrypted with Bob's public key.

Now, Bob will see a transaction that his private key is able to claim. Nobody else will know the transaction was to Bob because neither Bob's public key nor any analog of it appear in the block chain. Bob will have no idea the coins came from Alice and nobody else will have any idea the coins went to Bob.

This method still leaves the coins fully traceable. But no traceable accounts ever appear in the block chain.

This solves two 'problems' with Bitcoin. If I publish a bitcoin address somewhere, anyone can see how many Bitcoins that account got. If someone wants to transfer me bitcoins that cannot be traced, he must obtain a one-time use account from me, which he cannot easily do if he wishes to give me the coins anonymously.

You can still generate and use one-time accounts with Bitcoin, but you cannot broadcast them or they cease to be one-time accounts. And there is no easy way for someone to anonymously request one from you.

You might think this means every account must be tested to claim every transaction, resulting in an inefficient scheme and making things like web-based mass wallets computationally impractical. However, I've discovered a truly marvelous solution to this problem, but this answer is already too long.


Why do we need in RSA the modulus to be product of 2 primes? I think I roughly understand how the RSA alorithm is working.

However, I don't understand why we need the $N$, which we use as a modulus, to be $pq$ for some large primes $p, q$.

I vaguely know it has something to do with factorization, but I am kind of lost. So, hypothetical questions.

What would happen if the $N$ was not $pq$, but just a big prime?
What if $N$ would be some random composite (that's easy to factor)?

The other parts of RSA would stay the same.

RSA would still "work" with such $N$, but isn't secure for $N$ that are easily factored. If you know the factorization of $N$ (which is trivial for prime $N$s) you can calculate the private key from the public key. This totally breaks the desired security properties of RSA.

The essential equation for RSA is that $m^{\phi(N)+1}= m \mod N $ for all $m$. This works for all $N$, but only for some $N$ it's hard to calculate $\phi(N)$. When using RSA we require $\phi(N)$ being hard to calculate, since once you know $\phi(N)$ you can get $d$ from $e$ by solving $e \cdot d = 1 \mod \phi(N)$ using the extended Euclidean algorithm (just like what you do when legitimately creating the key-pair).

If $N$ has more than two factors, but at least two of those are large and hard to guess, it's still secure. But almost nobody uses this RSA variation.


Why do the majority of SSL cipher suite used CBC? I am looking at a wireshark capture of the cipher suites sent by my browser to the server during an SSL handshake; however, almost 90% of them use CBC, with 2 or 3 having GCM.

Why is CBC most used? Is there a specific property that makes CBC preferred by web communications?

Also literature suggests that the non-feedback modes (e.g., counter mode) perform better in practice; however GCM shows up in only a few cipher suites.  Any ideas why?

Historically, CBC was for long the dominant block cipher mode, but in recent years there's been a slow but firm move away from it, based on two trends:

The move toward authenticated encryption as the "go-to" ciphers for practical applications;
A reevaluation of the merits of CTR-based modes over CBC, driven by a variety of factors like:

The proliferation of attacks against CBC-based ciphersuites;
The simplicity and performance of CTR.

So you see a lot of CBC because it was the king for a long time, and it's only going away slowly.  This blog entry by Cloudfare has graphs of the SSL cipher suites they're seeing and shows AES-GCM gradually gaining over AES-CBC.

Two references I've found useful:

Phillip Rogaway, "Evaluation of Some Blockcipher
Modes of Operation"
Chris J. Mitchell, "Error Oracle Attacks on CBC Mode:
Is There a Future for CBC Mode Encryption?"


How secure is XOR-CBC? How secure would this be? To be clear, I mean replacing the block cipher encryption step in the Wikipedia diagram explaining CBC with plain old XOR?

EDIT:

Replace block cipher encryption part of diagram with XOR ($\oplus$)

CBC diagram

Or:
($C_0 = IV$)

$$C_i \equiv \left(\bigoplus_{C_{i-1}}^{P_i}\right) \oplus {K}$$

Completely insecure.

If you just replace the encryption with XOR with the key, then the first ciphertext block is just $c_1=m_1 \oplus k$. The second block would be $c_2=m_2 \oplus c_1 \oplus k = m_2 \oplus m_1$.

The second block is actually not encrypted at all. And that goes on, the first, third, fifth and so on block is just an XOR with the key, the second, fourth, sixth and so on doesn't depend on the key at all.


Is RSA provably secure in the sense of Douglas Stinson's ``provable security''? Here's a quote from Douglas Stinson:

  “[i]f a cryptosystem can be ‘broken’ in some specific way, then it
  would be possible to efficiently solve some well-studied problem that
  is thought to be difficult. For example, it may be possible to prove a
  statement of the type “a given cryptosystem is secure if a given
  integer n cannot be factored.” [...] [B]ut it must be understood that
  this approach only provides a proof of security relative to some other
  problem, not an absolute proof of security. This is a similar
  situation to proving that a problem is NP-complete [...].”

Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman
and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.

Does this apply to RSA?  Suppose I find the private exponent by some other way other than factoring $n$.  Then I would have broken RSA without factoring.

So although Stinson's example mentions factoring, we can't immediately think of RSA here because there's no proof that factoring is the only way to recover a private key.  What do you say?

Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption.

This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with appropriate padding can be reduced to the RSA problem (extracting $e$-th roots mod $n$), which is a well-studied assumption... But only because this is the one underlying the RSA cryptosystem, and we have been using the cryptosystem a lot in the past decades.

Something much more satisfying would be to reduce it to a problem which had long been studied before, in different context; the most natural such candidate is indeed factoring. Unfortunately, we do not know of a reduction from RSA to the hardness of factoring integers - in fact, we even have proofs that it will be hard to find such a reduction (in a well defined sense).

We have, however, many other cryptosystems which can be reduced to factoring; the earliest example of this kind is the cryptosystem of Rabin.


ZK proof that two short solutions are equal Let $A_1$ and $A_2$ two $m \times n$ matrices defining SIS problems.
Does there exist a zero knowledge proof that two short solutions are the same, i.e.
$$y_1 = A_1 x $$
$$y_2= A_2 x $$
$$ \Vert x \Vert < \beta$$

This paper Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications is a good place to start researching. The paper appeared at PKC 2013 so have been peer-reviewed. In addition, there is an upcoming paper at CRYPTO 2016 which looks very related How to prove knowledge of small secrets.


Distributing shares in a particular monotone access structure Consider 6 people, $A,B,C,D,E,F$ and a secret. Construct a scheme which enables the following subsets of people to retrieve the secret:

three players from the set $\{A,B,C,D\}$

two players from the set $\{A,E,F\}$

two players
from the set $\{B,C,D\}$ together with at least one player from the set $\{A,E, F\}$.

I want to know how I can distribute $6$ shares amongst these people so that the secret can only be obtained when three shares come together i.e a threshold of three. I've tried so many options but there always seems to be one unauthorised subset that gains access to the secret that causes it not to work. For example if I label the shares $1,2,3,4,5,6$ and distribute them like the following:

$A - 1$

$B- 2$

$C - 3$

$D - 6$

$E - 2,5$

$F - 3,4$

Then the unauthorised set $\{D,F\}$ for example will have three shares and be able to recover the secret. Is there a way to distribute them so that only authorised subsets can gain access to the secret?

Well, the easiest way I can see to represent this access structure is:

Select three random values $r_1, r_2, r_3$
Generate a threshold-2 secret sharing scheme with the secret $S$ (where $S$ is the ultimate secret), and whose shares are $\alpha_1, \alpha_2, \alpha_3$
Generate an independent threshold-2 secret sharing scheme with the secret $r_3$, and whose shares are $\beta_1, \beta_2, \beta_3$.

Then,

$A$ gets $\alpha_1$, $r_3 \oplus S$
$B$ gets $r_1$, $\beta_1$
$C$ gets $r_2$, $\beta_2$
$D$ gets $r_1 \oplus r_2 \oplus S$, $\beta_3$
$E$ gets $\alpha_2$, $r_3 \oplus S$
$F$ gets $\alpha_3$, $r_3 \oplus S$

It's easy to see that any of the allowed subsets can recover $S$ (e.g. for the subset $A, B, C$, they jointly know $\beta_1$ and $\beta_2$, that allows them to recover $r_3$; and with $r_3 \oplus S$ gives them $S$).  It should be fairly clear that any subset not within the access structure gets no information about $S$.

This doesn't give an answer to the precise question to raised; it does appear to solve the problem you were trying to address.


Newbie question: one-way functions in cryptography I'm reading this article on the basics of cryptography and it says that the main principle is about taking such an algorithm that knowing the end result and the algorithm, an eavesdropper wouldn't be able to determine the initial data.

They give an example:

Supposedly, I know the numbers in the second and third row, but don't know the x and can't derive x. But I can: all I need is to do something like this:

for (int i=0; i<100_000_000; i++)  {
      if (i%7==5)  {
        if (getPower(i, 3)!=-1)  {
            System.out.println(i+", " + getPower(i, 3));
        }
      }

}

It gives me:

243, 5
177147, 11

meaning, that 243 and 177147 are 3^5 and 3^11 respectively and also give the residual 5 when divided by 7. So it doesn't look like a one-way function to me.

So it doesn't look like a one-way function to me.

What you're missing is the scale and basic ideas used in cryptography. Namely the following three facts:

Cryptographic exponents for discrete logarithms have thousands of bits instead of 3 as the example in the question. As such merely trying one value at a time, would take several billion years at least.
In cryptography, you only ever see the result of the exponentiation after the modular reduction (the third row of the graphic), because there are efficient algorithms for finding logarithms over the real numbers.
When using these system in cryptography we don't actually perform $2^{1000}$ or so multiplications but instead use repeated square and multiply which brings this down to a few thousand multiplications. Note that this algorithms requires full knowledge of the exponent to be applied.


Enforce weak RSA in TLS I'm going to give a small talk on the mathematical background of RSA. My audience will consist mostly of software engineers and to make the mathematical stuff tangible, I wanted to demonstrate how to calculate the private key from the public key and the modulus in some reasonably realistic scenario.

What I was planning to do is to set up a simple server (Spring Boot inside Docker) which has one POST-endpoint and this endpoint should only be accessible via https.

Then I wanted to use tcpdump to capture the communication between some client and this server. Since I want to be able to decrypt this communication, I want the key exchange between client and server to be performed over RSA with the modulus so small that it can be easily factorized.

However, I fail in creating a (self signed) server certificate with decryptable RSA because the tools I know all require the primes to have some minimum size.

Does anyone know some good way to create such a certificate? Or, maybe, has someone already set up a similar scenario?

Does anyone know some good way to create such a certificate?

As you need to put the private key on the server anyways, you could just copy it of and use that for demonstration purposes.

Alternatively you could use software versions from the time when such keylength restrictions were not in place.

In particular you might want to take a look at FREAK, in particular this website (need to scroll down a bit) has a list of vulnerable server and client software that you should be able to retrieve from release archives for demonstration purposes.


Is a modulo addition safe for the encryption of private keys? I'm writing a JavaScript library which needs to encrypt 256-bit private keys. The algorithm often used for that is AES, but the shortest implementation around has 172 lines of code.

I'm trying to optimize for code size, so I'm looking for shorter alternatives. I've done some research and believe this should work well enough:

encrypt(key, password):
    salt = random64Bits()
    hash = keccak256(salt + password)
    enc = []
    for i from 0 til 32:
        enc[i] = (key[i] + hash[i]) % 16
    return enc + salt

I.e., the modulo-16 addition of each byte of the password and the hash of (key + a random salt). It can be implemented in about 10 lines, so, if there isn't anything inherently wrong, I'd certainly favor it.

Is this encryption scheme secure? Are there equally simpler alternatives properly standardized?

Note that I already require Keccak for other functionality, so the Keccak code base doesn't count to the amount of code required.

Note: I will not talk about potential implementation flaws in this answer but rather about the conceptual way to approach this problem.

OK, so what you have a 256-bit hash function $H$ (Keccak) and what you need is a (somewhat) secure password-based encryption scheme that from what I could guess avoids operations on bit-wise data.

So what should be used is really CTR-mode with a Keccak-MAC and an iterated Keccak for password-based key-derivation purposes. I shall now discuss these three components:

Iterated Keccak PBKDF. Right now the code does $k\gets H(s\parallel p)$. This means an attacker has to do exactly one evaluation of the (fast) hash function to verify a password guess. This is way too fast, as users tend to choose weak passwords which then get brute-forced quickly. If you want to read further into this, this is basically equivalent to "salted, plain MD5". Now for the solution: As you seemingly can't afford to use a proper password hashing scheme, your best choice is to use PBKDF2 with Keccak as your PRF, ie your PRF would be $F(k,x)\mapsto H(k\parallel x)$. I expect this to only take a few lines and you can re-use your salt. As for the iteration count, you should adjust it such that the derivation takes roughly 100ms.
Keccak-CTR. Right now your code iterates over all nibbles and adds the "noise" that was generated by the hash function call. This is safe (in theory), however it only works as long as the output of the hash function and the size of the data object in question match. If they don't anymore, you really want to use CTR-mode, or rather want to use $c_i\gets p_i\oplus H(k\parallel i)$ for blocks of the size of a hash function output. I also have to recommend against using the key directly as the "pad" for the data, but rather that it is run through the hash function once more, the reason being cryptographic key separation (and it doesn't scale as mentioned above).
Keccak-MAC. Right now you wouldn't nice manipulations on the key, which could potentially lead to keys being more easily attackable or just "simple" denial-of-service attacks. This is why you should use cryptographic authentication. Doing so is actually quite simple, due to Keccak being a sponge construction: $\tau\gets H(k\parallel s\parallel c)$, ie the authentication tag is the result of the concatenated hash of the key, the salt and the cipher text. Append this to your output and verify the consistency of this value on loading and you can rest assured that it hasn't been tampered with.


RSA numerical questions Let $n$ be the modular arithmetic, $p$ and $q$ the two large primes such that $n=p*q$ and $e$ the public exponent. Here they are two "simple" numerical questions:

If $p = 13$ and $q = 17$, what is the range for exponent e?
Let be $p = 7$, $q = 11$ and $e = 3$. What is the max integer that can be encrypted?

About 1), I know that $e$ needs to be relatively prime to $φ(n)=(p-1)*(q-1)$, but how can I determine the range?

About 2), is there really a threshold on the maximum integer I can encrypt with RSA?

what is the range for exponent e?

Actually, there is no required upper bound for $e$ (except that some implementations may reject ridiculously large values).  The math behind RSA states that any $e$ that is relatively prime to both $p-1$ and $q-1$ will work, no matter how large it is. There might not appear to be a need for an $e > lcm(p-1, q-1)$ (as for any such $e$ larger than that, there is a smaller $e$ that acts equivalently). However, there are obscure cases where such $e$ arise; one possibility is some shared computation of the RSA key pair (where no one entity knows the factorization) could possibly generate such a huge $e$ (depending on how that shared computation works).

  What is the max integer that can be encrypted?

Well, if you omit the padding, the largest value that can be encrypted is $N-1$, as Raoul722 states.  However, it is rarely a good idea to omit the padding in RSA (and if you have to ask, you don't know enough to safely omit it).


Multiple private keys Bear with me, I'm a utter newbie in this field.

I'm looking for a way to tackle this:

  Alice and Bob have a secret document. Alice gives Bob a key to secure
  the document. Bob uses this key to encrypt the secret document. Nobody
  that finds this key should be able to decrypt the data. Alice holds a
  special key that can decrypt the document.

  Some time passes and Bob needs to read the document again. Alice gives Bob
  the special key to decrypt the data.

So in this scenario, once the document is encrypted only Alice has control over when Bob can read the document with her special key. We assume that the key Bob used to encrypt the document can stolen or found. So the key to encrypt the document can not be used to decrypt it. Only Alice her special key can. So this means: use a public key to encrypt and a private key to decrypt the document. So my research points me to for example: RSA.

Now let's make it a bit more complex and closer to our real scenario:

  Alice and Bob have a secret document. Alice gives Bob a key to secure
  the document. Bob uses this key to encrypt the secret document.

  Alice and Cesar have a secret document. Alice gives Cesar the same key as
  Bob to secure the document. Cesar uses this key to encrypt the secret
  document.
  Nobody that finds this key should be able to decrypt the data. Alice holds a
  special key that can decrypt the document.

  Some time passes and Bob and Cesar need to read the document again. Alice gives Bob and Cesar each a different special key decrypt the data.

So this is sorta the same as before. Only this time we use multiple private keys and one public key. My first option was RSA but since RSA can only have 1 private key, what are my options?

You can use different key pairs for this. You can give both Bob and Cesar two public keys that they can use to encrypt documents with. Those public keys are part of a key pair that is shared with Bob and Cesar - one for Bob and one for Cesar.

Bob or Cesar encrypt the document by first encrypting a two random symmetric keys with the public keys (one each) and using the result of XOR-ing the two random values as another symmetric (data) key. Then either of them needs to encrypt the document with the symmetric data key. To decrypt they both need to decrypt both symmetric keys, combine them and then decrypt the document. They can do this in any order, as long as the two symmetric keys become available at the same time.

This is a fairly basic secret sharing scheme with an asymmetric component.

Undoubtedly there are better schemes that have additional properties. Having some kind of signing or authentication should be high on your wish list as well.


Does CCA security imply authenticated encryption? Does CCA security imply authenticated encryption?

No. RSA-OAEP is indistinguishable under adaptive chosen cipher text attacks (and even non malleable under adaptive chosen cipher text attacks), but it is not an instance of authenticated encryption. - The sender who encrypts the message might even be anonymous to the recipient who decrypts the message.

More generally, in a successful Chosen Cipher text Attack the adversary gets the honest decryptor to accept a forged cipher text, decrypt it, and accept the resulting plain text. It is not primarily a key recovery attack (although in some cases it might be extended into one). In fact, you can't turn a CCA against a secure block cipher in any standard mode, into a key recovery attack. You can however alter the decrypted plain text by altering the cipher text, unless the scheme is NM-CCA2. Often this is enough - most attacks against SSL/TLS don't actually recover any secret key, but only gets the recipient to accept plain text as authentic even though it is not.

In the case of asymmetric encryption, this gets more complicated. Plain unpadded RSA is not secure against CCA (which at the same time makes it possible to use it for homomorphic encryption). RSA-OAEP is secure against CCA, meaning you can't take a RSA-OAEP cipher text encrypted by someone else, alter it (in any other way than by replacing it with another message RSA-OAEP encrypted with the same public key), and get the owner of the private key to decrypt it.


Are there any security flaws in using an involutive S-box? I know that it is difficult to answer these questions without knowing the full scheme it would be used in, but are there any problems that could be introduced into a block cipher if an involutive S-box is used?

As pointed out by Aleph and poncho, it is difficult to provide an educated answer without seeing the whole cipher.

One one hand, involutive S-boxes can be used to attack a scheme: e.g., this key-recovery attack against MANTIS observes that since the SBox is involutive, its DDT is symmetric, and uses it against the scheme. This paper by Biryukov shows that involutional components can be used as a leverage to ease distinguishing attacks.

On the other hand, there are block ciphers like ICEBERG which heavily rely on involutional components and are still secure: in ICEBERG, the SBox is involutional, but also the multiplication matrix and even the whole cipher itself (up to the key schedule).

Also keep in mind that the rationale usually given for putting involutional components in block ciphers is that they allow compact hardware implementations (you can reuse the same components for encryption and decryption). So if hardware implementation is not your goal, I would advise against using involutions as they can introduce subtle weaknesses.* As there already exist many great block ciphers, I would also strongly advise against designing your own.*

*unless there is a strong incentive to do so (or if you are doing it for research/recreational purposes)


hardware and software optimizations for Salsa20 I'm using the Crypto++ implementation of Salsa20 for a software project we are working on and I'd like to know if there are any SSE or software optimizations that will increase the speed of the CSPNG?

Looking at the Crypto++ 5.6.2 implementation for Salsa20 it seems they do have an SSE implementation, but it doesn't use intrinsics so it doesn't look very portable between compilers.

If you're not exactly set on using Salsa20 I would recommend using ChaCha20, which is a small modification of Salsa20 by the author (Daniel Bernstein) that is slightly faster and cleaner. And if you really value speed I would recommend using Salsa12, which reduces computation time by about 40%.

For ChaCha20 I would recommend the crypto_stream\chacha20\krovetz implementation found in SUPERCOP. Similarly for ChaCha12.

For Salsa20 I suggest you look inside the crypto_stream\salsa20 folder and look for an appropriate implementation for your target platform. You can see timings for various platforms at these pages.


Using Whirlpool hashing function to encrypt data I've read that the Whirlpool hash function can produce footprints that could be used as a pseudorandom generator.

Is it "OK" to use it to encrypt some data using something like the following?

EncryptedData = Concat(DataBlock XOR Whirlpool(DataBlock + SecretKey))

Occasionally, for instance in very constrained environment, it can be useful to use only a few cryptographic primitives for all processing. (When you only have a hammer everything looks like a nail.)

In such environments, it may be useful to use key derivation function to derive stream to be used as a stream cipher, or use hash function as cipher and so on.

However, using primitives in non-standard ways risks implementation mistakes and often is "path less traveled", thus risking vulnerabilities that were not thought of.

EncryptedData = Concat(DataBlock XOR Whirlpool(DataBlock + SecretKey))

Have you thought of decrypting data encrypted this way? The DataBlock is supposedly to be kept as a secret, but Whirlpool takes it as input. Thus, to decrypt EncryptedData, it is necessary to know DataBlock.

A pretty well examines way of using hash function based on cipher function as cipher is SHACAL-2. SHACAL(-2) is one of the most well examined "hash-function turned into cipher" constructs. It has been used with SHA-1 and SHA-2 hash functions. It would be possible to use similar construct to turn (some implementations of) Whirlpool into a forward cipher function, and then use that in, in counter mode.

If it is mandatory to use entire Whirlpool function (above "WhirlpoolCAL" construct would not use padding part of hash function), then you could, for instance, use key derivation construct as stream cipher. See NIST SP 800-108 Recommendation for Key Derivation Functions using Pseudorandom Functions. The document shows a few ways that could be used to construct keys stream using a hash function (approved hash functions are SHA family, but here you would use Whirlpool). Note the NIST SP 800-108 requires HMAC construct to build keyed hash function from hash function.

That document also warns against idea of using the function as stream cipher:
"To comply with this Recommendation, the derived keying material shall not be used as a key stream for a stream cipher2.
2 The level of security provided by using the key derivation functions specified in this Recommendation to generate a key stream for stream ciphers has not been investigated."

So summary is, that you "could" do it like this:

EncryptedData = Data XOR KDF(HMAC(Whirlpool))

Where KDF is implemented using the following process (see the above mentioned document SP800-108 for full details).

Process:

n := ⎡L/h⎤.
If n > 2r-1, then indicate an error and stop.
result(0):= ∅.
For i = 1 to n, do
a. K(i) := PRF (KI, [i]2 || Label || 0x00 || Context || [L]2) 12
b. result(i) := result(i-1) || K(i).
Return: KO := the leftmost L bits of result(n).

But: The comment above from Stephen Touset, the SP 800-108 document, and this answer also, are all warning against doing it this way. Use good cipher like AES (or maybe Camellia or ARIA or whatever) in appropriate mode for symmetric encryption and decryption needs and avoid home-baked cryptography.

(AES-CTR if you want to use XOR and no message integrity. AES-GCM is typically even better idea.)


how to prove our algorithm is secure against chosen plaintext attack? I am working on a topic in cryptography where I have tried to develop an encryption scheme.

How could I prove mathematically that my algorithm is secure against chosen plaintext attacks?.
Will it be sufficient to say that as my algorithm is uniformly distributed, it is secure against chosen plaintext attacks?

The usual approach to prove IND-CPA security is to construct a logical argumentation called "reduction". In this argumentation you first start with the assumption that certain computational problem is hard (for example, the Decisional Diffie-Hellman assumption), and then you proceed to demonstrate that if your crypto scheme were insecure with respect to IND-CPA (which means that the adversary has access to an encryption oracle), then you could construct an algorithm that uses your scheme to break the hard problem. If our current knowledge dictates that indeed the chosen problem is hard, then your scheme must be IND-CPA-secure.
No. A trivial counterexample would be a deterministic encryption scheme. It is a well-known fact that an encryption function that is deterministic cannot be IND-CPA-secure. This is true regardless if its output is uniformly distributed.


Differences between OWP and OWF and their IND-CPA security I am learning about one way permutations and one way functions and am not sure of the differences if there are any.

Also in the random oracle model are they both IND-CPA secure?

A one-way permutation is just a one-way function in which the function is a permutation (id est, a bijective function). Every OWP is a OWF, the converse is not true.

IND-CPA security is a security notion specifically related to encryption schemes. OWF and OWP are not encryption schemes, hence they cannot be said "IND-CPA secure"; however, one can construct an IND-CPA symmetric encryption scheme from any OWF, or OWP. (for asymmetric encryption schemes, stronger primitives are needed).


Are two keys derived from the same password vulnerable to a related key attack? Background

I am currently writing a password manager application. As usual, the passwords are put in a file encrypted using a user-entered password. I'm using the NaCl library but actually it's not really important.

Here is what I do to encrypt the file content with a user-entered password P:

First I generate a random salt S of 32 bytes (256 bits) and store it at the start of the encrypted file.
Second I derive a secret encryption key K from the password P and salt S using Argon2i.
I then compute a hash H of the file content using SHA-512.
Then I encrypt and authenticate the hash H with the XSalsa20 and Poly1305 primitive of the NaCl library (crypto_secretbox functions) using key K and nonce 0 and I store the encrypted and authenticated hash in the encrypted file after the salt.
Finally, I split the file content into blocks of 1024 bytes, except for the last block which may be less than 1024 bytes. The blocks are encrypted/authenticated and stored in the encrypted file in order, one by one, using the XSalsa20 and Poly1305 primitive. The first block is encrypted with key K and nonce 1, second block with nonce 2, third block with nonce 3, etc...

The file content length is not hidden since the last block is not padded to 1024 bytes but I don't believe it's a problem for a file holding logins and passwords.

Each time a file is encrypted or re-encrypted, for instance after having been modified, a new salt S is generated to prevent the same key K from being used twice.

To decrypt the file, the plaintext salt is used to derive the key again from the password entered by the user, then the hash H and file content are decrypted and authenticated and a hash of the decrypted file content is computed and checked to see if it match the initial hash H.

The reason I'm computing a hash H and encrypting and authenticating it is to prevent the individual encrypted blocks of the file from being added, removed or swapped. If an attacker try to do this, the hash H will not match at decryption. I'm also using block size of 1024 bytes because the NaCl website warns that primitives are only tested with message lengths up to 4096 bytes (https://nacl.cr.yp.to/valid.html). 1024 is completely arbitrary, I could have chosen 2048, 3159 or 4096 but I thought "Better take some margin" and I feel power of 2 are neater.

Question

It's obvious that in a given file, a combination of K and a given nonce is never used twice, since the nonce is incremented each time the key K is used. The same key K is also never used twice since it depends on the salt which is random and changed each time and is therefore never the same. So unless I'm overlooking something, it seems to me that my scheme is not vulnerable to a reused key attack.

However, the NaCl website also warns that "NaCl does not make any promises regarding the resistance of crypto_stream to related-key attacks". Since crypto_stream is XSalsa20, I believe this warning also applies to XSalsa20 + Poly1305. It makes me fear that two secret keys K1 and K2 derived from the same password P using Argon2i and two different salts S1 and S2 are somewhat related, since they come from the same password.

On the other hand, I'm thinking that even if a mathematical relation exists between K1 and K2 it's not a simple direct one. Otherwise we could compute, say Argon2i(P, S1) from Argon2i(P, S2) and that would mean that Argon2 was flawed since the salt would be ineffective.

Does two keys K1 and K2 derived from the same password P but from two different salts using Argon2i are vulnerable to a related key attack ? By the way, do you see any other flaws in my file encryption scheme? My main goal is confidentiality but it's a plus if my application can detect files which were tampered with, that is authenticity.

Unless the key derivation function you use is specifically designed to exploit related-key attacks, then no, it will not result in a vulnerable related-key pair. It is true that XSalsa20 is not designed with related-key attack resistance in mind, but a key put through any decent KDF will not lead to exploitable weakness.

This answer explains the kind of effort that can go into creating a pair of related keys. Suffice it to say, there is absolutely no reason to worry that a KDF will produce such keys. The only other kind of attacks occur for certain ciphers when keys are extremely similar. An example of this is RC4, where encrypting known-plaintext with multiple keys that differ in only a few bits can lead to complete key recovery.

Note: I have not analyzed your overall password management scheme, just your direct question about related keys.


Preimage attack given half of the preimage 512 bit X has been hashed using SHA256(X) = Y

Given Y and half of X (the first 256bits) to attacker, how hard is to reveal whole X
Can SHA256 or any real world function be cracked to allow this problem to be solved faster

Is this problem known in cryptography? and under what name? Tried google for concatenated preimage attack but found nothing.

Knowing the first 256 bits of X is of little use. Intuitively you can understand this becsuse most values for the first 256 will have a matching second 256 which will lead to Y.
Assuming pseudo random distribution throwing n balls in to n bins will leave only n/e of them empty.
By knowing there is an answer with said prefix the brute force is slightly faster, not by doing anything clever in the brute force but by virtue of eliminating the possibility of no value. If we have a random oracle hash the worst case brute force with the prefix is 2^256 and without it is 2^512 but the difference in expected attack time is rather small. And in any cass it is entirely not fessable. Threre are no known relevant attacks on sha255 to make this even remotely feasible to launch.


Probability distribution function in Regev Cryptosystem In Regev - On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, chapter 5, Public Key Crypto System, it is stated that

  The probability distribution function $\chi$ is taken to be $\Psi_{\alpha(n)}$ ... we can choose $\alpha(n)=1/(\sqrt n\  log^2n)$

The document states in §1 that the standard deviation is $p\alpha$

How does $\Psi_{\alpha(n)}$ look like ?

Should I take $\Psi_{\alpha(n)}(x)=\frac{1}{p\alpha(n)\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{x}{p\alpha(n)})^2}$ or $e^{-\pi(\frac{x}{p\alpha(n)})^2}$?

EDIT

The document also states that the curve is centered around 0 and that the probability of zero is roughly $\frac{1}{p\alpha(n)}$.

So starting from the generic probability density function
$$
f(x|\mu,\sigma2)=\frac{1}{\sqrt{2\pi\sigma^2}}e^{\frac{-1}{2}(\frac{x-\mu}{\sigma})^2}
$$
My best guess is that

$$
\Psi_{\alpha(n)}(x)=\frac{1}{p\alpha(n)}e^{-\frac{\pi x^2}{(p\alpha(n))^2}}
$$

A confirmation would be much appreciated.

Neither of the alternatives in your question is completely correct.
The distribution $\Psi_{\beta}$ is as defined by equation (7) in Section 2 of your reference:
$$\Psi_{\beta}(r) = \sum_{k = -\infty}^{\infty} \frac{1}{\beta}\,\exp\left(-\pi \left(\frac{r - k}{\beta}\right)^2\right),$$

for $r \in [0, 1)$. So $\beta$ is not the standard deviation of a normal distribution (instead, the standard deviation is $\beta / \sqrt{2\pi})$. Note that $\Psi_{\beta}$ is not a normal distribution though, but a "periodization" of normal distribution.

Also keep in mind that $\bar \Psi_\beta$ is a discretized version of $\Psi_\beta$, i.e. the distribution that you get after multiplying by $p$ and rounding to the nearest integer mod $p$. This is why the introduction mentions that $\bar\Psi_{\alpha}$ has (roughly) the shape of a normal distribution with standard deviation $p \alpha$.


How does the key agreement process take place in Virgil E3Kit SDK for end to end encryption? I'm using Virgil E3Kit SDK to implement end-to-end encryption in my App. Their E3Kit SDK is very effective and not too hard to understand, but I still don't understand how does the key agreement process take pace in Virgil E3Kit SDK. The workflow they describe in SDK document is:

If A want to send messages with end-to-end encryption protection to B, so the steps are:

A generate her key pairs (one Public Key is published on Virgil Card Services and
one Private Key is saved securely on her own device).
B generate his key pairs.
A looks up for B's Public Key on Virgil Card Services and
uses B's Public Key to encrypt the messageA-B.
When B is received the messageA-B, he use A's Public Key to verify the messageA-B's
integrity and he uses his Private Key saved on his device to decrypt the messageA-B.

In the document page, Virgil shows algorithms that are used in Virgil E3Kit, in which:

They uses PRNG for key generation
They uses KDF2 for key derivation
They uses X25519 or ECDH for key exchange

I think both X25519 and ECDH need a new random shared secret for each secure communication session. How does Virgil E3Kit do that while both parties of communication just only need to generate their key pairs when they first register account, then they can start using end to end encryption with these key pairs forever? Virgil E3Kit uses asymmetric key exchange with X25519 or ECDH, but after that they use symmetric encryption with AES GCM to encrypt messages in endpoints.

So my questions are:

How can Virgil E3Kit SDK use symmetric key for symmetric encryption in endpoints, while they use asymmetric key exchange? And could you please illustrate and explain for me about this process?
And, what role PRNG, KDF2 (key derivation function) and X25519 or Ed25519 (Elliptic Curves) play in this key agreement process?

E3kit uses ECIES under the hood. It's a hybrid encryption scheme where symmetric key is encrypted using the key derived from the DH shared secret. KDF is needed because it's not secure to use the raw DH result as a symmetric key.


Is there any relationship between Paillier Cryptosystem's random r and other factors I want to try run an example of  Paillier cryptosystem(Algorithm), So i just started with some basic examples, but cannot obtain correct result/decryption.
I just change random factor r from 97 to 101 in Reliable Implementation of Paillier Cryptosystem, and return with wrong result. is there any relation between the random r and other Paillier factors i,e; g, λ, n etc
The other example is:

Key Gen:

p = 5, q = 7 ,n =3 5 ,n² = 1225;
g = n+1 = 36;
λ = LCM(p-1,q-1) = 12;
μ = L(g^λ mod n²)^(-1) mod n
μ = L(36^12 mod 1225)^(-1) mod 35
μ = L(421)^(-1) mod 35
μ = 3    ; where L(421) = 12

Encryption:

Let m = 32; random r = 17;
c = ((g^m) * (r^n)) (mod n^2)
c = ((36^32) * (17^35)) mod 1225
c = 278

Decryption:

m = L(C^λ mod n^2) * μ (mod n);
m = L((278^12) mod 1225) *3;
m = 1191*3 mod 35;
m = 3;

But the original message is 32. what is wrong?
I went through some other example, but unable to decrypt correctly.

You made a mistake in decryption.

You wrote:

m = 1191*3 mod 35

You lost L(...) here. Instead of 1191 it should be L(1191):

m = L(1191)*3 mod 35
L(1191) = 34
m = 34*3 mod 35
m = 102 mod 35
m = 32

Voilà. We got the original message.


What is the significance of the Period of a Steam Cipher If we only know the period of a Stream Cipher, let's say 150-200 bit in length, how can we use this information to attack a stream cipher?

Taking a look at this link, What is the period of a cipher? I see that the period of the stream cipher is simply the amount of data we encrypt before starting the encryption over again.

From the attacker's stand point, this let's us know the chunk size of data we are encrypting but how does this help us attack the stream cipher? Won't we still need to know plaintext and cipher text?

If you know the period of the stream cipher, you can XOR 2 different encryptions from the same point in the period (integral number of periods apart) and eliminate the pseudo random stream entirely.  All that would be left are 2 plaintexts XOR'd together, and this is something a smart child can break in a short time.


Does AES-128 have the same strength as AES-256 with a padded key? When I use the same 128-bit key for AES-128 and AES-256 with a known/public padding for the latter,

is there some weakness in AES-256 that is not present in AES-128 with essentially the same key?

This might be the case when I'm receiving the key from an

algorithm which just doesn't produce enough bits (128 or less).

Is it better to use AES-128 in this case or can I use AES-256 with an one-size-fits-all attitude?

I feel like the answers in this question answer my question,

but don't explicitly state the effectively used key size.

In this scenario, it is better to use AES-128 than AES-256 if you are to 0-pad a 128-bit key to 256 bits.

If you 0-pad, the round key for round 1 is all 0s, and round 3 is effectively worthless as well. So now you are down to 12 effective rounds vs 10 for AES-128.

Then you need to look at the effectiveness of the remaining keys. Here are some example key schedules for AES-256 (0-padded 128-bit key) and AES-128:

00  a1b625fe 019e24c8 0a7f661b 9ad9d51c    00  a1b625fe 019e24c8 0a7f661b 9ad9d51c
01  00000000 00000000 00000000 00000000
02  c2d5469c c34b6254 c934044f 53edd153    01  3d0e10fc 3c903434 36ef522f ac368733
03  ed553eed ed553eed ed553eed ed553eed
04  9780ba2c 54cbd878 9dffdc37 ce120d64    02  fe9f15e9 c20f21dd f4e073f2 58d6f4c1
05  669ce9ae 8bc9d743 669ce9ae 8bc9d743
06  8dbd6726 d976bf5e 44896369 8a9b6e0d    03  86f5e352 44fac28f b01ab17d e8cc45bc
07  18887679 9341a13a f5dd4894 7e149fd7    04  e36ea834 a7946abb 178edbc6 ff429e7a
08  834e9df5 5a3822ab 1eb141c2 942a2fcf    05  3978842f 9eecee94 89623552 7620ab28
09  3a6d63f3 a92cc2c9 5cf18a5d 22e5158a    06  0d40336d 93acddf9 1acee8ab 6cee4383
10  fddd44bc a7e56617 b95427d5 2d7e081a    07  e1101b37 72bcc6ce 68722e65 049c6de6
11  e29e5351 4bb29198 17431bc5 35a60e4f    08  6fe2c58b 1d5e0345 752c2d20 71b040c6
12  794b6037 deae0620 67fa21f5 4a8429ef    09  db412299 c61f21dc b3330cfc c2834c3a
13  34c1f68e 7f736716 68307cd3 5d96729c    10  5b64ce86 9d7bef5a 2e48e3a6 eccbaf9c
14  a707f037 79a9f617 1e53d7e2 54d7fe0d

Round 5 is effectively 64-bits instead of 128, and while you cannot see it with this example, rounds 2 and 4 are also very linear with respect to subkey 0, and only at round 6 do we see a level of acceptable nonlinearity (we get this at round 3 with the 128-bit key schedule). Further nonlinear expansion is also slower, I would suggest the final round keys are similarly linear to the original key for both key schedules.

It is probable that even with the extra 4 rounds, the full AES-256 cipher with the padded key will be weaker than AES-128 against a variety of attacks, while taking 40% more time to encrypt. As CodesInChaos suggested, expanding a 128-bit key to 256-bits using a cryptographic hash will result in a stronger cipher than AES-128 while still only having an effective key size of 128-bits. I would not recommend duplication of the key to expand to 256-bits, round key linearity is still high, and it is probable existing attacks will be more effective.


ECDSA secp256k1 attacks Are there any known and feasible ECDSA attacks on secp256k1 which can reduce the bit security of the algorithm? For example from 256 bits of security down to 192 bits?

Yes.  Pollard's $\rho$, a generic method to compute discrete logs, costs only about $2^{128}$ group operations for a group of order about $2^{256}$ so secp256k1 should be considered to have a ‘128-bit security level’, not a ‘256-bit security level’, against discrete logs.  But a 128-bit security level is enough to thwart all adversaries—at least, the ones who don't have a quantum computer or a cryptanalytic breakthrough against secp256k1 in particular.


Proof that a given function is not a OWF I'm currently learning about one-way functions. I have a book with the following exercise (Sadly there is no solution in the book...)

  Let $g\colon \{0,1\}^n \to \{0,1\}^n$ be a one way function.
  Prove that $f\colon \{0,1\}^{2n} \to \{0,1\}^n$ with $f(v,w) := g(v)⊕w$  is NOT a one way function.

I don't really get how I can solve this exercise... because if $w$ is, for example, $0^n$, it would be a simple reduction to show that it is in fact a one-way function, right?

How can I get an advantage $>\mathit{negligible}(n)$ ?

The attacker is given $y = f(v,w)$ and must find $v$ and $w$. The attacker can generate a random $v_0$ and calculate $g(v_0)$; then they can simply calculate $w_0=y⊕g(v_0)$ and then return $(v_0,w_0)$, for which $f(v_0,w_0)=y  \implies \Pr[\mathit{Invert}=1]=1>\mathit{negl}(n)$.


How to anonymously transfer ownership where sender cannot resend I'm new to cyptography, so I apologize if this is a dumb/impossible goal or has already been answered (I was not able to find it by searching).

I wish to devise an anonymous protocol for transferring digital goods, where the message contents are publicly viewable, but neither sender nor recipient can be determined from the message contents alone.

Additionally, once the sender has transferred the goods to the recipient, he should not have the ability to resend the same goods again to another recipient.  Only the initial recipient should have that ability (i.e. a recipient should obtain sole ownership of the goods once transferred).

The goods may change hands many times, and ownership should be publicly provable at the time of a transfer without revealing the identity of the sender or recipient.

My initial design is for all users in the system to generate their own public/ private keys and a transport (for Diffie-Hellman exchanges).  A user's public identity would consist of their public key and transport.

When a sender wants to transfer goods, he first generates new random public/ private keys and transport (not his publicly known values, in order to obscure the fact that he is the sender).  He uses these in a Diffie-Hellman exchange with the recipient's publicly known values to generate a shared secret.  This shared secret is used as a salt to generate a specific public/private key pair.  The sender also generates a completely random public/private key pair.

The sender uses the specific public key to encrypt the random private key.  This encrypted value is included in the message contents, along with both public keys and the generated transport.  The message contents also contain a random number, and that number encrypted with the specific public key.

The sender also adds the hash of a previous message which was used to transfer ownership of the goods to him originally.  The sender then signs the message using the private key that was encrypted in that previous message.

Users in the network listen to messages, and attempt to recreate the shared secret from the public key and transport included in each message, using it as a salt to recreate the specific public/private key pairs.  If the specific private key decrypts the correct random number, then a user comes to know that he is the intended recipient.  He can then use the specific private key to decrypt the random private key, which he can now use to prove he has ownership of the goods.

The problem with this strategy of course, is that both the sender and recipient have access to the key used to prove ownership, and this would allow the sender to transfer the goods to additional recipients (i.e. the original recipient does not have sole ownership of the goods).  Are there some additional cryptographic measures that could be added to this process to prevent the original sender from re-sending the goods?  Or am I heading down a dead-end path and need a better strategy?

After some thought, I have devised one possible solution to the problem (I am definitely open to other ideas too).

Rather than proof of ownership being used solely for the purpose of a subsequent transfer, instead there can be an additional step added to the process whereby the recipient claims ownership of the goods.  The system would not allow multiple claims of ownership for the same transfer request -- only the first claim would be validated, and subsequent claims rejected.  Any time goods are transferred, both proof of ownership and proof of claim would be required.

Once a recipient identifies that he is the recipient of the goods (using the process I outlined above), he would broadcast his intent to claim ownership of the goods.  At this time, he would use the encrypted random private key to verify that he is the intended recipient, and generate a new random public/private key pair.  He would broadcast the new public key as part of his claim, and use the private key to later prove that he claimed ownership of the goods.

Of course, the sender would also have the ability to broadcast a valid claim of ownership after broadcasting the original transfer message (because sender and recipient are both obscured), but that is not a problem as long as the system only validates one claim.  If the sender uses this to reclaim ownership, then the recipient will know that he has not received the goods and can respond accordingly.

This basically allows the sender one opportunity to change his mind before he relinquishes ownership of the goods.  It also allows the sender to reclaim his goods if he accidentally sent them to the wrong address, or if the recipient does not respond in some reasonable amount of time.  So definitely seems to be positive feature of the system.


AES-128 or AES-256 with 18 bytes of key storage? I have only 18 bytes in which to store a (randomly generated) key.
Is it more secure to:

use AES-128 and a 16 byte key,
use AES-256 and a 18 byte key padded with 14 zero bytes to make a 32 byte key, or
use AES-256 using a KDF to turn 18 bytes into a 32 byte key, each time it is needed?

I'd argue for (3) for these reasons:

the algorithms are used within their operating assumptions;
related: AES may be insecure if the keys have a specific format;
no entropy is lost when performing the conversion to 32 bytes as compared to (1).

AES-128 is also considered secure at the moment, but it may not be if quantum computers are created that enable Grover's algorithm. So there is some reason to prefer AES-256 over AES-128. Of course, Grover will still work for 18 byte keys as well, but with the KDF you'd have at least a trickier target.
Of course you'd want a KDF that provides 256 bits of security, accept 18 byte input key material and provide key expansion. HKDF would probably be a good choice.

Note that you could argue that reason #1 & #2 is rather speculative. Actually, the NIST FIPS 197 standard (AES) reads:

No weak or semi-weak keys have been identified for the AES algorithm,  and there is no restriction on key selection.

However, AES doesn't have the strongest key expansion routine, and I'd also be somewhat worried about side channel attacks. Better error on the safe side...