How to find g in Factoring-Based Trapdoor Hash Function Please explain how to find a value of $g$ if
$p,q$ are safe primes having $p'=(p-1)/2$ and $q'=(q-1)/2$ are also primes
$n=p*q$
$\lambda() = \operatorname{lcm}( − 1,  − 1) = 2''$.
How to chose at random an element $g$ of order $\lambda()$?

There are several different ways to do this:

The most obvious way to do this, if you know $p$ and $q$, is to select random values $r$ relatively prime to $n$, and determine their order; that is, verify that none of $r^{\lambda(x)/(p-1)}, r^{\lambda(x)/(q-1)}, r^{\lambda(x)/2}$ are 1.  Since approximately three quarters of possible $r$ values do have order $\lambda(n)$, this is efficient (if not as efficient as the methods I show below).

However, this doesn't work if either you yourself don't know the factorization of $n$, or you need to demonstrate to someone else know doesn't know.

$t$ has order $\lambda(n)$ if $t, t-1, t+1$ are all relatively prime to $n$, and if $t$ is either a quadratic nonresidue mod p, or a quadratic nonresidue mod q (or both).

The easiest way to select such a $t$ is to go with the 'both' option; select a random $r$ and set $t = -r^2 \bmod n$ (and verify that $t+1$ is relatively prime to $n$); $r^2$ is a quadratic residue mod p (obviously), and as $p \equiv 3 \pmod 4$, if $r^2$ is a quadratic residue, $-r^2$ must be a quadratic nonresidue (and similarly for $q$).  And, if we select $r$ to be a nothing-up-my-sleeve number, so is $t$.  The only downside is that this process will generate only a third of the potential values.
Another approach is to select random $t$ values (where $t-1, t+1$ are relatively prime to $n$), and compute the [Jacobi symbol][1] to $t$ with respect to $n$; if it is -1, then we know that $t$ is a quadratic residue to one of $p, q$, and a quadratic nonresidue to the other; we don't know which, but in this case, we don't care.  Approximately half of the possible $t$ values will have a -1 Jacobi value and so this is also reasonably efficent (if a bit more work, in part because libraries that can compute the Jacobi symbol are a tad more rare).  And, this method will generate the two-thirds potential values that the previous method does not.

And, if it is critical that we generate a value which is strictly uniform (even if you don't know $p$ and $q$), you can use the $-r^2$ method with probability 1/3, and the Jacobi method with probability 2/3; that turns out to generate all possible values with uniform probability.

[1] https://en.wikipedia.org/wiki/Jacobi_symbol


How to generate many passwords from one passphrase, so that knowledge of one password does not compromise the others? The limitations are:

it should be a function.
passphrase is so weak, that if hash of it is known (or big part of hash), then it can be brute forced.

I want to get N passwords from one passphrase. Lets imagine, that N hackers have web sites with login pages, and I want to use my N passwords as passwords for accounts on their web sites. I don't want one hacker to be able to find my password for another hacker's web site.

First what comes to mind is to divide passphrase to N parts, and use each part as a key. Like

f("MyWeakPassphrase") = {"My", "Weak", "Passphrase" }

(It satisfies restrictions)

But are there better ways?

update
Most of answers suggest to use kdf with salt + counter or something similar. It is still a hash, and if broken, all other passwords revealed. I thought there might be an algorithm, so that brute forcing passphrase will reveal only part of a passphrase if only one password is known. Like function above, but better.

You can just use a counter along with a key derivation function (https://en.wikipedia.org/wiki/Key_derivation_function) such as a hash, and do something such as:

for(int i = 0; i < numberOfPasswordsToGenerate; i++){
   aNewPassword = hash(MyWeakPassphrase + i);
}

The counter makes sure you get a new password, for each iteration of the loop, and they will never know the hash of the original passphrase without the counter.

Of course this can be brute forced, given a large enough dictionary for a dictionary attack or a good rainbow-table, so use a as well salt to prevent that... Actually, just always use a salt.

Edit:
To be clear on what I mean, this will make it more akin to this:

for(int i = 0; i < numberOfPasswordsToGenerate; i++){
   aNewPassword = hash(MyWeakPassphrase + i + salt);
}

The salt is just a large enough randomly generated number for each password you store next to the encrypted/hashed password in your database. If you just use a single identical salt for all the passwords, it is called a pepper instead, if I remember correctly.

Note: If you want to go further on security, you could use an IV (initialization vector) that contains the beginning number of the loop, so that the attacker has no idea which numbers you used, unless he gains knowledge of your IV as well.

This would look sort of like:

void generatePasswords(int IV) {
   for(int i = IV; i < IV + numberOfPasswordsToGenerate; i++){
      aNewPassword = hash(MyWeakPassphrase + i + salt);
   }
}

I'm bad at writing pseudo-code, sorry! It always get C-like, but yet not quite C.

Hope it helps!

NOTE: Please read Krystian's comment. We all suggest that you make different passwords by adding a counter and salt to it. This prevents precomputed attacks, but if someone learns the salt and counter (which can be expected, these are considered "public" knowledge security-wise), then they can bruteforce your primary password.
The fundamental problem here is that, you want to map a password to multiple unrelated values. In order to be able to recreate this mapping later on (which I assume you would want to, since you derive the passwords from the same passphrase), you need to make the passphrase different and still unique for each new password you make. We do this by adding a salt and counter. Since you need to store the salt and counter to recreate the mapping, they are considered public and thus anyone can still bruteforce your password, since it is weak.


Security (CPA?,CCA?) in Authenticated identity-based encryption When I read authenticated identity-based encryption by Ben Lynn, encryption works to send data from user A to user B where:

$$a=e(d_{A},B)$$
$$s=H_{3}(Msg,K)$$
$$C=<s,\gamma \oplus H_{2}(a,s),H_{4(\gamma)}(Msg)>$$

Revealing [$H_{2}(a,s)$] can break the security if the correct ($a$) value is known by attacker.

The scheme may be CPA-secure if the private key extraction query restricts for sender's identity. However, if decryption oracle exists, will it be CCA-secure?

Attacker will modify the ciphertext as follows:

$$C^{*}=<s,\gamma \oplus H_{2}(a,s) \oplus H_{2}(t,s),H_{4(\gamma)}(Msg)>$$

where $t$ will be any pairing operation and submits $(C^{*},IDB)$ to decryption oracle. I think the oracle will return $\gamma \oplus H_{2}(t,s)$. Thus, attacker can easily reveal $\gamma$ by XORing with $ H_{2}(t,s)$.

Could you tell me if it is CCA-secure?

What is a suitable assumption for the problem of finding $e(d_{A},ID_{B})$ value knowing $ID_{A}$ and $ID_{B}$? Is it a bilinear Diffie-Hellman problem?

The eprint version has the following to say (adapted for your notation):

  Authenticated-decrypt: [...]
  Check that $s = H_3(\gamma, Msg)$. If not, reject the ciphertext, otherwise output then plaintext $Msg$.

In the attackers case, the decryption oracle would try to check if $s = H_3(\gamma', Msg)$ with $\gamma'=\gamma \oplus H_{2}(a,s) \oplus H_{2}(t,s) \oplus H_2(a, s) = \gamma \oplus H_{2}(t,s)$. This leads to a wrong hash and the oracle rejects the decryption before giving any useful information to the attacker.


(Simple) Tool for analysing performance (speed in particular) of cryptographic hash function? I am doing some research for which I intend to insert some (external) function in different cryptographic hash functions and I would like to analyse how the insertion of this extra code in the hash function affects its performance, especially its speed in hashing and any other performance measures.

I came across SUPERCOP and SMHasher (a test suite for non-cryptographic hash functions) but I have no idea whatsoever how to go about using either.

Anyone have any idea how any of these tools is used?
Otherwise, does anyone know any other tool which I can use and how it is used?

Thanks in advance for your help.

Edit: My code is written in C under Linux.

The performance can be configuration specific, so beware that any outcome is specific to a machine. Take care that you test on the right configuration(s).

The performance may also be specific to a certain input size. So test for specific amounts of data while keeping in mind that most hash methods operate on blocks (it doesn't make much sense to test 1 byte input and then 2 byte input, one block will be hashed regardless).

You don't need a lot more than a timer to measure such performance. First do x rounds of hashing just to make sure you are not left with startup flukes (hash code not loaded in cache of CPU yet). Note that this is specifically required when running on a VM. So for C / Linux it may not be that relevant - you can choose a smaller x.

Now let it run n rounds, divide by n.  Choose a large number for n. That's about it.

If you want to reuse existing code then you can simply reuse the openssl speed commands. Just look up what happens in the code for openssl speed sha256 and implement another one next to it or extract the code.


Integrity compromised - HASH modified As we are all aware that HASHing is user to verify integrity in cryptography. I have a query about hashing.

Suppose a man in the middle attacker manipulates the data and creates new HASH (by running algorithm on manipulated data) using the same hashing algorithm (becausehashing algorithms are universal algorithms) and send it along with the manipulated data to the receiver.when receiver runs the algorithm on manipulated data, it gets the same HASH ( HASH created by the attacker) and though integrity will be verified. But actual data has been manipulated/modified and integrity is compromised.

Is it possible? and if it is possible how can we eliminate this problem (solution for the same)?

Indeed hashing is used to ensure integrity, but not this way.

What you have in mind it seems is sending (msg, Hash(msg)). Indeed this is not secure because of the attack you describe.

The first step starts with something you say by yourself:

  hashing algorithms are universal algorithms

The name is not univesal but public, it means anyone knows it.
Instead of a hashing algorithm we will use a MAC (Wikipedia:MAC), which a hashing algorithm with a key. A well-spread MAC construction is HMAC: HMAC(msg,key1,key2) = H( key1 || H(key2||msg) ) where H is a cryptographic hash and || is concatenation.

If we prevent the adversary from knowing the key we used, he cannot re-compute the MAC after he modified the message.
So now we only need privacy on the MAC key, which is another challenge, you can solve it with a Key-Exchange protocol (typically: Diffie-Hellman), probably with authentication if you have a Man-In-The-Middle, and so on ...


After 20 years of AES, what are the retrospective changes that should have been made? I realize that this could be very opinion based, but I feel that there should be some solid information on AES at this point that could be referenced.  After 20 years, I expect that there should be a "woulda, coulda, shoulda" list somewhere.   For instance, I suspect that one could have gotten away with two fewer rounds, which would still have an acceptable security margin, but would this increase the speed of the cipher significantly.
Is there a comprehensive retrospective on AES in literature now that it has been used for 20 years?

Nobody seems to need a 192 bit version, we can do fine with just AES-128 and AES-256. Having a key that's 1.5 times the block size is a nuisance (or 0.75 times the block size if the block size is doubled).
The key schedules of AES-192 and AES-256 are vulnerable to attack; we could do with a better key schedule where even these attacks are avoided. They don't have much influence when the cipher is used for confidentiality, but we could do without those attacks regardless.
And while we're expanding the block size and fixing vulnerabilities to the key schedule anyway, we might as well make it suitable as underlying cipher for a cryptographic hash function and make it a tweakable block cipher.


What is the role of IV in Stream Cipher? Why is it needed and what is it's importance? I ran into this problem when I read the stream ciphers and did not find a satisfactory answer.

Why is an IV needed in stream ciphers, and what is the importance of using it?

Take a cipher, any cipher, and suppose the key is used for multiple messages.

Suppose that two messages happen to be identical. If the ciphertext depends only on the key and the message, then the ciphertexts for these messages will be identical. This leaks information about the messages. There are scenarios where this doesn't matter, but conversely, there are scenarios where it matters. Therefore any cipher uses a nonce in addition to the key. In ciphers that use an IV (or something related such as an initial counter value), the IV is this nonce

The nonce must have at least the property that the sender never performs two encryption operations with the same nonce. (Encrypting distinct messages with the same nonce would leak the fact that the messages are distinct.) Depending on the role that the IV plays in the cipher, there may be additional constraints.

With a stream cipher, the effects of encrypting twice with the same key and without using a nonce are rather devastating. Write $M[i]$ for the $i$th bit of the message and $C[i]$ for the $i$th bit of the ciphertext; then $C[i] = S[i] \oplus M[i]$ where $S$ is the keystream. If $S$ only depends on the key, then an adversary who obtains two ciphertexts $C_1$ and $C_2$ obtains $M_1 \oplus M_2 = S = C_1 \oplus C_2$. Guessing one bit of one message automatically reveals the bit in the same position in the other message.

The remedy is to ensure that the same keystream is never used twice. This can be done by ensuring that the key is only ever used once, or by incorporating a nonce (an IV) in the way the keystream is derived from the key.


Find Consecutive X-Coordinate algorithm The question is as follows: Is there an algorithm to calculate a $(x,y)$ pair which is consecutive to an existing $x$-Coordinate on an elliptic curve?
Background Information for the curve:
Known Values: Prime Curve ($p$), Prime Multiplier ($N$), Trace ($P-N$), Curve is Half. Multipliers $(M_1 + M_2) = N$, $y$ Coordinates + Inverse $Y$ Coordinate = $P$.
Any help is greatly appreciated.
Update: An algorithm to calculate a $(x,y)$ pair and integer multiplier which is consecutive to an existing $x$-coordinate on the curve.

Let $P = (x,y)$ be a point on the curve $E$ with the $y^2 = x^3 + ax + b$ with Weierstrass equation over the prime field $\operatorname{GF}(p)$1, i.e. it satisfies the curve equation.
The consecutive $x$-coordinate point can be found with the below algorithm.
for i from 1 to number_of_poinst_on_the_curve
    temp = x + i mod p
    if  (temp, y) satisfies the curve equation
       return (temp,y')
    else
       continue
throw no_consecutive_element

The $\bmod p$ is necessary since we don't want our $x$ has value out of the possible space.

$y'$ is one of the two possible solitons to the $y^2$, except when $y=\mathcal{O}$, the point at the infinity. The educative details of finding the square root in modular arithmetic can be found on Fgrieu's latest answer;
Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate

The algorithm will terminate since the EC has a finite number of points. The number of points can be

limited by Hasse's Theorem: $N - (q+1)| \le 2 \sqrt{q}$ over finite field with $q$ elements.
Or, exactly found by Schoof's algorithm, In the paper Counting Points on Elliptic Curves over Finite Fields, published in 1985,
Or, the improved version Schoof–Elkies–Atkin algorithm

1 This is used to simplify the algorithm. EC doesn't need to be defined over a prime finite field. In Cryptography, we use the general case of Finite Fields $\operatorname{GF}(q=p^m), m \in \mathbb{Z}, m\geq 1$. Expect the prime field, the other fields have different representation for the elements.

For $y^2 = x^3 + x^2 + x$ over $GF(131)$

E = EllipticCurve(GF(131),[0,1,0,1,0])

P=E.lift_x(0) #lift can throw an error if there is no point with the given input
              #tested before that there is a point with x=0

plotE = E.plot()

for t in srange(1,129):
    try:
        R =  E.lift_x(t)
        plotE += line([P.xy(),R.xy()],color='red')
        P = R
    except ValueError:
        pass
plotE

update
Though I don't see the direct effect on Cryptography, there are academic works on this;

Integral Points in Arithmetic Progression on $y^2=x(x^2-n^2)$, by Bremner, Silverman, and Tzanakis, 2000.


Are the Common modulus attack, Common Factor Attack, and Wiener's attack different? Is there a difference between:

Common modulus attack
Common Factor attack
Wiener's attack

or are these just a different name for the same attack?

Wiener's attack;

In Wiener's attack, an attacker may efficiently find $d$ when $d < (1/3) N^{1/4}$
Coppersmith's attack

The Wiener attack works on low $d$, but Coppersmith attack works on small $e$. In general case, the Håstad's broadcast attack uses The Coppersmith method. In the simplest form, it uses CRT when the sender sent the same messages to different parties.
Common modulus attack

In Common modulus attack, the modulus is the same but the public exponents are different.

As a result, they are different attacks with different names.

And, here a nice paper from Dan Boneh; Twenty Years of Attacks on the RSA Cryptosystem


AES PKCS5 Padding when it's not needed I'm using AES/ECB with PKCS5 Padding (From what I've read, PKCS7 Padding is actually used internally) and PBKDF2(HMAC-SHA256) to encrypt some passwords in Java. I enter a password, that goes through PBKDF2 and gets a hash, which I use as a key for encrypting. PBKDF2 is set to output a 128b key.

I've realised, that whenever I enter the wrong password, I get a "BadPaddingException" error. I thought, that the output of PBKDF2 should be long enough to not be padded(128b). And even if it is padded, shouldn't the padding be the same for all the passwords (even wrong ones)?

Why does this happen?

No, it is not the output size of the PBKDF2. The problem is when you enter an incorrect password the PBKDF2 generates an incorrect key for you with the correct key size. When you perform decryption of the ciphertext, the library will test the validity of the PKCS#7 padding on the plaintext. Since the key is incorrect you will get a garbage message with the padding part is also garbage. The library is throwing the exception of BadPaddingException. With some low probability, you will get no exception but the padding will be correct. Like with $(1/256)$ probability you will get 01 at the end and this will be valid padding although the message is garbage. This is why you need integrity, too.

You should not use the ECB mode, which is insecure, leaks pattern, and even we don't call it a mode of operation.

PKCS#7 padding is also vulnerable to padding oracle attacks on networks. Returning bad padding is not a good idea.

If you want to get rid of padding you can use CTR mode which doesn't require any padding at all. The CTR mode turns a block cipher into a stream cipher where there is no need for padding. Similarly, the CFB and OFB don't require padding/

Actually, all the above modes, ECB, CTR and including the CBC, are an archaic mode of operations of block ciphers. In modern cryptography, we use and advise authenticated encryption modes like AES-GCM and ChaCha20-Poly1305. They provide you Confidentiality, Integrity, and Authentication in a bundle. The AES-GCM internally uses CTR mode inside.

Note 1: In GCM mode never reuse the IV/nonce. The result can be catastrophic.

Note 2: A padding can be applied to the plaintext even there is no access to the encryption key, i.e. padding mechanism is independent of the encryption. Only the block size is required. And reversely, it can be removed from the plaintext.

Note 3: If the reason for the bad padding not clear, then reasons can be;

The IV is incorrect: An encoding/decoding issue or not transmitted at all?
The Key is incorrect: entered the wrong key or used an incorrect password to the KDF.
The encoding: The data sent over the network in binary instead of base64 or similar encoding. Binary data can confuse some protocols.
Data corrupted: The message is corrupted during transmission and you didn't have any mechanism to detect it.


What does the special form of the base point of secp256k1 allow? The popular ECC parameters secp256k1 are documented in SEC2 as using curve $y^2\equiv x^3+a\cdot x+b\pmod p$ with $a=0$, $b=7$, $p=2^{256}-2^{32}-\mathtt{3d1_h}$, base point $G$ with the apparently haphazard $(x,y)$ coordinates (hex)

79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

and order $n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf_h}$, cofactor $h=1$.

However, it turns out that $G$ is $G'+G'$ with $G'$ having $(x',y')$ coordinates (hex)

00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
c0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

which is easily computable as $\displaystyle\frac{n+1}2\times G$.
The 90 leading zero bits in $x'$ show beyond doubt that this is a deliberate choice. What does it allow (faster computation, attack..)?

As an aside: is it known how $x'$ was chosen? The earliest mentions of that number that I could find are in this answer (January 5, 2015) without mention of its property, and in this challenge (date unknown but it existed on June 5, 2015) where its property is meaningful.

Update: I notice that the generator of secp224k1 is also twice a $G'$ with the very same anomalously small $x'$ as above (this time with 58 leading zero bits, which is still remarkable). I found nothing similar about the generator of secp192k1 or secp160k1. I did not check other SEC curves (but  secp112r1 secp112r2 secp128r1 secp128r2 secp160r1 secp160r2 secp192r1 secp224r1 secp256r1 secp384r1 secp521r1 are reportedly verifiably random, thus nothing similar should occur).

The special form of $G$ seems to allow some perceptible speedup when computing $k\times G$ for arbitrary $k$ by some elementary methods. We can rewrite $k\times G$ as $(2k\bmod n)\times G'$, and the frequent point additions of $G'$ or ($-G'$) occurring in left-to-right binary scan of the scalar multiplier can be sped up a little (at least when using affine, projective or Jacobian coordinates), because multiplication by $x'$ occurs in the point additions, and some of the word multiplications can be skipped.

However, I do not know if the fastest methods used in practice can take advantage of the special form of $G$ (or what these methods are).

One thing we know is that it doesn't allow any special attack.

Let us assume that we knew a special point $G$ that makes computing the discrete log easy, that is, given $xG$, it's easy (or at least, easier than expected) to recover $x$.

Then, given $H$ and $xH$, here's what we could do; we know that $H = yG$ for some $y$ (as $G$ is a generator), and so we can use our special purpose discrete log problem to recover $y$.  Similarly, we have that $xH = zG$ for some $z$, again, we can recover $z$.  So, we have $x(yG) = zG$, or $x = y{-1}z$; that immediately gives us the value $x$.

Hence, if they knew a 'weak point' $G$, that would imply that the entire curve is weak.  Since we don't believe that, we can assume that their special value $G$ is no weaker than any other point (as long as $G$ generators the entire group, which is true in this case)


Why did Histiaeus tattoo his slave's head? The story is often told that Histiaeus tattooed a secret message on his slave's head, waited for his hair to grow back, then sent him off to Miletus. Why would he have done this?

The story is usually cited as an early historical example of steganography. But a message in someone's memory is less obvious than a message on one's skull. A message in someone's memory doesn't seem more resistant to torture (a strong-willed slave might not disclose the message, while a strong-willed torturer would almost certainly discover the tattoo). It also doesn't seem likely that the message could be kept secret from the messenger (since the messenger could just ask a friend to read it off his skull).

In short, is there some information-theoretic advantage to this anecdotal method?

Exact motives will remain unknown, since we only have Herodotus's word for the whole story, and he doesn't say. However, we can imagine a plausible reason: the whole ordeal provides some level of authentication.

Indeed, Histiaeus's slave could hardly have made himself the tattoo, and certainly not without Histiaeus noticing. Since hair growing is slow (and cannot be accelerated, at least not in Ancient Greek times, where hair grafting was not known), the presence of the message as a tattoo shows at least a purposeful dedication in time to the process. In modern terminology, it is a "proof of work". A contrario, a purely verbal message could be made up on the spot by the slave himself. Aristagoras could believe such an oral transmission to be merely the invention of a disgruntled slave.

Alternatively, this could be Herodotus having absorbed too much Samos wine. He tries to be careful, but since most of what he writes is hearsay, he at times swallows wonderfully extravagant stories, such as some about giant ants that can devour adult camels (one hypothesis is that he confused "giant ants" with marmots, but these peaceful rodents don't attack camels either!).


Can a random permutation be restored / decrypted? Say you have a 1,000,000 random bytes file and you split it into 1000 x (1000 bytes) pieces.

You then pick two random pieces and swap them writing down the position of the pieces (eg. swapped piece 34 with piece 457).

You repeat the process 1000 times at least.

Is it possible for somebody else to recover the original file without any other information but the scrambled file ?

What if multiple files encrypted like this (using the same permutation) are intercepted, how difficult is it then to decrypt them ?

This is basically just a single transposition cipher. The key to the transposition cipher would be a list of the source and destination locations, or just a list of final destinations of the blocks. It's not a very good one because it may well be that you do not swap certain blocks or that you swap something back and forth a few times.

It is not possible for somebody to recover the original file with any kind of certainty. This is not because of the cipher but because a file filled with randoms has no distinguishable information; even if the attacker would guess the key correctly, there is no way for the attacker to verify the result.

It would be easy to guess a few of the blocks right though: just return the ciphertext. The blocks are not shuffled that well, so chances are some of them never changed position; this chance for each block is higher than 1/1000 making the cipher insecure.

For multiple files just containing random information the chances of each file is the same as for a single file. If they were somehow interrelated then the contents would not be random. QED.

(Of course if you'd guess the location of one block right for the first file you'd guess them right for all of them when using the same permutation, but again, no way to verify this.)


Is it possible to compress random sequence with high entropy I have an algorithm that generates pseudo random sequence with length of 100k and high entropy. I would like to check the quality of randomness. So, I used a popular software to compress the generated file and it could manage to compress the original file into a file with just one-third of original file.
I have come across to some random test suites out there. But, I have no idea why a random sequence with high capacity can be compressed like this.

My question is whether compressing the generated file is a proper test?
Does the algorithm fail because of the generated file can be compressed?

Any comment is appreciated.

Random data can not be compressed. Good pseudo random data can not be compressed(with generic algorithm).
As Paul commented if you use an inefficient encoding such as hexadecimal or Decimal ASCII characters you are using a full 8 bit character to represent less information. Hexadecimal is compressible to 50% and decimal to $\log_2(10)/8$ which is approx 41%.
If your data is in binary or compresses significantly more than the inherit encoding used.  This is a significant flaw in your random number generator.
A compression test with a Lempel-Ziv based compression algorithm is a good important but not sufficient test. It essentially tests for repeating sequences of arbitrary length. So it can find all sorts of biases in your algorithm.

However for cryptographic security, the chances your homegrown algorithm is secure are slim even it passes all generic statistical tests with flying color.


Does iterative hashing of mouse/keyboard input improve its properties as an entropy source? In the questions, Are mouse movement coordinates useful as a seed for a RNG? and Is this a good entropy collector and whitening technique? the posters each talk about collecting mouse and keyboard input as a source of entropy. The replies make the good point about this being dangerous and requiring a large sample to ensure sufficient entropy for cryptographic purposes.

I am wondering if the quality of these inputs as entropy sources would be improved given the following scheme and, if so, by how much?

Imagine a system where X is some input from the user (e.g. mouse coordinate pair or key code combined with current timestamp) and H is some latest-generation hashing function and e is our current entropy pool state after each iteration. After the first input is collected we have:

e = H(X1)

This has low entropy. We collect another sample from the user and this time combine with the previous entropy and and hash it:

e = H( X2 + e )

or:

e = H( X2 + H(X1) )

Then we keep doing the same thing for each new value collected, combining it with the previous entropy and hashing them together:

e = H( Xn + e )

or:

e = H( Xn + H(Xn-1 + H(Xn-2 + H(Xn-3 + ...))) )

Does hashing iteratively like this in any way change the rate of improvement of the quality of the entropy produced, or is it about the same as collecting all of the samples and hashing them once like this:

e = H( X1 + X2 + X3 ... Xn )

Update

This answer to What happens to entropy after hashing? also has a good analysis that I think applies here:

  If we have a Hash function SHA which doesn't have any collisions, then it has no effect on entropy; that is, H(X) = H(SHA(X));

The biggest problem with capturing mouse & keyboard input is that the number of likely things a user does within a small timeframe is limited.

Imagine that you hash 3 alphanumeric characters of userinput H(X1 + X2 + X3) (assuming + means concatenation and H is a cryptographic hashing function). The number of possibilities from 000 to ZZZ would be about 62^3. Now if instead you would use H(X3 + H(X2 + H(X1))) the number of possibilities would still be 62^3. You could even use something like pbkdf2 with a ridiculous number of iterations without changing the number of possible outputs.


What are the typical input lengths for KDFs? I am looking for typical input lengths for key derivation functions like the HKDF. I know the parameters of HKDF, but can not find any information about typical input sizes to HKDF or any of the other KDFs. What are the typical input lengths for KDFs? If possible, can you also point me to (a) relevant reference paper(s)?

As indicated, KDF's themselves can have any input size. But you can of course take a look at protocols where they are used.

First of all, HKDF is a Key Based KDF. So if it is used with a secret key (the "Input Key Material") you'd expect it to have enough security on its own. So that would be key sizes of 128 to 256 bit (or, more likely, just 128 or 256 bit).

KBKDF's are frequently used to create session keys after key agreement, for instance HKDF in TLS 1.3 (draft). In that case the entropy is first extracted from the given master secret. In that case the input of the KDF is simply the output of the key agreement protocol. Usually that's DH or ECDH.

For DH the output size is the same as the size of the prime (e.g. 1,024, 2,048, 3,072 or 4,096 bits). Note that some older algorithms may not include leftmost bytes if the calculated secret is one byte or more smaller than the modulus. In TLS 1.3 the size of the secret will be identical to the modulus size (I know, because I hinted that feature to the mailing list, to make it symmetric with ECDH, and probably leaks less information through side channels).

For ECDH the size is usually the size of the $x$ coordinate, which is encoded as the same length as the key size. Look up often used domain parameters to get an idea of what is possible there.

Of  course, the size of the Info field can be about anything. But usually it is a relatively short string, so you could just use 16 bytes or so to be on the safe side.

HKDF also may have a salt but that's a bit harder to guess, as I haven't seem it used yet. Salts normally are 64 or 128 bits, although a 256 bit salt is not unheard of.


AES vs AES-CMAC for session key derivation Assume two parties have exchanged a secret 128-bit Master Key, MK.
When the two parties want to communicate, one of them generates a random 128-bit value, R, which is then sent in plaintext to the other party. Then, a KDF is used to generate a 128-bit Session Key, SK.

SK = KDF(MK, R)

SK is then used to encrypt communication between the parties. Let's say an authenticated encryption algorithm as AES-CCM is used with SK as input.

The question is: is there any difference between choosing a simple AES primitive and the more complex AES-CMAC as KDF?

The question is: is there any difference between choosing a simple AES primitive and the more complex AES-CMAC as KDF?

If you use AES as "KDF" in this way, it is equivalent to sending an AES-ECB encrypted key that the recipient decrypts. It's just that you have swapped the direction of encryption and decryption for AES. (AES-ECB is secure with random one-block messages.)

Using CMAC is slower if you take into account the key derivation, but not much different otherwise.

Note that neither version of the protocol has any protection against replay attacks. An attacker can send an R value that has already been used and make the other party reuse a key. Depending on what that session key is actually used for, that can be really bad. (E.g. CTR mode with constant starting nonce.)

A proper protocol would likely let both parties affect the session key. Using e.g. ephemeral Diffie–Hellman with the master key for authentication would be one way to accomplish that while also getting forward secrecy.


AES encrypting multiple files So if I want to encrypt all the files in a folder with AES (same password) I take each file and generate the key schedule using PBKDF2. As the PBKDF2 algorithm takes in a salt then this salt should change (and thus the keyschedule) for each new file being encrypted. Now if I want to decrypt then I load the plaintext salt and generate the different key schedule for each ciphertext file.

Is this correct? If so the problem I'm seeing is that the recommended number of iterations to make the encryption more secure (0.5 seconds e.g.) will considerably slow down the encryption process as each file requires a lengthy key derivation procedure. Is this just a necessary part of a secure encryption process?

Thanks!

You are correct that using a different salt for each file will slow down encryption and decryption, in proportion to the number of files. But it is not useful to do so. An adversary is not helped if she knows that the salt is common to several files hashed with the same password (under the assumption that she can recognize a correct password with fair probability from one ciphertext, and cost dominated by PBKDF2). Both with common and different salt per file, the hard work for the attacker is finding the password; the cost of recomputing PBKDF2 for other files when salt is different will be comparably negligible.
Thus an option if to have the enciphering program generate the salt at random common to every files, and appropriate IV for each file (e.g. 48-bit file number, and 80-bit zeros; this is enough for $2^{48}$ files of $2^{84}$ bytes each, encrypted using AES-CTR); compute only one key using PBKDF2; and store salt and IV as header of each enciphered file. The deciphering program can cache the key in RAM for reuse when deciphering files with identical salt (it should not assume all files have identical salt, in case files separately enciphered are merged into the same directory).
When using other block-cipher operating modes such as CBC, CFB or OFB for enciphering multiple huge files, you may approach the limit of reasonable usage of one key. For this reason, or just for added peace of mind, you might want to have one key per file. This can be done while still amortizing the derivation of key from password over multiple files, by generating a common "slow" master key from password and master salt (e.g. random) for each encryption session, and a "fast" derived key from master key and secondary salt (e.g. file index) for each file, with both salts in the encrypted file's header. The "fast" derivation could be with PBKDF2 and a minimal iteration count c=1, or just one HMAC.
Also: you might want to consider scrypt instead of PBKDF2 (at least for the master key), for it provides better security for a given time overhead, as summarized in this table from the scrypt paper (2009):

Update (2020): state of the art has evolved. Bitcoin mining has shown that dedicated ASICs performing SHA-256 at high rate (220 TH/s) and efficiency (15 pJ/H) can become commercially available for few thousand US dollars. This makes it untenable to rely on PBKDF2-HMAC run on standard hardware for stretching of user-chosen passwords in high-security applications. Scrypt still stands strong, however the new best practice for password hashing is the winner of the password hashing competition, Argon2.


What is the 'Version Incompatibility" Problem in TLS 1.1/1.2 and 1.0? It's unclear to me if there are multiple problems, or a single one, (and just what that problem is) with servers incorrectly negotiating down from a client offering 1.1 or 1.2 to something they support like SSL 3 or TLS 1.0.
Eric Lawrence has said that some version outright chokes on TLS 1.1 and 1.2.  Adam Langley points it out again:

Due to a different, common bug in SSL 3.0 implementations (nearly 12 years after SSL 3.0 was obsoleted by TLS 1.0), browsers still have to perform SSL 3.0 downgrades to support buggy servers. So even with a TLS 1.1 capable browser and server, an attacker can trigger a downgrade to SSL 3.0 and bypass the protections of TLS 1.1.

And there are significant notes in the TLS 1.2 RFC also.

Note: some server implementations are known to implement version
negotiation incorrectly.  For example, there are buggy TLS 1.0
servers that simply close the connection when the client offers a
version newer than TLS 1.0.  Also, it is known that some servers will
refuse the connection if any TLS extensions are included in
ClientHello.  Interoperability with such buggy servers is a complex
topic beyond the scope of this document, and may require multiple
connection attempts by the client.

And finally, Eric Rescorla who's somewhat 'up' on TLS adds:

First let's dispose of the TLS 1.1 angle. As has been apparent from the beginning, the ultimate fix is to upgrade everyone to TLS 1.1. Unfortunately, the upgrade cycle is really long, especially as many of the popular stacks don't have TLS 1.1 support at all. To make matters worse, due to a number of unfortunate implementation decisions which I'll hopefully get time to write about later, it's likely to be possible for an attacker to force two TLS 1.1 implementations to speak TLS 1.0, making them vulnerable. So, upgrading to TLS 1.1 is basically a non-starter.

Are all these notes about the same problem?  Is that problem as straightforward as a server choking on a 1.1 or 1.2 offering ( { 3, 2} or { 3, 3} ), or is there more to it?  Is there any documentation or notes about just what servers choke on TLS 1.1?

The problem is not as simple as just the version number, though according to Eric Rescorla, there are some of those. In my experience, most problematic implementations have a problem with ClientHello extensions, which were formally defined after TLS 1.0 was a standard. As such, some servers are hardcoded to expect ClientHello and no more data, which means they will choke on any TLS extensions being sent to them.

Since SSLv3 didn't have the notion of extensions, none of the implementations that I'm aware of send any extensions in their ClientHello. This causes usage of SSLv3 to succeed even against servers that fail on receiving TLS extensions. As such, because of browsers' desire to connect to any server, they try to connect with TLS and extensions and if that fails, they will fallback and try with SSLv3.

For browsers that support TLS 1.1/1.2, it is even more fallback logic, as it maybe that the server didn't accept 1.1, but accepts 1.0 just fine, so you have multiple cascading fallbacks.

So to sum it up - version number and TLS extensions handling are the two most common problems and yes, the above statements are all referring to these types of problems and the browser behavior.


Can N, q be shared for multiple users when using SRP-6A Is it considered bad practice to use the same N and q parameters for all users in an SRP-6A based authentication system?

I know that q MUST be a Sophie Germain prime and N a safe prime, but can they be generated ahead of time and be somewhat fixed / hardcoded in the client and server? Or should I generate a fresh pair for each new user registration?

I imagine, it's better to have a different one for each account, but if it's not affecting the security of the system in any way...

You can pre-compute and hardcode N and g into your client and server. There's no harm in doing this. I do not believe that using per-user N will provide any additional security.

It is common practice to define SRP parameters for a particular application or (larger) protocol, see e.g. RFC 5054.


Better understanding what big O is referring to I thought I understood big-O notation relatively well, but now I'm not sure. In particular, I've seen several posts like this discussing how the discrete logarithm problem is (probably) hard since our best algorithms are exponential in terms of number of bits.

If I understand correctly, to find an $x$ given an integer $y$, generator $g$ and prime $p$ s.t
$$g^x \equiv y\ \mod{p}$$
would require at most $O(p)$ trials. But if $p$ is $k$ bits then the run time is actually $O(2^k)$.

I'm struggling to understand why we decided to express the runtime in number of bits. For example, sorting can be done in $O(n\log n)$ time where $n$ is the number of elements in an array-like structure. Well $n$ also has $k$ bits, so that means the runtime is $O(k*2^k)$; sorting is exponential? I'm clearly missing something, so any help would be appreciated.

We write it in terms of the number of bits because it accurately models the reality of how computers work.
Computers don't natively support addition of arbitrarily sized numbers in 1 time step. Instead, they break such operations into addition of constantly-sized numbers (say bits for simplicity), and then use these as a basis for some algorithm to add larger numbers. Essentially, to measure the time complexity of some algorithm, we need to state what operations "cost" 1 time step, and any choice we make should be informed by how computers are built in practice.

You're also slightly misunderstanding the complexity of sorting. Things like quicksort state that you can sort an $n$-element array using $O(n\log n)$ comparisons. But how much does each comparison cost? If all elements in the array are assumed to be constant-sized, this is $O(1)$, so the overall time complexity is $O(n\log n)$.

But what if the size of elements in the array grows with the overall array? If you have an array of $n$ elements, each of which is an $n$-bit number, quicksort still works in $O(n\log n)$ comparisons. How much does each comparison cost though? In terms of bit operations, it should be $O(n)$ time. So one has that the complexity of sorting this array is:
$$
O(n\log n) \text{ comparisons} \times O(n) \frac{\text{time}}{\text{comparison}} = O(n^2\log n)\text{ time}
$$
So sorting this array is actually $O(n^2\log n)$ time.

In your example, you're right that it takes $O(p)$ trials. If $p$ is $2^k$ bits, why should this be "exponential"?
Consider the very basic part of your algorithm, which is setting some counter $i = 0$, and incrementing it all the way up to $p$. How many bit operations does this simple part of the algorithm take? While this sounds like a dumb question, actually designing an algorithm and evaluating its cost (in terms of bit operations) may be useful for your understanding.


AES CBC MAC Generation I am working with Atmel's/MicroChip's ATAES132A 32K AES Serial EEPROM chip for hardware encryption and decryption. This is my first venture into cryptography. I've been reading through the datasheet and have a question on how to generate the MAC for decryption. I've asked this question on the Atmel forum, but I didn't get any responses. I figured this is more of a cryptography question rather than a technical one.

Per the datasheet:

  I.3 MAC Generation

  The following example shows how the integrity MAC is calculated for an
  authentication operation requiring up to 14 bytes of authenticate-only
  data. This operation involves three passes through the AES crypto
  engine; all three using the same key. If there are more than 14 bytes
  of authenticate-only data, then another pass through the AES crypto
  engine is required. There are two passes through the AES crypto engine
  in CBC mode to create the cleartext MAC. The inputs to the crypto
  engine for those blocks are labeled B0 and B1, and the outputs are B’0
  and B’1, respectively.

  • B0 is composed of the following 128 bits:

  – 1 byte flag, a fixed value of b0111 1001. – 12 byte Nonce, as
  generated by the Nonce command. – 1 byte MacCount, one for first MAC
  generation. – 2 byte length field, always 0x00 00 for authentication
  only.

  • B1 is the XOR of B’0 with the following 128 bits: – 2 byte length
  field, size of authenticate-only data. – 14 byte data to be
  authenticated only.

  • B’1 is the cleartext MAC, which must be encrypted before being sent
  to the system.

  There is one additional pass through the AES crypto engine in CTR mode
  to create the key block that is used to encrypt the MAC. The input to
  the crypto engine for this block is labeled A0 and the output is A’0.
  A’0 is the MAC sent to the system as the output parameter of the Auth
  command.

  • A0 is composed of the following 128 bits: – 1 byte flag – fixed
  value of b0000 0001. – 12 byte Nonce – as generated by ATAES132A
  during Nonce command. – 1 byte MacCount – one for first MAC
  generation. – 2 byte counter field – always 0x00 00 for A0.

  • A’0 is XOR’d with the cleartext MAC (B’1) and sent to the system.

  Input integrity MACs for Auth, Counter, KeyCreate, and Lock are also
  calculated using this procedure. If the input MAC does not match A’0,
  then the command returns an AUTH error.

So my question is, in suede-code, are my steps correct?

B'0 = B0 XOR with the secret Key

B'1 = B1 XOR with B'0

A'0 = B'1 XOR with A0

What you are reading is a description of how CCM is performed within the "Cryptographic Element Device. The block names are from the CCM description by NIST.

A more clear description is the following:

N = Nonce(12)

# this implements CBC(key, IV, 79 | NONCE | 01 | 00 00 | LL LL | DATA)
# taking only the last block (AES / CBC-MAC)

IV = 00000000000000000000000000000000 # presumed, it's logical

B0 = 79 | NONCE | 01 | 00 00
B'0 = CBC(key, IV, B0)

B1 = XOR(B'0, LL LL | DATA)
B'1 = CBC(key, IV, B1)

N2 = Nonce(12) # it may be that N2 should be identical to N1, look into spec

# this implements CTR(key, A0, B'1)

A0 = 01 | N | 01 | 0000 # this is the initial counter for CTR mode
A'0 = CTR(key, A0, 00000000000000000000000000000000)
R = XOR(A'0, B'1)

This is a block by block description on how CCM mode is performed internally when up to 14 bytes of data are just MAC'ed - not encrypted. You could use it to mimic the implementation if you're just given AES-CBC and AES-CTR or indeed just AES. On a normal computer you'd just use an existing library that contains CCM.


FIPS 140 compliance for encrypted files Does FIPS 140-2 require specific key sizes, or does it have specific requirements for the data?
In other words, if I encrypt a file, how I can check whether it is FIPS-compliant or not? Does only the key need to be checked, or does the encrypted file have to be checked too? If yes, is it possible to elaborate on how to check an encrypted file for FIPS compliance?

FIPS 140-2 only certifies cryptographic modules, not entire systems. So, to tell if your system is 140-2 compliant, it must be using a 140-2 certified module. NIST publishes a list of all FIPS 140-2 certified cryptographic modules.

It is important to remember, though, that 140-2 certification does not certify that the module is used in a secure manner. From the FIPS 140-2 document:

  Similarly, the use of a validated cryptographic module in a computer or telecommunications system is not sufficient to ensure the security of the overall system.

Looking over the document, I don't see anything on specific key sizes. It discusses key management, including key storage. So you'd have to make sure keys are stored properly. I don't see anything in the document about requirements on the data which is to be encrypted. That makes sense though as you would want your module to be data agnostic.

So, there is no way to look at an encrypted file and tell if it is FIPS 140-2 compliant. You would have to look at the module that did the encrypting.


An iso file containing its MD5 hash? My colleague remembers and old backup tool, packaged as a standard bootable ISO image. He thinks the file was about ~250 MB, containing a MD5SUM.txt, which included the MD5 Checksum of the entire ISO image.

I am no crypto/hash expert, but according to my understanding of checksum methods, he is wrong. He should have downloaded checksum separately, or else, the vendor should have had a hard time guessing the right MD5 such that adding it's hex form in a text file beside all other contents of the image makes the exact same checksum, right? I can't think of any shortcut to calculate such checksum.

(Unfortunately we don't have the ISO right now, so that I can win the bet and get a free beer.)

With a secure hash function what you are describing is entirely impossible. MD5 is considered totally broken and yet I am unaware of a method of accomplishing this feat even with known multi collision attacks.
SEJPM gave a relevant link to what can be done with multi collision attacks on MD5 but placing the resulting hash in plain text is harder and I don't believe has been done. Definitely didn't happen as a matter of fact implementation detail. Should someone do this even with MD5 it would be a significant cryptography feat.
In order to demonstrate that with a turing complete format it is easy to have a file produce its own hash with no need for cryptanalysis: I created a proof of concept and wrote a Scala program which prints its own SHA-256 hash. This technique can work with any hash function, and any turing complete language, including postscript
https://gist.githubusercontent.com/meirmaor/3d858568d5da35f568fe96687ed7dbaf/raw/c26d3bdd298567e76e92c6c37ab96e353a3d8cdf/QuineHash.scala

scalac QuineHash.scala
scala QuineHash
6bae798a607d1f74630734435cc93d17c9b92a6705f7663c6fd47f7439c69669
sha256sum QuineHash.scala
6bae798a607d1f74630734435cc93d17c9b92a6705f7663c6fd47f7439c69669 QuineHash.scala


Hash Function representation in identity-based encryption Some describe as $H:F_{q}\times G_{2}\rightarrow \{0,1\}^{n}$.Some describe as $H:\{0,1\}^{*}\times\{0,1\}^{*}\rightarrow F_{q}$.
What is the meaning of product function? what kind of operation does it refer to?

The authors describe it that way because the functions operate on different inputs and produce different outputs. In your first example $H$ outputs an $n$ bit string, while in the second $H$ outputs an element of the field $F_q$. Clearly, one can represent an element of a field $F_q$ by a bitstring of size $n$ for some $n$ (using some suitable encoding). However, I guess that the authors who use the second definition use the output of $H$ for some computation in $F_q$, while the authors that use the first one use it to compute an XOR with some other $n$ bit string or the like.

The product just means that the function takes as input a pair $(a,b)$ where $a$ comes from the first domain ($F_q$ or $\{0,1\}^*$) and $b$ comes from the second domain ($G_2$ or $\{0,1\}^*$). The details how $H$ exactly looks like is not specified by this notation. For instance, if $H$ has two inputs $(a,b)$ one way of implementing it is as $H'(a\|b)$ with $a$ and $b$ being some encodings to bitstrings and $\|$ denotes concatenation and $H'$ takes inputs from $\{0,1\}^*$.


How to break AES CBC with PKCS#5 padding? If I have a string encoded with AES CBC with PKCS#5 padding, how can one possibly decrypt/crack it? What are the approaches that one can take to break its security?

You may take the following approaches:

You can check if the key generation or storage has any weaknesses;
You can check if padding oracle attacks apply;
You can check if (part of) the ciphertext has been generated previously (using the same IV).

Neither of these methods work when AES CBC has been correctly applied. AES does provide adequate confidentiality, even for many ciphertext&plaintext pairs.


Why is Symmetric encryption classed as Private Key? I am going for my ethical hacking exam soon and I still can't get my head around why symmetric key encryption is classed as "Private/Secret Key encryption" when symmetric encryption uses the same key and asymmetric encryption (Public Key) uses a public and PRIVATE key.

I just remember by thinking "As symmetric encryption begins with an S that's Secret key and secret key doesn't have a public and secret (private) key because it's weird."

I'm hoping someone will help me think of this in a less confusing way.

Here's an easy way (in my opinion) of keeping it straight: Think of encryption as creating a "secure channel."

Symmetric:

Secret Key K <-----------------------> Secret Key K

Each side has the same shared key. Since they have a shared secret key, messages flow freely between them - they can both encrypt messages to send to one another. The picture is symmetric... the two sides match.

Asymmetric:

Public Key   -----------------------> Private Key

One side has the private key, the other the public key. The public key holder can encrypt messages such that only the private key holder can read them, but the private key holder cannot use his private key to send secure messages to the public key holder (unless they negotiate/exchange some other key(s)). The picture is not symmetric anymore.


Do any other factors aside from length of input affect the runtime of the SHA-256 hashing algorithm? To my understanding, the only factor that (even if ever so slightly on most implementations) affects the run time of SHA-256 is the amount of padded chunks the extension & compression function have to run over. The only way to alter the amount of padded chunks is to change the length of the input. Therefore, the only factor influencing the runtime of SHA-256 is the length of payload to be hashed. Is this correct, or are there further aspects that influence the runtime of SHA-256?
Edit: To clarify, this question is talking about the abstract runtime / the runtime on one particular implementation

Your question is not very clear, but I assume you're asking whether the runtime of a SHA-256 invocation depends on anything about the input other than its length. In other words, if an adversary knows how long it takes to calculate SHA-256(M1) and SHA-256(M2), does this leak any information about M1 and M2 other than their length?
The answer, with plausible implementations, is no. SHA-256 (like all common hash algorithms: MD5, SHA-1, SHA2, SHA3, Blake, etc.) only uses the message for bitwise operations (and, or, xor, shifts by a constant size, negation) and additions. All of these operations use a constant time on all common (and most imaginable) hardware, and compilers are very unlikely to turn them into non-constant-time operations. There are no multiplications or divisions (which on many CPU are not constant-time), no shifts by a message-dependent amount, no conditions or table lookups based on a value that's derived from the message content (other than the message's size).
So unlike, say, AES (where the most natural implementation involves a table lookup based on values derived from the key), you generally don't have to worry about timing-related side channels in SHA-256 or other common hash algorithms.
On the other hand, leaks from power consumption can be a worry.


How can I get the binary form of AES's MDS matrix in MixColumns tranformation? I need to write a procedure for calculating the MixColumns's operation result in the following form:

$M*X^T,$

where $M$ is a 128x128 binary matrix, $X$ is a 128-bit vector (the state).

My question is how to build such $M$ matrix.

Help much appreciated. Thanks!

EDIT:

As far as I understand, the MixColumns transformation can be represented as

$\begin{pmatrix}MDS & 0 & 0 & 0\\0 & MDS & 0 & 0\\0 & 0 & MDS & 0\\0 & 0 & 0 & MDS\end{pmatrix} * \begin{pmatrix}s_0\\s_1\\\vdots\\s_{15}\end{pmatrix},$

where $MDS = \begin{pmatrix}02 & 03 & 01 & 01\\01 & 02 & 03 & 01\\01 & 01 & 02 & 03\\03 & 01 & 01 & 02\end{pmatrix} - $ matrix with elements over $GF(2^8)$ and

$s_0, \dots, s_{15} \in \overline{0, 255} - $ elements of the state.

I need a hint how to convert each element of the $MDS$ matrix into a 8x8 binary matrix over $GF(2)$. For example, I guess that the element $01$ would be converted into the 8x8 identity matrix.

Is that correct?

Concretely, given an element $x \in$ GF($2^8$), to multiply it by 2, we simply do a left shift and xor with 0b100011011 if the result of the shift gets above 0b11111111 (255). To multiply by 3, we multiply by 2 and add the input.

Those two multiplications can be described with 8x8 binary matrices. The easiest way to find the matrices is to think how those operations would be implemented in hardware. Well, there is an efficient way to do it. Given a 8 bit inputs, $y_0 y_1 y_2 y_3 y_4 y_5 y_6 y_7$, first store $y_0$, do a left shift, and xor the result with (0b00011011 $\cdot \ y_0$). And the multiplication by 3 is simply a multiplication by two xored with the input.

Those multiplications by 2 and 3 are described by the following binary matrices :

$M_{mul2}$:

\begin{bmatrix}
     0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
     0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
     0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
     1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
     1 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
     0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
     1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
     1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{bmatrix}

$M_{mul3}$ (which is $M_{mul2} \oplus M_{identity}$):

\begin{bmatrix}
     1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
     0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
     0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
     1 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\
     1 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\
     0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\
     1 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\
     1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{bmatrix}

Actually, from $M_{mul2}$ and $M_{identity}$ you can construct all the matrices of for the multiplication in the AES field by combining them with a double and add algorithm.

From this, you can construct the 32x32 binary matrice of the the MixColumns operation (here 1 is $M_{indentity}$) :

\begin{bmatrix}
        M_{mul2} & M_{mul3} & 1 & 1\\
        1 & M_{mul2} & M_{mul3} & 1\\
        1 & 1 & M_{mul2} & M_{mul3}\\
        M_{mul3} & 1 & 1 & M_{mul2}\\
\end{bmatrix}

and you can deduce the rest (as well as how to do the same for decryption).


Is the 'nonce' in bitcoin really a nonce? Is the 'nonce' in bitcoin really a nonce? Reading definitions of nonce and salt it seems the number is used as a salt but the same value can occur in multiple blocks; there's no requirement or indeed method to enforce that the value is not used again.

I will assume you mean the nonce that bitcoin miners iterate. Depending on e.g. wallet software other salts or nonces may be involved.

That nonce is only used once, because every miner1 will be hashing a different transaction block (hash) – one which sends the reward for solving the proof of work to their address. A miner could reuse a nonce but they would be recomputing something they have already done so it would be a waste of time.

Since the nonce is only 32 bits, miners will eventually reuse values, but that will be with a new timestamp, or even a new previous-block hash (when someone else solved a block).

1 Slightly more complex for mining pools, of course.


Time-release Protocol Implementation “How to Build Time-Lock Encryption” by Jager

“Time-release Protocol from Bitcoin and Witness Encryption for SAT” by Liu, Garcia, and Ryan

I looked through the references, googled, searched GitHub but couldn't find an implementation of either of them in any programming language.

Are these theoretical with no implementation yet?

I would greatly appreciate a link to an implementation if one exists.

Tibor Jager (author to the first paper linked in question):

  "There is no implementation yet. Given that there are no really efficient Witness Encryption schemes yet, the construction so far is rather theoretical."


How to perfrom modular division while numerator is lesser than the denominator? I'm implementing point addition and point doubling of elliptic curve cryptography. The formula that I'm using for slope is

Point addition: $S = \frac{(P_y-Q_y)}{(P_x-Q_x)}$ where $P$ and $Q$ are the two points.

Point doubling: $S = \frac{(3P_x)^2+a}{2P_y}$ where $P$ and $Q$ are the two points and $a$ is one of the parameters of the curve.

The divisions involved here are modular divisions. I use extended euclidean algorithm.

My question is what if the numerator is smaller than the denominator? In that case can i still use this algorithm? Or is there any other algorithm to perform such modular divisions? Or there is no possibility at all for the numerator to end up smaller than denominator in elliptic curves??

I'll assume we are working modulo $p$, which most likely is some large prime. When evaluating $S={P_y-Q_y\over P_x-Q_x}$, one really is finding a representative integer of the residue class of the equivalence relation modulo $p$; that is, the result is defined within addition or subtraction of $p$ any number of times.

The same holds for numerator $P_y-Q_y$ and denominator $P_x-Q_x$: addition or subtraction of $p$ to these quantities, any number of times, is immaterial. That makes comparing numerator and denominator moot; and even ambiguously defined: when working modulo 7, we can't tell which is the smaller of 2 or 6; that's because we could as well be comparing 2 to -1, or 9 to 6.

As long as $P_x-Q_x$ is not a multiple of $p$, one evaluates $S={P_y-Q_y\over P_x-Q_x}$ without considering a comparison of numerator and denominator. The result is, depending on definition

any integer $S$ such that $S\cdot(P_x-Q_x)-(P_y-Q_y)$ is a multiple of $p$;
or perhaps the single non-negative integer $S$ less than $p$ with this property; this would be obtained by "reducing modulo $p$" some $S$ with this property; that is:

if $S$ is negative, change $S$ to $S+p\cdot\lfloor{p-1-S\over p}\rfloor$, where $\lfloor{p-1-S\over p}\rfloor$ is the quotient of the Euclidian division of the positive integer $p-1-S$ by the positive integer $p$, and $\cdot$ stands for ordinary multiplication;
otherwise, change $S$ to $S-p\cdot\lfloor{S\over p}\rfloor$ (or equivalently, change $S$ to the remainder of the Euclidian division of $S$ by $p$).

If we stick to the convention that $S$ and intermediary results are kept as non-negative integers less than $p$ (or, equivalently, as kept reduced modulo $p$), the evaluation of $S={P_y-Q_y\over P_x-Q_x}$ could go:

evaluate the denominator $U=P_x-Q_x$, reducing the result modulo $p$;
abort if that's zero;
compute the modular inverse $I$ of $U$ modulo $p$ using the extended Euclidian algorithm, reducing the result modulo $p$ ($I$ is well defined if $p$ is a prime);
evaluate the numerator $V=P_y-Q_y$, reducing the result modulo $p$;
evaluate $S=I\cdot V$, and reduce the result modulo $p$.

The same applies for $S$ as used in point doubling, except for what numerator and denominator are (the formula to be used will depend on the curve).


Hill cipher is not perfectly secure I am on cryptography course and there is a homework question to show that Hill cipher doesn't have perfect security.

So assume we have an cryptosystem $(P,C,K)$, where $P = C = \mathbb Z_{26}^N$ and $K$ is the set of invertible $N \times N$-matrices modulo $26$. Now we also have some probability distribution on $P$ and also some distribution on $K$.

A cryptosystem has perfect secrecy if $p(x) = p(x|y), \forall x\in P \wedge y\in C.$

Now, one option I considered is that according to Bayes rule, if system has perfect secrecy,  the cardinalities of these sets $P,C,K$ must fulfill $|K| \ge |C| \ge |P|$. But this seems to be the case, so I can't use that.

The $p(x)$ is whatever the original distribution says it is. Now $p(x|y)$ cannot be the same as $p(x)$ for this homework to make sense. $$p(x|y) = \frac{p(y|x) p(x)}{p(y)}$$ $p(y) = \sum p(k) p(d_k(y))$, so probability that key used was $k \in K$ times the probability of decrypted message being $d_k(y)$. I would think $p(d_k(y))$ is same as $p(x)$, as $x$ is $y$ encrypted and as we sum over all the keys, for any key there is some $y \in C$ which maps back to a given $x \in P$, this is same as $p(x).$

Thus $p(x|y) = p(y|x)$. I would think that as we know $x$, and every key maps every plaintext to different cryptotext, they would have same distribution, so $p(x|y) = p(y|x) = p(x)$.

So we have perfect secrecy.

Now, what am I not getting here? I am sure I do something wrong, but help would be welcome.

One possibility for what you might be missing: normally the same key (the same matrix) is re-used to encrypt many messages.  So now try counting the total entropy in $M$ length-$N$ messages, and the entropy in a $N\times N$ matrix, and compare what happens when $M$ gets large....

Another possibility you might be missing is the consequences of the fact that you are working modulo $26$.  I think you need to calculate out $p(y|x)$ carefully.  You might start by considering what happens when $N=1$.  Can you calculate the value of $p(y|x)$ and $p(x|y)$, for all possible values of $x,y$?  Maybe write a program to do it, or do the case analysis so you don't have to consider $26\times 26$ cases exhaustively.  I think you'll find that is enough to let you figure out what's going on.

I don't want to say more, because this is an exercise, and should solve your own exercise.


Brute force RSA cracking Suppose one had a complete list of primes up to $2^{n+1}-1$. Then wouldn't one be able to crack an $n$-bit RSA public key in time $O(\pi(2^{n+1}-1))$, making RSA insecure?

Thanks,

René

Actually, one would be able to crack a $2n$-bit RSA public key in $O(\pi(2^{n+1})-1)$ time.  However, $O(\pi(2^{n+1})-1) = O(2^n / n)$, and we already know how to factor $2n$-bit numbers faster than that.

Hence, even if someone could come up with such a list (and find some place to store it), it wouldn't actually affect the security of RSA.


XOR a set of random numbers Basic question about XOR and entropy - given a set $S$ of pseudo-random numbers in the range $[0,b]$, will XORing them produce a new pseudo-random number in $[0,b]$ or will the operation decrease the entropy? In the case that some numbers in $S$ not being random. e.g. selected according to some deterministic process - how does this effect the randomness of the XORed result? Would also appreciate links to any relevant math/crypto lit about these kind of problems.

Thanks so much!

Assuming that $b = 2^k-1$ for some positive integer $k$, XORing two (or more) numbers in the range $[0,b]$ will indeed yield a number in the same range.

If the numbers are random, uniformly distributed over the range and independent, then the result will also be random and uniformly distributed.  In fact, we can even prove a stronger result saying that if even one of the numbers is random and uniformly distributed over the whole range, and independent of the others, then the result will be random and uniformly distributed.

(There are a variety of ways to prove this.  Probably the most straightforward way is to observe that the map $x \mapsto x \oplus c$ is a bijection over the range $[0,b]$ regardless of the value of the constant $c$.  Thus, if $x$ is uniformly distributed over the range, then so is $x \oplus c$; and since this is true for any constant $c$, it's also true even if $c$ itself is a random variable, as long as it doesn't depend on $x$.  For the specific case of XOR, you can also first show the same result for each bit of the number, i.e. reduce the problem only to the case $b=1$, and then generalize to multiple bits.)

Effectively the same result also holds, basically by definition, even if the numbers are only pseudorandom, i.e. computationally indistinguishable from true random numbers.  That's because, if the result of XORing them was not indistinguishable from a truly random number, then this would provide an efficient way to distinguish the original numbers from truly random ones, thus showing that they weren't really pseudorandom in the first place.

Note, however, the the assumption of independence (or indistinguishability from independent random numbers) is important.  Otherwise, there are trivial counterexamples, like picking a truly random number $x$ uniformly from $[0,b]$, and then letting $y = x$.  Thus, both $x$ and $y$ on their own are truly random and uniformly distributed, but $x \oplus y = x \oplus x = 0$.


Are block ciphers used in public key crypto? I was reading about block ciphers and most articles state they are being used in symmetric key cryptography. Are they also being used in public key cryptography? if not, what alternative pkc use?

Thanks,

Yes, block ciphers are used in public key cryptography, though typically as auxiliary building blocks rather than as the heart of the public key scheme by themselves.

One example is in digital signatures: many use a hash such as SHA-1, to digest the message being signed into a short cryptogram, and/or as part of a Mask Generating Function (loosely speaking: used as a randomizer before applying a public-key primitive). And in turn many hashes, including SHA-1, use a compression function built from a block cipher. Sometime, the function of a Mask Generating Functions is directly performed by a block cipher, as in this proposal.

Also, as rightly pointed in this other answer, block ciphers are often used in combination with public key cryptography, to form a hybrid cryptosystem.


Is the complexity of Pollard rho for discrete logartihm really the modulus? so I'm reading everywhere that the Pollard Rho for Dlog's complexity of $g^a \pmod{n}$ is $\mathcal O(\sqrt{n})$.

Shouldn't it be $\mathcal{O}(\sqrt{q})$ with $q$ the order of $g$?

The complexity of Pollard-Rho is indeed $O(\sqrt{\text{ord}(g)})$, but even though $n$ refers to the modulus, their statement might be correct depending of the context. If the modulus considered in your situation is a "classical" modulus in crypto (e.g. $n = (2q+1)^k$ for a prime $q$ and a small $k$, etc), as the modulus will be in general chosen so that ord$(g)$ is big, $n = t\cdot \text{ord}(g)$ for a small constant $t$ so $O(\sqrt{\text{ord}(g)}) = O(\sqrt{n})$.


Elliptic curve commitments mod p As far as I understand secp256k1 is defined over the group p with

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

I don't really understand how out of bounds values are handled in particular with homomorphism of the commitments.
Assume I commit to the value 5 which would be $G + G + G + G + G$ and then commit to the value p + 5 which would be $(p+5)G$ will those be the same commitment?

Based on this assumption I have implemented the following javascript code (using elliptic library ):

it('Test mult property of commitments', () => {
    const T1 = ec.g.mul(secp256k1.p + 5n);
    const T2 = ec.g.mul(Maths.mod(secp256k1.p + 5n, secp256k1.p));
    const T3 = ec.g.mul(5n);
    assert(T1.eq(T2));
    assert(T2.eq(T3));
});

In this example, T2 and T3 are the same, but T1 is different, so it seems like my assumption is incorrect, does this mean I can commit to values greater than p?

You are confusing the prime $p$ over which the curve is defined (the coordinate of the points are all defined mod $p$) with the prime $q$ which is the curve cardinality and is also prime.

We have $qG = G + \ldots + G = \infty$ the neutral element (like $0$ with the addition with numbers).

Taking your example, you have: $T_1 = (p+5)G$ and $T_2 = 5G$. Of course it is not the same since $p + 5 \not\equiv 5 \bmod q$.

You will find the value $q$ somewhere in the parameters of the curve and if you replace $p$ with $q$, the equality will hold.


What does a stream cipher provide that cannot be obtained with AES CTR mode operation? I can precompute the key stream for the CTR mode operation and the encryption at that point is similar to a stream cipher. So why are there stream ciphers still used and proposed after RC4? Recently the ChaCha20 as part of the ChaCha20-Poly1305 AE cipher.

Are there advantages to using a stream cipher especially?

AES-CTR is a stream cipher, of a particular kind where the keystream is obtained by encryption of a counter. So the question reduces to: what are drawbacks of AES-CTR compared to other stream ciphers?

The main ones compared to ChaCha20 are:

Without hardware support, AES can fail to cache-timing attacks.
Without hardware support, AES is slower.
Without hardware support, the fastest implementations of AES use significant memory.
Pre-computed AES subkeys (which speeds-up things) require not quite negligible memory (160 bytes for AES-128 in addition to the base key, compared to none for ChaCha20); this is an issue when many sessions each with a different key are active simultaneously.
There's a theoretical distinguisher for AES after about $2^{68}$ bytes (but it requires as much memory, and wouldn't be much a practical issue anyway).

Compared to other modern stream ciphers like Trivium, AES requires more hardware at comparable speed. On the other hand it allows random access to the keystream, and parallelization (as ChaCha20 does), when many other stream ciphers (including Trivium and RC4) do not.

Bare AES-CTR does not provide authenticated encryption (AES-GCM does, and uses AES-CTR for encryption), so comparison to ChaCha20-Poly1305 is unfair.


TLS Handshake with DH I try to understand the TLS Handshake with DH. I googled the concepts and I think I understood the basics. But there are somethings I'm still struggling with. I also read the following two posts Why does the SSL/TLS handshake have a client random? and Why does the SSL/TLS handshake have a client and server random?

I don't understand how client random, server random, pre-master-secret and master-secret relates to the DH parameters.

Is the Client-Public-DH-Value A (A = g^a mod p) the same as the pre-master-secret? and the master-secret the same as the DH secret/Session Key s (s = A^a mod p)?

There are a lot of images e.gl Wikipedia but I don't see the relation between these steps.

Meta: although both are reasonable, I'd actually consider this Q a better fit for security than crypto. Be that as it may ....

In https://security.stackexchange.com/questions/81597/in-psk-tls-how-is-the-key-used-for-encryption-derived (suggested by RoraZ) the steps from premaster to master to working are applicable, but the premaster step (even for DH_PSK) differs from normal DH keyexchanges, plus TLS1.0 is out of date.
What is the purpose of pre master secret in SSL/TLS?  and What is the purpose of four different secrets shared by client and server in SSL/TLS? similarly focus on the later steps although the former does mention (EC)DH.

So to lay it out:

the publickey and privatekey values for the two peers are just keys. TLS specs use the notation where X is the privatekey and Y = G^X mod P the publickey, plus an identifier of the party owning the key: dh_Ys is the server publickey and dh_Yc is the client publickey.

Although TLS isn't careful about it, there is actually a distinction between on the one hand parameters P,G which must be shared between TLS peers and can be shared on a larger scale (such as an organization or community), and on the other hand key(pair)s X,Y which should be unique to one peer and not shared and for ephemeral DH (the preferred kind) should further be unique to one session and not stored.

In TLS to date (although draft 1.3 proposes to change this) the server selects the group (parameters) and for ephemeral generates the server keypair in that group; the client generates its keypair in the same group for ephemeral.
the DH agreement value is used as the premaster secret; see RFC5246 sec 8.1.2. With the TLS notation this is Ys^Xc (computed at client) or Yc^Xs (computed at server).
This step is (very) different for other keyexchange methods.
the premaster secret plus the two nonces (client_random and server_random) are used to derive the master secret per 8.1 and then the master secret and the nonces are used to derive the working keys per 6.3. In case of renegotiation, the second derivation (from master secret to working keys) is repeated using the new nonces from the second handshake, see F.1.4. These steps are the same for all keyexchange methods.

Both key-derivation steps use what is now called the 'pseudo-random function' PRF. Unlike the other steps, this varies between protocol versions: SSL3 used nested MD5 and SHA1 (and didn't label it PRF), TLS1.0 and 1.1 use doubled both HMAC-MD5 and HMAC-SHA1, and TLS1.2 uses doubled HMAC of a hash that can be selected for each ciphersuite but so far is always SHA-256 or SHA-384.


Rely on NSA Suite B Cryptography? NSA's Suite B Cryptography suggests some cryptographic algorithms for encryption, digital signatures, message digests and key agreements. The selected algorithms and their key size are suggested by the security level needed.

But is there any reason to think that the NSA suggests those algorithms because they know backdoors or something like that? Is it really secure to rely on those algorithms? Or should one assume that the NSA just suggests these algorithms in order to make people use algorithms with backdoors?

It mainly depends on how the algorithm was selected. If it was selected by a public competition like for AES, then it is likely to be secure. If it was forced in by the NSA such as Dual-EC random number generator, then you may have some doubts.

Other questions you may want to ask yourself are:

Is this an "original" algorithm or was the problem that it relies on already known?
Is there a formal proof (often not possible), checked by independent persons or organizations?

In the end you will always have a grey area here. Some things like AES are probably secure, Dual-EC certainly is not. But for the (NIST/SECP) ECC parameters it's a lot harder to say.

Saying that Suite B is safe or not is a blanket statement that oversimplifies what is happening in the field of cryptography.

As it is highly visible, it will be highly scrutinized by the cryptographic community. But as Dual-EC proves nothing is to be fully trusted.


Hashing items of different Bytes but same length would enable a timing attack? I am following this paper which comes highly recommended as a secure Registration/Login system over TLS which uses client side computation for the Password Processing Function (PPF). What my main question is about is how the design prevents account enumeration (an attacker finding out if usernames are valid on the server).

To summarise the final solution in Section 4:

  On the server, each valid user has a different $v$ which is generated by a CSPRNG and is at least 128-bits of random data.

  For login, if the user exists, it computes the salt as:

  hash( username || domain-name || $v$ ).

  If the user does not exist, it computes the salt as:

  hash( username || domain-name || $σ$ )

  Where σ is a server secret value of 128 bits of random data.

The point of this is that a salt is always returned, regardless of whether the username is valid or not. This prevents an attacker from making many queries to figure out everyone's usernames and it also prevents timing attacks as the computation is always done server side and it takes the same time.

However in the system we have, we do not have usernames so we are replacing the username here with the user's email address instead. Also we have another requirement where our support team needs to change user's email addresses on their behalf if they lose access to them. The design in the paper would appear not to work in that case because the salt is then based on the email address, and hence the PPF computation is also tied to it. So if the user changes their email then their previous salt is no longer valid and they need to re-do the PPF computation which is a nuisance. Also it's much worse if the support team changed the user's email because then they would definitely be locked out of their account.

So my thoughts to resolve this for valid users is to have the salt calculated as:

  Salt = hash( domain-name || padding || $v$ )

And for invalid users the salt would be calculated as:

  Salt = hash( email || domain-name || padding || $σ$ )

So for this to work, emails would be limited to maximum 80 characters. Then the length of email + domain-name + padding would always be 100 Bytes. And for valid users the domain name + padding would also always be 100 Bytes. The padding character could just be a 'P' and everything is always padded to 100 Bytes.

So my main questions:

Is it possible for an attacker to do a timing attack on the network
request with the server to check if an email is valid/invalid?
Will there be a give-away (detectable) timing difference between hashing        the email || domain-name || padding, vs hashing just domain-name || padding if they're both 100 Bytes in length? I.e. does hashing different characters make the computation take longer or go faster.

It is a bad idea to use any user information of host information to generate a salt. Salt should be random.

Use password stretching. Depending on tools available to you considers bcrypt, scrypt, argon2. Then no matter if user exists or not the password stretching can take (depending configuration) substantial time. It will be safe against timing attacks.

Since the stretched password hash will not depend on user ID,  your users will be able to change their IDs (whatever you use as ID - email, user name or anything else) as often as they want. When user ID changes, it will not bve necessary to recalculate the password hash.


Decryption of Huffman code I know that Huffman is not a encryption method, but I have a bit-stream that I know it's Huffman coded. However, the tree/table that maps the codes to real characters is not available. Surprisingly, during my searches I couldn't find helpful sources or even academic papers on this problem. It seems this problem has no literature.

Can anyone introduce a helpful resource on this? Is there any algorithm that I can devise or adapt to solve this problem?

P.S. Actually I know that the bit-stream is a JPEG file which is Huffman coded.

Thank you in advance

There is some discussion here and a paper from 1996 here. I had looked at this cursorily years ago, it is not so easy. And a google search brings up some other papers. The discussion may be the way to start.


Shamir Secret Sharing - How to reconstruction secret? Example I try implement Shamir Secret Sharing.

In this video: https://www.youtube.com/watch?v=j7Ngtl1cCpY is example.

But for another three share holders is can't reconstruction secrete.

For example:
a)
a(1) = 15
a(2) = 6
a(4) = 10

b)
a(1) = 15
a(2) = 6
a(5) = 6

But for another three share holders is can't reconstruction secrete.

Sure they can.

In the field $GF(17)$, we have:

$$\frac{43}{3} = \frac{9}{3} = 3$$

because $43 = 9 \pmod {17}$, and $3$ is the value that, when multiplied by 3, gives us 9 modulo 17.

And, we have:

$$\frac{23}{2} = \frac{6}{2} = 3$$

beause $23 = 6 \pmod {17}$, and $3$ is the value that, when multipled by 2, gives us 9 modulo 17.

Remember that, when we work in a finite field, division isn't exactly the same as it is when we're working with in $\mathbb{R}$; for example $\frac{1}{2}$ is not 0.5 (which is meaningless in $GF(17)$, but instead it is 9.


Best practises to generate IV for AES-CTR in this scenario I'm building a cloud storage application that will store files on my servers.

I want these files to be encrypted with AES in CTR mode and the key will be always the same.

I'm wondering what would be the best way to derive an IV.

The encryption will happen on many servers so I can't use progressive values (e.g. incrementing first 8 bytes for every different encrypted file) since I can't keep count across servers.

Numbers of stored files can reach tens of billions.

What's the best practise in this scenario to derive the IV (or maybe a Key + IV)?

Should I use only one key that never changes?
Should I derive a new key for every encrypted file (from the master key)?

Edit:

If key mustn't be the same, would it be secure to do the following:

A new key (256-bit) is randomly-generated for every file.
This key is encrypted with the masterkey in ECB mode (since it's highly entropy data, do we need CBC?)
The file key is appended at the beginning of the file.

You may want to rethink your whole setup. Like mentioned in the comments, there is a lot more to securely storing files than throwing encryption on them. In particular, you need to be concerned with authentication (CTR without authentication is malleable). I would also look into client side encryption in anything that puts user data in the cloud.

Still, there are probably some situations where just using CTR to encrypt a bunch of files is the right thing to do, so I will answer your questions below.

  What's the best practise in this scenario to derive the IV (or maybe a Key + IV)?

Usually in CTR mode you have a nonce concatenated with a counter. If you want to support arbitrary file sizes, you probably want the counter to be 64 bits. However, that does not leave enough space for a nonce, since 64-bit nonces will collide after a few billion files. If e.g. your API restricts you to this setup, you would be better off with per-file keys.

If you can use random 128-bit nonces, with e.g. the lower half incremented as the counter, that should be fine. You would avoid the need for key setup, which would be an advantage especially with small files.

  If key mustn't be the same, would it be secure to do the following:

  A new key (256-bit) is randomly-generated for every file.
  This key is encrypted with the masterkey in ECB mode (since it's highly entropy data, do we need CBC?)
  The file key is appended at the beginning of the file.

ECB would be acceptable for encrypting random data, but concerns about authentication remain. Alternatively you could use key derivation. That way you can use e.g. a random 128-bit salt for each file even with 256-bit keys.


What are known metrics for TRNG? I was wondering what the known metrics are for studying the randomness of TRNG (besides NIST tests).  For example, for PUFs, there are known metrics such as uniformity, uniqueness, BER, etc.

The one metric that generically matters in cryptography for a physical entropy source is the min-entropy: the exponent of the most probable outcome, in bits.  This depends on the physics of the entropy source.  As long as it exceeds 256, you can feed a sample through a typical preimage-resistant hash function such as SHAKE256, a conditioner, and you will have what is effectively a uniform random string fit for use as cryptographic key material.

(Sometimes the physical device is called a TRNG; sometimes the composition of the physical device and the conditioner like SHAKE256 is called a TRNG.)

If your device can't produce a sample with that much min-entropy at once, but it can produce a sequence of IID samples, then you can concatenate them.  The result may be much longer than 256 bits—even if it is very far from uniform in whatever is your favorite measure of statistical distance, what matters for cryptography is only that its min-entropy be at least 256 bits.

The NIST tests hypothesize various families of probabilistic models for the entropy source, fit parameters based on a sample, and then print the entropy of the models with the fitted parameters.  These models are very simple-minded and were designed without knowledge of your device, so they are at best a way to spot-check particularly obvious predictable distributions—so obvious an engineer thought of them without even knowing what your device is.  (More details on how ‘entropy tests’ work.)

Generic measures computed on samples from your device, designed without reference to any model of the physics of your device, have very little value in studying the security of the system.  The min-entropy you advertise must be computed from a specific probabilistic model of the physics of the system to give any meaningful confidence in it.


Safely erasing encrypted data My secret message is encrypted in a byte buffer with AES-128 in CBC mode.  The first 16 bytes are the IV and the message follows contiguously.  If I want to securely delete this message is it enough to delete (overwrite with random) the IV, the first block, or both?

In an answer to similar post (crypto shredding by erasing the IV instead of the key) it was suggested that if the key and one plain-text block is known then the entire message can be recovered.  So it may be better to overwrite the entire secret message...

However, if the secret key has been forgotten decryption is impossible and so the length of the encrypted message is unknown.  There may be circumstances where overwriting the entire is undesirable.

If I want to securely delete this message is it enough to delete (overwrite with random) the IV, the first block, or both?

No, it's not enough.  Not even if you erase both.

(Not unless your message is at most two blocks long, that is.)

Erasing the IV makes the first block of the message undecryptable.  Erasing the IV and the first $n$ blocks of ciphertext makes the first $n+1$ blocks undecryptable.  In either case, the rest of the message can still be decrypted normally.

For modes other than CBC, the details may vary, but for all commonly used modes the conclusion remains the same: to ensure that no part of the message can be decrypted even if the key is compromised, you will need to erase the entire ciphertext (or the IV and almost all of the ciphertext, at least).


Router for Quantum key distribution As far as I know QKD needs a quantum channel to send the photons. If anyone measures the photons they are useless.

It sounds as if Alice needs a fiber optic cable all the way to Bob - or at least line-of-sight to Bob. So no wifi through walls.

One of the things that really makes the internet work is packet switching done in routers. If every sender would need a cable to every receiver then the internet would never have been such a success.

How would you build routers that can route photons from Alice to Bob for QKD? Will they work, if Bob is using his tablet under a blanket on a cruise in the middle of the ocean?

Background

I have attended a few talks on quantum computing breaking currently used asymmetric ciphers. Usually the presenter then mentions that quantum encryption will solve this. The presenter mentions this as if we can use the existing infrastructure, which I feel certain is wrong. So I am wondering if I am missing some obvious way to be able roll out QKD to every computer.

How would you build routers that can route photons from Alice to Bob for QKD?

I know of three possible ways of addressing this problem (only one of which is currently practical).

Have the routers have QKD systems on each link; and so Alice does QKD with router 1, which does QKD with router 2, which does QKD with Bob.  The obvious issue with this is that router 1 and router 2 also get the keys.  This obviously doesn't work on the Internet (which you don't trust every service provider between you and Bob), it may be plausible in, say, a data center (where the same organization runs the entire network, and so does have some trust on their own infrastructure.
Have routers that don't actually measure the quantumsignal.  I have heard of two proposed subvariants of this one:

One based on mirrors that can be moved ultraquickly.  In this case, when Alice wants to talk with Bob, she informs the routers, which would quickly set their internal mirrors so that photons from Alice get reflected at Router 1 to Router 2, which reflects them to Bob.  Now, this doesn't do anything about the QKD length limitations, and I actually haven't heard this option mentioned in the last several years, and so people may have given up on it.
One based on Quantum Amplification.  In this case, Router 1 would take photons from Alice 1, and in a way that doesn't break the Quantum State, forward them to Bob in some amplified/quantum error corrected state.  We currently can't do this; this appears to be quite difficult (perhaps not much easier than building a full Quantum Computer), and I'm not exactly sure how they intend to get around the 'no cloning theorem' (which states that you cannot duplicate a quantum state, hence it's unclear how they expect to amplify one).

QKD satellite; here, there is a satelite that sends pairs of entangled photons to the two end points (and the end points use their entangled photons to agree on keying material).  There's just been given a proof-of-concept, and there are several obvious issues ("does everyone have a satelite receiver?  How do you talk between end-points that are beyond satelite range?  How do you deal with satelites that can communicate only intermittently (currently: at night, when the weather is clear, and when the LEO satellite is over the horizon)?"


Autocorrelation in Autokey I know that Vigenère can broken using auto-correlation (as explained at cryptool-online.org). Now my question is: Why does this also work with autokey (tested it using crypttool)?

To prove that I have already put work into this, I have read Simon Singh: “The Code Book”, F.L.Bauer: “Decrypted Secrets”. Though the latter book said in does not work the same way in autokey than it does in Vigenère. Why is there still a maximum of coincidences when the text is shifted by the key length?

In a Vigenère cipher, the $i$-th ciphertext letter $c_i$ is calculated as $p_i + k_{i \bmod \ell}$, where $p_i$ is the $i$-th plaintext letter, $k_i$ is the $i$-th key letter, and $\ell$ is the length of the key.  Thus, the difference between two ciphertext letters at positions $i$ and $j$ is $$c_i - c_j = p_i - p_j + c_{i \bmod \ell} - c_{j \bmod \ell}.$$

Normally, for this difference to be zero, the difference between the key letters would have to just happen to cancel out the difference between the plaintext letters.  When $i \equiv j \pmod \ell$, however, the last two terms cancel out, leaving just $p_i - p_j$, which, since the plaintext typically has an uneven letter frequency distribution, is more likely to be zero than one would otherwise expect.

Now, consider the autokey cipher, where (beyond the first $\ell$ letters) $c_i = p_i + p_{i-\ell}$.  Now the difference between two ciphertext letters is given by $$c_i - c_j = p_i - p_j + p_{i-\ell} - p_{j-\ell}.$$  This time, when $i - j = \ell$, it's the middle terms that cancel, leaving just $p_i - p_{j-\ell}$ $=$ $p_i - p_{i-2\ell}$.

Again, it's a lot more likely for a single pair of plaintext letters to be identical than it is for the differences of two pairs of letters to cancel out just by chance.  Exactly how much more likely depends on details of the plaintext frequency distribution, but the qualitative behavior is quite robust and shows up for most naturally occurring letter frequencies.

Ps. Note that the conditions for this cancellation to occur are different.  For the Vigenère cipher, cancellation occurs whenever $i - j$ is a multiple of the key length $\ell$, producing a characteristic comb-shaped autocorrelation plot.  For an autokey cipher, however, cancellation only occurs when $i - j$ exactly equals the key length, resulting in just a single peak.


Format Preserving Encryption - Generating coupon codes If I use cycle FPE with AES to generate 20 digit coupon codes, what is the probability that an attacker could generate a valid coupon?

That depends on what coupon codes are accepted rather than the details of the FPE. FPE is a pseudo-random permutation that depends on the key. If the attacker inserts any encrypted coupon code in the specified domain (in this case 20 digits) then it will with certainty result in a 20 digit coupon code after decryption.

So what chance is there that the coupon code is accepted? Well, it is exactly the same as a normal coupon code. If the coupon allows any 20 digit code then the likelihood of it being accepted is of course precisely one. Commonly though a coupon code also contains a method of verification. Then it depends on the verification method what chance there is of a random coupon code to be accepted.

Say there is one decimal check digit and a calculation that results in a uniform distribution given random input of the other digits. In that case the chances of generating a probability of generating a valid coupon code is of course one in ten.