Any famous approach for analyzing the randomness of data? I'm writing a function that will allow me to analyze the randomness of some input data and return some stats about the probability of this data to be random.
Obviously it should be based on two things:

How often each byte value is found / not found (randomness / distribution)

And how much data we have (certainty)

So among the outputs of my function will be two values:

"randomness" (0 - 100) which tells how random the bytes look (regardless of how much data we have)
"randomlike" (0.001 - 99.999) which tells the general likelihood of the whole data to be random (a combination of randomness and length).

Is there a famous approach for this or I have to rethink the whole logic from scratch? This is probably something widely used in cryptography because this is how we can test keys: the decrypted data is highly random until the key is right.
I'm not looking for any particular language, just the math/logic approach.
One thing that puzzles me is: What does 50% randomness correspond to? Is it a subjective thing (like an art...) or math has some scientific ways to define what "50% randomness" means.

In terms of a measure of randomness, the usually accepted measure is Shannon entropy. In this sense for example 2 random bits which are 00 1/2 of the time, 01 1/4 of the time, 10 1/8 of the time and 11 1/8 of the time would represent 1.75 bits of random (from $\frac12+2\times\frac14+3\times\frac18+3\times\frac18$).
In your example then, if we sample $N$ bytes and byte $i$ comes up $b_i$ times we compute $p_i=b_i/N$ and then sum
$$-\sum_ip_i\log_{256}p_i$$
and that is the "proportion" of a byte's worth of random that you are getting with each byte. By taking $N$ larger you get a tighter confidence interval for your estimate and I'll defer to better statisticians on the details.
BUT note that if you generate bytes just by listing them 0, 1, 2,..., 255, 0, 1, 2... then this will score (very close to) 1 even though most people would say this is not very random at all.
For a measure of how likely a sample is to be producing uniform random bytes, you should perform a Pearson $\chi^2$ test on the data.
For more general randomness tests also consider Marsaglia's Diehard tests.

I [sic] have to rethink the whole logic from scratch?

Not entirely, but the complexities make this harder that it appears.

"randomness" (0 - 100) which tells how random the bytes look (regardless of how much data we have)

This is still somewhat of an open question for the general case of auto-correlated samples. The simple Shannon $\log$ formula is no use whatsoever as it is impossible to adequately populate set $p_i$ of $-\sum p_i \log p_i$. Similarly $\chi^2$ values fail for exactly the same reason; defining the domain of the probability mass function for the sample distribution. Simple Shannon only works for uncorrelated data, like perhaps testing keys from good sources.
And for the same reason again, the more common measure of cryptographic entropy, min.entropy $(H_{\infty})$ is also very problematic in the general case. An example of how hard and varied general entropy  measurement can be seen on this page. Many of those techniques are various forms of compression.
Anyway you'd have to shift your metrics away from 0 - 100, towards 0 - 1 bits/bit or 0 - 8 bits/byte of Shannon entropy. The measurement effectiveness is inversely related to the degree of auto-correlation (loosely).

"randomlike" (0.001 - 99.999) which tells the general likelihood of the whole data to be random (a combination of randomness and length).

This need to be changed to a $p$ value of the certainty that whatever randomness test suite (NIST STS, TestU01, diehard, dieharder, ent, AIS-31, pkzip, FIPS 140 etc.) you run is accurate. It ranges 0 - 1, and 'famously' we tend to exclude values within 1% - 5% of the tails (suite dependant). And you do get $p = 0.0005$ as false negatives because imagine an output domain like (it's a TRNG random walk):-

If you test the blue box, the data is appears highly biased and it fails. If you test the green box, as the data is uniform it passes. And yet it's a  good TRNG overall. Randomness is pesky like that.

What does 50% randomness correspond to?

However you manage to measure the Shannon entropy, 50% $\equiv$ 0.5 bits/bit or 4 bits/byte. So there would be a half cup of stuff that varies unpredictably, and a half cup that remains constant/so auto-correlated that it might as well be constant.

The family of paq8 compressors are pretty efficient, and running your data through one will give you a good estimate of the amount of randomness but not a  certainty for the reasons above.


Can all affine cyphers be expressed with this formula There are $26!$ permutations of the English alphabet.
In Modern Cryptography textbook, William Easttom states that

the basic formula for any affine cipher is $ax + b \equiv \pmod{26}$.

I'm wondering whether this formula can express every possible permutation. It does not seem obvious that for every permutation $\sigma$ there exist $a$ and $b$ capable of expressing it. If this statement is true, what approach can be used to find $a$ and $b$?

$a\cdot x +b $ means affine  not permutation. And $a\cdot x +b \bmod 26$ is modular affine transformation.
$a\cdot x +b \bmod 26$ can have at most $26\cdot 26$  affine transformations some of which have no inverse and therefore without an inverse an affine transformation is not suitable for encryption where it is already not close to the modern encryption methods.
To have an inverse one must have $\gcd(a,26)=1$. This means $a$ cannot be divisible by 2 or 13. To find the actual number we can use Euler's Totient Function that counts the positive integers up to a given integer $n$ that are relatively prime to $n$. Then $$\phi(26) = (13-1)\cdot (2-1) = 13$$ So there are actually $26\cdot 12 =312$ possible affine transformations.
In any case, we have $26! = 403291461126605635584000000$ permutations and $312$ affine transformations, therefore the affine transformation cannot cover all possible permutations. The reverse is correct; the permutations can represent the invertible affine transformations.

Yes, that formula can express every possible permutation - as long as a can become very large.
GCD(a,26) must equal 1 to get a valid permutation.  When a is less that 26, that is constraining as even some primes, like 13, do not qualify.  That is because, for prime p, there is a risk that p x n=26, for some n other than 1, i.e. they share a factor.
When a is prime and greater than 26, life is much easier.  All primes are suitable, (because by definition a prime cannot share a factor with a smaller number)
However at some point there will be a repeat of the permutation as Pigeonhole principle there are 'only' 26! available.  But 26! is very big.


Block Cipher vs Stream Cipher in Web Application I'm doing research about "Cryptographic attack methods in Web Application" so I have some questions to ask you guys:

Block Cipher vs Stream Cipher, which is more common used in Web Application?
How and Where is Stream Cipher implemented in Web Application?

Hope to get your response soon :)

Very few cryptosystems actually use a block cipher directly (i.e. in "ECB mode") to encrypt data — and those that do usually only do so because whoever designed them didn't really understand how a block cipher should be used.

Rather, the main use of block ciphers in cryptography is as versatile building blocks for other cryptographic components, such as stream ciphers, message authentication codes, hash functions, KDFs etc.  In particular, the usual way to use a block cipher to encrypt free-form data is by using a mode of operation such as CBC, CFB, OFB or CTR (or an authenticated mode like EAX, GCM, OCB or SIV) which actually uses the block cipher to construct a kind of stream cipher.

Thus, the actual distinction, insofar as there is one, is not between block ciphers and stream ciphers as such, but between stream ciphers based on block ciphers (like AES-CTR or AES-CBC) and "primitive" stream ciphers not based on block ciphers (of which the most common is probably RC4).

I don't really have any reliable statistics on how much those are respectively used in web applications, but my gut feeling would be that the majority (say, 95%) of (symmetric) encryption schemes used in such systems are probably based on block ciphers (mostly AES, some 3DES, occasionally rarer types like Serpent, Blowfish or old single DES).  Their main competitor is RC4, with a small but non-negligible share (say, 5%), while all other "primitive" stream ciphers (like the eSTREAM ciphers) are probably marginal (< 1%), mostly because few crypto libraries support them.

(The share of RC4 probably goes up a bit if its use in SSL / TLS is included in the total, particularly since many websites switched to it after the BEAST attack exposed weaknesses in the TLS 1.0 implementation of AES-CBC.)

I don't think stream ciphers are implemented in Web applications ( Actually they are not approved because of weak security) However the protocols like IPsec, SSL and PGP etc do make use of various block ciphers( e.g AES ). Web application security is totally dependent upon the security at individual OSI layers.


Can I use PGP to sign a message without providing cryptographic non-repudation? The difference between a digital signature and a MAC is non-repudiation. A message with a digital signature proves that only the sender could have signed the message, whereas a message with a MAC proves that either the sender or the recipient could have signed the message.

Can an OpenPGP implementation, such as GPG, be used to sign a message without providing non-repudiation?

Please note that I am referring to non-repudiation in the cryptographic sense, not in the legal sense.

Yes, there's an indirect way to perform what's asked with PGP and variants.

Draw a an asymmetric public/private key (of a type that can sign), protected by a passphrase. Publish the passphrase-protected private key. Discard the public key (it's in the private key anyway). Use the passphrase as you would use a symmetric key: share it by trusted means between sender and receiver (perhaps together with the passphrase-protected private key). Generate, transmit and verify a detached signature (sig file) of a file to integrity-protect as you would do for a MAC of the file.

Authentication is the process of providing assurance that a data has not been tampered with, whereas non-repudiation demonstrates that the message is from a the holder of a particular private key. In general hash methods are used to provide authentication. Signing data with a private key provides non-repudiation whether you like it or not.

If you want to send a message in a way where it can be authenticated, but not linked back to yourself then hash the unencrypted message. If the recipient has pgp or something like it you can encrypt the message and its hash with the recipient's public key.


Recovering plaintext from AES-128 given round key 10 and ciphertext I'm working on an old CTF challenge where AES-128 was used on a 16 byte block. I have the round 10 key and the ciphertext. What techniques exist for obtaining the plaintext?

Since this is CTF, I'll give you some detailed hints.

Normally by using only a ciphertext, you cannot determine the plaintext, since for every key the deciphered ciphertext is a valid plaintext and some of them are perfect in English or any other language. So, some other information must be given to you for verification.
16-Byte just means one block for AES.
There is a difference in key schedules between AES-128 and AES-182,AES-256.
Your CTF is not possible with the key schedules of AES-192 and AES-256
You have given only, one round key. The different key schedule of AES -128 will enable this.
Search for AES master key Round Keys ( in this site)


HMAC-Ripemd-160 in TrueCrypt I'm wondering if it is still secure.

I know TrueCrypt closed its doors but I continue using it because the cryptoaudit didn't find any huge bugs or security issues in TrueCrypt.

But I have a bad feeling about Brute Force and Ripemd-160. I've read that it only uses 3000 Iterations. So I ask myself: How long would it take to Brute Force the password of the encrypted disk?

The use of RIPEMD-160 is not a cause for concern. It's the relatively small number of PBKDF2 iterations which is problematic. More than a decade ago, the minimum recommended number of iterations was 10,000. Nowadays, you should probably not be using less than 100,000, regardless of the hash function in use. However, even that is not ideal. If possible, you should be using a memory-hard KDF like Argon2. That limits the parallelism that an attacker can use against you with any given amount of resources.

Also, TrueCrypt used only 2000 iterations, not 3000, of RIPEMD-160 and 1000 for any other hash.

The reason for an interation count is only to make brute forcing a weak key harder. If your key would take 1 hour to crack with only 1 round of hashing, it would be pretty easy to break - but with an iteration count of 3000, the same password would take 3000 hours - ca. 125 days.

As long as your password is good enough (in the meaning of entropy) you will have no problem with "only" 3000 iterations. (Newer software should still update the iteration count to highest still acceptable amount.)


Two working decipher keys giving various, valid results for one ciphered message - is it possible? Let's assume following scenario:

There's a ciphered message. Two decipher keys (let's name them A and B) are known.

Message deciphered with key A gives valid result - normal text but with no secret information. Let it be a poem or other meaningless content.

The same message deciphered with key B gives the right output, the real secret message revealed.

Please tell me, is it possible (or well-known and existing method/algorithm), or just a work of fiction? I've read about it in some novel a long time ago and tried to figure it out on my own, but with no result. But I'm rather ignorant in terms of cryptography so I might just miss something obvious.

Thank you in advance for any help - just a simple name of ciphering method or link to Wikipedia or something will be enough. I don't even dare to ask for the full and detailed explanation.

This property can be achieved with a One-time pad.

  "In fact, it is possible to "decrypt" out of the ciphertext any message whatsoever with the same number of characters, simply by using a different key, and there is no information in the ciphertext that will allow Eve to choose among the various possible readings of the ciphertext."

This is nicely shown in this example from Wikipedia (section "Attempt at cryptanalysis").

Thank you guys very much for your help and explanations.

I've started to Google for more info about one-time pad technique and found another suitable solution called Denial Encryption. Well, two of the most interesting content is available here, at crypto.stackexchange.com.... unfortunately I didn't find them before - maybe I didn't specify the proper search query - please don't blame me :)

Here they are, in case somebody looks for similar problem in future:

Deniable Encryption (*term corrected according to comment by Gordon Davisson)

Something similar, that could be helpful too

Thank you again and have a nice day.

P.S. I'm fully satisfied with answers received, so this topic could be freely closed/archived - I don't know how to do it on my own.


One Encryption, Many Decryption Keys I would like to share access to encrypted data among many recipients. I do not know the recipients ahead of time (when encrypting the data). Once the data is encrypted, I do not have access to the plaintext (so I cannot re-encrypt).

Right now, I have a shared secret key that is distributed to recipients as they are granted access to the data (again, encrypted so I do not have access ot the shared key). Unfortunately, that means any recipient of the shared secret can leak the key, compromising the data for everybody.

I can't really prevent "bad" recipients from the leaking the key (or the plaintext, for that matter), but I would like to be able to distribute unique keys to each recipient so that if a key is leaked, I can determine who did it.

I think I want a symmetric encryption scheme where the ciphertext can be decrypted by a set of keys, rather than a single key. Each secret key is unique and it's hard to derive one secret key from another (so one recipient cannot forge another's key), but its simple for me to generate new secret keys (so I can easily add new recipients).

Does such a schema sound familiar?

This is known in the cryptographic literature as "traitor tracing".  See, e.g., the following seminal paper:

An efficient public key traitor tracing scheme.  Dan Boneh and Matt Franklin.  CRYPTO 1999.

They show a public-key encryption scheme where each  possible recipient has their own private decryption key.  If an authorized recipient discloses their decryption key, it's possible for the authority to figure out whose key it was.  Moreover, they consider a further challenge -- what if a coalition of authorized recipients pool everything they know, and come up with another decryption key that is different from each of theirs but still works, and they leak that new key? -- and they show how to deal with that challenge as well.

There is an entire line of research that proceeds forward from there.

That said, this is often the wrong kind of solution in practice, for most situations.  You are assuming/hoping that the adversary will publish their decryption key.  But what if they don't?  What if they do something else?  There are all sorts of ways the adversary could cause problems without publishing their decryption key:

For instance, the adversary can leak the decrypted data without leaking the decryption key (this is the killer problem with all of these traitor tracing schemes that has rendered them mostly irrelevant in practice).
Alternatively, the adversary could make available an API that provides "decryption as a service".
Or, the adversary might release software for decryption that embeds the key but in an obfuscated form.

Traitor tracing doesn't help with any of those adversarial strategies.  So, beware that your threat analysis might be based on too narrow a view of what an attacker can do.

More fundamentally: this approach has seen no adoption in commercial systems (as far as I am aware), because of the extreme ease of acquiring false identities.  If you're going to sell access to paid content for $20, and you accept credit cards for payment, it's far too easy for someone to get a stolen credit card number, sign up and gain access, and then publish the decryption key (or the decrypted content).  Now what are you gonna do?  Even if you can trace back to the associated credit card number and name provided during signup, that name is surely fake, and the name on the credit card account is someone else.   At that point you realistically have no way to identify the perpetrator and no recourse.  All the fancy crypto in the world won't save you.

That's why these kinds of schemes might not be as useful as they at first appear, except in some special and limited circumstances.

Assuming your data is sufficiently easy to fake a digital signature is required in order to prove it actually originated from you. Therefore I propose the following:

in addition to encrypting the data with the shared secret key, obtain its hash, e.g. sha256
whenever someone gets access to the shared key, sign the secret's hash concatenated with a unique identifier for the new recipient and send them that individualized signature

The only way the recipient can prove the secret stems from you is by verifying the signature, which requires their unique identification to be included.

Of course a leak could still try and obtain another recipient's means of verification to frame them, so you should asymmetrically encrypt the individualized signature to the recipient and instruct them to not store it decrypted.


Are one-time pads crackable in theory? I've been taught that one-time pads are the only perfect encryption since the only way to recover the message is by knowing the key.

For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message.  This approach will produce all messages that can be expressed with 100 bits.

However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101.  This observation seems to contradict the idea of an unbreakable one time pad.

We know two random bitstrings are independent of each other, as well as independent from non-random bitstrings.  So, knowing a random bitstring will not allow you to shorten the description of a second bitstring and vice versa.  Thus, if we randomly generate a bitstring BS1, then when XORed with the key BS2 it will produce a third bitstring BS3 that is not compressible.

Proof: If BS3 is compressible, then knowing BS1 would allow us to describe BS2 with a short description (i.e. BS3).  Then, either BS1 and BS2 are not both random or are not independent.  The only case where they are random, but not independent, is if one is a part of the other.

This means that if XORing BS1 with ciphertext BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

So, at least in theory, it seems that one-time pads are breakable, although this approach is not computable since we'd need to compute that a bitstring is truly random.

This argument contradicts what I've been taught, and I'm wondering if OTPs are only said to be perfect because randomness is not computable.

For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message. This approach will produce all messages that can be expressed with 100 bits.

That's not the reason why one-time-pads are considered secure. The reason is that even if you try all possible keys that you get all possible plaintext and you have no method of choosing which one is right. The size of the plaintext/ciphertext/keystream doesn't matter.

  However, not all bitstrings are random, e.g. 111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.

111111111111 is equally likely as 01101001001101 or any other value of the same size when chosen randomly.

  Proof: If BS3 is compressible, then knowing BS1 would allow us to describe BS2 with a short description (i.e. BS3). Then, either BS1 and BS2 are not both random or are not independent. The only case where they are random, but not independent, is if one is a part of the other.

Values are compressible if they are part of a set where certain values are more likely than others. This is not the case for $C = P \oplus K$ if $K$ is fully random. This is because $C$ will be fully random as well, independent of $P$ being random or not.

  This means that if XORing BS1 with cyphertex BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

This will never be the case as BS5 will not be compressible; each possible value of BS5 will be as likely as the other values of BS5 because of the reasons explained above.

There are two levels to this answer: generic and specific. The specific problem addresses the decryption of a single encrypted message, the generic the decryption of all messages produced by a particular encryption system.

The starting point is the presumption that the message actually contains data. That argues for some kind of pattern to it, commonly a language of some sort, which then offers a handle to the decryption. In fact, this is what we do anyway in reading plaintext; we interpret what is written into semantic meaning our brains can assimilate.

What single-use pads do is stop the development of first-level cracks into generic cracks of the entire system, as there should be no common ground between the pads. However, this is not entirely guaranteed, as some kind of seed is needed to generate a pseudo-random sequence.

The most important thing about encryption is not that it preserves the data content eternally, it's that it keeps it hermetic for long enough for its relevance to degrade, so that if, for instance, a military force were to plan a surprise attack, the attack would happen before the code is broken.

I'll leave it to others to discuss the maths, however the fact there is a key means that in theory any message is breakable under a brute-force attack. Sometimes double-encryption actually creates exploitable lacunae, and sometimes just plain sloppy thinking exposes the key. I personally cracked a major system through simple inspection once, working with one of the system managers, so the exploit was rapidly corrected: that was done on a kudos motivation. Then again, I have a genius IQ, was schooled by one of the founding fathers, and actually made systems manager at Dollis Hill, after the code-breakers had left.

The inverse of the problem is that the encrypted message must also be decryptable in short order: it's pointless if a time-critical message takes longer to decrypt than the period it is important for. Equally, the decryption equipment itself must also be secure in all locations, the loss of several cypher machines gave Bletchley Park huge pointers towards a generic crack of Enigma. It's a subset of the approach of the security gurus, whose ideal machine is disconnected from a power supply, encased in lead, covered in a concrete sarcophagus twenty feed thick and dropped into the crater of your nearest volcano (the Frodo solution!). It may be perfectly secure, it's also perfectly unusable. And in the trade-off lies the weakness. A single-use pad is used twice, to code and decode. Lose either and the game is in play. The Man Who Never Was was a case in point, where the code sold the gambit.


Secure communication between multiple peers on a public channel I am wondering how can I secure communications between multiple peers over a public channel, like an IRC channel.

With two peers it is easy - they exchange their encryption keys and decrypt the secret messages using their private keys, but how would this work with multiple peers without creating excessive duplication of messages?

Is there some way to encrypt a message that would be readable by multiple peers not sharing the same secret key?

Generate a symmetric key
Encrypt symmetric key using public keys of all recipients, and broadcast (or provide on request from a client)
Transmit all user messages encrypted under the symmetric key

This means you only have one copy of the message (but you do have lots of copies of the encrypted symmetric key).

Of course you need to solve the key distribution problem first, to ensure you're only encrypting the symmetric key using authenticated public keys.

CLAE is an asymmetric encryption algorithm that provides ultra security and the simplicity to share the secret keys with anyone, anywhere over the Internet.
http://www.connectinprivate.com/clae.php


Build set with PKI from reliable broadcast / random beacon I am trying to build a protocol (or find an existing one) for creating a set $S_2$ with PKI from a set of parties $S_1$ that initially does not know anything about the other parties.

We assume end-to-end communication and broadcast, all with a delay up to $\text{Delta}_\text{transmission}$. Additionally, we also use NIST random beacon (could simplify the protocol, but it doesn't solve the deadline problem below).

So every party $p \in S_1$ would run this protocol $A$ at a time $t_1$, and we would like at $t_2$ that all honest parties have the same set $S_2$ of parties with PKI.

I could imagine a solution where all parties generate a private/public key pair, and then the protocol dictates that for each round, they broadcast a signed message with their public key and current vision of $S_2$; ie $m = [pk, S_2]$.

each time they receive a valid signed message with a new public key $pk'$ and a new set $S_2'$, they do $S_2 = S_2' \cup S_2 \cup {pk'}$, and rebroadcast $[pk, S_2]$

The main problem with this scenario is termination : if we want the protocol to terminate at any deadline $t_2$ fixed in advance; there is always a way for an attacker to break consistency (all honest parties have the same set $S_2$ in the end) by sending a new valid message $m'$ just before the deadline to a party $p$, so that this party accept it, but when the honest party rebroadcasts his new set including the new key, other honest parties discard it because it arrives after the deadline $t_2$.

Any help, either directly on how to fix the deadline problem, or indirectly how to build such protocol, would be greatly appreciated :)

There might be multiple solutions, and this could be one of them.

You can use multiple rounds of Terminating Reliable Broadcast (TRB). Each party in $S_1$ sends a message with their own proposal $pk$ -- this corresponds to one round of TRB.

After $|S_1|$ rounds, you're good to go. Since all honest parties have the same set of individual proposals, they can deterministically compute the result $S_2$.

Naturally, if you assume $f<|S_1|$ nodes can fail (e.g. by crashing, arbitrary), you have to stop the protocol after $|S_1|-f$ rounds.

PS: I might have misunderstood some of the details in your the question, so please correct me if anything's amiss.


What does the term “nontrivial rotation” mean? The paper “Gimli: a cross-platform permutation” contains the following information:

  Occasionally (after rounds 24, 20, 16, etc.) Gimli adds an asymmetric constant to entry 0 of the first row. This constant has many bits set (it is essentially the golden ratio 0x9e3779b9, as used in TEA), and is not close to any of its nontrivial rotations (never fewer than 12 bits different)

What does the term “nontrivial rotation” mean? How to distinguish a “nontrivial” rotation from a “trivial” one?

A trivial rotation is one where the input to the rotation is equal to the output (hence the rotation is equal to the identity function). Rotating by a multiple of $n$ is a trivial rotation for all $n$ bit values. Note that for certain values other trivial rotations may exist. See below for the values of the (right) rotations of 0x9e3779b9 ($n = 32$) and the amount of different bits for each:

0:  0x9e3779b9 (0  bits different)
1:  0xcf1bbcdc (14 bits different)
2:  0x678dde6e (22 bits different)
3:  0x33c6ef37 (18 bits different)
4:  0x99e3779b (12 bits different)
5:  0xccf1bbcd (14 bits different)
6:  0xe678dde6 (18 bits different)
7:  0x733c6ef3 (16 bits different)
8:  0xb99e3779 (14 bits different)
9:  0xdccf1bbc (12 bits different)
10: 0x6e678dde (16 bits different)
11: 0x3733c6ef (16 bits different)
12: 0x9b99e377 (16 bits different)
13: 0xcdccf1bb (14 bits different)
14: 0xe6e678dd (12 bits different)
15: 0xf3733c6e (16 bits different)
16: 0x79b99e37 (20 bits different)
17: 0xbcdccf1b (16 bits different)
18: 0xde6e678d (12 bits different)
19: 0xef3733c6 (14 bits different)
20: 0x779b99e3 (16 bits different)
21: 0xbbcdccf1 (16 bits different)
22: 0xdde6e678 (16 bits different)
23: 0x6ef3733c (12 bits different)
24: 0x3779b99e (14 bits different)
25: 0x1bbcdccf (16 bits different)
26: 0x8dde6e67 (18 bits different)
27: 0xc6ef3733 (14 bits different)
28: 0xe3779b99 (12 bits different)
29: 0xf1bbcdcc (18 bits different)
30: 0x78dde6e6 (22 bits different)
31: 0x3c6ef373 (14 bits different)

in simple terms a rotation where a rotation is performed on a figure such that the  figure maps   itself back to its original position  such that the rotation is greater than 0° but less than 360°.


Generating random vector for Full Homomorphic Cryptography The site below explains that part of doing homomorphic encryption, you need to generate a vector of random numbers that have the property that its dot product against a randomly generated bit vector mod 2 has an absolute value less than some amount (but greater than zero).

http://windowsontheory.org/2012/05/02/building-the-swiss-army-knife/

Is there any way to generate such a vector other than brute force?  Seems like it could take a long time for a large vector.

After thinking about it here's what I think.  Let me know what you think.

First, I generate a random vector of floats and figure out what the dot product is.

I then pick one of the elements of the float vector that correspond to a 1 in the binary array (randomly?), and then adjust that value the necessary amount to make the dot product come out to the value I want.

Thoughts? Seems like it should be ok.


Difference between Symmetric and Asymmetric. Is this answer correct, based on a written test? I asked the following question on a final exam:

  Symmetric Ciphers (e.g. AES, DES, Blowfish) use up to 256 bit on the
  best case, which are considered strong against brute-force attacks. On
  the other hand, asymmetric cryptography (e.g. RSA, DSA, Elgamal) use a
  higher amount of bits (~2048). Explain the reason of the bit
  difference between Symmetric and Asymmetric Ciphers.

His answer was:

  Asymmetric Ciphers use more bits because generally it uses powers,
  which generates a bit increase. Additionally, Asymmetric Encryption
  requires more processing time than Symmetric, which leads to a higher
  cost on a bit level.

By “powers”, he meant “math powers”. He quotes the following from the internet to support his answer:

  "The algorithm is slow, since it uses math operations which have a high
  cost and works with big key sizes. Part of the problem is on the
  choice of the exponent"

And finally:

  "Although is not mathematically exact, the first operation could be
  accepted as linear since the number of operations is directly
  proportional to the size of both operands. On the other hand, the
  second operation is an exponential type because doubling the input
  size, the number of operations to make does not double, it increases
  exponentially in time."

Although the answer is here, I see that part of his statements are correct, but is he answering the question correctly?

I don't believe he is answering the right question.  You essentially asked "why are public keys so much larger than symmetric keys", and after his first sentence (which started to address the question, but was a bit vague), he tried to answer the distinct question "why are public key operations so much slower" (not that he got the details of that correct; his last sentence appeared to imply that public key operations take an exponential amount of time).

symmetric ciphers are based on exactly the same and ONE and ONLY key on both sides. asymmetric ones are based on one or more exactly the same keys on both sides and at least one truly private key on each side, if we're talking about a bidirectional communication. key size is not important here.


Does RSA operate over a Finite Field (Galois Field)? Is it correct to say that RSA operates over a Finite Field (Galois Field)? In this case GF(p)?
I do understant that the modulo in RSA is not itself a prime number, but all the operations (multiplication, inversion) occur as if it is a GF(p).

No, RSA encryption and signature is performed in (the multiplicative semigroup of) the factor ring $\mathbb Z/n\mathbb Z$ which is not a field since the non-zero elements $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) do not have multiplicative inverses. (However, one easily observes that all other non-zero elements are invertible, as their representants are coprime to $n=pq$).

William Stalling says

  RSA is based on exponentiation in a finite (Galois) field over integers modulo a prime

Source: http://williamstallings.com/Extras/Security-Notes/lectures/publickey.html


RSA with small exponents? Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse of $d \bmod \varphi(n)$).  Given a plaintext message $m$, we obtain the ciphertext $c = m^e \bmod n$; we subsequently decrypt the ciphertext by calculating $c^d \bmod n$.

Suppose I'm trying to implement RSA on a device with low computational power, and these exponentiations take too long.  I decide to make my implementation run faster by choosing small values for $e$ and $d$ (e.g. in the tens or hundreds).

Are there efficient attacks against such an implementation?

First I must state that a secure RSA encryption must use an appropriate padding, which includes some randomness. See PKCS#1 for details.

That being said, $d$ is the "private exponent" and knowledge of $d$ and $n$ is sufficient to decrypt messages. $n$ is public (by construction) so $d$ must be kept private at all costs. If it is very small then an attacker can simply try values for $d$ exhaustively.
On a more general basis, if the size of $d$ is lower than 0.29 times the size of $n$ (in bits) then there exists an efficient key recovery attack. The accepted wisdom is that trying to get a $d$ much smaller than $n$ is a bad idea for security.

On the other hand, there is no problem in having a small $e$, down to $e = 3$. Actually, with RSA as you describe, there is a problem with a very small $e$: if you use $e = 3$ and encrypt the very same message $m$ with three distinct public keys, then an attacker can recover $m$. But that's not really due to using a small $e$; rather, it is due to not applying a proper padding.

$e$ and $d$ cannot both be small, because $ed$ must equal at least $(p-1)(q-1)+1$, which is very large if the scheme is to provide any security against factoring algorithms.


Is there a theoretical maximum useful keysize given the block-size? Consider a block-cipher $F$ with a $N$-bit block-size and a $M$-bit key-size. That is, if  $k$ is a $M$-bit key, $p$ is a $N$-bit block of plain-text and $c$ is a $N$-bit block of cipher-text, then:
$$
F\left(k,p\right) = c
$$

Each plain-text block of $N$ bits must have a 1-to-1 correspondence with a cipher-text block of $N$ bits.

My question is: is there a theoretical maximum number of distinct keys such that in the set of such keys, there are no two keys $k_1$ and $k_2$ for which $F\left( k_1, p \right) = F\left( k_2,p\right)$ for all values of $p$?

For instance, if all we could do was a bit-permutation and an exclusive-OR with masks derived from the key, then  $M \le N + \lfloor\log_2 N!\rfloor$ could be such a maximum. But given for instance the 'MixColumns' and 'SubBytes' steps in AES, many more distinct keys would be possible. But is there a theoretical upper limit?

If you are asking about a truly theoretical limit for a theoretical block cipher (as opposed to a practically usable one, like AES), you could calculate the number of possible keys like this:

A block cipher, together with a key $k$ ($|k|$ = $M$), describes one of many possible random permutations: For every plaintext block, there is exactly one ciphertext block. The number of possible blocks is simply $2^M$, where $M$ is the length of a block in bits.

The number of permutations of $n$ different objects is $n!$, so for our (very unpractical) block cipher, there can be at most $2^M!$ keys. Many of those will be unusable in practice (for some, plaintext and ciphertext will differ for only a single block), but they all satisfy your condition that they differ in at least one plaintext-ciphertext-pair from all other permutations.

Now, specifying one of all possible permutations without any optimization would take an insane number of bits to transfer (the number of plaintext-ciphertext-pairs in the permutation, times the number of permutations: $2^M\cdot2^M!$

To be able to actually transmit the key with fewer bits than any conceivable message, we limit our keyspace to mere $N$ bits, or $2^N$ possible permutations.

If you insert the actual numbers, we get $2^{256}$ possible keys for AES-256, which seems like a lot (and for practical purposes, it is), but the theoretical limit for 128-bit blocks is much, much higher: $2^{128}\cdot2^{128}!$.

Update:
Avijit has pointed out in the comments that there is an easy optimization which allows enumerating all possible permutations with "only" $\lceil log_2 2^M!\rceil$ bits (which allows for $2^M!$ keys). This is a lot more compact, but still much larger than any practical key size.

Since there are only $2^N$ unique output blocks, an $N$ bit key is the maximum useful size, assuming the block cipher is a perfect 1 to 1 permutation with all distinct keys giving distinct ciphertext block for a given plaintext block.

Since that is not proven, the maximum key size is $2^{2N}$ in practice, this is because of the possibility of equivalent keys with a key size matching the block size, which is generally accepted (i think) as $2^{N-1}$ unique outputs for $2^N$ keys for a well made cipher.

Note that this is only for 1 plaintext block, 2 keys that give the same ciphertext for one block may not have the same behavior for any other plaintext block for a given cipher. For this reason a maximum key size of $2^N * 2^N$ or $2^{2N}$ is logical.

In some ciphers (including AES) the round count is also determined by the key size, making other attacks more difficult, to match or exceed the workload of a brute force attack on the key space. Different ciphers use different building blocks that are dissimilar, but in all instances a maximum key size of double the block size makes the most sense mathematically, with a minimum key size of the block size.

Try to break it down and think of a cipher with 2-bit blocks and keys, then extend that to 4-bit keys.


Is it theoretically possible to construct a string that contains its own hash value? After saw the xkcd comic Self-Description, I wonder if it is theoretically possible to construct a self-descriptive string that contains its own hash value?

Let's say the string's MD5 value is 663ef7d3f38cf900574cd4d9f83eb1b7, the string would be something like:

...
The md5sum value of this file is 663ef7d3f38cf900574cd4d9f83eb1b7
...

Yes, for any secure cryptographic hash function, it is overwhelmingly likely that there exists a string which contains, or even begins with, its own hash value (in any given encoding, even).  However, if the hash function is indeed secure, it is also exceeding unlikely that we could ever find such a string.

First, let's look on the positive side.  A good cryptographic hash is, a priori, supposed to be indistinguishable from a random function from the set of all bitstrings (or byte strings) to bitstring of a given fixed length $k$.  For such a random function, the probability that a randomly chosen $n$-bit string (where $n \ge k$) maps to its own $k$-bit prefix is $1/2^k$.  Since there are $2^n$ distinct $n$-bit strings, the probability that none of them maps to its own $k$-bit prefix is:

$$\begin{aligned}
(1 - 1/2^k)^{2^n}
&= \exp(2^n \log(1 - 1/2^k)) \\
&\lesssim \exp(-2^n/2^k) \\
&\to 0 \quad \text{as } n \to \infty
\end{aligned}$$

Thus, the probability that there is at least one $n$-bit string that maps to its own $k$-bit prefix tends to $1$ as $n$ increases.  Indeed, the convergence is extremely rapid, being given by the exponential of an exponential.  For example, for a 256-bit hash, the probability that there exists some 260-bit input string that hashes to its own 256-bit prefix is about $1 - \exp(-2^{260}/2^{256}) =$ $1 - \exp(-2^4) \approx$ $1 - 10^{-7}$.  For 261-bit inputs, it's $1 - \exp(-2^5) \approx$ $1 - 10^{-14}$, and so on.

Obviously, the probability that there is an input string that hashes to some substring of itself must be at least as high as the probability that there is one that hashes to its prefix.

In particular, a curious corollary of this result is that, for any secure hash function, the probability that there exists an input string that hashes exactly to itself is very close to $1 - \exp(-1) =$ $1 - 1/\mathrm e \approx$ $0.63$.  (This approximation is good as long as the output bit length $k$ is greater than about 4 or so.  For, say, a 256-bit hash function, it's as close to exact as makes no difference.)  This is a general mathematical result: for any sufficiently large set $S$, a randomly chosen function $f: S \to S$ has a fixed point with probability close to $1 - 1/\mathrm e$.

Now for the bad news: to find such a string by brute force, the expected number of trials we'd need is $2^k$.  For, say, $k=256$, such a search is way beyond not just currently available computing power, but any conceivable computing power achievable in the universe using known physics.

Now, of course, real hash functions are not actually random functions, and it's possible that there might be some way to find such strings more efficiently than by brute force.  However, if such a method were found, it would arguably be good evidence that the hash function in question was not secure, and that its use should be discontinued.

In particular, the ability to efficiently find an input string that hashes to a given value would be a clear break of first preimage resistance, and any hash function allowing it would be considered completely broken.  Technically, just having the ability to efficiently find strings that hash to a substring of themselves, without being able to control what the actual hash value is, would not violate any of the three standard security properties required of a hash function (first and second preimage resistance and collision resistance).  However, it would allow the hash function to be distinguished from a random function, and in practice, any plausible attack that would allow such input to be found would almost certainly compromise other security properties of the hash as well.

For MD5 You can use HashClash to find "Chosen-prefix Collision".


Can padding length, and thus plaintext length, be considered public information when using aes-cbc? Right now I'm using a simple padding system that takes the plaintext, hashes it with SHA512, and appends $x$ bytes of the hash as padding where $x$ is the delta between the plaintext and nearest blocksize multiple.

Is this considered a secure method of padding the message? I am also authenticating the encrypted data using HMAC-SHA512, would this effect the security?

For AES CBC i would suggest you stick to the standards.

The PKCS7 padding scheme is pretty easy to implement and has been tested extensively now that its been out in the public for a while. I had implemented PKCS7 padding for my AES CBC cipher a few weeks ago and you can see the code here if it helps.

Note that hashing by itself does not provide you with authentication, you will need a MAC (Message Authentication Code) for that. If you like using the SHA family, you can use something like HMAC-SHA256.

Is there any particular reason why you wish to use hashed data as a pad? If you are looking for authenticated encryption, you should stick to the standards like GCM for AES.

You should use a vetted padding scheme. Unfortunately PKCS#7 is not the right one (search for "pkcs7 vulnerability").

It seems that ISO.2FIEC_7816-4 isn't vulnerable.


What exactly is a quantum key distribution network for? There are many diagrams out there explaining how quantum key distribution works on a physics /optics and mathematics level. I understand these explanations fairly well so I'm not asking about the underlying principles.  This is one of the few that actually features people on it (although they seem to be fairly incidental to the usage):-

As I understand it, the machines only transmit keys not actual business data.  I appreciate the exchange is done with one time pads, but is it like Diffie–Hellman key exchange otherwise, but only between fixed machines /servers?  Do they replace entering AES keys transmitted over the phone /fax? Since AES is hard to break, surely the keys don't need replacing every hour?  And do they then operate in pairs, because two is only a network from a marketing perspective.  They can't control the log in into my desktop computer can they? And wouldn't all the desktops have to be interconnected with fibre optics rather than Ethernet? The latter is probably a rather naive question.

This additional image clearly shows the transmission of secure encryption keys through a Toshiba quantum network:-

At a separation of 20Km, the devices are generating /exchanging keys at a rate of 10 kbits/s.  Why as that's 40 no. 256 bit AES keys each and every second?  What exactly does someone do with 140,000 unbreakable AES keys per hour? Even more ridiculously, that's a million new keys in a single business day.

I'd appreciate an answer from a operational perspective, although I realise that this is firstly a cryptography theory site.  So what's it for?

I looked at Quantum key exchange skepticism/confusion  and a simulated network, but both were unfruitful.

It seems that the initial diagram is correct.  A QKDN is exactly this:-

and it relies on two pieces of kit, a quantum key generator and an encryptor device. A 256 bit AES key is generated and shared between Alice and Bob via the BB84 protocol running over dedicated fibre optic cable. The key itself is created via a true random number generator (perhaps based on the phase interference of a laser beam).

The keys are then passed to the encryptor devices which operate AES between themselves over conventional channels. So actual business data flows only between the encryptor devices, over common networking technology and not the quantum machines. The thing that ensures the security of the transmitted data is that the AES keys only have a life span of one minute.  They're then replaced.  That's why all that quantum data is transmitted.  AES keys are constantly being replaced before anyone could even attempt to break them. Clearly some of the numbers here are dependant on individual networks and hardware.

And QKDNs are used in anger all over the world including government and commerce. The first was deployed in Switzerland to secure their frequent public votes /elections. And there are some interesting future developments that won't require fibre optics at all, and some that will ensure secure key exchange over infinite distances.

All of this is to be found on YouTube.  Don't laugh.  It's a presentation by Kelly Richdale, head of quantum randomness at ID Quantique, a market leader in QKDNs.   There is also an unbiased and fair summary of QKD from  the European Network and Information Security Agency (ENISA) here.  It's concise but rather dated (Nov 2009), so a lot of the open issues should have been resolved or are in the process of being so.

I would say the quantum key distribution networks being built right now are for research. Comparing this research to other fields they would be at the 1969 level for space exploration and for the ARPA net. But we don't know yet if it will turn into something everyone will use for everything, like the internet or something that only has limited potential like space exploration (which only gave us GPS and spy satellites).

The main sales point is instead of making a encrypted communication channel a mathematically hard problem to solve like RSA, you make it an impossible physics problem that can't be solved.


Is the GOST block cipher broken? Is the GOST cipher broken or known to be weak and insecure? Please try to simplify your answer since I am a programmer and not a cryptographer and please consider this web page and tell me if the claims made there are true.

There are two ways a cipher can be broken: theoretically and practically. If the paper is correct then:

  Our fastest attack achieves a nearly feasible $T=2^{101}$ (cf. Section 28.6 and [28]). (emphasis mine)

If we verify this claim then we get:

  If we have a diverse population of at least $2^{79}$ diﬀerent 256-bit GOST keys generated at random, with access to $2^{32}$ CP per key, one can recover one of these 256-bit keys in total overall time of about $2^{101}$ GOST encryptions.

Now theoretically a cipher is broken if there is an attack that is (significantly) faster than brute force. Simply said, $2^{101}$ is a darn amount better than $2^{255}$ required for brute force. So if this claim is correct then the theoretical security of GOST is much lower than it is supposed to be. Hence it could be called broken.

Of course, nobody is going to invest that amount of memory or processing power to even prove this point. SHA-1 has a much lower effective security margin and it took a very long time before a collision could be found.

Given the structure of the paper I would say that it's likely that the claims are correct. That doesn't mean that anybody can now attack GOST. It does show that too many kinds of attack are possible. These kind of attacks will only get stronger. This is a clear indication that it would be wise to upgrade. The block size of 64 bit is also a good reason to upgrade, 64 bit is considered on the low side for many applications of block ciphers.

That all said, these specific cryptographic attacks can not be used to attack any well designed / implemented protocol that makes use of GOST. 101 bit security is generally thought to be out of reach, i.e. the "nearly feasible" in the text.

That a cipher is supported by the NSA doesn't mean that (publicly) it is developed by the NSA. The NSA can insert a backdoor requirements into the endevors of third parties, then promote this as a "secure" cypher.

AES was indeed not "developed" by the NSA, but it was promoted by the NSA. And still is. This is particularly important as this is the cypher used for cryptocurrencies and most "encrypted" info on webpages and messaging.

Furthermore the NSA does have a history of inserting backdoors. Even is less cryptographically/mathematically secure, all attacks on GOST are practically unfeasible without quantum computing, so in practice it is as secure as AES.

And it has a greater advantage: It was never intended for public use, so it woudn't be backdoored.


Is it better to encrypt before compression or vice versa? Is it better to encrypt a plain text file before compression, or vice versa?

Neither:

Encrypting first and then compressing does not work.
Compressing first can leak information about plaintext content through the ciphertext length, as poncho mentioned in comments to another answer.

Specifically, compression allows an attacker who can control parts of the message that is encrypted to reveal things about the other, secret parts, like cookies in the case of web traffic. It is most dangerous in a live protocol like TLS. Some forms of compression (e.g. truly constant bitrate lossy video/audio compression) may be immune to such attacks (but even then there might be side channel attacks due to the compression).

In most cases you should just encrypt the uncompressed data and be done with it.

Data storage and transmission is usually cheap enough. If you cannot live without compression, you must do it first, but then you have to really know what you are doing and likely accept at least some loss of security.

Compress and then encrypt is better. Data compression removes redundant character strings in a file. So the compressed file has a more uniform distribution of characters.

This also provides shorter plaintext and ciphertext, which reduces the time spent encrypting, decrypting and transmiting the file.

By comparison, encrypting and then compressing is innefficient.


Mapping between NIST test and TRNG features Each of the NIST tests are generally explained in Random Bit Generation - Guide to the Statistical Tests. I was wondering if some one can help me understand them better. For example, which tests show the robustness, independence, ergodicity, stationarity, etc.

Based on the description provided on NIST website, I think, the mentioned features can be understood from following tests:

robustness: cumulative sum test
independence: random binary rank test
ergodicity: Maurer's universal statistical test or linear complexity test
stationarity: cumulative sum test

I was wondering if these are correct. In addition, if other NIST tests can be summarized.

It's difficult to map each of the 15 tests to a particular qualitative descriptor. Adjectives like robust are not mentioned in the 800-22 documentation.

The null hypothesis of randomness ($H_0$) in all tests fundamentally requires samples from a stationary and ergodic process. Otherwise the tests would be inconsistent with respect to time, and could not accurately model the samples' shifting distributions or test score expectations.  Or the test scores for this million bits would differ widely from that million's. Although be mindful of some variability implicit in any random process.

The requirement for independence within each test varies though. §2 of 800-22 details the mathematical assumptions underpinning each test. NIST doesn't always highlight the level of significance of independence within each test.  They often don't attempt to debate the causality of a $H_0$ sequence, just it's effect and characteristics.

Some are explicitly discussed.  The Discrete Fourier Transform (Specral) test is an example of a test that specifically targets independence in the mathematical sense.  It looks for correlations between samples spaced $n$ samples apart.  Maurer’s "Universal Statistical" test is similar, exploiting correlation for compressibility. As is the Binary Matrix Rank test. Conversely the Frequency (Monobit) test doesn't.  It will accept any degree of correlation as long as the ones and zeros are evenly matched in line with a half normal distribution.

The sensitivity to independence is harder to identify with some of the other tests. You may have to decompose the statistics beneath  tests like the Serial or Cumulative Sums (Cusum) tests.

Don't confuse the recommended input lengths with non ergodicity.  The recommendations are there simply to facilitate some of the test metrics' reference distributions, or to limit processing time.


Method to calculating e in RSA For simplicity I choose two small primes for p and q.

p=3
q=11
n=33
Φ(n)=20

Now we need to find the public key e, which has to be coprime with Φ(n). For small numbers like these it is trivial, but how can it be done when larger primes are chosen?

This is easy, just pick $e$ as prime larger than $\max(p,q)$. As $\phi(n) = (p-1)(q-1)$ it has only prime factors smaller than $q$ and $p$.

You can also do trial and error. If $e$ is prime, the GCD test is very fast. But it is technically not necessary to choose $e$ prime. Also note that key generation is not time critical.

However, often one starts with $e \in \{ 3,5,17,257,65537 \}$ which are special primes. Then one choose appropriate $p$ and $q$.
These exponents have computational benefits as they are of the form $2^k+1$. That makes computation of the $e^\text{th}$ power fast. Note that there are attacks for small exponents, especially $e=3$. They are all related to bad implementations, i.e. padding and so on. The RSA-scheme itself is not affected.

My RSA generator in Python was a function written as follows:

def rsa_gen(p,q):

    n = p*q
    lambda_n = lcm(p-1, q-1)

    e_list = []
    e = 2

    while e < lambda_n:
        if math.gcd(e, lambda_n) == 1:
            e_list.append(e)
            e = e + 1
        else:
        e = e + 1

    e = random.choice(e_list)**
    d = inverse(e, lambda_n)

    return (n, e, d)

Obviously, I took the brute force approach for any pre-determined primes P, Q.

Basically, I initialize an array/list as empty, e as 2 since 1 and 0 are not appropriate. Then I run a co-prime check for all values 2 to lambda and populate the list/array with them. Then I pick randomly from that list to get my e.

Regards


Why does it make sense to use min-entropy for measuring cryptographic random data? Comments on Cryptographic Entropy Measurement seems to challenge the heart of NIST SP 800-90B, which proposes min-entropy as a conservative measure of entropy produced by hardware source.

[The idea of using min-entropy] has been taken to heart in the NIST SP 800-90 documents, using the most conservative measure, min-entropy. While this may make sense for cryptographic random data, it makes no sense when measuring entropy in raw random data. [section 1, page 2]

Why does it make sense to use min-entropy for measuring cryptographic random data?  I would have thought it was the other way around --- sensible for measuring raw random data, not cryptographic random data --- because entropy is produced in raw random data; cryptographic random data is processed random data, which cannot increase entropy, only possibly reduce it.

The central limit theorem does not hold and confidence intervals are
not well defined for [min-entropy].  If minimum entropy does not
satisfy the requirements set out by either Shannon or Rényi, why is it
used as the foundation for measuring entropy in cryptographic
applications? [section 3.1.1, page 6]

Does min-entropy satisfy the properties of an entropy measuring function laid out by Shannon?  If not, why is it being used for measuring entropy?
Update. @kodlu, the properties an entropy function $I(p)$, where $p$ is the probability of a certain event $s$ should have are:

$I(p) \ge 0$
$I(p_1, p_2) = I(p_1) + I(p_2)$ for independent events.
$I(p)$ is a continuous function of $p$.

Ignore NIST. It has more important legally binding agendas to debate outside of this forum. Use common sense.

Does min-entropy satisfy the properties of an entropy measuring function laid out by Shannon? If not, why is it being used for measuring entropy?

No. $H_{\infty}$ is to Shannon entropy as is JPEG to BMP. Shannon was interested in encoding all the data in the transmission channel.  $H_{\infty}$ is lossy and the original data cannot be retrieved in it's entirety. $H_{\infty}$ is used before transmission.

entropy is produced in raw random data

Yes. So measure it. You will have a lot more luck if you can prove the data to be IID.
It boils down to this:-

You need to separate information entropy from cryptographic entropy.
We want true random bits.
We get them via some generic form of hardware processing.
Current mathematical thinking revolves around the left over hash lemma which dictates the eventual output bias.
The thinking is predicated on $H_{\infty}$.
Thus $H_{\infty}$.


More suitable Substitution Box Can anyone suggest me any fast searching method or algorithm to find best S-Box among a big number of S-boxes? For example; if I have 100 different S-boxes, I want to pick that one which is more secure than the others.

There is no such specific algorithm to find the best S-box but you can construct a Diference Distribution Table(DDT) like this and check out the values in it .A DDT is a matrix containing input differences as rows and corresponding output differences in column.

A better S-box has-
1- Lower values in its DDT
2- Less occurence of higher or highest value

AES S-Box is not just a non linear substitution table, it is the result of a precalculation based on two operations. This is, imho, the greatest value of Rijndael, everything rests with maths.

The first operation is a non linear transformation $g: x\rightarrow y = x^{-1} \in \frac{\mathbb{F}_{2}[z]}{m(z)} $ with $m(z) = z^8+z^4+z^3+z+1$ who is irreducible that tells us all the elements are invertible. The second operation is an affine map in $(\mathbb{F}_2)^8$.

Do you like to build a different S-Box but with the same good properties? Lets use a different $m(z)$ (with the same degree) but this will not provide to you any extra feature. Do you like to build table from scratch? Any linearity introduced by mistake will be a weakness. The maths behind the Rijndael helps to avoid mistakes.


How robust is RSA-FDH against distribution bias? Suppose we want to use the RSA-Full Domain Hash (-FDH) signature scheme. This essentially works precisely like textbook RSA but instead of signing $m$ directly, we sign $H(m)$ with $H:\{0,1\}^*\to\mathbb Z_n^*$ being reasonable model-able as a random oracle (we need the ROM for the security reduction).

Now my question:
Are there any known attacks when $H$ exhibits a minimal (1-bit) bias?

In particular consider $H$ where $m$ is mapped to the first $\lfloor \log_2(n)\rfloor$ of SHAKE128(m), ie where we generate a hash output as long as $n$ but always zero the MSBit out.

Motivation: If we had such a bias for the generation of $k$ in (EC)DSA, this would probably allow for an attack and I talked in the past about how RSA-FDH is one of the applications of XOFs.

Fix a number of bits $t$, e.g. $t = 2048$; consider RSA-FDH with $t$-bit modulus $n$, so that $2^{t - 1} < n < t$.  Fix a hash $H\colon \{0,1\}^* \to \{0,1\}^{t - 1}$.  Can we use $H$ for RSA-FDH, even though the literature on RSA-FDH typically posits a hash $G_n\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$?

It is not hard to define a hash $G_n\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$ with near uniform distribution using a double-length hash $H_0\colon \{0,1\}^* \to \{0,1\}^{2t}$ by $G_n(x) = H_0(x) \bmod n$; the modulo bias at this scale is negligible, just like in EdDSA's use of SHA-512 to select $k$ from $\ell \approx 2^{252}$ possibilities.

If our signature scheme were randomized, we could do rejection sampling, as phayes suggests in another answer, and attain an exactly uniform distribution—indeed, if we wanted anonymous signatures so that signatures under two keys are indistinguishable without the keys, we would have to do rejection sampling, though on the signature rather than the hash, to thwart anglophone statisticians from counting German tanks.  But this question is about the deterministic RSA-FDH.

As far as I can tell, this specific question—where $H$ covers only about half of $\mathbb Z/n\mathbb Z$—has not been addressed in the literature.  But very similar questions have been:

Tight security can be proven for deterministic Rabin–Williams signatures using $H$[1].  Although there are barriers to applying the same proof to RSA, it seems unlikely that the space covered by $H$ is one of them: they rather have to do with differences between squaring and (e.g.) cubing.  (Questions like this are part of why [1] used a single $H$ with $t$-bit codomain instead of a key-dependent $G_n$.)
Tight security can be proven for PSS signatures using a randomized hash whose most significant bit is always zero[2].  Here the randomized hash is $$P_r(m) = 0 \mathbin\| w \mathbin\| (r \oplus H_2(w)) \mathbin\| H_3(w),$$ where $w = H_1(r \mathbin\| m)$, and $H_1$, $H_2$, and $H_3$ have the right widths to make it all work out.  The proof given by Bellare and Rogaway requires $|r| \geq 128$ to provide meaningful security.
Tight security can be proven for a randomized version of FDH[3] where the randomization is appended to, rather than embedded in, the signature, like in phayes' system: a signature $(r, s)$ on $m$ under $n$ satisfies $$s^e \equiv G_n(r \mathbin\| m) \pmod n.$$  Bizarrely, this tight security works even if $|r| = 1$, even though it can be proved that deterministic RSA-FDH cannot admit such tight security[4], although that proof works only for large exponents which leaves open the possibility of tight security for $e = 3$[5] (paywall-free).  This state of affairs raises all sorts of questions about the significance of these reductions[6].

The Bellare–Rogaway 1996 proof[2] that a $q$-query forger for a trapdoor permutation signature scheme $f(s) = G_n(m)$ can be converted into an algorithm for inverting $f$ on a point $y$ works by running the forger with a derived random oracle $G'_n$ that returns $y$ on a randomly chosen one of the $q$ queries, and otherwise defers to $G_n$.  If the forger succeeds in finding a forgery $(m, s)$, there's about a $1/q$ chance that it found the preimage $s$ for our chosen point $y$ rather than for the $q - 1$ options we sent to $G_n$, and thus that $s = f^{-1}(y)$ is the desired preimage.

If we replace the equation by $f(s) = H(m)$, the reduction simply doesn't work to compute $f^{-1}(y)$ for $y \geq 2^{t - 1}$, which happens with probability less than 1/2 if $y$ is uniformly distributed in $\mathbb Z/n\mathbb Z$, so the same inversion algorithm has about a $1/(2q)$ chance of success instead.  Formally this would suggest you need to add another bit to the modulus to attain the same security—but in practical terms that bit is likely inconsequential (some practical key generation algorithms vary with a slop of a bit anyway[7]), and it remains unclear what the significance of the tightness gap is at all here when adding a single bit of randomization enables proving a theorem that eliminates the gap.

In brief, it is hard to imagine that using a hash covering only up to $t - 1$ bits, where $2^{t - 1} < n < 2^t$, could meaningfully hurt the security of RSA-FDH.  Certainly there are no known attacks like there are against biases is per-message secrets in Schnorr- and DSA-type signatures.

This isn't answering your question directly, but is instead proposing a different solution that side-steps the question entirely.

Instead of zeroing out the most-significant bit, you could instead append a random initialization vector (IV) to the message before putting it through SHAKE128. If the resulting digest (interpreted as an integer) is larger than modulus n, then just generate a new IV and try again. You'll have to pass around the IV in addition to the signature, but this shouldn't be a big deal.

In Pseudocode:

iv = random_iv()
digest = shake128(message + iv)
while modulus_n < digest.as_int():
    iv++
    digest = shake128(message + iv)

I've implemented this in rust here: https://github.com/phayes/rsa-fdh


Best approach for storing private key I'm working on a web service application which uses a self signed certificate. I apologize up front if this turns to be a dumb question. When using openssl for generating private key, it reveals (as per my understanding) the encryption algorithm and initial vector. A bit of googling showed it follows PKCS5. These information of algorithm and key was not present in another private key which followed PKCS8.

Does this mean that PKCS8 has better security ? At present which is most popular and secure, while there is a requirement to store private key in filesystem?
Private key is encrypted with a passphrase and I use the hardcoded passphrase in the code to decrypt it. Is this the right way of using it?

PKCS#5 (RFC2898) is a standard for key derivation, not for key storage. Openssl can store an RSA private key either in its own format (default) or in PKCS#8 format. You can convert a key using the openssl pkcs8 command. Securitywise, there is no difference between the two.
You should rather store the password in a configuration file or make the user type it when starting the server software. Otherwise, you would have to recompile and reinstall your whole software, everytime you change the key's password or the key itself. Also, the password can be more easily protected in a single file on the server than in a source code repository.

In general you should assume that everything about your system is known except for the explicit secrets, in your case the private key. That includes PKCS and all other kinds of details about the algorithms.

This is called Kerckhoff's Principle and it allows a more structured analysis of the security of a system.

If an attacker had to guess which PKCS you use it would not be very good protection anyway because there are very few guesses that he has to try.

The field that deals with the systematic violation of Kerckhoff's Principle is called Obfuscation. ;)
It is used e.g. for computer software, where it is often impossible to systematically protect any secrets because they are on the user's computer.


What are the chances that AES-256 encryption is cracked? I'm currently building a web application and would like to encrypt all data on the back-end. I was thinking of using the AES-256 encryption but wasn't sure how safe it was. I did that math and felt safe.

I took this model to a professor at my college, who is a cyber security expert, and he seemed to have quite a different take. He told me there are only two encryption schemes that he knows of that cannot be broken, and AES is not one of them. He said sure, put it in, but just know that there are people out there who can crack it.

I Googled everything I could about the AES and it being cracked, and the only information I could find was this paper: Distinguisher and Related-Key Attack on the Full AES-256
(Extended Version). Sure it says the AES has been cracked but is still has a practical use, right? I believe it is $2^{231}$ instead of $2^{256}$.

So what gives? Is it practically secure to use or not? Does he just know something that most people don't? If my web application database credentials are somehow exposed, and a hacker gets the raw encrypted data, how can I ensure he won't be able to decrypt it within his lifetime?

He told me there are only two encryptions that he knows of that cannot be broken, and AES is not one of them

This tells me you asked your professor the wrong question.  You asked a cyber security expert if an algorithm could be cracked, to which the answer is always yes, with the exception of a handful of inconvenient algorithms, such as One Time Use Pads used in exactly the correct way.  Even in those cases, there's exploits to worry about.

AES-256 is an algorithm.  It can be broken.  If you look at the history of cryptography, every algorithm gets broken eventually.  That's why we make new algorithms.  The question is how long it takes to figure out the math to break it.

The real question to ask is "what is your threat model?"  What sort of attack are you trying to prevent?  Are you creating a digital lock on a diary to keep it safe from your sister's prying eyes, or are you Edward Snowden, on the run from several three letter agencies with billions of dollars of funding?

AES-256 is currently labeled as sufficient to use in the US government for the transmission of TOP SECRET/SCI information.  That's pretty much the highest classification level they could clear it for, so the US government is pretty darn confident that nobody can break AES-256 on the timescales required to protect our nation's greatest secrets.

(Well, almost.  What it really says is that they are confident that nobody outside of the US government can break AES-256.  What you believe that that says about whether the US government, themselves, can break it depends on your threat model... and whether you engage in discussions of whether heavy-duty tin foil  makes better hats or not)

If I recall a few years back AES256 was broken, but not in a significant way. Broken refers to finding a method which is faster than brute force to derive the key. And while i am not sure it was AES256 i know one of the popular encryption systems was broken, but it only reduces the expected time needed to break it slightly. As far as i know the only algorithms that have not been broken to date is Serpent, and DES. Now i know everyone will say that DES is broken, but in actuality it has not been broken, instead hardware advanced beyond the point where we could no longer consider it secure. Meaning it is trivial for us to iterate through all possible combinations of DES and find the key used. Which is why 3-DES is considered secure since it is essentially the same algorithm used 3 times in succession. This is a cautionary tale as well, as at any point we could see hardware advance to a point where it becomes trivial to brute force current algorithms. When DES was drafted they couldn't imagine a computer powerful enough to do this, now such hardware is so common that it is something they have us do as an exercise when teaching encryption. So in reality all you can do is use the best you know of and hope that it will last you for a reasonable period.
(Please, note that I did not check my references before posting, so my facts may be off slightly as they are from memory.)


What are the values of $w$ such that the corresponding $\text{Keccak-}f[25w]$ function is invertible (bijective)? From this answer, I see that from a mathematical point of view, one could define the $\text{Keccak-}f[25w]$ permutation for an arbitrary value of $w$.

I am interested in the following question: disregarding all properties of the resulting function except the invertibility (because $\text{Keccak-}f[25w]$ is required to be a permutation), is it true that if the value of $w$ is a multiple of $8$ and not a multiple of $5$, the corresponding $\text{Keccak-}f[25w]$ function is invertible (and bijective)? If the answer is “No”, then how to determine whether a particular $w$ is suitable (assuming that $w$ is required to be a multiple of $8$)?

$\operatorname{Keccak-}\!f[25w]$ is defined, by the Keccak specification, only when $w = 2^\ell$ for some $\ell$, and in all such cases it is a permutation.  The choices 1, 2, and 4 for $w$ are not multiples of 8.  No multiple of 5 is a power of 2 and consequently $w$ is never a multiple of 5.

Regarding Keccak-f[25w] I’m assuming that you’re referring to changing the total number of lanes (25 as outlined in the standard) and not changing the 64-bit lanes size. Changing the lane count, as stated in the previous answer regarding a change in the lane size, would also result in a non-standard version of Keccak. To the extent that modification of the source code would be required to execute the function.

Your question is directed specifically at the viability of inversion given a deviation from the 25 lane standard.

Is it true that if the value of w is a multiple of 8 and not a multiple of 5, the corresponding Keccak-f[25w] function is invertible?

The above statement is false. If the total lane count is a multiple of 5 Keccak-f[25w]  will be invertible, with the understanding that arbitrary constants can be added at the pi, rho, and iota steps.  Essentially a total lane count being a multiple of 5 is required to maintain continuity with steps theta and chi. If the total lane count is even there might be some issues with pi, because rotational symmetry might be broken.

Issues will be caused when there is a total lane count that is NOT a multiple of 5. If the total lane count is prime the s-box definition of chi will need to extend to the full lane count. I would probably write a test for the largest factor that isn’t equal to the total lane count. How this affects the statistical properties of chi after considering state truncation would require further analysis. With theta things started getting interesting. An arbitrary lane count change could be added to theta without affecting its forward derivation. By the bit-twisting definition of theta applied with the extension of the 1:11 indexing relationship. In the reverse direction you will encounter the same issue if the lane count is prime. Now even if the lane count is NOT prime and you leverage the largest factor not including itself, there will be a computational resource issue as a result of the nature with which theta is inverted.  Then again my theta inversion implementation could be a black boxed version of something glaringly simple. And always remember the print() statement is not necessarily truth.

Addressing below comment:

Keccak can be inverted as long a the lane width is an even number so w=8,16,48,64... are all viable sizes assuming you're comfortable throwing in some random bits to account for the reduced size of iota. I however wouldn't be able to invert Keccak when w > 1000.


Does ChaCha20 counter actually increment through iterations? RFC defines:

state = constants | key | counter | nonce

Suggested on multiple places is to set counter to 0 or 1.

It is still unclear to me what the function of counter is. Why not just use larger 128bit nonce, instead of a 32bit counter + 96bit nonce?

Does the counter at position of 13th byte actually increment by one? Can I extract the number of iterations from the state of ChaCha20? From the specification, Id say that the state gets randomized after as much as one iteration.

This brings me to a 2nd question - if it is customary to set counter to 0 or 1, we can consider this is public. Does this mean then that nonce can also be made public (just like IV for block ciphers) without compromising the security? (of course provided that key stays confidential)

Thank you all for answers!

You seem a bit confused about how the various parts of the ChaCha20 cipher actually fit together, so let me start from the top down and see if I can clarify things.

At the highest level, the ChaCha20 encryption algorithm is a synchronous stream cipher: given a secret key and a (possibly) public nonce, it generates a pseudorandom keystream which is bitwise XORed with the message to be encrypted.  Repeating this process (i.e. XORing the encrypted message with the same pseudorandom bitstream again) then lets the receiver reveal the original message again.

(The purpose of the secret key is to ensure that no-one else can generate the same keystream, and thus decrypt the messages.  The purpose of the nonce is to ensure that we never use the same keystream for encrypting two different messages, since that would allow an attacker to cancel out the keystream by XORing the encrypted messages together, leaving them with the bitwise XOR of the original plaintext messages.  So, no, the nonce doesn't need to be secret — all it needs to be is unique.)

The keystream is generated by concatenating a sequence of 512-bit blocks, each of which is generated by applying the ChaCha20 block function to an initial 512-bit input block consisting of the key, the nonce, a block counter and a fixed 128-bit constant.  The reason why the block counter is needed is because the ChaCha20 block function is deterministic, and would thus always produce the same output block if given the same input.  We don't want the keystream to consist of just the same 512-bit block repeated over and over, so we include a counter in the input block to make sure that every input to the ChaCha20 block function is different.

(This is essentially the same as the CTR mode construction for making a synchronous stream cipher out of a block cipher, except with the ChaCha20 block function used in place of the block cipher.)

Finally, going one level deeper yet, the ChaCha20 block function scrambles its input by iteratively applying 10 "column rounds" and 10 "diagonal rounds" to it, in alternating order (and then finally XORing the scrambled result with the original input to make the whole thing non-reversible).  Each of these column rounds and diagonal rounds, in turn, consist of four (possibly) parallel applications of the ChaCha20 quarter round  function, which takes a 128-bit slice of the full 512-bit block and scrambles it in a particular way, as described in the linked RFC.

All that iterated scrambling ensures that even tiny changes to the input block (like, say, incrementing the block counter by one) will cause the output of the block function to look completely different.  Thus, even though the successive inputs to the block function for any given message are all the same except for the counter, the keystream obtained by concatenating the scrambled output blocks is effectively indistinguishable from random, unless one knows all the inputs that went into generating it (including, in particular, the secret key).

Of course, to deterministically generate the keystream from a given key and a nonce, we need to decide how to choose the initial counter value for the first block, and how to increment it for the later blocks.  (If we don't do it consistently when encrypting and decrypting, the keystreams will be different and we won't get the original message back!)  The obvious choice would be to number the blocks consecutively as 0, 1, 2, 3, 4, …, but in principle other methods could work just as well.

Indeed, the RFC you linked to describes the ChaCha20 encryption algorithm as taking the initial counter value as an input, in addition to the key, the nonce and the message to be encrypted (or decrypted), and describes it as follows:

  A 32-bit initial counter.  This can be set to any number, but will
    usually be zero or one.  It makes sense to use one if we use the
    zero block for something else, such as generating a one-time
    authenticator key as part of an AEAD algorithm.

Note that this is the initial counter value, used to generate the first 512-bit block of keystream, and incremented by one for every subsequent block.  So if the initial counter value is set to 0, the blocks will be numbered as 0, 1, 2, 3, 4, …, whereas if it's set to 1, the blocks will be numbered 1, 2, 3, 4, 5, … instead.

So why would you choose to set the initial counter value to something other than 0?  Well, probably because you want to start the keystream at some later block number, e.g. because you already used block 0 for something else.

In particular, the AEAD_CHACHA20_POLY1305 authenticated encryption scheme works by using block 0 of the ChaCha20 keystream to generate the one-time Poly1305 key for protecting the integrity of the encrypted message, and then using the rest of the keystream starting from block 1 to actually encrypt the message as described above.

It is still unclear to me what the function of counter is. Why not just use larger 128bit nonce, instead of a 32bit counter + 96bit nonce?

Technically you could, but only a constantly repetative key stream would pop out.  As you imply, you could make the block function iteratable so what you would be doing is simply repeating the function with no further inputs, like  $ state_{n+1} \leftarrow  \operatorname{ChaCha}(state_{n})  $.  There would be a (small) risk that a cycle developed $j$ iterations long, and you got another repetitive output.  Perhaps $ \operatorname{ChaCha}(\operatorname{ChaCha}(state))= state  $ with $j=2$. This would be disastrous.

The possibility of a cycle/fixed point is avoided by the inclusion of a counter. It's a mitigation to increase the security bounds over an pure iterated construct such as OFB mode. Have counter, have smaller nonce to fit.
 You see exactly the same principle in AES & SHA CSPRNGs and CTR mode encryption. There's further similar discussion at Why is there a counter in CSPRNGs? as they and stream ciphers are not a million miles apart.

It also allows you to position the key stream arbitrarily in $O(1)$ time, but not all constructs require that.


How are one-time pads distributed? It seems that OTP encryption is unbreakable. I have read some articles (Wikipedia, Blogpost, etc.), but I could not find any information about how they are used.

If I wanted to create a messenger service, how would I distribute the OTP keys? Both the sender and the receiver need this key before the message is sent, right?

And how do I make sure no one else gets these keys?

If you perform the distribution digitally (using networks) then you have a problem. Unless you use another one time pad you lose the perfect confidentiality as the distribution itself won't deliver perfect security. But using another one time pad is pointless: you would lose exactly as many key bits as you are distributing, while you are only protecting the data for confidentiality, not integrity and authenticity.

So basically you'll probably have to physically distribute the keys. That kind of burden is probably not very useful. Hence we mostly treat the one time pad as a theoretical cipher. One very big reason for this is that - although not proven secure - there are many (stream) ciphers that are thought to be secure. There is simply no need for a one time pad.

So the key management / key distribution is extremely awkward for one-time-pads not just because of the size, but also because anything you do with the key breaks the perfect secrecy you are trying to achieve.

Your question is now 4 1/2  years old, and things have moved on for pad distribution (at least in the professional arena).  Hobbyists are still stuck with pigeons and USB drives secreted about their bodies, having clandestine meetings and physically exchanging bits.

Professionally, there are an ever increasing number of quantum key distribution networks (QKDNs) which send the OTP material via laser beams.  In essence it happens like the following, with ALICE beaming her true random bits from her TRNG (typically a beam splitter) to BOB:-

After some processing and validation, BOB and ALICE are both in possession of key material suitable for OTP use. Voilà.

And as for "how do I make sure no one else gets these keys?" It doesn't matter. The distribution of the photonic based keys is governed by the Observer effect which means that in an ideal QKDN, if nasty EVE reads the photons, ALICE/BOB will be able to tell as their polarisations will have changed. They then invalidate that particular key transmission and redistribute. There are more nuances to QKDNs than punched paper tape distribution used to have, but essentially the focus of trust shifts from the courier to the QKDN provider.

Image is an extract from a longer answer...


How to quickly detect incorrect password in encrypted file without compromising security? I am developing a software to encrypt/decrypt files/streams using symmetrical encryption algorithm. During encryption phase data wil be compressed and encrypted.

When decrypting data, I want to be able to check whether supplied password is correct. For that purpose encrypted file contains header (which I would like to keep as small as possible), where some signature derived from password is going to be stored.

There are several condition that must be met:

A. Password checking must be as fast as possible and it should not require excessive CPU/memory resources. Risk of using weak/guessable password is NOT present as we declare in advance that only secure, long, random passwords are going to be used for encryption.

B. If we encrypt the same plaintext file twice with the same password, the header and encrypted text must not be the same.

I assume that a theoretical attacker has complete source code of my software. The one and only thing that the attacker does NOT have is password.
My question is - what kind of signature should I use so the security is not compromised?

Here are possible options that I was thinking about and my commentary to them:

Password hash (SHA, MD5, etc.). Probably not a good idea because of risk of precomputed dictionary attacks.
Hash of the salted password. Salt is going to be generated using pseudo-random number generator (PRNG). The initial seed of the PRNG is derived from the password. I suspect this won't help at all since we know that the attacker has access to the source code - so the attacker will always be able to generate salt for the given password and, hence, generate the hash. Then the attacker can write proprietary software which will be able to perform dictionary attack agains files encrypted with my software using our own hash-generating algorithm.
Using key derivation function (KDF), like PBKDF2. This does not meet condition A, because all good key derivation functions should deliberately use excessive CPU/memory resources.
Using HMAC. I am not very good at understanding HMAC, but I think that in this case HMAC would not be used for what it was designed. I don't need to verify integrity of the password AND the encrypted file (or, in cryptographical terms, key and the message). I just need to verify whether the password is correct.
Other options?

I would be grateful if someone who understands cryptography better than me could give me some ideas or comments.

This is a perfect job for a Key Based Key Derivation Function or KBKDF. Generate two keys from the input (salt and password). One is stored directly in front of the ciphertext and one is used as encryption key. Because the KBKDF is based on PRF it cannot be reverted, so the keys are not related as far as an attacker is concerned.

Currently the best KDF is arguably HKDF. It contains both an extract functionality (to handle long passwords) and can take a salt and OtherInfo structure as input. The OtherInfo can be used for inserting an ASCII string identifying the key, e.g. "KCV" (key check value) and "ENC" (encryption). It is possible to derive the IV by using "IV" of course, in case the salt is already random for each encryption. You may want to perform only one extract and three expands of HKDF.

I would strongly recommend authenticated encryption. Make sure you use a fresh salt for each encryption procedure.

This is an addition to the answer of Maarten Bodewes. I have found RNCryptor, which is file encryption/decryption utility. IMHO, anyone who is trying to solve problems similar to mine (checking passwords, encrypting files) will benefit from studying algorithm and specification of encryption/decryption process of RNCryptor. Not sure what would cryptography experts would say about their algorithm, but it looks good to me - at least for the task I am trying to solve.


Why is the rand() function in C not a cryptographic pseudo-random generator? For example, one of the possible rand() implementations：

int rand_r (unsigned int *seed)
{
    unsigned int next = *seed;
    int result;
    next *= 1103515245;
    next += 12345;
    result = (unsigned int) (next / 65536) % 2048;
    next *= 1103515245;
    next += 12345;
    result <<= 10;
    result ^= (unsigned int) (next / 65536) % 1024;
    next *= 1103515245;
    next += 12345;
    result <<= 10;
    result ^= (unsigned int) (next / 65536) % 1024;
    *seed = next;
    return result;
  }

How to proof that it is not a pseudo-random generator?

This is a Pseudo Random Number Generator, but not a Cryptographically Secure PRNG, which requires that the output is undistinguishable from random for one not knowing the initial *seed.

One problem is, the effective state is very small: 27 bits at most (or less, limited by the size of int), because only the 27 low-order bits of the input *seed ever have a chance to influence either result or the low-order 27 bits of the output *seed. That alone limits the generator to 27-bit security, which is not enough (40-bit was already low security down in the 1980's). Also, this small effective state limits the period to $2^{27}$ (about 134 million), which is not enough even for simulation purposes.

Worse, one 31 bit output result is (at least, most likely) enough to easily reconstruct the full state *seed on output and then trivially predict future output, a total disaster for a CSPRNG. One simple method for that is: enumerate the $2^{16}$ possible values of the low 16 bits of next in the line result = (unsigned int) (next / 65536) % 2048;, and deduce the other 11 meaningful bits of next as result>>20; then check that guess of next against the 20 lower bits of result by replicating what the code does. We are down to 16-bit security, and that could be brought further down.

Walking back and computing previous output is trivial, too. The low 27 bits of *seed are transformed by three iterations of the linear $x\mapsto a\;x+b\bmod2^{27}$ with $a=1103515245$ and $b=12345$, giving $x\mapsto y=c\;x+d\bmod2^{27}$ with $c=a^3\bmod2^{27}=8240309$ and $d=117712863$ determined from $x=0$. And that is inverted as $x=e\;y+f$ with $e=c^{-1}\bmod2^{27}=70668701$ and $f=80477501$ determined from $x=0$.

The problems are these are "linear" to be total period.. use nonlinear instead.
A total period rng needs variable size 1, reversible rng needs variable size 2, nonreversible needs size 3 but must scramble all at once or be internally reversible.
Entropy must move freely in one direction per the integer noerrortrap unsigned multiply but also the other direction.  So to give you a specific function I need you to tell me the C language instruction for the machine language instruction to do that
The a = a × b : b = b xor a obviously has trouble with a or b being 0, so either have both odd or a = a xor b × c  etc
The output function to produce result range 0 to n-1 should not be separate but use that as a rng.
If 32b × 32b → 64b then xor upper half with lower, if float × with integer × I'd prefer 2 64 bit floats to one 32 bit integer and one 64 bit float so just xor lower half to upper half

?
Entropy must move freely in one direction per the integer noerrortrap unsigned multiply but also the other direction. So to give you a specific function I need you to tell me the C language instruction for the machine language instruction to do that???


Can an AES-GCM be cracked if the key is known but the nonce isn't? I'm kind of new in this field and I've been trying to learn it.

I'm now facing an issue where I have a couple of packages encrypted with AES-128 GCM and I have the key that was used to encrypt these packages. However, I dont know the nonce or the H.

Is there any way for these packages to be decrypted? or is the nonce not being known keeping them safe in a case like this?

Would appreciate all help. Thanks a lot!

You'll have to guess the plaintext of at least one block (128 bits) that is on a 128 bit boundary from the start of the GCM ciphertext. Then you can XOR it to retrieve 128 bits of the key stream.

Now the key stream you can decrypt since you have the key. This will get you a counter value. The counter in GCM mode starts with a 12 byte nonce and the counter as four bytes: 00000002 in hexadecimals. Once you have that nonce you can generate all the other required nonce + counter values.

So yes, it is possible, but only if you can guess at least one block of the plaintext.

If, by H, you are referring to the hash key (used to create the tag), it is generated by encrypting an all-zeros block with the encryption key.  So it is no trouble to regenerate that.  But to recover the nonce (or often called the IV (Initial Vector)), I think only Maarten's answer will work.  I believe the IV is sent in-the-clear during a key exchange, so if there was a key exchange and you had that data, it may be possible to retrieve the IV from that.