Availability of a simple limited PRNG algorithm I am in need of a really simple limited PRNG, that either exists or can easily be created in virtually any language on any platform.  It takes only the initial seed, and is only expected to generate a small amount of output in its lifetime, normally 32-64 bytes but potentially more with very low probability.  It will not reseed.  There is precisely one consumer of its output - an ECDH key generator.  If given the same initial seed on different languages or platforms, the PRNG must generate the same exact output.  (Hence, given the same initial seed on different languages or platforms, it is possible to determinstically recreate the same ECDH keypair.)

The requirement for cross-platform consistency and no need for reseeding are driving me to seek a well known standard implementation of some standard PRNG.  It will not be Yarrow or Fortuna because they obviously don't fit the requirements.

Does there exist some well known PRNG that fits this description?

Note:  I removed "My Simple Limited PRNG" as it is no longer relevant.  Because the answer to the first question "Does something like this already exist, that is well known" is yes.

Yes.  This paper on nist.gov gives five such PRNGs.

Three of them are based on hash functions and two of them are based on block ciphers.


How to encrypt a string using RSA public key only? I have been given the following public RSA key:

MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAl2uzoWA2iEGfeqDYO4XA0mQV8odb6qgdLT0T/k1PsbviMMt+SlAnZpwDkPlFySxNejOv8zAUHwDTWV7NGpYA0y+TrrBLkGGl9uUrzOjQLryJmFWsXxBGFd4emYXYBzROaH+r7pzhK7mIWLw1e2Cj5RL9Ac6wKA56axqCr2UZRNDBcS5A+nKTQTWy5eTrq6EQSBA6Hr81UWtYwlNSo1YbZ9JSNdD75Go7Du/zv1iPI+wWr7tMp0AJVBmieeB0kryXl+8zhli80wa72hDtyTkmfkBJAid5Il1biTrOXtMDaqXdfi9s4xzFp/ilP17KnA+VeAH2eLcqaC6LkEp/A1LApwIDAQAB

Now, I need to encrypt a string with this public RSA key.

What I have tried so far:

Put the key in a file, and name it public. Ran the following command to get the .pem version of the key:

openssl rsa -in public  -pubout > file.pem

But doing so says the following:

  unable to load Private Key

So how can I successfully encrypt a string using a public RSA key only?

This is not a question about cryptography itself, but rather use of a program or library related to crypto (OpenSSL). It would fit better on security.SX or superuser, or stackoverflow if you want to do it in your own code.

Your key is base64-of-SPKI which is nearly OpenSSL's PEM format; just break it into lines of length 76 (can omit this step if using OpenSSL 1.1.0 given your key is not too long), add a line -----BEGIN PUBLIC KEY----- before and a line -----END PUBLIC KEY----- after. (Note 'line' must have a terminating LF or CRLF depending on OS.) Alternatively just convert it from base64 to binary and that's OpenSSL's DER format.

Much as Squeamish said you can then use this key to encrypt small data (such as a symmetric key) from commandline using

 openssl rsautl -encrypt -inkey file -pubin [-keyform der]

or (in 1.0.0 up)

 openssl pkeyutl -encrypt -inkey file -pubin [-keyform der]

as described in their respective man pages which should be present on your system or on the web; or from code in ways depending on the API(s) available or preferred which you didn't identify.

Both of these by default use the traditional padding of RSAES-PKCS1-v1_5 (commonly abbreviated pkcs) and optionally can do OAEP from PKCS1 v2 (see the man pages) or raw/none (which is usually a very bad idea). You need the recipient to tell you what padding (or possibly choice of paddings) they accept; if you have a choice OAEP is better (and the reasons why are ontopic here but already answered). If they require something other than the two PKCS1 schemes you'll almost certainly need to code it yourself.


many time pad attack I am a beginner in cryptography. I studied many time pad attack and now I want to solve a popular exercise, It consists 11 ciphertexts (s1,s2,...,s11), that encrypted by a same key and I want to find plaintext(p11) of s11.
I know:

p10 ⊕ k = s10
p11 ⊕ k = s11
p10 ⊕ p11 = s10 ⊕ s11

Now, what should I do for getting p11?
If assume k = s10 ⊕ s11,
so:

  s11 ⊕ k = p11
  s11 ⊕ (s10 ⊕ s11) = p11

. Is it correct?

You need to know something about the plaintexts and their structure for an attack, otherwise (more precisely: if you have to assume the $p_i$ are uniform distributed and truly random) knowing $s_1,...s_{11}$ is the very same as having $11$ one-time-pads for the same message (consider $k$ the message and $p_1$ to $p_11$ the keys) - which is still perfectly secure.

If you know for example that the plaintext is English words encoded in ASCII, then you can identify probabilities for the Xor of two plaintexts and start there. However, in that exercise you might be challenged just to try out different things, if they don't tell you anything else. Your best bet is so calculate all $s_i \oplus s_j$ with $i \neq j$ and compare this distribution to the XOR of symbols of natural language.


how to prove that given cryptosystem is not IND-CCA secure? Let $m$ and $k$ be positive integers ($m$ bit plain text) ; let $Q$ be a family of trapdoor one-way permutations such that $f : \{0,1\}^k \rightarrow \{0,1\}^k$ for all $f$ in $Q$; and let $G : \{0,1\}^k \rightarrow \{0,1\}^m$ be a random oracle. Let $P = \{0,1\}^m$ and $C = \{0,1\}^k \times \{0,1\}^m$, and define

$K = \{(f, f^{(-1)},G) : f$ in $Q\}$

For $K = (f,f^{(-1)},G)$, let $r$ in $\{0,1\}^k$ be chosen randomly, and define

encryption of $x = (y_1,y_2) = (f(r),G(r) \oplus x)$, where $y_1$ in $\{0,1\}^k$, $y_2$ in $\{0,1\}^m$

decryption of $(y_1,y_2) = G(f^{(-1)}(y_1)) \oplus y_2$

The functions $f$ and $G$ are public key; the function $f^{(-1)}$ is the private key

Given two plaintexts x1; x2 and a ciphertext (y1; y2) where y1 = f(r) and y2 = G(r) xor xi
for a random i(1,2) a CCA can query the decryption of (y1; ~y) where ~y != y2. Upon
receiving the answer x, the attacker can recover G(r) = ~y xor x. Then the attacker can
compute xi = G(r) xor y2 and find i.


Verify membership of an item within a set while obscuring the number of elements in the set? I'm wondering whether it is possible to achieve the following scenario:

Say you have a set of names {Alice, Bob, Jake}. To verify that the name 'Bob' exists in the set, you can simply compare 'Bob' against each element of the set and discover that one of the entries in the set does indeed match the name 'Bob'.

I need a way to verify membership of, say, 'Bob' in the set, but without exposing the number of elements in the set.

Is there some transformation that can be done on the set {Alice, Bob, Jake} so that the resulting entity can be used to verify the independent membership of any and all of 'Alice', 'Bob', and 'Jake' within the set, but at the same time the resulting entity does not allow one to view the total number of elements that the set comprises?

Thanks a lot

You don't mention multiple parties at all, so the question is: Who knows what? And who must not know the number of elements in the set?

And then, the most simple solution actually doesn't need cryptography:

Let's assume Bob has the set of elements and Alice wants to know if some element $x$ is in the set.
Alice sends $x$ to Bob.
Bob answers with yes or no.

Obviously, this doesn't hide $x$ from Bob. If we use some hash value $h(x)$ instead (Bob hashes all elements, too, the rest is the same), then given enough entropy in $x$ Bob might not be able to find $x$ - if it isn't in the set (if it is, he also knows the preimage as you can assume Bob didn't delete the original elements).

Depending on what kind of properties you want, there are various constructions. For example set membership proofs, where Bob actually has to prove that the element is in the set and a simple yes or no isn't enough. If you want to achieve that Bob doesn't even know if the answer is yes or no, this might also be possible - based on some sort of oblivious transfer.

Another interesting construction, which might suit your needs, might be  accumulators - and that's my best guess right now: Bob gives the accumulator to Alice, which doesn't expose the elements or their number on its own. But he is able to prove that some element is actually contained in the set represented by the accumulator.


Format preserving encryption FFX In FFX mode the format of the ciphertext is same as plaintext. How does it ensure data integrity and authentication? Is there any bit flip attack in FFX mode?
Is it malleable?

FFX is not malleable. It's a strong tweakable pseudo-random permutation, where the "strong" here indicates that both encryption and decryption look like random permutations from the attacker's perspective. In particular, there's no relationship between the plaintexts of closely related ciphertexts (aside from the trivial observation that different ciphertexts give different plaintexts).

FFX can provide integrity protection in very limited circumstances. If most plaintexts aren't valid, then you can detect tampering by ensuring that the plaintext is valid upon decryption. (This is not true for encryption in general --- it's another feature of algorithms with strong tweakable pseudo-random permutation security.) For example, if the plaintext contains a checksum, as with a credit card number, then validating the checksum provides some degree of integrity. However, in most cases this isn't a very strong check; a single-digit checksum will allow one in ten forgery attempts to succeed. (See "Encode-then-encipher encryption" by Bellare and Rogaway as well as the RAE definition in "Robust Authenticated Encryption: AEZ and the Problem it Solves" by Hoang, Krovetz, and Rogaway.)


Can we use a sort of "hash" function in CTR mode instead of a block cipher? CTR mode does not use the decryption function at all, only the encryption function.

This may suggest that a different primitive that has this "one-way" property could do the trick. For instance, I just thought we could map the secret key with the counter under a secure hash function to obtain a complete usable and secure cipher with CTR mode, why is this assertion false?

Maybe a secure hash is not enough, but

  Can we use a different primitive as a cipher in CTR mode, not necessarily a PK Cryptosystem?

Thanks a lot for your answers and comments.

Your intuition is on the right track: if you run a pseudorandom function in counter mode with your secret key, you get a stream cipher.  Some stream ciphers are designed like this, perhaps most notably Salsa20 (and its later variant ChaCha20).

But the key to answering your question, as I see it, is to note that a collision-resistant hash function like SHA-2 is more complicated than what you need for this use:

You don't need the collision resistance property of cryptographic hash functions.
Standard cryptographic hash functions are unkeyed; they don't take a secret key as input.  You are using a custom construction to incorporate a secret key into your use of a hash function, and that means that you have to ask if your construction is secure, or use a standard construction that has been analyzed to be secure.
Hash functions (as normally understood) feature compression—they turn input data of arbitrary length into a fixed output size.  But you're feeding fixed-size inputs to the hash function.

So what you really want is a pseudorandom function that takes these three fixed-size arguments:

The key (secret);
A nonce (not secret);
A block counter value (not secret);

...and produces a fixed-size keystream block.  So if you read for example RFC 7539 ("ChaCha20 and Poly1305 for IETF Protocols") you'll notice that this is precisely the interface of the ChaCha20 block function (section 2.3):

  2.3.  The ChaCha20 Block Function

  The ChaCha block function transforms a ChaCha state by running multiple quarter rounds.

  The inputs to ChaCha20 are:

  A 256-bit key, treated as a concatenation of eight 32-bit little-endian integers.
  A 96-bit nonce, treated as a concatenation of three 32-bit little-endian integers.
  A 32-bit block count parameter, treated as a 32-bit little-endian integer.

  The output is 64 random-looking bytes.

Or, alternatively, feed the exact same inputs to a block cipher like AES.  Block ciphers are pseudorandom permutations (a subset of pseudorandom functions) and thus already keyed, and they work on fixed-size inputs already (they don't feature compression), so they're a good tool for this use.


How to actually compute the statistical distance? I have an algorithm for discrete sampling that I've defined. This is to say that $A$, upon input some pdf $p(x)$, outputs samples from the pdf $p(x)$. There are some nuances (you have to make the support of $p$ finite, so you're really only sampling from some distribution within some statistical distance $SD$ of the distribution of $p$), but nothing too complicated.
By statistical distance I imean the "Total Variation Distance":

  $$d(D_1,D_2) = \sum_{x\in\mathsf{supp}(D_1)\cup\mathsf{supp}(D_2)}\lvert \Pr[D_1 =x] - \Pr[D_2 = x]\rvert$$

Imagine I can (theoretically) prove that this process truly does sample from a distribution that's within $SD$ of the true distribution, and I want to implement this sampler. What are the typical ways to show that $A$ produces the distribution that it theoretically should? Given a perfect implementation, this wouldn't be an issue, but I'm hoping to use this to catch bugs.

There are easy naive things to do --- for example, draw some number of samples $(x_1,\dots,x_n)$, treat this as an empirical distribution, and compute the statistical distance between that and the (true) pdf $p(x)$. My worry about this is that the Statistical Distance problem is complete for the complexity class Statistical Zero Knowledge (see chapter 4 of Vadhan's thesis for a survey), which might hint that this is a poor method of finding bugs.

Of course:

It could be that my instance of the problem is easy
My problem is presented in a slightly different form (SZK is a circuit class I believe)

Still, this makes me worry that checking the statistical distance of $A$ from $p(x)$ is an intractable problem. Is this true? Are there better algorithms for it than the naive one I mentioned above?

Prove your method correct.
Factor your code into a nondeterministic uniform bit sampler and deterministic logic.

You can use the full suite of standard software testing techniques for to test deterministic part.
You can use automated formal verification tools to prove the deterministic part is correctly implemented.
You can use well-studied cryptography—also with deterministic known-answer test vectors—seeded by observations from well-studied unpredictable physical models for the uniform bit sampler.

‘OK,’ you say, ‘but Shirley, you should be able to also use empirical hypothesis tests of random samples—after all, the goal is to test that a random sampler for a distribution is correct, so why not run it and apply a standard empirical hypothesis test of distribution to the samples?  Specifically, we can consider the null hypothesis that the software correctly samples from the intended distribution, and apply a hypothesis test with a specified statistical significance level for that null hypothesis!’

This is not wrong.  But there are several issues with it.

Empirical hypothesis tests of distributions are qualitatively different from the normal kinds of automatic tests you might be familiar with in software engineering, because they necessarily have false alarms:

A test for deterministic software properties rejects certain samples, because correct software cannot yield them—thus it is a bug if you encounter them.
A random test for the distribution of a null hypothesis rejects certain samples, even though correct software can yield them—the conceit, of course, is that buggy software will yield these rejected samples with much higher probability than correct software.

What do you do, then, when your test suite rejects the null hypothesis and raises an alarm?  Well, it might be a bug, or it might just be a fluke!  Better run it repeatedly to make sure that the rate of alarms is exactly what the significance level was set to—so maybe we should run a hypothesis test for the null hypothesis of iid Bernoulli trials weighted by the significance level, but what do you do if that test fails?  Well, it might be a bug, or it might just be a fluke…
For these empirical tests to be useful, they need high statistical power to detect the bugs that might be in your program.  So you need to hypothesize plausible bugs, and confirm that the tests have high statistical power to detect those bugs.

You could hypothesize specific bugs that occurred during development, and relatively easily make tests for them.

But, you could also just test those in the deterministic part of your program.
You could hypothesize bounds on statistical distances: null hypothesis, $D(P \mathbin\| Q) \leq \varepsilon$; alternative hypothesis, $D(P \mathbin\| Q) \geq \varepsilon + \delta$.  Then you can choose hypothesis tests that are guaranteed to have certain false alarm rates and statistical power for those alternative hypotheses.  You could even choose the two bounds to use different statistical distances, e.g. the null hypothesis might be bounded KL divergence while the alternative hypothesis is a bug of excess Hellinger distance.

But, the numbers of samples required for these tests to attain prescribed false alarm rates and statistical power are usually superlinear in $1/\varepsilon$ and $1/\delta$—if they exist at all with such guarantees, which for some statistical distances $D$ they do not!
You could just apply standard hypothesis tests and blindly hope they'll catch bugs.  Actually in practice this works quite well during development to catch obvious bugs early on.

But, it doesn't get you very far.

As your system gets bigger, you will be tempted to expand the tests you do.

With deterministic property tests, adding a test case to a test suite just means each run of the test suite takes a little more time.
With $n$ random hypothesis tests, if each test case has a false alarm rate $\alpha$, the test suite has a false alarm rate $1 - (1 - \alpha)^n$ which rapidly approaches $1$—i.e., false alarms nearly all the time—as $n$ increases.  What can you do when you add a new test?

Leave the false alarm rate of the test cases alone.

But, then if you had calibrated the test cases so that the test suite has a prescribed false alarm rate, that rate will go up as you add more tests—even if the software is working perfectly!
Whenever you add a test case, recalibate all the test cases to have false alarm rate $\alpha' < \alpha$ so that $1 - (1 - \alpha)^n = 1 - (1 - \alpha')^{n + 1}$, i.e. choose $\alpha' = 1 - (1 - \alpha)^{n/(n + 1)}$.

But, the number of samples needed in each test case to maintain the same statistical power at lower false alarm rates tends to grow rapidly with $n$.
Give up on a notion of ‘tests passing’, and instead record a detailed history of test case runs on which you can do meta-analyses later.

But, software people don't like it when the answer from a test suite isn't just PASSED or FAILED, and none of the standard tools like Jenkins are designed to cope with such nonbinary fluidity of notions of test results, as is typical for the white cismale culture in Silicon Valley that dominates software engineering tooling.

My name is Squeamish, not Shirley.
If we're talking about cryptography, the statistical distances are generally going to be so small you don't have a snowball's chance in a Manhattan trash can on a summer day of detecting them anyway.  So go back to step 1: prove your method correct.

Of course, all of this depends on more details about what you're doing.  Maybe, for your application and your distribution and your sampler and your type of statistical distance and your bound $\varepsilon$ on magnitude of statistical distance and your tolerance $\delta$ on magnitude of statistical distance and your development process and your toolchain, you can actually address all these concerns, in which case, great!  Go for it!


Is there a difference between private key cryptography and symmetric encryption? I have often seen these terms being used interchangably, but is that correct? Are there Private Key Algorithms that do not use Symmetric Encryption?

Private key cryptography is often used as synonym for symmetric cryptography, that is, cryptography with constructs that use a symmetric key. For instance professor Katz uses this terminology.

Symmetric keys can be used for e.g. a block cipher such as AES, a stream cipher such as RC4. HMAC - which is a keyed hash construct - also uses a symmetric key, and doesn't use a cipher at all. The term "symmetric encryption" is usually limited to constructs that provide confidentiality, although authenticated ciphers may also provide integrity and authenticity of the encrypted messages.

So the question " Are there Private Key Algorithms that do not use Symmetric Encryption?" has the response "yes" for the simple reason that HMAC it does not provide encryption, and it is certainly a private key algorithm. Symmetric encryption which is a goal rather than a construct uses certain private key algorithms to accomplish the goal.


Why is $h(H, m) = E(m, H) \oplus m$ insecure? I am taking a cryptography class on Coursera. I learned that the compression function $h(H, m) = E_m(H) \oplus m$ is insecure (even though other variants like Davies-Meyer or Miyaguchi-Preneel are secure).  Why is this compression function insecure?   What is the attack?

(See also Why are the Davies-Meyer and Miyaguchi-Preneel constructions secure? for a related question.)

Well, the problem with $h(H,m) = E_m(H) \oplus m$ is that it makes the preimage attack easier than we'd expect; with a 128 bit hash, we'd hope that it'd take around $2^{128}$ attempts to find a preimage; with this compression function, we can find a preimage with only around $2^{64}$ effort.

This happens because this compression function is reversible; with a fixed m and a target value J, as one can efficiently find the H with $h(H,m)=J$, namely, $H = D_m(J \oplus m)$ (where $D_m$ is the decryption operation using $m$ as a key).

Here is how we use this property to find a message that hashes to $J$:

We select $2^{64}$ distinct initial blocks $m_1, m_2, ..., m_{2^{64}}$, and compute the $2^{64}$ values $h(H_0, m_i)$, where $H_0$ is the fixed IV of this hash function
We select $2^{64}$ distinct final blocks $n_1, n_2, ..., n_{2^{64}}$ and compute the $2^{64}$ values $h^{-1}(J, n_i)$, where $h^{-1}$ is the compression function run backwards.

Search the two lists for a common value; assuming a 128 bit hash, a collision is likely.  If we find a pair with $h(H_0, m_i) = h^{-1}(J, n_j)$, when we have found a message $m_i || n_j$ which hashes to $J$.


Are there known special cases where the first 160 bits of keccak256 can be null ? Or does finding a collision is required? In the Tronix contract code (a large ICO listed on many exchanges) lies this modifier which is used for all token transfers :

modifier validAddress {
    assert(0x0 != msg.sender);
    _;
}

The code is written by serious professionals : not the kind of Ponzi scheme coder leaving useless code that cost money to everyone while processing transactions. As the contract is no longer maintained, developers are no longer replying on such questions (mailto:service@tron.network).
The point is msg.sender is set by the network : contract cannot act on that value.

Most of time unofficial answers I’m getting is it’s indeed possible to send transactions as 0x0 : that is Keccak256(ECDSASIGN(transaction_data_to_sign,e, c, v)[1:])[12:] where Secp256k1 is used would returns NULL.

So… First, are there known keccak256 values that would return NULL once truncated or does NULL involve bruteforcing like all other values ?

No. SHA-2, Keccak, and serious alternatives to those two are all assumed to be model-able as a random oracle. Given an valid input it will return back a bit string chosen from a uniform random distribution.

The probability of any one such string starting with an all zero 160 bit prefix is $2^{-160}$. That's too small to find by chance. The amount of work to search for such a string should therefore be about equivalent to $2^{160}$ hash evaluations. That would consume a lot of time and a lot of power. So much so that it's impossible for any of us Earthlings to acheive.

If there is a way to search for inputs whose outputs have a certain property which is faster than by brute force, then that means the algorithm is broken. An attack that lets you easily find inputs that result in output bits set to a certain value is called a (partial) preimage attack.

Edit: I answered only the cryptography part of the question. Not the cryptocurrency. That's off topic for this site. Also off topic is the contract code. There could be some subtle (or obvious) problem in the code that causes problems or enables scams. Maybe there is some type conversion rule that mixes up zero values, null pointers, none-value. Maybe errors propagate as null pointers or zero return values. Do not interpret my not covering non-cryptography material as endorsement of a product.


Small Prime Difference in RSA In RSA, the $p$ and $q$ should be randomly generated, and they are the same size. The difference between $p$ and $q$ should not be small.

Suppose that $u=|p-q|<20$ and $p \times q =2189284635403183$. Find the values of $p$ and $q$.

I have no idea how to compute $p$ and $q$. I use calculator to compute square root of thr product. But it is definitely not correct as I get something ends with $2$. Can anyone help me?

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists.

Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by at most (very slightly less than) $|p-q|\over2$ candidates. Some easy speedups are possible (skipping even candidates, generalizable to candidates divisible by the first few small primes).

The method described in this comment, and equivalently in this answer, also work. They succeed after testing at most $|p-q|\over2$ candidates. Depending on implementation (of the squareness test in particular), speed can be slower or faster than trial division.

I'll describe a method that avoids any trial and error under the assumption that $|p-q|<(64n)^{1/4}$. With the given $n=2189284635403183$, that translates to $|p-q|<19348$, which very comfortably holds since $|p−q|<20$ is given.

Theorem: Given any odd integer $n$, if there exist unknown integers $p$ and $q$ with $n=p\times q$ and $(p-q)^2<8\sqrt n$, the following non-iterative algorithm outputs these $p$ and $q$:

compute $a=\lceil\sqrt n\rceil$ (that is, the smallest non-negative integer which square is at least $n$)
compute $s=a^2-n$, which amazingly will be the square of some integer
compute $b=\sqrt s$ (that is, the non-negative number which square is $s$)
output $a+b$ and $a-b$.

Proof:

Without loss of generality we reorder $p$ and $q$ so that $p\ge q$. We know $p$ and $q$ are odd, since their product is. Thus, when we define $c={p+q\over2}$ and $d={p-q\over2}$, these are non-negative integers. Further, $c^2-n=d^2$ holds.
In step 1 of our algorithm, $a$ is computed as the only non-negative integer $x$ satisfying $x^2-n\ge 0$ and $(x-1)^2-n<0$. From $c^2-n=d^2$ it follows that $x=c$ satisfies the first of these conditions. The second condition is $(x-1)^2<n$, which is satisfied if $0\le x-1<\sqrt n$, that is $1\le x<\sqrt n+1$. $x=c$ satisfies $1\le x$, since $c={p+q\over2}$ with $p\ge1$ and $q\ge1$. Thus $c<\sqrt n+1$ would imply $a=c$.
Since $c\ge0$, we can equivalently prove $c^2<(\sqrt n+1)^2$, that is $n+d^2<(\sqrt n+1)^2$, that is $({p-q\over2})^2<(\sqrt n+1)^2-n$, that is $(p-q)^2<4((\sqrt n+1)^2-(\sqrt n)^2))$, that is $(p-q)^2<4(2\sqrt n+1)$. It follows from our hypothesis $(p-q)^2<8\sqrt n$.
We have shown that step 1 produces $a=c$; thus step 2 produces $s=a^2-n$ equal to $d^2$; thus step 3 produces $b$ equal to $d$; thus step 4 outputs $p$ (for $a+b$) and $q$ (for $a-b$), Q.E.D.

The above is the basic Fermat factorization method, but reduced to its first step and without any test (because we can do without it in the question, and that simplifies our algorithm and proof). The full basic Fermat method performs $\Big\lceil{(p-q)^2\over8\sqrt n}\Big\rceil$ tests, and thus requires less computing effort than trial division from $\sqrt n$ by a factor of $O\big({\sqrt n\over|p-q|}\big)$ as a first-order approximation; this can be huge, but only when $|p-q|$ is much smaller than likely under random selection of $p$ and $q$ in an interval of width a sizable fraction of $\sqrt n$. Description of Fermat's methods, classic improvements, and computing cost, would be the subject of a different question.


Homomorphic encryption - Why does addition not imply multiplication? As far as I know:

There are some partially homomorphic encryption (PHE) systems that support either addition or multiplication.

A fully homomorphic encryption (FHE) system can do addition as well as multiplication and thus supports arbitrary computation on ciphertexts.

My question is (disregarding computational efficiency):

Why does a PHE-system that allows addition on ciphertext not directly imply that it also can do multiplication, since

$$a \times b$$

is the same as

$$\underbrace{a + a + \cdots + a}_{b\text{ times}}?$$

Are there some computations that are only possible with a direct multiplication instead of a continuous addition?

There are at least two problems;

The $b$-times addition leaks the $b$. A semi-honest observer can see that you add the $a$ by $b$ times. However, in FHE, the $b$ is also encrypted with semantically secure that leaks no information. The only information available to the observer is the circuit.
In FHE, the $b$ is coming (or may come) from another result, which means that $b$ is also encrypted. In additive PHE, you cannot multiply by $b$ without decryption.

You can look at some example of FHE circuits from this answer to see that some of them are not even possible with additive PHE.


Is fixed key AES in counter mode a PRG? I want to implement a PRG (Pseudorandom Generator). As AES is implemented in hardware, I am planning to use AES for efficiency. I am planning to use:

$(AES_k(seed) \| AES_k(seed+1) \| AES_k(seed+2) \|....)$

as a PRG ($k$ represents the key of AES). The receiver of this sequence does not know the random seed, but knows the AES key $k$. So, is this sequence a provably secure PRG, when the AES key is known (at least in ideal cipher model)?

Hint: given $AES_k(seed)$ and the key $k$, what can an adversary compute? Should this be possible for a secure PRG?

A better option would be standard CTR mode, i.e. $AES_{seed}(0) \| AES_{seed}(1), ...$


Is it okay to send an encrypted key using XSalsa20-Poly1305, and send subsequent messages using ChaCha20-Poly1305? I am looking at a cryptographic protocol in a somewhat unusual environment: the communicating parties can share arbitrarily long secret keys over a secure channel.

If forward secrecy is not required, it seems that one can simply encrypt/authenticate a (random) 256-bit key using the 256-bit shared secret, and then start sending messages encrypted using ChaCha20-Poly1305 (or AES-GCM).  This seems to be trivially secure assuming that the underlying ciphers are secure (Proof: The attacker cannot forge or reorder messages after the first without breaking the AEAD or knowing its key -- but to obtain the key the attacker would need to break XSalsa20-Poly1305 or the CSPRNG used, or the 192-bit nonce of XSalsa20-Poly1305 would need to be reused, or the shared secret would need to be leaked.  The AEAD and XSalsa20-Poly1305 are both widely believed secure, the shared secret must be assumed secret, and the probability of a 192-bit nonce collision is negligible).  A counter starts at 0 each time, serving as both message sequence number (to prevent reordering) and nonce.

TLS-PSK is designed for this, but it is extremely complex.  This seems much simpler.

Yes, this is secure.

Even simpler would be to just use XSalsa20-Poly1305 and the long term key directly. You could authenticate any additional data with the Poly1305 just as well as in the case of the ChaCha-based combination. However, if you use e.g. libsodium where the former interface does not support additional data and the latter has a short nonce, then combining them like you suggest is OK as well.

Note, regarding your comment: there is no need to authenticate the message length separately. The whole message is already authenticated by default so you can just calculate its length.

If the only additional data you need to authenticate is a sequence number, you could include it as part of the 192-bit nonce and use XSalsa20-Poly1305 only. 128-bit random part and 64-bit sequence number would be fine, and 160/32 would be even better.


Finding a winner in mental poker game In a mental poker game I am designing as an learning exercise, (One used in example is a 3 card flash with no desk cards) suppose I have a set of cards and other person also has a set of cards. each card is mapped to a prime order (EC)DH group element. We both know other persons cards raised to some power. That is if my opponent has cards c1, c2 and c3, I know c1z1, c2z2 and c3z3, with z1, z2 and z3 being known only to my opponent. The mapping (which card maps to which group element is publicly known) and what my opponent knows is the discrete logarithm of the numbers I know he has base a valid card. Of course this is exactly what my opponent knows about my card too. Now is there any way to find out who won without revealing the cards or any other information about my cards (like whether the doubles or sequences exist), as in zero knowledge proof.
EDIT:
Just realized that it is called Pohlig-Hellman cipher. I assume others know what I am trying to do with this to shuffle cards. I guessshould be we can create a EC version of it too. While I understand that it is not IND-CPA, I don't think that it much of a problem in this game.
I looked at security problems with PH cipher but almost all of them has to do with the fact that it can distinguish plain texts based on whether or not they are QR modulo p in group ℤp* and they are malleable. Actually, I need to use this malleability. This malleability is what allows players in my game to produce a proof that they have not cheated, I realized that the proof will be too damn long tho). But the game I am designing uses no Quadratic non-residue, the group is a $q$ order subgroup of quadratic residues as we often use for Diffie-hellman and (large prime subgroup as we normally use in EC versions), the card to group element mapping must be pseudo random and different in each game, agreed to by each player. My another question is are there any other security risks associated with it?

OK
I had asked this unanswered question earlier and now, I think I have an answer (sort of), not really but I think I know where to look for it. We assign each type of card combination a score such that a winning card combination always has a higher score and a tie always have equal score.The two players then play Yao's millionaire's problem to decide who is winner. With mapping known, a player who reveals the secret exponentiations (or cards) and the secret data used to provide his/her input to the problem, one can easily verify that they have shown scores honestly. Which means that the problem is in NP and thus the player should be able to construct zero knowledge proof showing that the score really reflects his card rank without revealing either the cards or the score according to a 1987 paper.That way two players can check who won without actually revealing his/her cards


In GnuPG, what's the difference between --s2k-cipher-algo and --cipher-algo? I want to change some encryption options while using GnuPG to encrypt a file symmetrically.

1) However, for choosing the cipher algorithm, GnuPG has two commands and I don't know which one to use.

Between these two, which one should I use?

  --s2k-cipher-algo AES256

  --cipher-algo AES256

2) Also for choosing the digest algorithm, there are two options,

Between these two, which one should I use?

  --s2k-digest-algo SHA512

  --digest-algo SHA512

3) Is there anything wrong with this encryption?

  gpg -symmetric --cipher-algo AES256 --digest-algo SHA512 --s2k-mode 3
  --s2k-count 65011712 PlainText

Edit: This is not a duplicate question, I can't find any post here on Stackexchange or any where in the net that specify the difference between --s2k-cipher-algo and --cipher-algo.

(1,2) You could use:

gpg2 --s2k-mode 3 --s2k-count 65011712 --s2k-digest-algo SHA512 --s2k-cipher-algo AES256 --symmetric /*file path*

According to The GNU Privacy Guard Manual, p. 71, we use --s2k-cipher-algo name when we want to apply symmetric encryption with a passphrase if --cipher-algo name or --personal-cipher-preferences string have not been set.  The default is AES128 for GnuPG 2.1 and higher.  The setup above is the strongest one available in the OpenPGP Proposed Standard (RFC 4880).

The result will look like this (but the salt will surely be different):

gpg2 --list-packets /*file path*
 gpg: AES256 encrypted data
 gpg: encrypted with 1 passphrase
 off=0 ctb=8c tag=3 hlen=2 plen=13
 :symkey enc packet: version 4, cipher 9, s2k 3, hash 10
    salt 406974B08EF1428B, count 65011712 (255)

(3)

Yes, there were two errors:  one hyphen was left out in front of symmetric.  It should be:

--symmetric

Secondly, after  --s2k-count 65011712 one should put the path to the file.  Those usually look something like this:

/home/me/Documents/myfile

Keep in mind what your goals are.  Perhaps you should focus on using a very strong passphrase:  long, truly random, using all possible characters.

So, in short, those pairs of commands you listed do the same things, but the s2k specifiers only apply to symmetric encryption with a passphrase (note that s2k specifiers have another function: in the encryption of the secret part of private keys in the private keyring).


Java - What are the additional 8 bytes of output generated by AES/CCM/NoPadding? What are the additional 8 bytes of output used for in Java's (Bouncycastle) AES/CCM/NoPadding? I do not believe this is padding as I am requesting "NoPadding," and the block size is not 128, 192, or 256 bit. Is this some sort of Message Integrity Check (MIC)?

For example:

Encrypting 16 bytes yields 24 bytes of output.
Encrypting 20 bytes yields 28 bytes of output.
Encrypting 31 bytes yields 39 bytes of output.

BTW.: The reason I ask is that I am trying to send/receive encrypted data from a bluetooth node. The bluetooth's firmware, written in C, encrypts data with AES/CCM with the same first 16 bytes of output as I get here, but only produces a 4-byte MIC (total of 20 bytes). I'm working on finding a solution to this. Apparently Bouncy Castle isn't supported in C?

The additional 8 bytes are the Message authentication code (MAC), which is called the Message integrity check (MIC) in Bluetooth terminology.

For more info, see here.


Which MAC to choose? I am currently reading Cryptography Engineering by Bruce Schneier and Niels Ferguson. There is this chapter about MACs and they recommend HMAC-SHA-256, but with the side note that SHA-3 will be most likely be recommended in the future.

I wanted to google what MACs are currently recommended but couldn't find satisfying pages. If I search for something including MAC I will only get some computer pages (thanks apple) and if I type it out it shows only general pages that show how they are generated or pages that are already a few years old and maybe outdated.

I don't want to know how to construct MACs or how I should use them. My questions are:

Which MACs are currently considered as secure?
Where can I get information about the currently recommended MACs myself?
Is there maybe a list that shows recommended MACs for either speed or security?
How do you keep yourself up-to-date with the newest MACs, hashes, cyphers, implementations, ...?

Maybe the first question is to much opinion based and to fast out of date so feel free to ignore the first one.

As a MAC, HMAC is fine, with any of the SHA-* functions. It's even fine with MD5, even though MD5, as a hash function, is quite broken. One interesting characteristic of HMAC is that it requires no nonce or IV, which makes it quite harder to get it wrong. It's also very easy to implement (over a hash function implementation), and a straightforward implementation will even be constant-time.

Now, HMAC is defined with two nested hash function invocations, so as to provide a secure MAC when the underlying hash function is a Merkle-Damgård design (like SHA-1 or SHA-256). SHA-3 was defined so as to make that double invocation unnecessary; with SHA-3 you can simply hash the concatenation of the MAC key and the data, and that is a good MAC, while doing the same with SHA-256 or SHA-512 would fall prey to the so-called length extension attack. However, you can also use HMAC with SHA-3, it works and is not insecure.

Over long input data, HMAC has about the same performance as raw hashing, so it is quite fast, and it takes some effort to find a situation when that speed is not already more than sufficient. If you found a case where you actually need an extra boost, then there are other MAC constructions that can give it to you, e.g. Poly1305. However, they are more difficult to implement, and even more so to use properly, because they need a non-repeating nonce, which is not a simple requirement in many contexts.

That being said, most usages of MAC are, in practice, part of protocols that combine MAC and encryption. Making both safely is known to be fraught with perils (SSL, famously, got it wrong), so you would be well-advised to use an authenticated encryption mode that will do the job in a cryptographer-approved way. Usual AEAD modes include AES/GCM and ChaCha20+Poly1305. Selecting such a mode voids the question of choosing a stand-alone MAC.

Speaking of good advice, Schneier and Ferguson got it wrong (at least in the first edition of their book), in that they recommend to use MAC-then-encrypt (MAC on the plaintext, not on the ciphertext), which is exactly what plagued SSL/TLS before TLS 1.2 introduced AEAD-powered cipher suites.


Encrypt-then-authenticate variant used in IPsec I am trying to understand the variant of Encrypt-then-Authenticate (EtA) that is used in IPsec. For this I have looked at this chapter.

What I got so far is that the integrity and confidentiality computations cover different parts of the EPS packet. What I don't understand is what exactly is done and how this is different from the general EtA composition (i.e. what is modified in comparison to the general EtA composition).

This is standard Encrypt-then-Authenticate. The only difference is that when doing EtA, it actually isn't necessary to encrypt everything. This strategy makes sense when there is some part of the message that needs integrity and not privacy. In IPSec, the ICV (which is a counter to prevent replay) does not need privacy. Furthermore, by not encrypting it, it is possible to not have to decrypt in order to check if a packet is being replayed (rather, it suffices to check the MAC).

It is important to note that it is possible to use IPSec incorrectly, and do MAC-then-encrypt. This is achieved by computing the IPSec authentication header, and then encrypting. Despite being recommended by some experts, this is BROKEN! So, if you want privacy and integrity, then it should all be done inside the ESP, as is described here.

The fact that AtE is broken in IPSec is not theoretical. See, for example, the paper On the (In)Security of IPsec in MAC-then-Encrypt Configurations by Degabriele and Paterson.


is this range proof i made sound? so to prouve a value $v$ is in range $[0,2n−1]$ we convince the verifier that $v$ is represented by a binary vector $a∈\{0,1\}^n$ so that $<a,2n>=v$
$//$ $2n∈Zn$
is the vector of powers of $2$ satch that $2n={2^0,2^1,2^2,,,,,2^n}$
we have $r∈Zn$ a random vector for blinding
we also have $G$
an eleptice curve generator and $A,R1,R2,R3,R4,V$ are eliptice curve points such that :
$A=<a,1>G,R1=<r,1>G,R2=<2n,r>G,R3=<a,r>G,R4=<r,r>G
$ and $V=vG$
//
for an example $R3$ equals : $R3=(a_1*r_1+a_2∗r_2....+a_n∗r_n)G$
the prouve goes like this:
$-$ the prouver send $A,R1,R2,R3,R4$ to the verifier
$-$ the verifier send back a challenge : $x$
$-$the prouver compute and send:
$fx=xa+r$
$-$ the verifier verify:
$<fx,1>G=?=xA+R1$  $//$ check that $fx$ was constructed corectly
$<fx,fx>G=?=x^2A+xR3+R4$        $//$ check that $a$  is a binary vector because a binary vector is the only vector where $<a,a>=<a,1>$
$<fx,2n>G=?=xV+R2$  $//$ check that $<a,2n>=v$
is this prouve sound? i'm a beginner so probably not
thanks and let me know if anything is unclear

If you're using the syntax $<a, b>$ to mean dot-product, then the assumption that you make:

a binary vector is the only vector where $<a,a>=<a,1>$

is incorrect.  It is correct in the ring $\mathbb{Z}$, however we're not in the integers, we're in a finite field.
Counterexamples in finite fields are easy to find; for example, in $GF(11)$ (picked solely because it's large enough to be nontrivial, but small enough for the computation to be easy), we find that for $a = \{ 2, 5 \}$, we have:
$$<a, a> = 2 \cdot 2 + 5 \cdot 5 = 4 + 3 = 7$$
$$<a, 1> = 2 \cdot 1 + 5 \cdot 1 = 2 + 5 = 7$$


Secure way to store fixed size string of digits I need to store a string of digits (0-9) of a fixed size in my database securely.

I've already performed a rainbow table attack on a plain hash, and it broke it in a matter of seconds.

One option I had was to break the string into 2 or more parts and store them separately, within reason (i.e do not have the resources for multiple servers), but I feel like this will only delay an attacker a small amount.

The other option is using salted hashes, but I'm not sure if this will help in this case.

Does anyone have any suggestions?

It'll be the same situation that NY City suffered some days ago: when you have little variability on your data, i.e., they have a fixed-small size, it'll always be fast to brute force.

You don't say how long your number is, so I'll assume it can range from 0 - 10,000,000,000 (so, a unique number for each human being on Earth today, plus some spare).  You said that you'll have 9 digits, so anything I say below will be 100 times faster.

In that case, using any kind of hash will only delay the attack by some amount. If you use MD5 hash, some hardwares can calculate 28 Billion hashes/sec.

If you use a unique, random salt for each number, once the attacker finds our the salt (it's not secret, since it's stored in the database), he'll only need to calculate those hashes including the salt, and will take 1 sec for each number you have. No good.

Other hashes (SHA in general, Scrypt, etc and etc) will again slow things down, perhaps requiring more memory, but they won't do magic: in the end it'll be just a matter of time.

And what about changing your digits, for example encoding it so that it'll have letters on it? Still, won't solve your problem, because your data can only have 10 billion variations (in my hipotheses, your case might be even worst).

And what about making another table, with correspondence, that was a proposed solution to the NY City data? Won't do any good to you, since if someone is able to access your number, or their hashes, probably he'll be able to access those data too.

What would I do in your case?

1 - If the data will be inside your system, in your database, and in your company, and not available via web systems: protect as hard as you can using firewalls, blocking who can access the database, scrutiny of your workers, and pray. If some computer of your network is compromised, it might have privileges to access the database, and you're gone.

2 - The data must be exchanged with other systems or other companies: although there are hardware designed to protect data communication (quantum encryption, etc), you'll have to worry about your insiders again, and external attacks on your computers, and the previous scenario still applies.

3 - Does your data really needs to be secret? Perhaps what you can do (or I would do) is nothing. If you have a small number of possibilities for your data, concatenating more information (be it a salt, the email of the user, anything else) won't help, since all that "information" will be stored somehow in your database, or in your code, and will be accessible anyhow.

Protect only the hardware with physical protection (like using HSM) isn't enought. You also need to worry about the ways the application needs to access that information, and in what aspect it would be different if a hacker gained control of one computer inside your company and what he also would be able to do with a keylogger, screenlogger, and so on.


What is the difference between SHA-3 and SHA-256? I am new about cryptography,
I learned that SHA-3 (Secure Hash Algorithm 3) is the latest member of the Secure Hash Algorithm family of standards, released by NIST.

But I recently saw SHA-256 but I don't get what is it in comparison to SHA-3 ?

The main differences between the older SHA-256 of the SHA-2 family of FIPS 180, and the newer SHA3-256 of the SHA-3 family of FIPS 202, are:

Resistance to length extension attacks.
With SHA-256, given $H(m)$ but not $m$, it is easy to find $H(m \mathbin\| m')$ for certain suffixes $m'$.  Not so with any of the SHA-3 functions.

This means, e.g., that $m \mapsto H(k \mathbin\| m)$ is not a secure message authentication code under key $k$ when $H$ is SHA-256, because knowing the authenticator on one message lets you forge the authenticator on another.  The length extension property partly moviated the development of HMAC.

In contrast, the key-prefix construction is secure as a MAC when $H$ is any of the SHA-3 functions—or either of the newer SHA-2 functions SHA-512/224 and SHA-512/256.  For SHA-224, which is essentially the 224 bit truncation of SHA-256 (but with a different IV), the adversary has a $2^{-32}$ chance of guessing the discarded bits of output in a single trial—small but not negligible.
Performance.
The SHA-2 functions—particularly SHA-512, SHA-512/224, and SHA-512/256—generally have higher performance than the SHA-3 functions.  Partly this was out of paranoia and political reasons in the SHA-3 design process.

(In response, one of the SHA-3 finalists was spun out into the much faster BLAKE2, also widely used on the internet today, and the SHA-3 winner Keccak was spun out into the much faster KangarooTwelve.)
Completely different internal design.
SHA-2 uses the Davies–Meyer structure, an instance of the Merkle–Damgård structure, with a block cipher (sometimes called SHACAL-2) built out of an ARX network, like MD4; SHA-3 uses the sponge structure with the Keccak permutation.

There is no user-visible difference here, but it made a difference for cryptographers' confidence in the designs after many DM/ARX designs based on MD4 were broken in the late '90s and early 2000s.

History.  There has been a long line of hash functions standardized by NIST in FIPS 180, the Secure Hash Standard, and later FIPS 202¸ the SHA-3 Standard: Permutation-Based and Extendable-Output Functions.  More details and history, including the related MD4 and MD5 hash functions on which SHA-0, SHA-1, and SHA-2—but not SHA-3—were based:

\begin{equation}
\begin{array}{ccc}
\text{hash} & \text{year} & \text{coll. res.} & \text{size (bits)} & \text{design} & \text{broken?} \\
\hline
\text{MD4} & 1990 & 64 & 128 & \text{32-bit ARX DM} & 1995 \\
\text{SHA-0 (SHA)} & 1993 & 80 & 160 & \text{32-bit ARX DM} & 1998 \\
\text{MD5} & 1993 & 64 & 128 & \text{32-bit ARX DM} & 2004 \\
\text{SHA-1} & 1995 & 80 & 160 & \text{32-bit ARX DM} & 2005 \\
\hline
\text{SHA-256 (SHA-2)} & 2002 & 128 & 256 & \text{32-bit ARX DM} & \\
\text{SHA-384 (SHA-2)} & 2002 & 192 & 384 & \text{64-bit ARX DM} & \\
\text{SHA-512 (SHA-2)} & 2002 & 256 & 512 & \text{64-bit ARX DM} & \\
\hline
\text{SHA-224 (SHA-2)} & 2008 & 112 & 224 & \text{32-bit ARX DM} & \\
\text{SHA-512/224} & 2012 & 112 & 224 & \text{64-bit ARX DM} & \\
\text{SHA-512/256} & 2012 & 128 & 256 & \text{64-bit ARX DM} & \\
\hline
\text{SHA3-224} & 2013 & 112 & 224 & \text{64-bit Keccak sponge} & \\
\text{SHA3-256} & 2013 & 128 & 256 & \text{64-bit Keccak sponge} & \\
\text{SHA3-384} & 2013 & 192 & 384 & \text{64-bit Keccak sponge} & \\
\text{SHA3-512} & 2013 & 256 & 512 & \text{64-bit Keccak sponge} & \\
\text{SHAKE128} & 2013 & {\leq}128 & \text{any} & \text{64-bit Keccak sponge} & \\
\text{SHAKE256} & 2013 & {\leq}256 & \text{any} & \text{64-bit Keccak sponge}
\end{array}
\end{equation}

In 1993, NIST published FIPS 180, the Secure Hash Standard, defining SHA-0, originally just named SHA for Secure Hash Algorithm, intended for use with the newly published DSA.  SHA-0 is a single 160-bit hash function aimed at 80-bit collision security (and now completely broken), based on the relatively new and fast design of MD4 in 1990.
In 1995, NIST quietly withdrew FIPS 180 and replaced it by FIPS 180-1 defining SHA-1, which differs from SHA-0 by the inclusion of a single one-bit rotation.  Like SHA-0, SHA-1 is a single 160-bit hash function aimed at 80-bit collision security (and now completely broken).

No public explanation was given for the change, but it was not long prior that Eli Biham had published differential cryptanalysis and the academic community realized that the NSA's tweaks to the DES S-boxes in the 1970s actually improved security (never mind that they reduced the 128-bit key size of Lucifer to 56 bits for DES, completely destroying security at the same time).  The same year, Dobbertin broke MD4[1], and the next year, severely damaged MD5[2].  Not long after that, in 1998, Florent Chabaud and Antoine Joux reported a $2^{61}$-cost collision attack on SHA-0[3].
In 2002, NIST published FIPS 180-2, defining SHA-2, a family of related hash functions with different sizes: SHA-256, SHA-384, and SHA-512, named for their output sizes and aiming respectively at 112-, 128-, 192-, and 256-bit collision resistance.  The SHA-2 functions continued the design principles of MD4, MD5, SHA-0, and SHA-1, with more rounds and bigger state.  Not long after that, in 2004, Xiaoyun Wang's team reported full collisions on MD5 and other hash functions[4], and in 2005, published a $2^{69}$-cost attack on SHA-1[5], substantially cheaper than generic.  With many of the designs based on MD4 having been broken now, the everyone got nervous about that design, so…
In 2007, NIST launched the SHA-3 competition to design a successor to SHA-2, in case the design turned out to be bad.  The competition would take place over several years.
Meanwhile, in 2008, NIST updated the Secure Hash Standard with FIPS 180-3, adding SHA-224 to the SHA-2 family, and then in 2012, NIST updated it again with FIPS 180-4 (2012), adding SHA-512/224 and SHA-512/256, faster 256-bit and 384-bit hash functions on 64-bit machines with resistance to length extension attacks that let one compute $H(m \mathbin\| m')$ given $H(m)$ and certain $m'$ without knowing $m$.
In 2013, the SHA-3 competition concluded with Keccak as NIST's chosen winner, which they published in FIPS 202.  SHA-3 includes four fixed-size hash functions, SHA3-224, SHA3-256, SHA3-384, SHA3-512, and two extendable-output hash functions SHAKE128 and SHAKE256 which attain up to a 128-bit or 256-bit security level if the output is long enough.

The design of SHA-3 is completely different from SHA-2, which gives confidence that cryptanalytic breakthroughs on line of designs based on MD4 probably won't affect SHA-3, although a decade and a half after the bloodbath of the early 2000s there hasn't been much progress on SHA-2 either.  The parameters chosen for the fixed-size SHA-3 functions were kind of accidentally overdesigned for political reasons[6], so SHA-3 functions like SHA3-256 are slower than they need to be, and you should generally just use SHAKE128 or SHAKE256.


Security of Even-Mansour scheme with keyed shuffle? I was researching the Even-Mansour scheme and had a question that wasn't addressed in the paper that I saw, and google was minimally helpful.

What if a permutation that uses secret data like the Fisher-Yates shuffle was used as the F permutation instead of a publicly known one? Would the scheme still be equivalently secure?

I noticed the section in the paper that if F is an involution the security proof no longer holds. So there appear to be certain restrictions, and I'm not sure if this idea would violate them.

To understand the Even-Mansour security result, it helps to first understand the random oracle model.  Roughly speaking, the random oracle model says that a hash function should behave like a randomly chosen function, and have no detectable patterns or structural properties that a random function wouldn't have.  Of course, the hash function is publicly known, so anyone can compute it, but apart from that, it shouldn't have any other structural properties.

Even-Mansour uses something similar, but now for permutations.  The requirement in the Even-Mansour proof is that $F$ is a random permutation oracle: it has to behave just like a randomly chosen permutation (random bijective function), and have no detectable structural properties that a random permutation wouldn't have.  Of course, $F$ can be publicly known (so given $x$ anyone can compute $F(x)$ and $F^{-1}(x)$), but apart from that, it shouldn't have any other structural properties.

This is like an unkeyed version of the ideal cipher model.  See What is the ideal cipher model?.

Once you understand the ideal cipher model, you can then evaluate whether some specific construction would qualify.  It basically comes down to whether your other construction qualifies as a reasonable instantiation of a random permutation oracle (i.e., as a reasonable instantiation of an unkeyed version of an ideal cipher).

Fisher-Yates is not suitable except for constructing block cipher, as the running time of Fisher-Yates is super exponential: if you want a random permutation on $b$ bits, the running time of Fisher-Yates is at least $(2^b)!$, which grows asymptotically as something like $2^{(b-1.44) \cdot 2^b}$... i.e., huge.


Why can an elliptic curve private key be 1? I often see in papers (e.g. this one) that for an elliptic curve with generator point $G$ and order $n$ the private key $d$ can take on any integer value in the range $[1, n)$. When $d = 1$ the corresponding public key $Q = dG$ is of course then just the generator point $G$. Why is this allowed? I understand that the chances that $d = 1$ for a sufficient size curve are basically non-existant, but doesn't $d = 1$ break the hardness assumption that elliptic curve schemes are based on (i.e. if I see $Q = G$ I can immediately infer $d$ without having to compute a discrete log over an elliptic curve).

By the same argument, they would have to forbid $d = 1234$; after all, an attacker can trivially compute the value of $1234 G$; and if they see it, then they can immediately infer $d$ without having to complete a discrete log over an elliptic curve.  Of course, this logic would forbid all possible values of $d$...

The issue is that if the attacker gets lucky and guesses $d$, he wins (and there's nothing special about $d=1$ in this).  However, he is quite unlikely to get lucky (and again, there's nothing special about $d=1$ in this either).


How to calculate mapping in bilinear I am trying to read a paper in cryptography. In key generation phase, paper give a definition for bilinear like G and Gt be two cyclic groups of prime order p

$e: G * G \to G_t$.  be a map with the following properties:

and in one place i found a definition like

my doubt is in the last part. Specifically in m.e(g1,gn)^t
suppose m is any message, g1=3,gn=13 t=6 (for more information v=5,gi=10.no problem whether all the value assumptions are true or not). then how can i compute e(g1,gn)^t part? sorry for my bad math notation

According to PBC manual, Pairing functions, map $\hat e(,)$ (without t-power) could be calculated as follows:

pairing_pp_t pp;
pairing_pp_init(pp, g1, pairing);
pairing_pp_apply(r1, gn, pp); // r1 = e(g1, gn)
pairing_pp_clear(pp);

Before calculating the map, pairing parameters must be initialized.


How a sender will ensure that the public key used for encryption is the key of intended reciver? Say Alice is the sender and Bob is the receiver. Alice has the public key of Bob and wants to send some data to Bob. How Alice will ensure that the public key she is having is really belongs to Bob?

This is usually guaranteed by a Public Key Infrastructure (PKI). Typically a certificate authority (CA) signs and issues certificates that bind public keys with the associated entities' (e.g., Bob's) identity. A CA is a trusted third party such that everyone can verify the CA's signature on a certificate to see if it is valid or not. Such a verification algorithm (or the CA's public key associated with its signing secret key) has already been distributed to Alice and any other users who trust the CA (e.g., pre-installed on a laptop).


Indistinguishability Obfuscation : What are it's consequences on crypto? I was reading about the construction of IO using MIFE and compact FE . I am just curious to know what are the consequences if there exists an IO.

Indistinguishability Obfuscation (iO) is a quite powerful tool, but its implications alone are really hard to tackle - as so often, the combination of different primitives enables us to do new and exciting things.

But before going into details, I am not sure if this is clear to you:

If you can use an algorithm $A$ (in your question that would be compact functional encryption) to get some interesting property $P$ (this would be the construction of iO), then this has no consequences for $A$ itself besides the obvious - that you can use $A$ to get property $B$.
Even if $P=NP$ is true, then iO would still exist. But it is also known, that public key cryptography and oneway functions would not exist. Generally speaking, $P=NP$ would be a nightmare for cryptography, because we would loose almost all of our building blocks. However, any construction/property from iO alone would still have to hold in a world where $P=NP$ - and the meaning of "security" is severely restricted there (or phrased differently: a lot of our current definitions would be invalid).

Regarding the general construction of IO in general, I suggest reading Survey on Cryptographic Obfuscation (2015, Horváth), which gives a decent overview. But here is a problem with iO:

The elephant in the room - Multilinear Maps:

The first construction by Garg et.al.in 2013 based ona primitive called multilinear maps - with a nice definition of their security. From that they build iO, but there was a problem: Multilinear maps in the way they defined them did not exist - and as far as a I know we only have constructions for limited versions of multilinear maps. So while their construction of iO is actually secure, we don't know if their assumptions actually hold for any construction.

In Obfuscation without the Vulnerabilities of Multilinear Maps (2016, Garg et.al.) this issue is adressed quite elaborately and proposes iO with multilinear maps without the known vulnerabilities. There are also other constructions of iO out there, but there are still open questions.

As for the current state of research: The topic is still relatively new and it is not fully explored. With iO we can achieve interesting constructions, for example deniable encryption, functional encryption, non-interactive zero knowledge arguments, etc. But all of those require some other assumption (which would be invalid in a world with $P=NP$) and build upon constructions with those. And as far as I know we don't have a construction which just uses standard assumptions.

The only way to get to know all the current research is by reading all related publications on the major conferences, I don't think there is any shortcut.


Using a public key as a secret to authenticate the sender Question
I have a scenario where a public key is exchanged out-of-band with exactly one person $A$ and is later used in a key-exchange scheme with $A$.
Is knowledge of the public key (i.e., producing a valid encrypted message to the public key) a good authentication of $A$?
Example
Let's say Alice wants to set up a secure channel to Bob. All cryptographic primitives are assumed to be secure, including message authentication, encryption, etc. This is obviously a simplified example. I only care about the properties of $p_{BA}$.

Bob generates a new key pair $kp_{BA}$ that is only used for this session with Alice.
Bob shares the public key $p_{BA}$ with Alice out-of-band (such that an attacker has no way of knowing $p_{BA}$)
Alice generates a symmetric key $k$
Alice sends $k$ encrypted with $p_{BA}$ to Bob.
Bob successfully decrypts $k$.
... they use $k$ to encrypt messages to each other.

Now does 5) imply that the sender could only have been Alice?
Does 4) give an attacker information about the nature of $p_{BA}$?

In general this is not secure.
Proof (by Maeher): Given any public-key encryption system, we can make a variant that prefixes the ciphertext with the public key. Since the public key is assumed public (hence its name) in all standard security definitions, the new system is as secure as the previous one from the perspective of such definitions. But if we use that variant in the question's scheme, at step 4 Alice now sends the public key and some cryptogram. An adversary intercepts her message to Bob, gets the public key, generates a new $k$, encrypts it with the public key per the variant cryptosystem, then impersonates Alice including in step 6.
Another example, this time using a well-known (though insecure) public-key encryption scheme, would be textbook RSA encryption: at step 4 Alice computes and sends $k^e\bmod n$. An adversary replaces that cryptogram with the integer $1$ (or $0$). Bob successfully decrypts that message, to $k=1$ (or $k=0$), because $1^e\bmod n=1$ (or $0^e\bmod n=0$) for all RSA public keys $(n,e)$. Again the adversary knows $k$ and impersonates Alice including in step 6. Also, textbook RSA is among schemes performing essentially no check after decryption, thus step 5 just can't fail.
If on the other hand we use RSASSA-OAEP, I see no attack. That's because (contrary to Textbook RSA) there are stringent checks after decryption, no obvious way to craft a cryptogram that pass them without the public key, and only very little exploitable information about the public key leaking in a cryptogram. For any attack I think of, the question's protocol will stop at step 5 (if Alice was not involved in preparing the cryptogram) or/and it will use at step 6 a key chosen by Alice and unknown to the adversary. But this is not how RSAES-OAEP is designed to be used, thus that security is accidental and is not to be relied upon.
Exchanging out of band the secret key for a symmetric cryptosystem, and optionally using that to build a session key $k$ will do better.


What does this paraphrase of the birthday problem mean? The following is an excerpt from A Generalized Birthday Problem - David Wagner:

  One of the best-known combinatorial tools in cryptology is the birthday problem:
  Problem 1. Given two lists $L_1, \space L_2$ of elements drawn uniformly and independently at random from $\{0, 1\}^n$, find $x_1 \in L_1$ and $x_2 \in L_2$ such that $x_1 \oplus x_2 = 0$.

It's not so intuitive for me to understand. In my understanding, the birthday problem is about the probability that at least 2 people in a room have the same birthday. How does the birthday problem transfers to this? Please give me some hints.

$x_1 \oplus x_2 = 0$ is equivalent to $x_1=x_2$ (because $\oplus$ is bitwise XOR, and that equivalence stands for bits, and multibit quantities being equal in all their respective bits is equivalent to these quantities being equal).

Now assume that $x_i$ is the birthday of person $i$ in the room, expressed as days since the first day of the year, in binary, with a year of $2^n$ days, and what's meant should be clear.

Notice that the problem studied in the quote is about two lists/rooms, rather than one in the standard birthday problem.


What are the roles of the simulator in simulation based proofs I'm trying to better understand simulation based proofs in the UC model - but the guidelines to construct a simulator confuse me. To my understanding, the simulator is activated in two ways:

Outbound: S simulates the real world adv. A and as such, it intercepts all its messages and sends them to the ideal functionality.
Inbound: The ideal functionality F leaks some information (depending on the protocol) when an honest node interacts with F.

Assuming the above is true (please correct me if I'm wrong or if it's incomplete), what does the simulator try to do? Does it run the real world protocol somehow? Does it alter the output when called in #1 or #2 such that it matches the real world execution, and then sends it back to the env.?

In general, the role of the simulator in simulation-based proofs is to show that the real protocol behaves like some idealized one. Actually, simulation goes back to the original definition of semantic security for encryption and is also the way zero knowledge is defined. In these settings, the aim of the simulator is to show that nothing is revealed (in encryption, nothing beyond the length of the plaintext; in zero knowledge, nothing beyond the validity of the claim). For concreteness, consider zero knowledge for a moment. In this setting, we construct a simulator who outputs a view of the verifier that is indistinguishable from its view in a real proof execution. Now, if the verifier can learn something from the proof itself, then we can run it also on the view generated by the simulator (or it itself can run the simulator on itself) and it will learn the same thing (up to computational indistinguishability). However, the simulator does not know the witness and it only knows the public statement being proved. Thus, this proves that the only thing that the verifier can learn is what can be learned from the public statement and a single bit that the statement is in the language.

When we consider the more general setting of secure computation, the adversary is allowed to learn the inputs and outputs of all corrupted parties. Thus, the role of the simulator here is to simulate the view of all corrupted parties, given their inputs and outputs. The problem that arises first is that the corrupted parties may change their inputs and so this is not something which is well defined. Thus, we consider an IDEAL MODEL with a trusted third party who receives the parties inputs and provides their outputs. The simulator works in this ideal model, and the requirement is that the output distribution of the honest parties and the simulator in an ideal execution is computationally indistinguishable from the output of the honest parties and adversary in a real execution. Once again, this shows that anything that a real adversary can do, can also be achieved in the ideal model. However, trivially, the only thing the simulator can do in the ideal model is to chose the corrupted parties' inputs. Observe that the simulator (who we also call an ideal-model adversary) actually has two types of interaction:

The simulator externally interacts with the trusted party, sending it the corrupted parties' inputs and receiving back their outputs. This is real interaction with an external party.
The simulator internally interacts with the real adversary and generates a view that is indistinguishable from its view in a real execution. This is not required by definition per se, but is really the only way to work. Note also that this is not real interaction, but the simulator runs the real adversary internally. It is necessary to do this in order to make sure that the output distribution is like in a real execution. Thus, the inputs used by the corrupted parties are effectively extracted by the simulator, and other events (like if a corrupted party aborts) are also detected. In the standard definition of secure computation, the simulator runs the adversary internally and so it can rewind it and do other tricks. The input extraction is necessary since the simulator needs to send the corrupted parties' inputs to the ideal trusted party (as in the previous item). Thus, it needs to be able to extract the effective input used by the real adversary. This shows that protocols that are secure under this definition have the property that all inputs are fully defined!

When it comes to universal composability, things become more complex since there is another entity called the environment. This is an external entity and the real and ideal adversaries interact with it (as real external interaction). The aim of the environment is to try to distinguish if it is interacting with a real adversary running a real protocol with honest parties, or if it is interacting with an ideal adversary/simulator and a trusted party computing the ideal functionality. In this case, we have the following interaction:

The ideal adversary interacts with the environment and hands it messages that it expects to see from the real adversary; this is real external interaction. In general, if the simulator generates a view for the real adversary that is indistinguishable, then whatever the internally simulated real adversary wants to send to the environment is just forwarded by the simulator to the environment (and whatever is sent back is forwarded to the internally simulated real adversary).
External interaction with the trusted party, as above
Internal interaction with the real adversary, as above. Note that a real adversary can forward every message it receives immediately to the environment and can get back some response (and in fact, it could be the environment who decides on all actions by the real adversary). This actually prevents the simulator from rewinding the real adversary since essentially it is the external environment who runs the adversary, and this is external interaction with the simulator and so cannot be rewound.

I know that this is all very complicated, but with some considerable effort, it makes sense in the end...


Bilinear map assumpion Is there an assumption that says from a tag $k\cdot e(g,g_1)^{rx}$ ($k,r$ are secret) it is difficult to forge it with some x': $k\cdot e(g,g_1)^{rx'}$, as long as you cannot solve DL in $\mathbb{G}_1$ or $\mathbb{G}_2$?

It is obvious that the only way to forge is to extract the randomness $r$ such that you forge with $k\cdot e(g,g_1)^{rx}\cdot e(g,g_1)^{rx'}$ for a valid forged tag $k\cdot e(g,g_1)^{r(x+x')}$.

But it is not obvious how to build the reduction from Dl. Assuming $\mathcal{B}$ receives $g^a$ either in $\mathbb{G}_1$ or $\mathbb{G}_2$,then it gives to $\mathcal{A}$ tags $k\cdot e(g,g_1)^{ax}$.

At some point we assume $\mathcal{A}$ forges with $e(g,g_1)^{ax'}$. How this can help $\mathcal{B}$ to output $a$ at his DL challenge?

It's unlikely that you'll be able to prove unforgeability from Discrete Log alone. You might need a new assumption altogether on bilinear maps.

Also, in the bilinear world, assuming discrete log is usually not enough to prove security. You need stronger assumptions such as Bilinear Diffie-Hellman or XDH, or the bilinear generic group model (see Appendix A of BBG05).


Understanding how Oscar can decrypt a message in RSA I have the following set-up:

  Bob has an RSA Cryptosystem with a large modulus $n$ for which
  the factorization cannot be found in a reasonable amount of time.
  Alice sends a message to Bob by representing each alphabetic
  character as an integer between $0$ and $25$ (that is, $A ↔ 0$, $B ↔ 1$, etc.),
  and then encrypting each residue modulo 26 as a separate plaintext
  character.

I want to figure out how Oscar can easily decrypt a message in this case. However, I don't really understand how the encryption works here.

For RSA we have

$e_k(x)=x^b\bmod{n}$

But I don't understand what $b$ would be in this case and I don't fully understand what 'then encrypting each residue modulo 26 as a separate plaintext character' implies. Would this mean that each character is encrypted as

$e_k(x)=x^b\bmod{26}$?

Let's assume textbook RSA, which is not apparent from the question. In that case $b$ is the public exponent (usually this is $e$). So yes, encryption is then the first-to-last formula if $x$ is the index in the alphabet of the character. However, the $\bmod 26$ in the last formula doesn't need to be used; I think that the text is just used to indicate that $x$ is within the range $[0, 26)$. The word residue is out of place here; no division is performed on the alphabet, so there is no residue. The modulus for RSA encryption is just $n$.

There are many ways how this crypto system is vulnerable:

textbook RSA is deterministic, so you can do frequency analysis of the ciphertext if the characters are encrypted separately;
indices 0 and 1 (A and B) produce the values 0 and 1 after encryption;

but the main reason that this is insecure is that an attacker could just take the public exponent and then encrypt each character of the alphabet, creating a table from a specific ciphertext to a letter. After that you can iterate over find each ciphertext and replace it with the letter.

These attacks are not feasible if a good padding scheme such as RSA / OAEP is used.


Is the encryption more secure if we apply Pohlig-Hellman cipher twice with different keys but with the same modulus? To encrypt a message $M$, we compute $C=M^k \bmod p$
and to decrypt a Cipher-text we compute $M=C^{k^{−1} \bmod (p−1)} \bmod p$

But if we use Pohlig Hellman twice like $C_1=M^k \bmod p$, and then $C_2=C_1^k \bmod p$,
So is this more secure than doing it just once or not.

And what if we do it multiple times like a Cascade?

So is this more secure than doing it just once or not.

TL;DR; No, multiple encryptions are equal to single encryption and this is not better than single encryption

Pohlig-Hellman Cipher

In setting up of Pohlig-Hellman Cipher;

Select a large prime modulus, let say $p$,
then select a public modulus $e$ with $\gcd(e,\varphi(p))=1$ otherwise no unique decryption.
so, we have a public key as $(e,p)$.
Your private key is the tuple $(d,p)$ such that $e \cdot d \equiv 1 \bmod \varphi(p)$.

To encrypt a message Alice take a message $m < p$, then encrypt you with $$c = m^e \pmod p$$

Once, you get the message you decrypt by $$ c^d = m^{e\cdot d} \equiv m \pmod p$$ with the help of the Little Fermat Theorem.

Example:

p = 3001
e = 37
d = 973

let $m = 57$ then $c = 57^{37} \equiv  2778 \pmod{3001}$

with $c = 2778$ then $ m = 2778^{973} = 57 \pmod{3001} $

Cascade Property: Double encryption is single encryption

To show the cascade property we will use the same modulus with different parameters. This will show that double encryption is equal to single encryption.

Let $p$ is the modulus, $(e_1,p)$ and $(d_1,p)$ be corresponding pairs and $(e_2,p)$ and $(d_2,p)$ be another pair. Let encrypt a message $m$ with the first public key then with the second.

$$c_1 = m^{e_1} \pmod p$$ then
  $$c_2 = c_1^{e_2} = (m^{e_1})^{e_2} = m^{e_1 \cdot e_2} \bmod p$$

Let call $e' = e_1 \cdot e_2 \pmod{\varphi(p)}$ and $d = e'^{-1} \pmod{\varphi(p)}$

Therefore $(e',d')$ will be the single key for the double encryption

Example:

Continue the previous example with $(31,3001)$ and $(871,3001)$ as second public and private keys.

$$2778^{31} \equiv 197 \pmod{3001}$$

$$e' = 31*37 \equiv 1147 \pmod{3000}$$

$$d' = 1483 \pmod{3000}$$

Now, decrypt with $d'$

$$ 197^{1483} \equiv 57 \pmod{3001}$$

Some notes on Pohlig-Hellman Cipher

It is vulnerable to KPA.
It is not IND-CPA secure
It is Multiplicative
No probabilistic Encryption.
Security relies on the discrete logarithm
The prime $p$ must be chosen properly, safe prime*, against Pohlig-Hellmans' algorithm for finding a discrete log.

*A safe prime is a prime number of the form 2p + 1, where p is also a prime


What if in AES-128 CBC, IV is very related to KEY? while digging into some secured communication protocol, I noticed a  usage of AES-128 CBC that raised my attention.
In it, the IV is tightly coupled to the Key, being a xor of its values with the byte index:

for(i=0; i<16; i++)
{
  IV[i] = Key[i] ^ i;
}

Could it be an issue if an attacker knows the first blocks of a plaintext?
Does it weaken the implementation of the encryption?

Thank you in advance

This implementation is horribly broken, since the IV is (most likely) sent in the clear. An eavesdropper who knows the implementation will immediately be able to deduce the key and decrypt all data.

The IV will also be the same for repeated uses of the key. This opens up several weakness. For one, it leaks information on when multiple plaintexts begin with the same data, and for approximately how long. IV reuse is also vulnerable to chosen plaintext attacks. See this answer for more details.


Finding Multiplicative Inverse In Field Consider the finite set Z_257 of non-negative integers less than 257. The number 257 is a prime, so Z_257 forms a field with addition and multiplication mod 257. How can I use the Extended Euclidean Algorithm to find the multiplicative inverse of the element 254 in this field.

For such small numbers, brute force search will do: by definition $a^{-1}\bmod p$ is the integer $x$ in $[0,p)$ with $a\,x\bmod p=1$. The desired $x$ can be found by trial and error. This requires less than $p$ additions, tests, and subtractions, noting we can move from one candidate $x$ to the next using that $((a\,(x+1))\bmod p)\,=\,((((a\,x)\bmod p)+x)\bmod p)$.

One of the most recommendable and fastest classical algorithms is the (half) extended Euclidean algorithm. In crypto, we sometime prefer that variant avoiding negatives. There also are binary variants. Essentially, these find unknown $x$ solving the Bézout identity $a\,x+p\,y=1$ for given $a$ and $p$, and some immaterial unknown $y$.

Yet another method uses $x\gets a^{p-2}\bmod p$. It's applicable when $p$ is prime and integer $a$ is not a multiple of $p$. It follows from Fermat's little theorem. This uses less than $2\log_2(p)$ modular multiplications, using binary modular expoentiation. The method is extensible to any group of known order.


Combining multiple symmetric encryption algorithms - implications? I was just wondering if I add more security by combining two or more symmetric encryption algorithms on a plain text.

For example: Plaintext → AES → Twofish → Serpent

Of course a different key and IV (produced with a cryptographic secure prng) is used for each algorithm. Speed fortunately is not important.

Or does this form of combination has other implications I do not see?

There is a question like that here at Crypto.SE (Is TrueCrypt's multiple/cascading encryption safe?) but it focuses on using the same key.

I can see based upon your question that you're not already a crypto-expert.  Given that, I think the single most useful answer I can give you is this:

  Multiple encryption addresses a problem that mostly doesn't exist. Modern ciphers rarely get broken -- at least, not in the Swordfish sense. You're far more likely to get hit by malware or an implementation bug than you are to suffer from a catastrophic attack on AES.

That's a quote from http://blog.cryptographyengineering.com/2012/02/multiple-encryption.html, which is an excellent article on this topic.

Moreover, if you have to ask this question, you should not be using multiple encryption.  It's a little bit tricky, and you're more likely to screw something up than to get any meaningful security gain.

Bottom line: No, you can't add more security by using multiple encryption.  The block cipher isn't the weak link, and strengthening the strongest link in a system does not add more security.  Modern block ciphers appear to be effectively unbreakable; if that's correct, multiple encryption is pointless.  So, my recommendation is: don't do it.  It doesn't solve any real-world problem, it doesn't add much benefit, and it adds the extra risk that you might screw something up.  Use standard well-vetted cryptographic solutions, like TLS, Truecrypt, GPG, etc.


Solving congruences using PARI I'm having trouble finding info in the docs about how to solve a system of congruences. The closest I can find is 'matsolvemod' in here: http://pari.math.u-bordeaux.fr/dochtml/html.stable/Vectors,_matrices,_linear_algebra_and_sets.html

but I'm not sure if that's exactly what it's used for because I don't really understand where the M parameter comes in with a system of congruences. Is there a function for solving a system of linear equations of the form:

x = a1 (mod b1)
x = a2 (mod b2)
...
x = an (mod bn)

(or even for just 2 or 3 congruences is fine)

EDIT: Okay, I've tried just using the algorithm and basic arithmetic instead of finding a function to do it for me automatically but am receiving an error:

Pari's "chinese" function (as in Chinese Remainder Theorem) does the solution for you, for two congruences. You can fold in more congruences via induction.

? chinese(Mod(42,91), Mod(11, 37))
%1 = Mod(3045, 3367)

The previous example solves for $x \equiv 42 \pmod{91}$ and $x \equiv 11 \pmod{37}$, which is unique modulo $91 \cdot 37 = 3367$. You can use "raise" to promote a Mod object to the integers.


Top 10-2017 A8-Insecure Deserialization , why products does not implement encryption On trying to understand Deserialization vulnerability, it was observed that serialization is the process of converting a complex object to a byte stream for sending it across networks and is deserialized on the receiver side.

On analysing OWASP TOP A8, it says the IT industry has an high prevalence of this feature being compromised for exploitation.

Question:

Why are products not encrypting the serialized data as discussed in the post below?

Which is better: “serialize and then encrypt” or “encrypt and then serialize”?

Why are products not encrypting the serialized data as discussed in [#30723]?

Because encryption by itself does not reliably prevent alteration of the data, which is the vulnerability here. As Maarten Bodewes comments in that very Q.

To prevent tampering in general you need -- as OWASP says -- an integrity check, like a MAC or signature. Not encryption. (Although if you have authenticated encryption, which does both encryption and MAC as a combined operation, and in recent years has become more popular and widely available, you might as well use it.)

Now, why don't/didn't people use a MAC or signature (or AE) on data which if altered can be dangerous? That's a good question. To which I don't have a good answer.


Combining secret keys into a single shared key Let's say there are $n$ participants each with their own secret key $x_i$. Is it possible for them somehow to build a shared key which is an arithmetic sum of all their secret keys ($x_0 + x_1 + ... + x_n$) but without revealing their individual keys to each other.

Also, ideally, this would be done non-interactively. Meaning, each participant shares something about their secret key with everyone else, and once everyone has shared this "something", the shared key can be constructed.

Secret sharing is a perfect tool for this application. Under any linear secret sharing scheme, individuals can generate shares of secret values to distribute to other parties involved in the scheme. Once each individual has distributed shares of their secret value to all the other parties, due to the linearity of the scheme they can each locally sum the set of received shares and the collectively hold a valid share of the summation. This is because, by definition, linear secret sharing schemes possess and additive homomorphism, meaning that adding shares yields shares of a value which, if revealed in a reconstruction process, is identical to the value of the summed secrets.

In a more detailed manner, illustrated with additive secret sharing, every party $P_i\ \forall i\in Z_{n+1}$ generates $n$ random values in some valid group denoted by $m$ which will serve as shares of the secret $x_i$ for all the other player i.e. $[x_i]_{\mathbb{Z_m}}^{P_j}\in_R\mathbb{Z}_m \ \forall i,j\in Z_{n} $ and the final share satisfies the following equation $[x_i]_{\mathbb{Z_m}}^{P_n}=x_i-\sum_{j=0}^{n-1}[x_i]_{\mathbb{Z_m}}^{P_j} \mod m$. Then every party $P_i$ sends $[x_i]_{\mathbb{Z}_m}^{P_j}$ to all other parties such that $i\neq j$. Finally, the parties all locally compute the following summation locally in which $x_\Sigma$ denotes the summed secrets.
$$ [x_\Sigma]_{\mathbb{Z}_m}^{P_i} = \sum_{j=0}^{n}[x_j]_{\mathbb{Z}_m}^{P_i}\mod m$$

Now each party holds uniformly random and information theoretically secure shares of the sum of their individual secrets and all parties must cooperate to reveal the underlying value. Specifically they would have to communicate all their individual shares to one another then they could each locally calculate:
$$x_\Sigma = \sum_{i=0}^{n}[x_\Sigma]_{\mathbb{Z}_m}^{P_i} \mod m$$

I encourage you to look deeper into secret sharing in general as well as other schemes, Shamir's secret sharing scheme in particular, due to the resilience it can introduce to a system in the presence of active adversaries or component failures.


In RSA $(e,n)$, $(d,p,q)$, why does it work even if plaintext $M$ is not coprime with $n$? I read this post
Does RSA work for any message M?, but I cant prove that $(M^e)^d-M\equiv 0\pmod{p}$ like this:

By construction, we have $ed\equiv 1\pmod{\lambda(n)}$, hence $ed\equiv1\pmod{\lambda(n)}$ since $\lambda(p)=p-1$ divides $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. Fermat's little theorem thus implies that $(M^e)^d-M\equiv M^{ed}-M\equiv0\pmod p$ for any $M\in\mathbb Z$.


CTR vs CBC cycles per byte with OpenSSL EVP I did some benchmarking using the EVP calls of OpenSSL in C, for CBC and CTR encryption/decryption.

(1) : I got 3.2 Cycles/Byte for CBC encryption.
(2) : I got 0.7 Cycles/Byte for CBC decryption, CTR encrypt, CTR decrypt.

How is it possible that I get 4 times less CPBs for CBC decrypt and CTR? (I know that (2) can be parallelized in theory.... but OpenSSL runs on a single thread in my benchmark). So how is it possible?

OpenSSL utilizes AES-NI instructions which are pipelineable. Note that CTR encryption and decryption and CBC decryption can all be computed in parallel, whereas CBC encryption is strictly sequential (you need the result of block $i$ in order to encrypt block $i+1$). Thus, CBC encryption cannot utilize the pipeline and you get 4+ times the running time. This is exactly as expected.


Steps to encrypt endorsements to a petition I plan to circulate a petition, asking people to support it. This petition will reach a senior government official.

In regular circumstances, people would support such petitions by writing their name, their national ID number, and their physical or email address.

However, due to the nature of the petition, people may be reluctant to sign it because it would expose their name to other people. People may even be reluctant to provide their name to the person collecting the signatures (me).

Let us assume that we trust in the senior government official receiving the petition: that official has the right to know what our real names are, and we assume that our identities and contact info will be safe.

Let us assume also that people who sign have no incentive to fake their signatures (sign using the name of someone else, etc).

Assume that the senior government official has a public key.

I was thinking about this setup: I get this website, with the text of the petition. People can enter a piece of text there.

That piece of text would be their name, national ID and contact info, encoded if they wish. If it is encoded, the only person able to decode that text should be the senior official.

Is there a user friendly way in which people can get a set of keys, write a short text, encode it, and then copy-paste it to the petition website?

Note that I don't want to install a key generator on my own petition website, since people would be right not to trust it.

This depends on the level of authenticity you want to provide with your system. A lot of public petition systems do not enforce authenticity of petitioners at all. Basically, anyone can submit a petition in behalf of their neighbor, for example, simply by introducing relatively public info about them (name, address, ID number, etc). In this case, public-key encryption seems the way to go. For example, this could be done with plain, old PGP, where the public key belongs to the government officer.

On the contrary, if you want the petitioners to actually sign the petition (digitally, obviously), then this has to be done with some sort of digital signature. I think you could implement this with designated verified signatures:

  A designated verifier signature is a signature scheme in which
  signatures can only be verified by a single designated verifier who is
  chosen by the signer.

In this case, the designated verifier could be trusted government officer receiving the petition.


Definition of ciphertext security If I got it right, chosen ciphertext security implies also CPA security. In other words, attacker can submit plaintexts to the challenger (along with ciphertexts).

I do not understand why encryption system (E,D) where D(k,0)=0 is considered as ciphertext secure.

Imagine CPA security game where an attacker just submits two plaintexts, m0 = 0 and m1 = (any value != 0). In that case if poor challenger returns 0 then we are certain that we're in experiment 0 and win CPA game.

What I am missing here?

The important thing to note here is that $\mathsf{D}(k,0)=0$ does not necessarily imply that $\mathsf{E}(k,0)=0$. That is the reason why your attack does not work in general.

To illustrate, let $(\mathsf{E},\mathsf{D})$ be a CCA secure encryption scheme.
We then construct a new encryption scheme $(\mathsf{E'},\mathsf{D'})$ as follows:
$$\mathsf{E'}(k,m) = 1\Vert \mathsf{E}(k,m)$$ and
$$\mathsf{D'}(k,b\Vert c) = \left\{\begin{array}{ll} 0& \text{if } b = 0\\ \mathsf{D}(k,c)& \text{if } b = 1\end{array}\right.$$

It is trivial to show via reduction that $(\mathsf{E'},\mathsf{D'})$ inherits the CCA security from $(\mathsf{E},\mathsf{D})$, but still it has the property that $\mathsf{D'}(k,0)=0$.

As you can see, your attack does not work, because $0$ is never encrypted to $0$ by the challenger.


An (N)LFSR…but for bytes! A linear feedback shift register can be thought of as an array of bits where NEW_BIT is calculated using F(REGISTERS). F is a function that takes values from two or more elements of REGISTERS and XORs them together. The new value of REGISTERS is equal to (in Python) [F(REGISTERS)] + REGISTERS[1:]. Do the dynamics change if we store values greater than 1 in each register, like say bytes? If F invoked operations other than XOR, then it seems like that would make it more like an NLFSR. Are the dynamics different there, too? Is something like this used by any cipher out there?

A classic linear feedback shift register is in fact a representation of operations in a modular ring of binary polynomials. In mathematical terms, you have a base field, which is $\mathbb{Z}_2$, the field with two elements (0 and 1); then a register of $n$ bits is a polynomial of degree at most $n-1$ in $\mathbb{Z}_2[X]$, and shifting the register is equivalent to multiplying the polynomial by $X$ modulo a given polynomial $P$ of degree $n$; that polynomial $P$ corresponds to the "feedback bits", i.e. which elements of the register you take to compute the new bit.

This model naturally extends to the case of using another base field or ring. For instance, if you use bytes and additions, then you are working with $\mathbb{Z}_{256}$, i.e. the integers modulo 256. With $n$ bytes, you still have polynomials of degree at most $n-1$, but this time in $\mathbb{Z}_{256}[X]$ (and it is still linear). Like the classic LFSR, taken alone as, say, a pseudo-random generator, it is still quite weak; moreover, $\mathbb{Z}_{256}$ is not a field, which tends to make matters worst (to express it "with the hands", additions modulo 256 will propagate carries only toward higher bits, so, in particular, the low bits of each byte will only depend on each other, not on the higher bits).

Now, symmetric algorithms are almost always built by assembling several (many) operations which, by themselves, would not constitute a cryptographic algorithm of any decent quality; for instance, SHA-256 is made out of about 2500 very simple elementary operations, the most complex of which being a simple addition. As such, LFSR expressed over various rings or fields can be used, and have been used, as building elements of larger algorithms. See for instance the Sosemanuk stream cipher, or the RadioGatún hash function.

A non linear feedback shift register would entail using operations that are not additions in some field of ring, i.e. not additions on integer or XOR. You could try some multiplications, but it will make analysis more complex with no clear immediate benefits. Remember that what is sought in symmetric algorithm design is a good trade-off between "mixing" (a generic terms for various concepts such as non-linearity and avalanche effects) and performance; moreover, we cryptographers really like to feel that we understand what we are doing, therefore "hard to analyse" is a bad thing, not a good thing.


Cryptography: Oblivious Transfer with at most one transfer? I am trying find a transfer method for this problem. Suppose Alice and Bob both has access to a function $\text{F}$ with two parameters. $\text{F}(x,y)$ randomly returns $p$ to alice and $q$ to Bob  such that $x\times y=p \oplus q$. Now as per rules of Oblivious Transfer, Alice has $s_0$ and $s_1$ and Bob has $c$. Bob wants to learn $Sc$. The catch is alice can transfer at most one bit in total to bob, that means they can communicate just once. How can Bob learn $Sc$ using this function?

The obvious approach is to help Bob learn $s_0 \oplus (s_0 \oplus s_1) \times c$, presumably using $F$ to help him learn this information.  So, here is the natural protocol:

Alice and Bob invoke $F$.  Alice provides the input $s_0 \oplus s_1$, Bob provides the input $c$.  Alice learns $p$ and Bob learns $q$, where we are guaranteed that $p \oplus q = (s_0 \oplus s_1) \times c$.
Alice sends $p \oplus s_0$ to Bob.

Notice that, with this information Bob can compute $s_c$.  I leave it as an exercise to you how to do that.

Also, notice that Bob learns only one of $s_0,s_1$.  I leave it to you as an exercise to prove that.

Finally, notice that if $F$ does not disclose anything about its inputs to either part, then Alice does not learn anything about Bob's bit $c$.