Recommendation of lightweight RNG for Miller-Rabin primality test Miller-Rabin tests the compositeness of candidate numbers (hence, input $x$) that's often used as a primality test.
The M-R test requires different random numbers for accuracy and confidence in the primality of $x$. To obtain such random numbers, I want to obtain them from a lightweight embeddable RNG, instead of a CSPRNG implemented elsewhere in my project.
So Q1: what's the minimal set of requirements for an RNG for use in M-R test, in addition to guarantee of distinct dissimilar output?
Now. The way I intend to use the RNG, is to seed it with the entire value of $x$ with an additional nonce (64-bit maximum) that's input to the M-R test routine. This means the RNG should be able to accept variable-sized seed, and an additional nonce.
An additional property I desire, is that it have a small state, for example, 128-bit if such implementation is possible and optimally efficient (I would consider slightly larger states if it's more efficient).
So Q2: is there a an existing RNG that meets the criteria (~128-bit state, variable-length seed, nonce)? And preferablely one that's based on one of those from the on-going NIST Lightweight Cryptography Project?
If not, Q3: what commonly-used constructs (LFSR, anti-circular bit-patterns) can I use to design a suitable RNG?

Last-minute clarification
When I say "embeddable", I mean incorporating the RNG code into that for the implementation of the M-R test.
And I'm not asking about RNG for generating RSA primes, I'm asking about a small RNG for use inside M-R test.

Secure embedded TRNGs are difficult
In an embedded system where the adversary is assumed to control the environment of the Target of Evaluation¹, like a Smart Card, making a TRNG is notoriously tricky. It's hard to ensure the output is truly unpredicatable.
When there is a hardware source, one line of attack freezes it, either literally (thru evaporation of a liquefied gas, lowering temperature thus reducing thermal noise and offsetting the comparator that translates noise to bits) or by other means (e.g. shorting the source's digital output line). A standard countermeasure tests if the source's output is "random enough", before feeding the output of that to a (CS)PRNG (it's pointless to test the output of a CSPRNG). It's difficult to make that test sensitive enough for security, satisfying evaluators, yet not degenerate into unacceptable field failure rate. And it might not be enough against more sophisticated attacks (I can vaguely imagine an adversary modulating the power supply to control the source's output, making it pass the source test, yet control the input of the CSPRNG, thus its output. And that naturally occurring conditions could have the same effect, perhaps explaining this embarrassing disaster).
For these reasons, only a fool, or one operating under pressure to deliver something good enough to pass a poorly designed test, would rely only on hardware source + source test + CSPRNG. It's best to add two ingredients to the mix:

A secret key, injected at manufacturing, that is fed into the CSPRNG. When that remains secret, and all else except the CSPRNG itself fails, at least the output of the CSPRNG is secret until it leaks by other means.
A counter in permanent memory, fed into the CSPRNG. When all else except the CSPRNG itself fails, at least the output of the CSPRNG is not reproducible from one power-on cycle to the next. Problem is making the counter demonstrably resisting power cut at that wrong moment (decided by the adversary, or it's common substitute Murphy). It's hard, or even impossible depending on hardware.

But do we need a TRNG for a Miller-Rabin primality test?
If we have to abide by some diktat standard mandating that a TRNG is used for the bases of the Miller-Rabin primality test, resistance is futile and we need a TRNG, see above. I disregard that in the rest of this answer.

what's the minimal set of requirements for an RNG for use in M-R test?

When we disregard the issue of side channels, it's sufficient that its output is unpredictable by whoever generates the candidate prime prior to that generation, and about uniform. That's not even necessary, see first bullet below.
We can do without a TRNG when at least one of the following holds:

We generated the candidate prime with a procedure we trust to produce random candidates, as must be the case for RSA key generation²: a fixed set of bases will do (under plausible mathematical conjectures). Yes, a 1024-bit integer known to have been generated at random in $[2^{1023.5},2^{1024}]$ that further passes MR to bases $\{2,3,5\}$ is prime with probability of the contrary less than $2^{-80}$, that is certainty in all except mathematical circles. And for added hope of getting rubber-stamped confidence, we can generate the bases with a public CSPRNG seeded with the prime tested.
We have a secret at hand: a CSPRNG seeded with that secret and the prime tested will demonstrably do, even if we are validating³ the primality of an externally supplied prime candidate intended for an RSA moduli.

Wrapping it up: for an MR-test built into the generator, using fixed bases $\{2,3,5\}$ is enough for 1024-bit or more; and using about any sound generator seeded by the integer tested (and negligible or zero probability that two bases are identical) is ample. For an independent MR test, use such generator seeded with a secret and the integer tested.

¹ I'm using Common Criteria vocabulary to make it look like I'm familiar with it. That's common trickery.
² In this case, we can do with a very small number of MR base. See FIPS 186‑4 appendix F.1, or earlier table C.1, which boils down to: 3 bases will do for primes at least 1024‑bit (when we disregard the issue of strong primes, which is common practice, and reasonable at least for two-factors RSA with primes at least 1024‑bit).
³ In this case we need more MR bases, and I know no much better bound than at least $k/2$ tests for $2^{-k}$ residual probability that a composite creeps.


Is HMAC needed for a SHA-3 based MAC? HMAC does nested hashing in order to prevent Length Extension Attacks.

Given that you use the SHA-3 hash (which is resistant against length extension attacks), would you still need to go through that procedure in order to produce a secure MAC?

Needless to say we'd still use a key, which we prepend or append to the message, but is that sufficient for a MAC?

Given that you use the SHA-3 hash (which is resistant against length extension attacks), would you still need to go through that procedure in order to produce a secure MAC?

No, you don't need to do that, but you can.

  Needless to say we'd still use a key, which we prepend or append to the message, but is that sufficient for a MAC?

Yes, you can prepend the message with the key, i.e. use $H(K||M)$.

Quoting the Keccak (SHA3) website:

  Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.

However, the original standard does not specify this MAC mode, only a hash function.

There is now a specification (pdf) of KMAC (and other constructions) based on SHA-3, or specifically the SHAKE extendable output functions. The changes from "prepend key to message" are key padding as well as the inclusion of constants and the output length, which are all done for domain separation.

It is possible to implement KMAC in this form using SHAKE128/SHAKE256 but not using the other SHA-3 variants.


Security trade-off when using low number of rounds with SHA256 I have a web application that stores hashed password reset tokens in a database table. The tokens are randomly generated 256-bit values. I'm currently using Python's passlib sha256_crypt function to hash the tokens which defaults to using 535000 rounds.

In order to speed up the hash computation, I'd like to decrease the number of rounds that the sha256_crypt function uses going forward. Passlib allows you to choose a rounds value between 1000 and 999999999, inclusive. Given that I'm hashing random 256-bit values, would it be safe for me to decrease the number of rounds to as low as 1000? Would there be any serious security trade-off from doing so?

As described in the comment, lets assume the password reset tokens is one-time token generated when a user requests its password.

The PBKDF (salt hashing in the loops) is used to make the password guessing much more expensive in case the database is compromised. The whole problem of PBKDF is based on observation that the user passwords are having low entropy.

  Given that I'm hashing random 256-bit values, would it be safe for me to decrease the number of rounds to as low as 1000?

Lets assume that the password reset token is plain.
The worst case what can happend is that the attacker (having read access) could reuse an existing reset token or create a new one (requesting a new password).

So you need some hashing to hide the original token value, but if the reset token is having enought entropy (is random and long enough) you would be ok with a simple hash. The length and randomness would deny the dictionary guessing process instead of expensive PBKDF function.


Can poly1305 be used as an error-correction code? Given a message $m$ of size $n$, a key $k$, and a message authentication code $mac = poly1305(m, k)$ what is the minimum amount of bitflips on the message that can be corrected (or at least detected) by someone who knows the corrupt message, the mac code, and the key?

what is the minimum amount of bitflips on the message that can be corrected

Zero bits, Poly1305 doesn't provide error correction (at least Bernstein doesn't claim that property in the original paper).

  (or at least detected) by someone who knows the corrupt message, the mac code, and the key?

One bitflip is already detectable, it will change all bits of the resulting hash with a 0.5 chance.

Of course, there is always a negligible chance that the data does result in the correct hash (a chance of 1 in $2^{128}$ for the full MAC output). However, that's not dependent on how many bits are flipped.

Generally, it is recommended to keep the full output of the MAC calculation as an authentication tag.

If you also want error correction against changes, you could include a block of error-correcting code over the message + authentication tag. That way both are protected against non-malicious changes. Or you could use a specialized MAC algorithm as indicated within your own comment.

Personally I don't see a direct way to add error correction capabilities to the Poly1305 calculations, but I'm not the best person to indicate if that's possible.


Why can't we reverse hashes? First off, I know hashes are 1 way. There are an infinite number of inputs that can result in the same hash output. Why can't we take a hash and convert it to an equivalent string that can be hashed back to the original hash output?

eg:

string: "Hello World"
hashed: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e

unhash: "rtjwwm689phrw96kvo48rm64unc8oetb5kmrjiuh7h8huhi6dde5n5"
        (a real string that gives the same hash as "Hello World")
hashed: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e

...

Take a simple mathematical operation like addition. Addition takes 2 inputs and produces 1 output (the sum of the two inputs). If you know the 2 inputs, the output is easy to calculate - and there's only one answer.
321 + 607 = 928
But if you only know the output, how do you know what the two inputs are?
928 = 119 + 809
928 = 680 + 248
928 = 1 + 927
...

Now you might think that it doesn't matter - if the two inputs sum to the correct value, then they must be correct. But no.
What happens in a real hash function is that hundreds of one-way operations take place sequentially and the results from earlier operations are used in later operations. So when you try to reverse it (and guess the two inputs in a later stage), the only way to tell if the numbers you are guessing are correct is to work all the way back through the hash algorithm.
If you start guessing numbers (in the later stages) wrong, you'll end up with an inconsistency in the earlier stages (like 2 + 2 = 53). And you can't solve it by trial and error, because there are simply too many combinations to guess (more than atoms in the known universe, etc)
In summary, hashing algorithms are specifically designed to perform lots of one-way operations in order to end up with a result that cannot be calculated backwards.
Update
Since this question seems to have attracted some attention, I thought I'd list a few more of the features hashing algorithms
use and how they help to make it non-reversible. (As above, these are basic explanations and if you really want to understand, Wikipedia is your friend).

Bit dependency: A hash algorithm is designed to ensure that each bit of the output is dependent upon every bit in the input. This prevents anyone from splitting the algorithm up and trying to reverse calculate an input from each bit of the output hash separately.
In order to solve just one output bit, you have to know the entire input. In other words, when reversing a hash, it's all or nothing.

Avalanching: Related to bit dependency, a change in a single bit in the input (from 0 to 1 or vice-versa) is designed to
result in a huge change in the internal state of the algorithm and of the final hash value. Since the output changes so dramatically with each input bit change, this stops people from building up relationships between inputs and outputs (or parts thereof).

Non-linearity: Hashing algorithms always contain non-linear operations - this prevents people from using linear algebra techniques
to "solve" the input from a given output. Note the addition example I use above is a linear operation; building a hash algorithm using
just addition operators is a really bad idea! In reality, hashing algorithms use many combinations of linear and non-linear operations.

All of this adds up to a situation where the easiest way of finding a matching hash is just to guess a different input, hash it and see if it matches.
Lastly, if you really want to know how hard reversing a hash is, there's no better substitute than just trying it out for yourself.
All good hashing algorithms are openly published and you can find plenty of code samples. Take one and try to code a version that reverses each step; you'll quickly discover why it's so hard.


Steganography in speech by adding extra "filler" syllables PREAMBLE

About 20 years ago, when reading a novel (set in late 1800) by some classic Russian writer I came across very curious example of steganography. The two main characters were peasants who got lost in the woods. Suddenly they come across wood cabin where a very dodgy forester lives. They have no other choice but to accept his "hospitable invitation" and stay in his cabin for the night. All three are in the same room in the cabin, but as they're scared of him harming them, they try to discuss between themselves a plan of how can they protect themselves. As their conversation happens "in the open" of the cabin room, they have to somehow ensure that the forester doesn't understand them.

THE STEGANOGRAPHY TRICK

Alice, Bob and Charlie all speak same language and are in the same room. But Alice and Bob do not want Charlie to be able to understand them, so they start speaking in this "steganographic variation" of their language. Method is simple: after every syllable they add an extra syllable "pa" or "la". (For simplicity I will use  Spanish language as example 'cos it has very syllabic and phonetic nature and you pronounce same way as you spell).

So for example:

HOLA would turn into HOpaLApa
or hopalapa!

AMIGO would turn into AlaMIlaGOla
or alamilagola!

(I don't think there were strict rules on when to put "la" or "pa", so speaker decides on the filler syllalble as he goes. Thus AMIGO can equally turn into ApaMIlaGOpa apamilagopa

Then a conversation

Hola Amigo!
Quiero una cerveza por favor.

Will turn into

Hopalapa Alamilagola!
Quieparopa ulanala cerlavelazala papor fapa

This method seems very interesting and I never ever had heard of such an approach ever again. Neither ever met anyone who had heard about it. Meanwhile, there's few amazing things about this method: from little practice I did, it seems that learning curve to be able to speak that way and to be able to understand this kind if speech is not very steep (maybe a week to master). Which makes sense - as peasants with little to no education in 1800ds would need a low barrier of entry into steganographic method. Of course when spelled out on paper and when meaningful syllables are capitalized, this method seems to be trivial, but when speaking - an untrained ear can't understand a word.

So I wonder if anyone has ever heard of this (or similar) method or any accounts in another cultures, languages or environments?

ps. I am not sure whether this method can apply well to English, because it is not as "syllabic" and "sing-a-songy" like languages like Spanish, Italian, Portuguese, Russian and pronunciation varies very strongly region to region.

To the extent that I think this is a cryptographic question (which I don't!), I don't think these language games qualify as steganography.  Steganography conceals the existence of a message by encoding it into (hopefully) undetectable modulations of another message, which is meant to appear innocuous to an adversary.  As Wikipedia puts it:

  The advantage of steganography over cryptography alone is that the intended secret message does not attract attention to itself as an object of scrutiny. Plainly visible encrypted messages—no matter how unbreakable—arouse interest, and may in themselves be incriminating in countries where encryption is illegal. Thus, whereas cryptography is the practice of protecting the contents of a message alone, steganography is concerned with concealing the fact that a secret message is being sent, as well as concealing the contents of the message.

But languages games like Pig Latin or jeringonza don't generally fool adversaries into thinking that the message is innocuous.  Some of these games produce output that is linguistically very marked.  For example, Hola amigo is pronounced ['o la 'mi ɣo] (International Phonetic Alphabet; stressed syllables are prefixed with apostrophe as is standard), with broadly trochaic stress (LOUD-soft-LOUD-soft) as is typical of Spanish (default penultimate stress).  But Chi-ho chi-la chi-a chi-mi chi-go, as in the Caribbean variant of the jeringonza game, is strictly iambic (soft-LOUD-soft-LOUD): [tʃi 'o tʃi 'la tʃi 'a tʃi 'mi tʃi 'ɣo].  So this particular language game produces outputs that are systematically different from regular Spanish phonology.  Nobody's gonna mistake this for small talk about the weather.

And while I stress that I don't think these language games are properly cryptographic, if anything they often resemble ciphers more closely than steganography.  One capsule explanation of modern cryptography is that it achieves security by transforming messages using trapdoor functions—schemes where messages are transformed in ways that are cost-effective to honest parties but prohibitively expensive for adversaries.  And if you squint really hard these language games approximate that paradigm—they transform a message in a way that the ingroup has mastered through practice (dare I call this "precomputation"?) but the outgroup hasn't.


Derived keys usable by threshold signatures Suppose there are $n$ members in a $(t,n)$ threshold signature scheme. The global secret key $sk$ is not known to any single party, as the keys are generated distributed. The parties are able to construct their global public key $pk$. So each member $i$ can sign a message $m$ with their secret share $sk_{i}$ which will produce $sig_i$. All signatures shares can be combined to create $sig$ which is verifiable under $pk$.

Is there any key derivation function $f$, such that each member can produce derived keys $sk_i^1$,$sk_i^2$,$sk_i^3$,...$sk_i^n$, that will be able to fulfil the threshold scheme? E.g. every member signs $m'$ with $sk_i^1$ and the combined signature $sig^1$ is verifiable under $pk^1$ which is constructed from the shares $pk_i^1$.

There are two mainstream ways of doing this. Using Schnorr or BLS signatures. The Schnorr formulations are more complex, but if you are willing to use bilinear pairings, the BLS solution is straighforward to understand.

Assuming the existence of a set of Shamir's Secrets Shares $\{(x_i, y_i) \in \mathbb{F}^2_p: i \in [1, n] \cap \mathbb{Z}\}$, where the Lagrange interpolation $L(x) = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}(x)$ and $L(0) = y$ is the secret. Normally $x_i$ are public parameters and simplified to $x_i = i$.

Defining the bilinear pairing as $e: \mathbb{G}_1 \times \mathbb{G}_2 \mapsto \mathbb{F}^{*}_{p^{k}}$, in type-3 settings, and a hash-to-curve $H: \{0,1\}^* \mapsto \mathbb{G}_2$.

Also $y \times G \mapsto Y$ is the corresponding public key, with $G,Y \in \mathbb{G}_1 $.

The BLS signature is defined as:

$Sign(y, m) \mapsto \mathbb{G}_2$ with the output $y \times H(m) \mapsto S$

And verified with:

$Verif(Y, m) \mapsto \{0,1\}$, result in 1 if $e(Y, H(m)) = e(G, S)$

To transform this in a threshold scheme just apply the Lagrange interpolation directly:

$S = y \times H(m) = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}(x) \times H(m)$

From a client, you can collect $t+1$ partial signatures $y_{i} \times H(m)$ and interpolate to construct $S$. Verification is unchanged.

However, this simple procedure cannot prevent parties from sending wrong results $y^{'}_i \times H(m^{'})$. It can result in a valid signature for an unkwon message. Although this is not a big concern for most practical purposes, it's something you should be aware.


Are there any symmetric cryptosystems based on computational complexity assumptions? Are there any symmetric cryptosystems which are provably secure in the sense that there exists a reduction from their security to the hardness of some underlying hard problem such as integer factorisation?

If not, why not?

Finding uniform random $x$ given $x^3 \bmod{pq}$ for uniform random 1024-bit primes $p$ and $q$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.*
Finding uniform random $k$ given $\operatorname{AES256}_k(92187681)$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.

That said, the best estimates for the cost of (1) are much cheaper than the best estimates for (2), and the computation of $x^3 \bmod{pq}$ is much costlier than the computation of $\operatorname{AES256}_k(92187681)$.  In other words, RSA-2048 is much more expensive for less security than AES-256.

You might be tempted to say that the RSA problem is a more fundamental problem in number theory, and as such is the only one that's really a ‘hard problem’.  But it is precisely because RSA is embedded in a rich mathematical theory—as is needed for separate public key and private key operations!—that it is more vulnerable to attacks.  In reality, AES is a much harder problem than RSA!

There are many symmetric cryptosystems that use AES, and for which there is a theorem that breaking them can't be much easier than breaking AES, such as AES-GCM.  Similarly, there are many public-key cryptosystems that use the RSA trapdoor permutation, and for which there is a theorem that breaking them can't be much easier than inverting the RSA trapdoor permutation, like RSA-PSS and RSA-KEM.

The term ‘provable security’ means nothing more than there is a theorem.  These cryptosystems—AES-GCM, RSA-PSS, and RSA-KEM alike—all have ‘provable security’ because there is a theorem, not because of any mathematical theory around AES or RSA.  So does a 1-bit universal hashing authenticator have provable security, even though the amount of security it provides is so small an attacker will win with the probability of a fair coin toss coming up heads.

* Incidentally, while the RSA problem can't be harder than factorization, we don't have a proof that it can't be easier.  There is some weak evidence—a reduction in the generic ring model—but there's no theorem that if factoring is hard then the RSA problem is hard.  Hence not even the RSA problem has ‘provable security’ relative to factoring.


Secure hash function into $\mathbb{Z}_q$ Given the existence of a secure hash function $h: \{ 0,1 \}^* \rightarrow \{0,1\}^k$, how can I construct a secure hash function $h': \{ 0,1 \}^* \rightarrow \mathbb{Z}_q$ ?

Of course this is easy for $q=2^k$, as we can always see $\{ 0,1 \}^k$ as the set $\mathbb{Z}_{2^k}$, but what if $q$ is an arbitrary integer?

Thank you in advance.

You can define $ h' $ as $ h'(m) := h(m) \mod q $.

As long as $ 2^k $ is larger than $ q $ by e.g. 128 bits, the resulting function $ h' $ is (almost) equally distributed in $ \mathbb Z_q $.

For a suitable hashfunction $ h $ you might pick a SHA-3 with variable output size, like SHAKE256.


Is this cascading encryption, and is my security weakened as a result? I'm trying to understand what is, and what is not, considered cascading encryption. All of the posts and conversations I've read over the past few days discourage the practice, including this article. Unfortunately, I don't really understand the variables in the equations. So, I haven't found anything that appears to address the setup, scenarios, and concerns I have in mind.

What I think I know:

AES is a cipher, and there are no known weaknesses in the cipher.
GPG is a crypto suite (a.k.a., "the implementation"?), and there are no known backdoors or weaknesses
OS X Disk Utility is (or could be considered) a crypto suite (a.k.a., "the implementation"?), and I ASSUME there are no known backdoors or weaknesses
OS X Filevault 2 is (or could be considered) a crypto suite (a.k.a., "the implementation"?), and I ASSUME there are no known backdoors or weaknesses

Initial Assumptions and Questions:

Assumptions:

No known backdoors or weaknesses in the ciphers or crypto suites
AES (at least 128) is used exclusively
Each encrypted "thing" (file, disk image, disk) is encrypted with a UNIQUE, random passphrase of sufficient length
Passphrases will not be leaked (by accident, rubber-hose, etc.)
Computer is not currently compromised (no monitoring, keyloggers, etc.)

Questions:

Any single "thing" (file, disk image, disk)

encrypted with AES,
via any of the crypto suites above,
using a sufficiently long and random passphrase,
provides "good" security, yes?

A GPG-encrypted file exists inside a Disk Utility-encrypted disk image. The disk image is not decrypted (not mounted). A copy of the disk image is stolen by someone who is equally knowledgeable as you in security matters. Is the file less secure inside the disk image than if it existed outside the disk image? Is it more secure? Why?
A GPG-encrypted file exists inside a Disk Utility-encrypted disk image. The disk image is not decrypted (not mounted). The disk image exists on an FileVault 2-encrypted disk. The computer is turned off and so the disk is not mounted. The computer is stolen by someone who is equally knowledgeable as you in security matters. Is the file less secure inside the disk image, on that encrypted disk, than if it existed outside the disk image and on an unencrypted disk? Is it more secure? Why?

I will likely ask follow up questions.

I would not consider your case to be a cascading encryption. The reason why is the fact you need multiple interventions before getting access to your file.

Here is what I would consider a cascading encryption (let's go crazy) :
$$E(k_1,k_2,k_3,m) = \text{KEYAK}(k_1,\text{NORX}(k_2,\text{AES}(k_3,m)))$$
which you would decipher with :
$$E^{-1}(k_1,k_2,k_3,m) = \text{AES}^{-1}(k_3,\text{NORX}^{-1}(k_2,\text{KEYAK}^{-1}(k_1,m)))$$
All operations are done in a single go. One should not need to enter keys one after the other.

Considering your questions now.

As long as you use AES (supposed in the good mode of operation: i.e. not ECB) and under the assumption (3.) your files should be secure as long as the key is not leaked.

In the case of GPG, I suppose you meant to use it in a asymmetric mode (the symmetric case fall under the previous assumption are it will generally use AES).
For larges files GPG generally generate a random decryption key $K_D$, encrypt the files with AES and this key $K_D$, encrypt $K_D$ with the public key, therefore we are sort of back to point (1.) but with a asymmetric key.
I suppose your file to be already encrypted. If your disk image is encrypted therefore yes it will be more secure as just finding the file : you need to decipher the disk before getting access to the file... However, if your file is encrypted with the same algorithm as the one used to encrypt your file. If the first one is broken, expect the second to be the same (meet-in-the-middle... ).
Same idea as in 2...

However what you should really consider is the fact that nowadays cryptography does not work that way. Assuming that the attacker has only access to the cipher text is assuming a very weak attacker.

Academics assume strong attackers : he has control over the plaintext, ciphertext and can ask for any part to be encrypted / decrypted. The only thing he does not have access is the key. The goal here is to retrieve the key. This is usually illustrated by the lunchtime attack.


Generating PGP key *without* random generator? (using fixed input only) I understand why in general, a strong random generator or source of entropy is used when generating PGP keys.

However, I have a use case where I want to generate PGP keys deterministically, i.e. based on certain fixed input, so that the same input will always result in the same PGP key.

Basically what I want is: instead of using 'real' random data, I want to generate the key from hash(passphrase), which can be considered pseudorandom data. Which will suit the purpose just as well, except this way I can regenerate the PGP key from just a passphrase.

Is there a solution that does this already, or would that involve messing with existing PGP software, and replacing their use of RNGs with my own source of entropy?

Yes, this could be done.  It would be easy to implement and use this in a way that would be horribly insecure (e.g. with too short a passphrase, and not enough key stretching), but if used carefully, it could even be secure.

Basically, what you'd do would be:

Generate a secure passphrase, e.g. a sequence of randomly chosen words.  This can be done separately from the other steps.  The passphrase needs to contain enough entropy that it cannot be guessed by brute force using currently available or foreseeable technology.  I'd say that means at least 80 bits (≈ 7 or 8 words at 10 to 12 bits/word), but you might want to go for up to 128 bits or so if you're feeling paranoid.  Double your estimate if you're worried about quantum computers becoming practical.
Use a key stretching KDF to convert the passphrase into a pseudorandom seed (of sufficient length; I'd say at least 256 bits).  The PGP standard already includes such a KDF (RFC 4880 § 3.7.1.3, Iterated and Salted S2K), but something like scrypt would be even better.  You can't use a random salt, because you want deterministic output based on the passphrase only, but you should still be able to get around 20 to 30 bits of effective extra resistance to brute force attacks (letting you use a somewhat shorter passphrase, and/or have a wider security margin) with little noticeable slowdown in normal use.
Use the output of the KDF as the seed to a deterministic PRNG, and use the PRNG as the randomness source for the key generation algorithm.
Optionally, temporarily store the generated key in memory (e.g. through the use of a background agent program) to avoid having to repeatedly retype the passphrase.

Note that all the parameters for steps 2–4 (other than the passphrase) need to be either fixed or specified by the user.  In particular, this includes the KDF and PRNG algorithms and any subcomponents (e.g. hash function) and adjustable parameters (e.g. iteration count) they may use, as well as the method used to generate the key.

Some variation, e.g. in the details of primality testing for RSA key generation, may be tolerable, provided that it has no more than a negligible probability of affecting the output, but other changes (e.g. anything the affects the order in which candidate primes for RSA are generated and tested) are likely to cause the same passphrase to no longer yield the same key.  In particular, this means that it would probably not be a good idea to rely on any third-party PRNGs or key generation code whose internal implementation might change, and that any implementation should be accompanied by a detailed unit test suite to detect any changes in behavior.

I'm not personally aware of any existing programs that would support something like this, but there are open-source PGP implementations (like GnuPG) out there, so if you wanted to write one yourself, at least you wouldn't have to implement the whole PGP standard from scratch.


Formal definition PRNG I tried to look for a book that presents cryptographic concepts(specially PRNG) in a formal way but what I find is an intuitive approach. So my question is what is the formal definition of Psuedo-random-number-generator(PRNG) or function?

If we call $U_k$ the random variable uniformly distributed over bit strings of length $k$, then a function $g: \{0,1\}^k \to \{0,1\}^m$ is called pseudo-random generator if no feasible(poly-time if you want) algorithm can distinguish $g(U_k)$ and $U_m$ with non-negligible probability.

More formally let $U'_m = g(U_k)$ then the distinguishing advantage of any distinguisher efficient $D$ that we denote as $\Delta^D(U'_m, U_m) = Pr^{DU_m}[Z = 1] - Pr^{DU'_m}[Z = 1]$ is negligible.

Here $Z$ is the output of the distinguisher, and negligible is any suitable notion of "really small"; same for efficient.


Searching for a differential characteristic (differential cryptanalysis) Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.

I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.

So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.

Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher  and produce related output differential(Δo).

Δx = X' xor X'' =>

                Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]

                 =[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]

We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).

As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.

In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):

choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.
** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.

-Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:

          -Each SBox has differential property and should  affect in
           each round in the differential characteristic when it is
           activated.

          -Multiply calculated probabilities by the prior probability in
           order to finding  rounds differential characteristics.

A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf


Confused about how chosen ciphertext attacks work? When performing a CCA, the adversary gets the public key. At some point, he will send a message m to the challenger, and the challenger will send back either $E_{pk}(m)$ or $E_{pk}(r)$, where r is some random string of same length as m. The goal of the adversary is now to guess which one the challenger sends back. However, the adversary already has the pk, so why can't he himself not just encrypt his message and check if it fits with the one he got back?

The adversary clearly can do that. But if the adversary wins with this strategy, then the scheme in question cannot even be CPA secure and is far away from reaching the goal desired from CCA security. Recall, CCA security requires that even having access to a decryption oracle (for any ciphertext but the challenge ciphertext) does not help the adversary.


NIST 800-90B /Non-IID track - min-entropy result > 8 for 8-bit symbol I'm conducting an analyisis of noise sources based on the NIST 800-90B Non-IID track.
Accordingly, I applied the non-iidmain.py script on a datarecord, which delivered the following output:

reading 1000000 bytes of data
Read in file ../some_data_rec.bin, 1000000 bytes long.
Dataset: 1000000 8-bit symbols, 256 symbols in alphabet.
Output symbol values: min = 0, max = 255

Running entropic statistic estimates:
- Most Common Value Estimate: p(max) = 0.00424421, min-entropy = 7.88029
- Collision Estimate: p(max) = 0.0119504, min-entropy = 6.3868
- Markov Estimate (map 6 bits): p(max) = 9.06705e-222, min-entropy = 5.73662
- Compression Estimate: p(max) = 0.00790364, min-entropy = 6.98327
- t-Tuple Estimate: p(max) = 0.006, min-entropy = 7.38082
- LRS Estimate: p(max) = 0.00389867, min-entropy = 8.0028
....

What I am wondering is the output for the LRS Estimate which delivers a min-entropy of 8.0028.
The symbols in alphabet are defined at 256 i.e. one byte.
So how is it possible a single symbol at one byte/8 bit is able to deliver more entropy than it is able to describe?
I expected the maximum entropy value for one byte should be 8 bit?

There are three separate reasonable questions here.

What does LRS Estimate mean?
Does the software compute it correctly?
Are stupid entropy estimation tools like this useful for your goal?

The setting is that we hypothesize specific families of generating processes for the data that came out of a black box.  The families of generating processes are all quite simple-minded.  For example:

A gremlin in the black box rolls a 256-sided die with unknown face probabilities $p_i$ independently for each octet in the string.
A gremlin in the black box emits outputs from unknown states by a hidden Markov model with unknown emission probabilities $e_i$ and transition probabilities $t_{ij}$.

Each of these models has a certain measure of min-entropy that is determined by the choices of parameters, such as the $p_i$.  The NIST tool, like any other entropy estimation tool, estimates the min-entropy by fitting parameters and evaluating or estimating an upper bound on the min-entropy in the specific case of the model with the parameters it fit.  Obviously 8.0028 is an upper bound on the min-entropy of an octet.  How do we get there?

To address (1), what the LRS Estimate means, the LRS estimator posits a generating process something like this:

A gremlin inside the black box has a hat with $d$ strings of varying lengths on it, the $i^{\mathit{th}}$ string having $n_i$ copies.  It shuffles the hat and draws a string out to add to the output; then it repeats.

The estimator works by guessing a few strings that might be in the hat based on repeating and nonrepeating contiguous substrings in the data, and uses the frequency of those strings as an estimate for the probability that they will occur.  (The complete details of the computation are in NIST SP800 90A, §6.3.6.)  From those probabilities it yields an estimate of the min-entropy using the standard $-\max_i \log p_i$ formula.

It doesn't consider all contiguous substrings in the output (there is a combinatorial explosion of them), so it ignores some of the probability space and thus slightly underestimates the probability of each substring it does consider, which has the effect of slightly overestimating the min-entropy—which would explain why it seems to produce an entropy rate of just over eight bits per octet.

Now, to address (2), does the software implement it correctly?  That's a question for codereviews.se, and maybe for stats.se if you want to make sure that the posited model and the estimator for the probabilities is sensible and what was intended by NIST.

Finally, to address (3), whether this is useful for your goal, the answer is not very.  It will detect certain families of patterns in your data, if those patterns appear.  High estimates like the LRS Estimate in your sample are not useful: they just mean that this particular pattern didn't appear.  Low estimates suggest that someone at NIST who wasn't even thinking about your particular noise source could predict its output with pretty good chances of success.  That's usually bad sign.  So don't worry about the slightly >8-bits-per-octet estimate for LRS: worry about the ~5-bits-per-octet estimate with a Markov model!  Does your device alternate between internal states with somewhat more predictable emission probabilities?

What you really need to do is study the physics of the object in question from an adversary's perspective, and try to find the best way to predict the output knowing how your particular noise source works.  Then compute the entropy of that model.  If it's higher than all of the NIST estimates, either you had a lucky sample or someone at NIST who doesn't even know what you're working on was better at studying your noise source than you are.


How to calculate number of possible key pairs in RSA What determines the number of possible RSA key pairs for a given $n$?
Is it because $\varphi(n)$ produces the number of values that are less than $n$ and coprime with $n$?
Is it as simple as $\varphi(n)$?

How to calculate number of possible key pairs in RSA

Well, if we bound the acceptable $e, d$ values to, say, $(0, \phi(n))$ (as I pointed out in the comments, if we don't have such a bound, then the number of such pairs is infinite), then the number of such pairs is:
$$(\gcd( p-1, q-1))^2 \cdot \phi( \lambda( n))$$
Or possibly one less, if you arbitrarily disqualify the $e=d=1$ pair.
It's fairly straight-forward to see that this is true; if we limit the bounds to $(0, \lambda(n))$, then for every $e$ relatively prime to $\lambda(n)$, there is precisely 1 value of $d$ in that range that is a valid pair; and because there are $\phi( \lambda(n))$ such values $e$ which are in that range, that means that there are that many valid pairs in that range.
However, we specified a larger range $(0, \phi(n))$; it turns out that for all valid pairs $(e, d)$ in the original range, all pairs of the form $(e + a\lambda(n), d + b\lambda(n))$ (for integer $a, b$) are also valid (and for any valid pair, there is a unique representation $(e, d, a, b)$ tuple (with $e, d$ being a valid pair in the $(0, \lambda(n))$ range)).
With that in mind, we can see that, for any $e$, there are exactly $\gcd(p-1,q-1)$ values $a$ for which $e + a \lambda(n)$ is in the range $(0, \phi(n))$, and similarly there are $\gcd(p-1,q-1)$ values $b$ for which $d + b \lambda(n)$ is in the range $(0, \phi(n))$; hence for any $(e, d)$ pair in the smaller range, there are $(\gcd(p-1,q-1))^2$ such pairs; because we have already seen there are $\phi(\lambda(n))$ such pairs in the smaller range, this gives us the formula for the bigger range.


What is the difference between encrypting and signing in ECC asymmetric algorithm? What is the difference between encrypting some data vs signing some data (using ECC)?

Does it simply reverse the role of the public-private keys?

In the past, I thought it was just a change of role for publickey and privatekey.

As the diagram:

(Encrypt diagram)

(Sign diagram)

But in practice, it seem not easy like me think.

For example, I can't use ECDSA public key to encrypt and private key corresponding to decrypt.

In this case I must use ECDH.

I do not have much experience on this issue. Please help me.

Thanks in advance.

ECDSA is just for signing. It stands for Elliptic Curve Digital Signature Algorithm. EdDSA is another signing algorithm, with some added security. ECDH is for key exchange: it creates a new secret key shared by both parties which no passive eavesdropper can discover.

ECC is pretty much never used to directly encrypt a message. Instead ECDH is used to create a shared secret key, and then a secret-key (symmetric) algorithm such as AES-GCM or ChaCha20+Poly1305 is used to transmit the secret data. The same thing is typically done with RSA, since asymmetric cryptography is slow it's faster to create a shared secret key and use symmetric cryptography. ECIES is a standard that does this, and several variants of the "ECDH+Symmetric encryption" idea are included in TLS.

The main use of direct encryption using an asymmetric algorithm would be a PGP-like system for encrypting e-mail or other old asynchronous protocols where no prior key agreement step is possible. I am not aware of any standard that uses ECC to do this.


Composite vs Prime Order Groups in Attribute Based Encryption Reading about Accountability in ABE currently and the paper "White-box traceable ciphertext-policy attribute-based encryption supporting flexible attributes" when comparing its system with an existing mentioned the fact that theirs is a prime order group scheme while the other is a composite order group scheme. My question is what significance does this have on the underlying scheme. And are there cases where one is preferred to the other or cases where on is applicable and the other is not.

Composite-order groups for pairings are sometimes a necessary tool provide a proof for adaptive security. Most schemes for prime-order groups only reach selective security in their respective security models.

While the security generally increases, the performance of composite-order group pairings decreases heavily. Compare prime-order pairings of Type A with composite-order pairings of Type A1 here. All operations for Type A1 take roughly 18 times as much time as operations for Type A (although, they have different Dlog security levels, but that doesn't influence as much).

Dual Pairing Vector Spaces (over prime-order groups) behave similar to composite-order pairings in that they enable more powerful security proofs, but perform roughly 10 times slower than basic prime-order pairings.


Advantages of making streamcipher stream depend on plaintext? Most descriptions that explain how streamciphers work (like the one on Wikipedia), tend to describe a model that boils down to a simple “$ciphertext = plaintext \oplus stream$”, where the stream is determined by a nonce and a key, while the plaintext and ciphertext do not affect the stream at all.

On the other hand, streamcipher designs like Helix* seem to ignore the usual approach as their stream depends on the plaintext… reasoning that this approach adds authentication.

My personal feel is, that the dependence on plaintext has a good chance to introduce additional attack vectors (chosen plaintext attacks etc.).  Looking at the potential downsides, it’s a bit unclear to me if I’m missing something. Maybe there are other reasons or arguments – besides the authentication aspect – which might support the idea of ignoring the regular streamcipher model, and I’m not seeing them.

Is there anything else to be gained by making the stream depend on the plaintext? If, what are the other potential advantages (besides gaining authentication) of making the stream depend on the plaintext, compared to the more frequently used “$ciphertext = plaintext \oplus stream$” approach?

* “Helix: Fast Encryption and Authentication in a Single Cryptographic Primitive” by Ferguson, Whiting, Schneier, Kelsey, Lucks, Kohno

Nota Bene: In his “Salsa20 Design” paper on page 4, Bernstein asks an alike question – ”Should the stream be independent of the plaintext?” – and argues against it. But he merely argues about the authentication part of things and nothing else… which doesn’t really help when trying to learn about the potential benefits such a construction might have besides the debated authentication aspect.

Most advantages have to do with the fact that it includes authentication. For example:

An authenticated encryption primitive is easier to use correctly.
Only a single primitive that has to be secure.
One pass over the data to both encrypt and authenticate may be faster. (Bernstein's rebuttal is that a separate MAC allows faster detection of forgeries, mitigating denial of service attacks.)

There is one potential benefit I can think of that isn't related to authentication, but it should never come into play if you are using the cipher securely:

A plaintext dependent keystream may recover from IV collisions.

This is similar to how a block cipher in CFB mode can be secure after the first block, even with duplicate IVs, if the plaintext differs.


We have $d = e^{-1} \pmod{ \phi(N) }$, this implies that $m = c ^ d \pmod{N}$


Faster Shuffling for a Simple Application Alice, Bob, and Charlie are working on three projects.

Alice is the manager.  At the beginning of each day, she chooses one
project to work on (this choice is based on her preferences and is
not random) and then assigns the other projects to Bob and Charlie.
Bob and Charlie demand that this assignment be 50/50 random and
anonymous (so Alice does not know who got which of the two projects).
Alice accepts this demand, but demands that her original choice be
anonymous too (so Bob and Charlie can not know which project Alice
has, unless they tell each other their projects to deduce the remaining
project).

To accomplish this, at the beginning of each day, Alice writes the
two projects she does not want on two cards and puts them face down on
a table.  Everyone mixes/shuffles the cards until everyone is content
that no one knows which is which.  Bob picks a card, Charlie gets the
other card, and they then work separately on the projects written on
their cards.

The only way I see to accomplish this "at a distance with cryptography"
is Mental Poker, based on
a commuting encryption/decryption method:

Alice shuffles and encrypts both (starting from her two unwanted projects)
-> Bob shuffles and encrypts both
-> Charlie shuffles and encrypts both
-> Alice decrypts both
-> Bob decrypts the first and Charlie decrypts the second
-> In secret, Bob decrypts the second and Charlie decrypts the first

This is a lot of back and forth for every daily assignment - Is there any
simpler solution?

Ignoring Charlie, I was thinking Bob could give some seed (generated from a
private key) to Alice before everything and then Alice would generate random numbers for Bob (readable with his private key, but unreadable to
Alice) which somehow exclude Alice's project...but maybe that is a pipe
dream.

The obvious way is to use two oblivious transfers.  In case you need reminding: an Oblivious Transfer is a protocol where one party (Alice) has a number of secrets (in this case, two), and the other party (Bob or Charlie) gets to pick which one he gets to learn, but he doesn't learn the other (and Alice doesn't learn which one he picked).  There are several known protocols that implement this.

Here is how it would work:

Bob and Charlie randomly agree on a random bit $b$

Alice takes the two tasks she doesn't want, and randomly labels them $T_0$ and $T_1$

Bob then performs an oblivious transfer with Alice, obtaining the task $T_b$

Charlie then performs an oblivious transform with Alice (but using the bit $1-b$ rather than $b$ in the oblivious transfer), obtaining the task $T_{1-b}$

Because of the guarantees that OT provides, neither Alice, Bob nor Charlie know any of the tasks other than their own.

Now, one obvious issue is that, if Bob or Charlie wanted to cheat, they could use the wrong value of $b$, and learn the task given to the other guy.  However, if they did that, they wouldn't learn their own, and so if we assume that they find that unacceptable, this isn't an issue.  It is possible to insert a zero knowledge proof that would ensure that they're not doing that (the details of which would depend on the OT protocol used); however I don't know if you need to do that.


What would happen if the last message in a three-pass authentication protocol was undelivered? I did read some articles about the protocol but couldn't figure out what would happen. Would the two parties be unable to verify each other? Or would it be something else?

based on the international standard ISO/IEC 9798-2.

The three-pass authentication protocol defined in ISO/IEC 9798-2 at 5.2.2. and it is defined as follows;

$\text{B}$ generated random $R_B$ and sends to $\text{A}$;
$$\text{B}\xrightarrow{R_B\|\text{Text1}}\text{A}$$
$\text{A}$ generated random $R_A$ and sends to $\text{B}$;
$$\text{B} \xleftarrow{\text{TokenAB}\;=\;\text{Text3}\|eK_{AB}(R_A\|R_B\|B\|\text{Text2})} \text{A}$$
$\text{B}$ generated random $R_A$ and sends to $\text{A}$;
$$\text{B}\xrightarrow{\text{TokenBA}\;=\; \text{Text5}\|eK_{AB}(R_B\|R_A\|\text{Text4})} \text{A}$$
$eK_{AB}$ is the encryption with the $K_{AB}$;

  What would happen if the last message in a three-pass authentication protocol was undelivered?

Whoever started the protocol, $\text{A}$ connects to $\text{B}$ by $\text{tokenAB}$.

If $\text{B}$ started then $\text{B}$ can send back the $\text{tokenBA}$ to $\text{A}$  for the agreement.
If $\text{B}$ doesn't send back the $\text{tokenBA}$, $\text{A}$ cannot decide it was actually $\text{B}$ or not. Since, anyone can send an $R_B\|\text{Text1}$ to $\text{A}$.

Old answer if the question was the Three-pass protocol of Shamir

It not verification of each other it is just message exchange.

From Wikipedia;

  In order for the encryption function and decryption function to be suitable for the three-pass protocol they must have the property that for any message $m$, any encryption key $e$ with corresponding decryption key $d$ and any independent encryption key $k$,  $$D(d,E(k,E(e,m))) = E(k,m)$$

i.e.

$$D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).$$

If the third, i.e. the last, is not delivered, the messaged won't be decrypted. He will have $E(k,E(e,m)))$ in his hand, but he cannot decrypt this because he doesn't know the key $d$ of the sender.

The receiver can use the Commutativity property to reach $E(e,E(k,m))$ but this won't help,too


When, where, and how to use HMAC This question may seem like a duplicate of some others, namely this one, but even though that question asked when and how to use HMAC, the answers only addressed what HMAC was and why/how it worked.

So, my questions are:

When is it appropriate to use HMAC? If I'm encrypting files on my local computer? If I'm encrypting and syncing files to a server? If I'm sending messages to Bob? When is it not needed?
Simply, what is the recommended algorithm for generating a HMAC? I've seen the Wikipedia page, which does something strange with padding, and have read about HMACs in 'Practical Cryptography', where it says a and b are "specified constants" without going into detail about the constraints on these constants.
The book previously used h(h(m)||m) to prevent length extension attacks, then later defined a different algorithm for HMACs. Why was the former not appropriate for HMAC?

When is it appropriate to use HMAC? If I'm encrypting files on my local computer? If I'm encrypting and syncing files to a server? If I'm sending messages to Bob? When is it not needed?

I think the best answer here is that you're mixing levels of abstraction.  Since you've been reading Ferguson et al's book, I would refer you to their material on the concept of the secure channel—an API that provides concepts at a level more appropriate to scenarios that you are describing here (even though the one they show may not ideal for all of them).  Indeed, in their book HMAC is applied in the context of how to implement a secure channel so that clients that need secure communications don't have to think about HMAC (or nonce reuse or anything of the sort).

The second point is that two of the big, hard-learned lessons of the past 20 years are:

The importance of authenticated encryption;
How easy it is to get it wrong!

So another answer to your question is that, by default, you should be using authentication everywhere unless you can prove that you don't need to.  That doesn't mean use HMAC specifically (again, you're mixing levels of abstraction!), but it does mean that nearly all encryption really ought to be authenticated encryption, and that it should not be ad hoc—it should be a well-studied construction, from a well-audited library function.

Some good reading:

http://blog.cryptographyengineering.com/2012/05/how-to-choose-authenticated-encryption.html
Why should I use Authenticated Encryption instead of just encryption?


Password Hashing Security Using Scrypt & Argon2 I am developing an app where the following cryptographic system will be in place:

Elliptic Curve key exchange (curve: secp521r1)
Double Scrypt the shared secret with different salts
Pass this result through Argon2 with another salt
Encrypt the data using AES 256 and the key from Argon2 (and an IV)

I was wondering whether at the password hashing and KDF stage there was any weaknesses of using double Scrypt then Argon2?? If so, what would be the solution to improve the security of the hashing?? Thanks

This home-made construction is pointless and unnecessarily complex, Complexity is often the source of vulnerabilities. In this case, for example, I’ll wager you’re not securely handling the intermediate variables as you chain the multiple password hashes together.

Simply use argon2 only and increase the work factors. “Double scrypt” is fairly meaningless as scrypt also has work factor parameters which can simply be increased.


Password verification I'm looking for feedback on whether or not this is the proper way to approach password verification without transmitting the actual password. Are there any problems with this scheme.

We are working on a cloud based encrypted file system and have implemented the following steps to verify that the entered password is the same when entered a second time on a different machine. All implementations are from the Microsoft .NET Framework 4.0 (Client Profile). Also, all communication is SSL/HTTPS.

Initial activation for a file system

RNGCryptoServiceProvider is used to create two 128 bit random salts (s0, s1)
Rfc2898DeriveBytes is used with the entered password and s0 with 20,000 iterations to create the 32 byte key (k0)
s1 and k0 are appended to produce b0
SHA512Managed uses b0 to produce the hash (h0).
h0, s0 and s1 are encoded as base64 and sent to the server to be persisited.

Password verification on second client

s0 and s1 are sent to the client as base64 encoded strings
Both salts are decoded.
Rfc2898DeriveBytes is used with the entered password and s0 with 20,000 iterations to create the 32 byte key (k0)
s1 and k0 are appended to produce b0
SHA512Managed uses b0 to produce the hash (h0)
h0 is base64 encoded and sent to the server. If the hash matches the original hash now stored on the server the server responds with true, otherwise false ie: password does not match.

If all is good k0 is used to actually encrypt/decrypt the file system locally using AES-256.

The protocol you are trying to reinvent is called SRP.

Unless you have a compelling reason to believe that your protocol is secure, it should by default be assumed completely broken. Given that your protocol has seemingly no benefits over SRP, you should seriously consider going with something that has been designed and analyzed by cryptographers, has existing software implementations, and has been around for over a decade.

  We are working on a cloud based encrypted file system...

Then you really should have somebody on staff who deeply understands cryptography. Your authentication protocol has a few sign that it was designed by novices. I don't mean to be rude or offensive, but cryptography is incredibly hard to get right. Thomas Ptacek said it best: if you think the dangerous stuff is in the primitives like the AES core, and if you just stick to the glue you'll be safe, you're gonna have a bad time.

  4. s1 and k0 are appended to produce b0
  5. SHA512Managed uses b0 to produce the hash (h0)

Why is this not an HMAC?

  If all is good k0 is used to actually encrypt/decrypt the file system locally using AES-256.

What is the point of the authentication protocol, if a malicious client can simply opt not to bother sending $h_0$ to the server and attempt decryption anyway? If the sole purpose is to prevent accidental decryption with an incorrect key, then this is trivially solved by simply using an authenticated encryption mode. Which, really, you should be using anyway.

You've also walled yourself into a design that doesn't allow password changes without decrypting and re-encrypting everything. Instead, you could use a protocol where the client sends a password-protected secret key to the server. After authentication over something like SRP, the server sends a copy of the encrypted key back to the user. If they wish to change their password, they can simply re-encrypt and re-send the secret key.

Note: the above description is the general approach that I would try and look for in an existing protocol, and not a description of an existing, vetted protocol for this type of exchange.


Secure Hash Function based on AES How secure would a hash function be which appends an extra block of 16 zeroed out bytes to the end of the message and then AES-encrypts it with a well-known password (say the first 128 bits of pi) using cipher-block-chaining and then XORs all the encrypted blocks together?

Not at all secure; generating preimages would be trivial.  Here's a demonstration with a three-block message:

Here is your suggested method (limited to three block messages):

$E_0 = Encrypt( IV \oplus P_0 )$

$E_1 = Encrypt( E_0 \oplus P_1 )$

$E_2 = Encrypt( E_1 \oplus P_2 )$

$E_3 = Encrypt( E_2 \oplus 0 )$

$Hash = E_0 \oplus E_1 \oplus E_2 \oplus E_3$

(with the key for Encrypt and the IV fixed).

Here's how you could find a message $(P_0, P_1, P_2)$ that hashes to a preselected value $Hash$:

Select an arbitrary value for $P_2$ (which may include the trailing padding for the last block)
Select an arbitrary value for $E_2$.
Compute $E_3 = Encrypt( E_2 \oplus 0 )$, $E_1 = Decrypt(E_2) \oplus P_2$ and $E_0 = Hash \oplus E_1 \oplus E_2 \oplus E_3$
Compute $P_0 = IV \oplus Decrypt( E_0 )$ and $P_1 = Decrypt(E_1) \oplus E_0$

You're done: $(P_0, P_1, P_2)$ hashes to preselected value; it's easy to see that hashing this value will cause the internal $E_0, E_1, E_2, E_3$ values that we have selected, and that exclusive-oring them will produce the preselected hash.


I am trying to create a simple image encryptor in python result isnt promising I am writing a program in python (myself) to encrypt images. I don't want or expect it to be state of the art encryption and safe at the end but i have a problem. The result encrypted image still has a recognizable trace of the original image. I know its because of they way i am encrypting it.... so what my program does it loads an image as an array of integer values for all pixel colors (RGB) and then i convert an ASCII password into numbers  from 0-94 (type-able characters) and then use a saved randomly generated dictionary to map these numbers randomly to numbers from 0-255 so that i would avoid colors possibly staying to similar. Then i use this number to shift the pixel values with formula old_pixel_value + hashed_password_character mod 256. The problem is though that if there is a big white-space or a patch of uniform color there are these repeating stripes and then you can kind of still recognize the shape ill put a picture below. So how do i change or what do i add so that the encrypted image seems more random???

(the first one is the non encrypted the second is after encryption)

What you've done is this:-

It's called electronic code book style encryption.  For block cipher encryption read your own pixel transformation algorithm.  And for plain text, read original pixel values. Can you see the how the pattern repeats?  That's the length of your hashed password, and what's called the block width.  You've used it over and over again encrypting a block width's amount of pixels.  Because the background is constant white, it encrypts to the same value over and over.  And as the block width straddles the bike, it kinda still shows up against the constantly repeated background.

What you need to do it this:-

It's called cipher block chaining and creates a relationship between sequential blocks.  You'll have to adjust your algorithm so that one block's data is somehow propagated to the next one.  The traditional way (as illustrated) is to simply xor it. Now every subsequent block will be affected by the previous block and you'll get a much more random pattern.

You don't need the initialisation vector thing at the moment. You can address that later when your chaining algorithm works.  It's highly recommended though to stop relay attacks and leak encrypted information when you repeatedly transmit the same information (the cipher text will be identical each time suggesting the same information was sent).

Note.  It's also traditional to use a fairly complicated set of xor and bit shift operations to encrypt your information /image.  These would be inside the block cipher encryption box.  They create an avalanche effect so very small changes create massive ones.  You use just a shift operator.  I'm not 100% confident that a simple shift will not still show the bike's outline somewhat. Anyone?


Are there any disadvantages of using libsodiums helpers for en-/decoding/comparision instead of the native ones? Libsodium has some helpers, which allow hexdecimal decoding, encoding and also constant-time string comparison.
So if you use the php binding libsodium-php you obviously also have the native php implementation of bin2hex and hex2bin. The libsodium replacements were introduced because the native implementations are not timing-resistent. So for sensitive data this should be used.

But if you have a library/project where you use libsodium anyway are there any disadvantages of using libsodiums functions even in places where this would not be necessary?
I mean one advantage clearly would that you can prevent to forget to use these timing-save implementations in cases where it is important if you just use it everywhere.

Functions often become timing resistant by not using short circuit evaluation. There is conceivably a small performance price to be paid by not using short circuit evaluation.

In reality, this is probably not a bottleneck or serious concern. Edit: It also might be possible that libsodiums function is faster anyways.

I would have commented with this, but I don't have enough rep to comment. There may be more to consider.


Security of Diffie-Hellman with multiplication for secret derivation? Today I saw this question again which presents an unusual variant of the Diffie-Hellman key exchange. Having thought about it for a while I could find out how functionally works, but have essentially little cue whether it actuappy provides security.

My question is now:
Does the below stated Diffie-Hellman-like key exchange protocol enjoy similar security properties as normal Diffie-Hellman?

First the variables: Let $(\mathbb G,g,q)$ be a multiplicatively-written group where the discrete logarithm problem is hard with prime order $q$ and generator $g$. Let $a,b,x,y \stackrel{$}{\gets} \{0,\ldots,q-1\}$ be sampled uniformly at random. Let $A=g^a, B=g^b$. Let $a,x$ only be known to Alice and $b,y$ only be known to Bob. Let $a,b$ be static and $x,y$ be ephemeral across multiple sessions. Let $K=g^{x+y}$ be the shared secret, which can be computed by both parties after the exchange. Now define the following messages (the letters on the left denote Alice and Bob):
\begin{align}
A\to B&:B^x=g^{bx}\\
B\to A&:A^y=g^{ay}\\
\end{align}

If you are questioning functional correctness at this point note that Alice can trivially compute $g^x$, knowing $x$, and can compute $g^y$ as $(A^y)^{a^{-1}\bmod q}$, yielding $K=g^x\cdot g^y$. The computation for Bob goes analogous.

This problem (in the computational sense) is equivalent to the CDH problem [1].
This problem can be summarized as "given $g, A, A^y, B, B^x$, compute $g^x \cdot g^y$
Given a CDH oracle, we can solve this with two queries; we get the inputs $g, A, A^y, B, B^x$, and we give the CDH oracle the values $B, B^x, g$, and it'll give us the value $g^x$; we do the same to get $g^y$, and a simple multiplication gives us $g^x \cdot g^y$
Conversely, given an oracle that solves this problem, we can solve the CDH problem; we get the inputs $C, C^x, D$, we select an arbitrary $E, y$ values, and give the oracle the tuple $D, E, E^y, C, C^x$; it'll return the value $D^x \cdot D^y$.  We then multiply that by $D^{-y}$, and that gives us the answer to the CDH problem $D^x$

Now, addressing the decisional problem would appear to be trickier; it's easy enough to show how to solve the DDH problem with an oracle that solves the decisional version of this problem; however, I don't see an obvious way to use a DDH oracle to solve this problem.

[1]: Note: for the CDH problem, I won't be using the usual formulation "given $g, g^x, g^y$, return $g^{xy}$, instead, I'll be using the equivalent "given $g, g^x, h$ return $h^x$.  That formulation would appear to be make the proof a bit cleaner...


Does password length affect AES encrypt/decrypt velocity? I'm implementing crypto in Node, following this article: https://lollyrock.com/articles/nodejs-encryption/

It defines:

var crypto = require('crypto');
var algorithm = 'aes-256-ctr';
var password = 'd6F3Efeq'; // AKA passphrase

Then, it uses the password/passphrase for encrypt and decrypt the strings.
Now, here my question:
Is the password length going to change the encrypt/decrypt velocity?

For example: is the password/passphrase d6F3Efeq going to take less time to encrypt/decrypt than d6F3Efeqd6F3Efeqd6F3Efeqd6F3Efeq?

Edit:
This is the way that the password/passphrase is used:

function encrypt(text){
  var cipher = crypto.createCipher(algorithm,password)
  var crypted = cipher.update(text,'utf8','hex')
  crypted += cipher.final('hex');
  return crypted;
}

function decrypt(text){
  var decipher = crypto.createDecipher(algorithm,password)
  var dec = decipher.update(text,'hex','utf8')
  dec += decipher.final('utf8');
  return dec;
}

PS.: I know that using createCipher is a bad idea and I should use other non-deprecated functions (like http://www.levigross.com/2014/03/30/how-to-write-an-encrypt-and-decrypt-api-for-data-at-rest-in-nodejs/), but I'm not asking about which crypto algorithm is better. I'm asking only about velocity/performance.

No, password length does not perceptibly change encryption throughput. That's valid for overwhelmingly most password-based encryption schemes using AES-256, especially the secure ones.

More precisely,

The time it will take to encipher an extra kilobyte of data is fully independent of the password length. That's because the password is first transformed into a 256-bit key, and then this key is used for encryption/decryption/authentication, and the throughput of that later step does not depend at all on the value of the AES key (that would be a weakness of the AES implementation).
Even the time it takes to encipher/decipher/authenticate the first kilobyte does not perceptibly depend on the password length, for reasonable size thereof (say, up to 55-byte password, often much more). That's because the code that transforms the password into key falls into one of two categories:

Slow: for these, up to said limit at least, execution time depends almost only on parameters adjusted to slow things in order to make password search suitably difficult.
Fast, thus of negligible cost w.r.t. the rest. CAUTION: these are extremely vulnerable to password search.

Note: 55 bytes is a limit above which some common hash algorithms (SHA-256..) see their computation time abruptly increase, because they process their input data split into 64-byte blocks, and there's an overhead of 9 bytes.

Note: this answer is independent of the nodejs context. The linked page gives zero clue about how the password is changed to key, and this site is not about language-specific questions.


How to argue to a paranoid that RSA is safe? From today's standpoint, most people would claim RSA to be secure. However, to my knowledge, this is purely based on the speculation that no one knows a computational feasible way to find a $d$ for given $n$ and $e$, s.t. $ed \equiv 1 \mod \varphi(n)$ - which can be reduced to the factorization problem.

However, it is still an assumption that the factorization problem is hard to solve but nothing that has been proven mathematically. Worse, as far as I understand it, it is not even clear to which complexity class integer factorization belongs. And if the past year has thought us anything then it is that often the "paranoia argument" is not that paranoid at all.

So I always wondered how probable it is that indeed no one has found an efficient solution to the factorization problem yet. How would one know? Or, in short:  How do you convince a paranoid that RSA indeed is secure?

The security of every single cryptographic algorithm(*) of any kind is ultimately based on: "many people looked at it for a long time and did not find a way to break it". Security proofs boasted by some algorithms are quite useful but they don't actually prove security, they move it (a security proof is a reduction to another problem which has to be assumed to be strong).

So one could "measure" the strength of an algorithm by the accumulated scrutiny it has sustained successfully. In that sense, RSA is about the best in class: it relies on mathematical principles which can be argued to have been studied for more than 2500 years by the smartest mathematicians in the World. Elliptic curves cannot compete with that.

This argument is, of course, debatable. At best. Yet one has to take into consideration that paranoia, by definition, is a distortion of the perception of reality and the balance of risks. So the paranoid can be convinced by arguments which depend on that distortion.

(*) Except the very few algorithms with unconditional security, like Shamir's Secret Sharing, but they are limited in scope. That which is done with RSA (asymmetric encryption, digital signatures) can be easily proven to be infeasible with unconditional security; e.g. signatures can always be theoretically forged through exhaustive search on signature values, since the verification algorithm is, by definition, public.

Convincing people is actually a more psychological than cryptographic endeavour. Context matters. If the context is economical, then it suffices to say: "Maybe RSA can be broken, but your competitors use RSA. Not doing the same incurs the risk of letting them run ahead of you." Indeed, the paranoid is averse to risk, and not doing the exact same mistakes as the competition is the biggest risk that can be taken by a business.


In search of platform independent 128-bit hash function We are currently using murmur3 as our hash function for small strings (up to 128 chars). We plan to replace it with a better non-crypto hash function which is fast and produces unique 128-bit hash for a given input across the platforms (32/64-bit, x86 & arm).

Farmhash could have been an ideal candidate with it's speed and collision resistance but it's quite machine dependent and produces different results on different platform which makes it useless for us.

Cityhash has been known for collision weakness as demonstrated by siphash. So it's out of considerations.

Siphash is too slow and so is Highway hash which appears to be derivative of siphash (feel free to correct)

metrohash, xxhash, and seahash are under considerations.

I wouldn't be bothered by minor difference in speed. However, uniqueness across platform and collision resistance are main criterions.

Please suggest.

If the space of inputs is predetermined before you deploy your system, you can create a perfect hash that is very fast to evaluate and guarantees unique hash values, such as with gperf or nbperf.

If the space of inputs is chosen by a non-adaptive adversary—i.e., an adversary picks a set of keys and then feeds them all to your system at once without picking some keys based on how the system reacted to others—then you can pick some (almost-)universal hash family such as Poly1305 with a secret key you choose uniformly at random: for any pair of inputs, the probability over all possible keys that the inputs collide is $O(1/m)$, where $m$ is the number of possible hash values.

If the space of inputs is chosen by an adaptive adversary and Siphash is too slow, you will need to describe your performance budget in more detail:

How many keys do you have?
What is the distribution of key lengths?
How many cycles per byte can you afford?
How many cycles per key can you afford?
How many bytes can you afford to transmit/store?
What is the cost of a collision?  Of $n$ collisions?

(Transmitting 8 bytes on a network is not free!  Exercise for the reader: How many nanoseconds and joules does it take to compute Siphash on a 16-byte input on your laptop's CPU, and how many nanoseconds and joules does it take your  laptop's ethernet phy to transmit 8 bytes?)


IND-CPA security of CTR mode Let's suppose CTR mode is instantiated such that the input to the block-cipher is $\langle \mathrm{IV}+\mathrm{ctr}\rangle$ instead of $\mathrm{IV}\mathbin\|\langle \mathrm{ctr}\rangle$, where $\langle X\rangle$ is the bit representation of $X$.

Will the mentioned version of CTR encryption scheme be IND-CPA secure against nonce-respecting adversaries? If not, can this be made nonce-IND-CPA secure by adding some cryptographic methods over it without altering the underlying structure?

The crucial property you want to achieve CPA security is that each combination of $\mathrm{IV}$ and $\mathrm{ctr}$ is used at most once, since you essentially derive a key from this combination and use it to encrypt the corresponding block with the one-time pad. If you choose $\mathrm{IV}$ uniformly at random from a large enough space, this will be the case with high probability for both variants you describe.

If $\mathrm{IV}$ is a packet counter, $\mathrm{IV} || \langle \mathrm{ctr} \rangle$ is still fine if you reserve enough bits for both $\mathrm{IV}$ and $\langle \mathrm{ctr} \rangle$ to exclude overflows. The variant $\langle \mathrm{IV} + \mathrm{ctr} \rangle$, however, now becomes insecure: If two packets are encrypted where the first one contains at least two blocks, the second block of the first packet will be encrypted with $\langle 1 + 2 \rangle = \langle 3 \rangle$, and the first block of the second packet will be encrypted with $\langle 2 + 1 \rangle = \langle 3 \rangle$. Hence, an attacker who knows the contents of the second block in the first packet can learn the first block of the second packet. As long as you only increment the combination of $\mathrm{IV}$ and $\mathrm{ctr}$ by one for the next block, this problem persists unless you ensure there is a large enough gap between two packets. This is exactly what $\mathrm{IV} || \langle \mathrm{ctr} \rangle$ ensures.


Salsa20 expands a 256-bit key and a 64-bit nonce into a 2^70 byte stream - where did the 2^70 come from? From Section 3.1 in DJB's document on The Salsa20 family of stream ciphers- https://cr.yp.to/snuffle/salsafamily-20071225.pdf

Salsa20 expands a 256-bit key and a 64-bit nonce (unique message number) into a $2^{70}$-byte stream.

Where does this $2^{70}$ number come from?

Salsa20 is a PRF working in Counter-mode. That is it generates the keystream as $K_i=F_k(N,\text{Counter}_i)$.
This Counter is a 64-bit value - not the nonce - thus allowing $2^{64}$ invocations of the PRF before repetition. Each PRF invocation yields 64 bytes, so in total $2^{64}\cdot 64=2^{70}$ bytes.

Salsa20 generates the stream in 64-byte (512-bit) blocks. Each block is an independent hash of the key, the nonce, and a 64-bit block number; there is no chaining from one block to the next.

The above is the relevant quote from the paper, about five lines below the quote in the question.


Does seemingly random output imply irreversibility in hash function? My question mainly stems from the following observation of properties of cryptographic hash function:

Preimage resistance: Given $H(x)$, it's hard to find $x$
Second preimage resistance: Given $m1$, it's hard to find another $m2$ such that $H(m1)=H(m2)$
Collision resistance: It's hard to find any two distinct messages $m1$, $m2$ such that $H(m1)=H(m2)$.

It is said that property 3 implies property 2 which implies property 1. I can understand if it is hard to find any two distinct messages $m1$ and $m2$ for $H(m1)=H(m2)$ then it will be hard to find a distinct $m2$ for given $m1$ for $H(m1)=H(m2)$ (property 3 implies property 2). And if I have $m1$ and $H(m1)$ then from property 2 I can say it is hard to get $m2$ from $H(m2)$ if $H(m1)=H(m2)$, and as $H(m2)=H(m1)$ it is hard to get $m1$ from $H(m1)$ as well (property 2 implies property 1).

Now my question is if a hash function has this property: for small changes in inputs it outputs such numbers that will seem random so that from output it will be hard to determine changes in input, does it imply any of the above property specially property 1, i.e. irreversibility of cryptographic hash function?

I am asking this because for $m1$ & $m2$ I will get $H(m1)$ & $H(m2)$ respectively and if $H(m1)$ & $H(m2)$ are correlated (not random) and I know $m1$ and $H(m1)$ (prior information) then from changes in output can I know easily changes in input thus know which input produces output? Putting slight differently is it possible to train a hash function from input and output if outputs are not seemingly random so that for given output I will know input?

Now my question is if a hash function has this property: for small changes in inputs it outputs such numbers that will seem random so that from output it will be hard to determine changes in input, does it imply any of the above property specially property 1, i.e. irreversibility of cryptographic hash function?

No. Randomness is hard to test and it's easy to use any of the non-secure random number generators to generate random looking output. So anything that is "non-random" is certainly not irreversible because of just that.

  Putting slight differently is it possible to train a hash function from input and output if outputs are not seemingly random so that for given output I will know input?

That's kind of the opposite. But if you just take $H'(x) = H(x) | 1$ then it should be clear that $H'(x)$ is as irreversible as $H(x)$, while the output is clearly not random.


Streaming mode of operation that is more resistant against nonce reuse Is it possible to create a streaming mode of operation where the reuse of a nonce does not destroy confidentiality?

In this question it would be allowed for the streaming mode to leak if ciphertexts are (partially) identical or not - like in CBC mode of operation. It is of course not permitted to introduce other secrets or random values other than the key and original nonce.

I've got the feeling that this is only possible by mixing in information from the plaintext, but that would make the cipher much less efficient.

For my answer I'll distinguish two cases: a) By "streaming" you mean "online" and b) by "streaming" you mean "can encrypt arbitrarily sized messages". See the CAESAR survey paper for the notions I use here.

There can be no fully nonce-misuse resistant online authenticated encryption scheme, i.e. a scheme where the only information leaked upon nonce reuse is whether two messages are identical. However, there's a weaker notion of nonce misuse resistance that allows the "longest common prefix of the messages" to be leaked. I think this notion may be sufficient to you.

The survey paper I linked above lists some candidate constructions for this property and may be more up-to-date than this answer (especially if the round three candidates are already in).

If you are willing to allow offline schemes (i.e. schemes that need at least some information about the complete message before being able to output cipher texts), then you're lucky. It is possible for those schemes to achieve the strong nonce misuse resistance. The most recent and most efficient example I've seen in this category (with full security proofs) being GCM-SIV by Gueron and Lindell.


Can I use a key-derivation-function as the hash function H in SRP? In the Secure Remote Password Protocol, the verifier must be stored on the server.  In the case of a server compromise, an attacker could obtain these verifiers.  If nobody reused passwords, this wouldn't be a big deal (as the users' data is probably also compromised).  However since people do reuse passwords it seems a good idea to make offline attacks against the password file difficult.

SRP is based off of a cryptographic hash H; part of the cost of an offline attack would be calculating H, so using an expensive hash for this step seems good.  However, I am unsure of the suitability of tunably expensive hashing mechanisms (e.g. PBKDF2, bcrypt, scrypt) for this.

Yes, you can and use a slow hashing function when constructing the verifier.  I would recommend using PBKDF2, as it is designed for this purpose.

In fact, Wikipedia says:

  $v$ is the host's password verifier, $v = g^x$, $x = H(s,p)$. Using of functions like PBKDF2 instead of $H$ for password hashing is highly recommended.

Thus, you could use $x=\text{PBKDF2}(s,p)$.  Alternatively, you could pre-hash the password with PBKDF2, then use the result as your $p$.


How to pick up random number within range using pseudo-random number sequence I want to generate PRP using Fisher–Yates shuffle for array  [1,2,3,4,5,6,7,8,9,10,11,12].

I implemented NLFSR_25bit  with specific seed for PRNG. (for picking up pseudo-random number in every iteration of algorithm )

Fisher–Yates takes pseudo-random number from interval(i.e (1,i) in every iteration of algorithm ) How can i pick up pseudo-random number from interval? (while my PRNG generate a sequence but not a number)

Beacuse my numbers are [1 , ..., 12] i want to use 4_bit lsb of  NLFSR_25bit and then compute 4_bit_lsb%12 for getting number between (1,12)

I would also appreciate other solutions.

If you have a uniform sampler for integers in the interval $[0, 2^k)$, such as an LFSR (which is not very uniform, but let's pretend it were) or any cryptographic PRNG truncated to $k$-bit outputs, the standard way to sample from integers in the interval $[0, n)$ when $n < 2^k$ and $n$ is not a power of two is by rejection sampling.

Consider reducing an integer $x$ in $[0, 2^k)$ modulo $n$, giving $y = x \bmod n$.  For each of the $n$ possible values of $y$, there are either $\lfloor2^k/n\rfloor$ or $\lceil2^k/n\rceil$ possible values of $x$ giving $y$—that is, either $2^k/n$ rounded down, or $2^k/n$ rounded up, depending on whether or not $y$ has an ‘extra’ representative $x \geq n\cdot\lfloor2^k/n\rfloor$.

For example, if $k = 4$ so $2^k = 16$, and if $n = 3$, then for $x \in \{0,3,6,9,12,15\}$, of which there are $\lceil16/3\rceil = 6$ possibilities, we have $y = 0$.  But for $x \in \{1,4,7,10,13\}$ or $x \in \{2,5,8,11,14\}$, of which there are $\lfloor16/3\rfloor = 5$ possibilities each, we have $y = 1$ or $y = 2$, respectively.  Thus $\Pr[y = 0] = 6/16$, but $\Pr[y = 1] = \Pr[y = 2] = 5/16$.

x =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
y =  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2 *0

If we first sample an integer from $[0, 2^k)$ uniformly at random, and then reduce modulo $n$, the result will be biased toward the values of $y$ that have an extra possible representative $x \geq n\cdot\lfloor2^k/n\rfloor$, such as the representative $x = 15$ for $y = 0$ in the example above.  That gives a nonuniform distribution on integers in $[0, n)$.  This bias is sometimes called the modulo bias, although it happens whether the map from $x \in [0, 2^k)$ to $[0, n)$ is $x \mapsto x \bmod n$ or anything else—you can never fit 16 pigeons into 3 holes and get the same number of pigeons per hole, no matter what order you put them in.

If we repeatedly sample integers from $[0, 2^k)$ uniformly at random, and reject some fixed subset of them, say $x = 15$ in the example above, then we can ensure that the only set of values for $x$ we will consider divides evenly into equal-size sets of representatives for $y$.  It doesn't matter which subset of values for $x$ we reject, as long as they divide evenly—we could also reject $x = 0$, or even $x = 3$.

x =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
y = *0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0

One easy choice is to reject all values of $x$ below $2^k \bmod n$, because that bound can be computed in $k$-bit unsigned integer arithmetic by the simple expression $(-n) \bmod n$, since
\begin{array}{}
2^k \bmod n &= 2^k \bmod n - 0 \\&= 2^k \bmod n - n \bmod n \\&= (2^k - n) \bmod n.
\end{array}

This gives the following algorithm for sampling an integer in $[0, n)$ uniformly at random given a uniform random sampler for integers in $[0, 2^k)$:

Sample $x$ uniformly at random from integers in $[0, 2^k)$.
If $x < 2^k \bmod n$, start over.
Return $x \bmod n$.


Does this description of verifiable random functions seem accurate? I've been thinking about verifiable random functions recently due to my interest in sortition (random selection of political officials). I wrote up this little paragraph below, and I'm wondering: Does this paragraph seem accurate? I'm not very confident in my thought process haha as I'm quite a newbie to cryptology and hadn't even heard of a VRF before yesterday.

If you do find problems in what follows, please let me know! I really want to understand at least the very basics of this correctly.

Of course, one time-honored method of random selection is to simply put some names in a big tub and mix them around. However, with recent advances in cryptology more sophisticated mechanisms could be used. In particular, verifiable random functions could be used to choose citizens. In general, the owner of a verifiable random function f employs a secret key and a chosen input x to compute f(x), which is essentially a random value. When x and f(x) are published, the owner also releases a proof that, combined with a previously disseminated public key, allows anyone to confirm that the published value f(x) was indeed correctly computed. However, the public never learns of the secret key and thus cannot evaluate the function for any input other than x. This is in part because verifiable random functions are a kind of “one-way function”: It is easy for the public to check the correctness of an output, but impossible for them to figure out how the function actually operates in general -- thereby preserving the secrecy and integrity of the procedure.

Sure VRFs can be used for sortition. One can say that a party is selected if the output of his VRF satisifies some property.

The VRF outputs two things - a random output and a proof that the output is computed correctly. It is not always the case that if the output of a VRF is f(x) the corresponding proof is x. For example, the VRF could simply output a pseudo random function $PRF_{sk}(x)$ along with a zero knowledge proof that the PRF was computed correctly.

"but impossible for them to figure out how the function actually operates in general" :
This would not be accurate, everyone knows how the VRF operates, else how would one verify that the output is actually correct. In cryptography the working of a protocol is never hidden (Kerckhoff's principle)

You can find more information on VRFs here. This is a working IETF draft to standardize the construction of VRFs. They have some interesting constructions there.

Welcome to the community!


Given a ciphertext $c$ and a public string, how do we check whether $c$ encrypts something that is roughly equal to the string without decryption? Let $$ be an encryption function, then we have $c = f(m)$ for some bit string $$. Here, we also have pattern matching function $(,′)$ which returns true whether $$ matches roughly with $′$ in terms of some criteria. Given $$ and $′$ (some public string), we want to clarify whether $$ encrypts $$ such that $(,′)=$ without decrypting it.

How can we do that?
I'm not looking for solutions based only on homomorphic encryption since the result will never be revealed without decryption.

Does ZKP help this?

In short: ZKP does not help mostly if you keep your scheme like that. But your scheme can be fixed if you don't need to rely on public encryption.

ZKP do help if a problem can be efficiency calculated if a witness is known and otherwise it is hard to compute. And that's the problem here since anyone can generate such proofs in some cases.

If we talk about encryption schemes, there will be three kind of schemes:

(1) One-Time based: An adversary chooses any m which g(m, m') returns true and compute $k = m \oplus c$. Now anyone can create the desired proof.

(2) Symmetric-key based: An adversary randomly chooses a key k and computes $m = f_k^{-1}(c)$ and outputs k, m, if g(m, m') returns true and otherwise repeats with a different k (algorithms used in practice might have simpler attacks too). Especially if the pattern function has a wide range the likelyhood to find a true returning pattern will break the ZKP since anyone can could generate such a prove then.

(3) Public-crypto: I'm not sure myself here, but I would not rule out attacks like in (2).

The attacks I described here works because the key can be chosen by an adversary. If you rely on the random oracle model, you can use a hash function as commitment (e.g. SHA256) to commit your key using $com \leftarrow H(k|decom)$. Now an adversary must generate a prove so that he knows a key k, a message m and a decommitment decom so that $H(k|decom) = com \land f_k(m) = c \land g(m, m') = 1$ which is hard to compute if you don't know the key and the message.

I would recommend you to use a generic  zero-knowledge protocols which proves the computation of a boolean circuit like presented here and here. The authors first paper even published a reference implementation of SHA256 on github. Hopefully your encryption scheme does not rely on public encryption, since otherwise the proof becomes impractical.