relationship between equivalent ways of computing RSA private key I have found two ways to compute the RSA private key, but i have trouble understanding why they are equivalent.

$1) D={k \phi(N)+1 \over E}$

$2) E* D=1 \mod \phi(N)$

$1)$ AFAIK comes from taking the relationship between eulers theorem and a modular identity such that.
$$
M^{1+ \phi(N)} \equiv M \mod N \qquad \land \qquad M^{E*D} \equiv M \mod N
\\
\qquad \text{ Euler}  \qquad  \qquad  \qquad  \qquad \qquad \qquad \text{ Identity}$$

So we can see that the exponents must be the same, and that exponentiating by an integer $K$ should make no difference in modular arithmethic

$k \phi(N)+1 = E*D$

so

$D={k \phi(N)+1 \over E}\\$

The origin of $2)$ eludes me, why is it equivalent to $1)$?

$D={k \phi(N)+1 \over E}$ is equivalent to $ED = k \phi(N) + 1$

$ED \equiv 1 \pmod {\phi(N)}$ means "there's some integer $k$ s.t. $ED = 1 + k \phi(N)$"

Hence, they're equivalent.

BTW: the actual necessary and sufficient condition on E, D actually is $ED \equiv 1 \pmod {\text{lcm}(P-1, Q-1)}$ (for RSA modulii that consists of two primes); the relation you're using is sufficient, but not necessary.


Supersingular vs non-singular (Same or different) I have a frustration for the term "supersingular" elliptic curve and "non-singular" elliptic curve.

In some paper, performance evaluation is done using supersingular elliptic curve and in some cases, they use non-singular elliptic curve.
Are they same or different curves?

Every elliptic curve is non-singular. Some elliptic curves are supersingular.

A quote from "The Arithmetic of Elliptic Curves" by Silverman, Remark V.3.2.2:

  Do not confuse the notions of singularity and supersingularity. A supersingular elliptic curve is, by definition, an elliptic curve, so it is nonsingular. The origin of the potentially confusing terminology is as follows. Historically, elliptic curves defined over $\mathbb{C}$ whose endomorphism rings are larger than $\mathbb{Z}$ were called singular, where "singular" was used in the sense of "unusual" or "rare". However, in this sense, all elliptic curves defined over $\bar{\mathbb{F}}_p$ are singular! The endomorphism rings of most elliptic curves over $\bar{\mathbb{F}}_p$ are order in imaginary quadratic fields. It is only the rare and unusual curve whose endomorphism ring is an order in a quaternion algebra, whence the term "supersingular".


Branchless AES Implementation Imagine a branchless implementation of the AES-128 cipher. Are there any benefits over the implementation that contains branches, other than possible prevention of timing attacks?

Is it even true, that a branchless code can mitigate a timing attack? Are there any other side-channel attacks that are prevented in this way?

What makes crypto code vulnerable to timing attacks is data dependent timing variations. Branching according to a round counter, or to the key size, does not create a vulnerability. Most implementations of AES make no branch according to key or data value, and supressing other branches won't help.

The main source of data-dependent timing variations in AES is in the table lookups for the S-boxes: according to if the entry is in cache, or not, the table fetch will take different time. See for example Daniel J. Bernstein, Cache-timing attacks on AES (2004) [direct link to pdf] for more info.

Among ways to make AES code free of any timing dependencies are:

using AES-NI or other hardware support;
using a CPU without data cache (and being careful about alignment of the table);
changing the S-table to a logical expression, possibly using bitslicing to regain at least some of the lost speed; unfortunately the AES S-table is rather hard to express  in this way (this has been studied by Joan Boyar and René Peralta, A new combinational logic minimization technique with applications to cryptology and A depth-16 circuit for the AES S-box; here are some of their equations).


Cryptography and FPGA I see a lot of papers about FPGA implementations. For what kind of "concrete" application should we implement cryptographic algorithms on FPGA ? Which secured application require such a huge data processing performance ?

For what kind of "concrete" application should we implement cryptographic algorithms on FPGA? Which secured application require such a huge data processing performance ?

Well, FPGAs are ideal for a wide variety of applications, from high-volume applications to state-of-the-art products.

Imagine you are…

a bank, or
a Big Data service provider, or
a governmental institution, or
a military force, or
…

and you need to encrypt terrabytes of data in the shortest amount of time possible, because…

time is money, or
your clients want their Big Data to be stored safely on your servers via a double-encryption, or
a huge stream of intercepted metadata needs to be protected from the public eye, or
the enemy is near your last line of defense and you need to secure some data immediately, or
…

Whatever valid reason you might have to need cryptography “now” instead of “later”, you will want to choose the fastest option possible. In that case, it makes sense to use the (immensely) faster FPGA (and/or ASIC) solutions instead of hoping your CPU(s) will manage to handle the job in such a short amount of time.

From a civilian point of view, I guess the most understandable motivation as to why cryptographic algorithms are implemented on FPGA would be the economic factor. It should be noted that you burn less energy when using an optimized FPGA or ASIC implementation. This practically means you can “produce more work” while investing the same (or less) amount power as you would have invested when using your CPU(s).

Now, related to your comment:

  Are there non cryptanalytical examples ?

Thinking about it, here’s a first, nice, practical, non-cryptanalytical example: cryptocurrencies. Just take a short look at the history of those folks… who evolved from “mining their coins” (read: creating their proof of work via cryptographically secure hashing algorithms) with CPUs, then switched over to GPUs because they were faster and more energy efficient, and ended up using specialized ASICs.

Besides that, there are – of course – other non-cryptanalytical examples. As a matter a fact, “An FPGA Implementation and Performance Evaluation of the. AES Block Cipher Candidate Algorithm Finalists” already hints at that, and a short search engine quest would have provided you with ample commercial product examples.

For your convenience, here are two randomly picked, non-cryptanalytical product ranges:

Helion : IP Core Products, based on ASIC or FPGA (Encryption, Authentication, Hashing, et al.)
Nallatech : 40Gbit AES Encryption Using OpenCL and FPGAs

I’m sure you’ll be able to find more examples using your favorite search engine…

EDIT (Lazy-Friday Bonus):

For the fun of it (and because I had a lazy friday afternoon), I whipped up two non-optimized C proggies just to show you something practical…

See that speed (and hash-count) difference?

Now imagine the increase that could be gained when using a field programmable gate array (FPGA). What might take years for one person, might just be a matter of hours for another.

Such speed differences are like a coin with two sides: benign users can enhance security in many areas, while malign users can attack faster (making some attacks feasable in the first place.)

That’s one of the reasons cryptographical FPGA solutions are of interest… no matter which side of the coin one prefers or chooses.


Trying to implement ring-LWE KE to understand the concept Today, after reading so much about ring-LWE key exchange, I decided to implement it in java to see if it works. Not a real world implementation, just to see if math works out. My assumption was that writing a code would be simple given some sort of Polynomial ring. My assumption turned out to be wrong. I searched internet looking for basic uni-variate polynomial ring library and I found this. It looked simple and had some jUnit test already that code was passing. I copied the parameters from here. In short, $\mathbb{Z_{2^{23}-1}} / (x^{1024} + 1)$.

I followed Regev's basic reconciliation method and ran the code. Even if there is no error, the exchanged keys did not match. Obviously, something is wrong and I am certain it is from my code not the Polynomial ring library. Maybe I did not understand some fundamentals of ring-LWE. I attached the code here:

This is the link for GitHub repository. Any help would be appreciated. I don't know what I am doing wrong.

Math: dimension = 4 (arbitrary)

$A, S, S' = [rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r,\\ rx^3 + rx^2 + rx + r]$

s.t. $r \in \mathbb{Z_{q}}$ (randomly generate)

$B = AS + error$, $B' = AS' + error$

$Shared key = SB' = S'B \to$ I did not use any error ($error =0$) but still shared key does not match.

Pseudo-code:

dimension = 8 # arbitrary
modulus = 65537
R = PolynomialRing(GF(modulus), "X")
S = R.quotient(X^1024 + 1, "x")

A = generate_matrix(dimension, modulus)
S = generate_matrix(dimension, modulus)
S_ = generate_matrix(dimension, modulus)

B = A.transpose()*S
B_ = A.transpose()*S_

alice = S*B_
bob = S_*B

print alice == bob  # returns false

Update:
I tried to write the code in sage (without any error) and still something is wrong. I am now sure my math is wrong. This is the link for sage code.

It seems to me that the problem lies in your setup of the vector/matrix multiplication.

What you have now: $a, s, s'$ are row vectors of ring elements.

$$ \text{Alice: } sB' = sa^ts'$$
$$ \text{Bob: } s'B = s'a^ts $$

Obviously, matrix multiplication is not commutative, but multiplying the underlying ring elements isn't either, because they're, well, ring elements.

So you need to shuffle and transpose some things.

Let $B = a^ts$, and $B' = s'^ta$.

Now let Alice calculate $B'^t s^t$, and Bob calculate $s'B^t$. If you work it out, this will give Alice and Bob consistent keys.

Proof: I modified your sage script, it returns true now.


A variant of Shamir secret sharing Suppose implement the Shamir secret sharing as following: we select a degree $d$ polynomial $P$ with a zero coefficient of 0, and all other coefficents selected randomly from $Z_p$; and to this polynomial $P$, we add the secret as a constant term $Q = P + secret$.  If we use $Q$ as the polynomial in our Secret Sharing scheme, this is precisely equivalent to Shamir's scheme.

Now my question is : what if we multiply instead of add?  That is, what if we select $P$ as above, except with a random 0th coefficient as well, and compute $Q = P \times secret$? This  makes the original polynomial recover harder, but my main concern is about the (semantically) security of the scheme.

For security in Shamir secret sharing we need that the coefficients of the polynomial are independent and uniformly random in the field. Multiplying the polynomial by a constant from the field does not change this, so yes, you can do it and still be secure.

In fact, in multiparty computation, something akin to this is done when we want to privately multiply a secret shared value by a known, public constant. We multiply each share by that constant. The effect of this is multiplying the polynomial by the constant.

Obviously there are some corner cases to consider. The secret cannot be $0$. If the constant term of the polynomial is $0$, you might also run into problems (depending on the application).

It is important that the secret you multiply by is in fact a single element from the field and not a polynomial itself. If it is a polynomial, then two problems occur. The coefficients are no longer independent and the degree of the polynomial changes.

Without knowing your application, however, it it hard to say whether or not this is useful. Can you still recover the original secret? Only if you know the constant term of the original polynomial, right?


Is there any advantage on encrypting the CMAC together with the message? I'm reading a protocol specification where the procedure is to generate a CMAC, take the first 4 bytes of it, append this authentication tag to the message and then encrypt the message + CMAC together with another key using CTR mode encryption.

Both CMAC and CTR mode are defined to use the AES-128 block cipher.
A separate key is used for CMAC authentication and CTR encryption.

Does encrypting the MAC add any extra security? Shouldn't CMAC be already "secure" by itself?

Is this a typical approach for doing encryption + integrity verification?

If a MAC is encrypted using CTR specifically then specific bits can still be flipped by an attacker. So although the MAC isn't known, specific bits can still be altered in transit. This may allow certain attacks, depending on the error handling of the receiver of the protected messages.

[The question I cannot readily answer is if such a small authentication tag gains nothing from being encrypted. Please alter.]

A CMAC should indeed already be secure by itself. Encryption of a MAC should not be necessary.

In the protocol you are describing the CMAC is however truncated to a very low number of bits. Look at this snippet from RFC 4493, section 2.4:

  It is possible to truncate the MAC.  According to [NIST-CMAC], at
     least a 64-bit MAC should be used as protection against guessing
     attacks.  The result of truncation should be taken in most
     significant bits first order.

No, it's not a "typical approach" in the sense that newer protocols usually calculate an authentication tag over the ciphertext instead of the plaintext.

There are however protocols where MAC-then-encrypt is used, notably Transport Layer Security (TLS). This actually opens up TLS to some attacks such as the Lucky Thirteen attack, although that attack also requires CBC mode encryption instead of CTR mode encryption.


Is the first version of the Message-Digest algorithm by Ronald Rivest publically available? Diving into the history and evolution of the Message-Digest algorithm by Ronald Rivest, I have been able to track back papers from MD6 down to MD2. Yet, somehow I can not seem to be able to find any papers, specifications or even the slightest indications of MD1.

As the numbering (MD2, MD4, MD5, MD6) seems to be a constant, it would be logic to expect that MD1 did exist at some point in the past. Since I can not find anything related, I'm reaching out for help...

Has MD1 ever been published or was MD2 indeed the first Message-Digest algorithm that Ronald Rivest showed to the world? And if MD1 has been published, where can I find that publication (or a copy of it)?

Since I have not received any reply from Mr. Rivest's office after bugging them with a total of four emails in four weeks, I have no other option than to give up on hoping I ever receive a reply from his office.

After spending 6 weeks hunting down information all over the internet (and not receiving any reply to my emails), I am currently suspecting that MD1 has indeed never been published. I base this on the fact that another algorithm — MD3 — never made it beyond the experimental status either… due to problems with its algorithm. It could well be MD1 faced similar issues and also never made it beyond the lab. Another reason for suspecting this is that all RFCs were published in April 1992. If there had been any "beyond lab" MD1, I'm pretty sure it would have been published together with the other MD papers. My best guess is that MD2 was born out of failed MD1 experiments.

Yet, my suspicions might also be completely wrong. As said: I was not able to find any papers or hard facts in relation to MD1. Should you ever find reliable information about MD1, please post it as an answer. I will gladly unaccept my own answer to accept any answer that's able to present verifiable information and/or a publication/paper/book/whatever related to MD1.


Shouldn't a signature using ECDSA be exactly 96 bytes, not 102 or 103? Attempting to use openssl to create a signature is confusing on several levels:

If I'm using it to sign a hash that I've already created (HMAC-SHA-384-192, specifically),

a. why must I specify another hash algorithm?

b. What algorithm is consistent with the one in the HMAC and ECDSA-384?
Why does the signature size vary between 102 and 103, instead of being exactly 96?
If I'm supposed to append a binary signature onto a potentially binary message (UDP), how is the recipient going to figure out where a message of unspecified length ends and a signed digest of unspecified length begins?

1) If I'm using it to sign a hash that I've already created (HMAC-SHA-384-192, specifically)

  a) why must I specify another hash algorithm?

HMAC is not a hash algorithm. It's a MAC, a message authentication code, or keyed hash. As the private key is used to create the signature there should not be any need for the secret key used to create a HMAC value. The hash itself is a integral part of ECDSA.

  b) What algorithm is consistent with the one in the HMAC and ECDSA-384?

You'd expect something like SHA-384, not HMAC-SHA-384-192.

  2) Why does the signature size vary between 102 and 103, instead of being exactly 96?

The signature consists of two integers. The format of X9.62 creates two ASN.1 INTEGER values for these and puts them within a SEQUENCE. The integer values are encoded as big endian signed values. So if the integers are 9, 17 or 25 bits smaller than the key size then the resulting encoding will be smaller.

Take for instance this 100(!) byte $r$ and $s$ value encoding for a 384 bit curve:

3062022e52884531f76504d28c0a60771025bce8881d33377fce5d62566d7d9a47da55066784b21b4bfcabd105dbe127ea6f0230560212a2b3078c55157842b92476dfaea7b6a58f2e4047d374de53b98629607b70e2ee06a1263c25db66f45572759c2d

decodes to

SEQUENCE(2 elem)
  INTEGER(367 bit) 1938306347072450679876740861736525521572671793660053577404161377925729…
  INTEGER(383 bit) 1323785767677292921898744777970756602439423500858315154875512504309946…

In principle they could also be slightly larger as a leading 00byte needs to be added for positive values where the very first bit is 1. This is because the initial bit is the sign bit, so if the first bit is set then the value would be interpreted as negative. The order of the curve however could well prevent this from happening.

  3) If I'm supposed to append a binary signature onto a potentially binary message (UDP), how is the recipient going to figure out where a message of unspecified length ends and a signed digest of unspecified length begins?

If you just concatenate both then you may not have a deterministic method of doing so. So basically you have to include a length of your message or signature.

You could also convert the signature to a signature that does contain two statically sized integers of course. The encoding of both "Plain Format" integers and "X9.62 Format" signatures is discussed in TR-03111 of the German BSI, section 5.2. You may want to reencode them back to ASN.1 DER format after the message is received and parsed of course, in case your API doesn't support Plain Format signatures.

In that case the signature size will be 96 bytes.


How to show CPA attacker does not need access to encryption oracle after receiving cyphertext In the private key CPA game, the attacker has access to an encryption oracle anytime during the attack.

However, I have seen this statement in lecture notes I downloaded "You can prove that for every polynomial time attacker that uses the encryption oracle after receiving the challenge cyphertext, you can construct another polynomial attacker that also breaks the encryption scheme only querying the oracle before receiving the challenge cyphertext."

I have tried to do reductions but I don't see how I could use the first type of attacker to build the second type, since the first requires oracle queries after knowing the challenge cyphertext.

I have also tried to search this but was unable to find.

"You can prove that for every polynomial time attacker that uses the encryption oracle after receiving the challenge cyphertext, you can construct another polynomial attacker that also breaks the encryption scheme only querying the oracle before receiving the challenge cyphertext."

Actually, that is not true in general; you need to make further assumptions on the encryption method.  Presumably, the lecture gave these further assumptions.

One counterexample to the general statement is a self-inverse cipher, that is, one for which $E_k(E_k(M)) = M$.  It is obvious, given $E_k(M)$ and an encryption oracle, how to recover $M$ with a single query.  However, if there are no further weaknesses, there is no useful way to generate queries before you see the challenge ciphertext $E_k(M)$.


HRNG for One Time Pad I have just advanced to the last grade of high school (in Denmark). In this year, we all get to do one big project, where we can build/invent/create whatever we want to "solve a problem". As I study Math, IT and electronics, I would like to build something where all these 3 subjects are included. I have thought about a project for a long time, but I don't really know about how much cryptography is applied in companies, so I would like your guidance before I start working for almost a year on it.

Many big companies use enciphering algorithms to protect any third-party companies/hackers to get access to sensitive data, however, not all the algorithms are safe and easy to use. I have been thinking about this problem for a long time now, especially because I love C#, cryptography and electronics, and making a product related to this subject would be very interesting.
(This school project is "just" a school project. We don't really sell our products anyhow when we have finished them, but it will get higher ratings if it really is useful).

I have though about making a Hardware Random Number Generator connected with a program, which will XOR the file and keyfile together.
I have thought about making a simple circuit like this one, using white-noise from an NPN transistor and/or an FM radio antenna tuned to unused frequencies. I would then collect these random output bits and send them to an Arduino (An open source electronics platform), which helps us send it through to a computer via USB. I will then program a C# application that would extract the random bits from the ARDUINO and XOR it with a file that we want to encrypt (One Time Pad).

My questions are (if you assume that I started a company selling our product):

Would it be useful for companies who need to keep their data safe?
Would the files encrypted with our "product" be safe?
I am aware of many other portable HRNG (List can be found here), however none of them seem to come with a program where they can be used. Most of them seed the linux dev/random. Can we "outperform" their product? (assuming size and transfer speed is the same, and I calculated the price to be roughly 65 US dollars).
Any idea how to improve my product? What should I do different?

I hope you can answer my questions and feedback my plans for my project.
Thank you in advance for any help you can provide!

Would it be useful for companies who need to keep their data safe?

No, a one-time-pad is only useful in very rare circumstances.

The main issue is key-management. You can only use each pad once, it's as large as the data you want to encrypt, and you need to get it to all parties in a secure way.

The direct competition of a one-time-pad is a stream cipher. They don't come with a proof of security, but are much easier to use, since they only have a small key(32 bytes or so) instead of a giant pad. Thanks to IVs the key reuse problem is much smaller too, you just need locally generate a random value of around 16 bytes.
Would the files encrypted with our "product" be safe?

If you manage to do everything correctly, yes. But the key management is so annoying that mistakes such as pad reuse are likely, and it's not solving a practical problem. So nobody will use it.
Can we "outperform" their product?

Hardware PRNGs are not that useful on desktop systems, since those tend to have sufficient entropy sources to seed a PRNG. Embedded systems which often suffer from entropy issues on the other hand typically can't afford a specialized HRNG module.

Intel is also working on putting a HRNG into their CPUs, making it practically free. You can't compete against that.


After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so? Preface: This question was originally asked on Theoretical Computer Science and later on Computer Science. The kind people on cstheory.SE referred me to this web site. It is being repeated here in an attempt to find a satisfying answer.

Over the years, two novel encryption techniques have come to mind and been implemented as programming libraries that could be integrated into applications. However, how to analyze their security and vulnerability characteristics has never been very clear, and their usage has been limited to mainly experimental tests. Are there tools available for automated examination of such parameters one may be interested in understanding for an encryption library? Are there bodies of people who are interested in being introduced to new encryption concepts for the purpose of executing their own personal analysis on such a process? I'm not sure where to look.

The first encryption algorithm is a mono-alphabetic simple substitution cipher. It requires two keys to operate and is designed to frustrate frequency analysis. The longer of the keys forms a table by which plain-text has a normal substitution cipher applied. Each encoded byte is then split into four values of two bits each. The second, shorter key is then used to allow a random selection from four groups of sixty-four unique bytes each. Each two bit value from the encoded byte is used to select which group of sixty-four bytes to use. Encoding has two disadvantages: the output is four times larger, and repeated data encoding may allow some frequency analysis.

The second encryption algorithm is a stream cipher like the first but internally operates on blocks of data. It utilizes two keys to operate: the first is a two-dimensional array that describes how to construct a (virtual) multidimensional grid, and the second is an initialization vector for the encoding/decoding engine. It attempts to overcome frequency analysis by encoding bytes with a window of preceding bytes (initialized from the second key). A byte with its preceding window of bytes form a multidimensional index into the aforementioned grid. Unfortunately, encoding duplicate blocks of data longer than the window size starts yielding equivalent data.

To answer your question "After implementing a novel encryption algorithm, how would one go about analyzing its security", well, the easy answer is "no, it's not secure".  The reason I can confidently give that answer is that you're a newbee, and newbee ciphers are never secure (unless they are massively overcomplicated; it doesn't sound like that's the case).  A newbee is about as likely to create a secure cipher as a blind man would be to paint a good piece of art; neither has any reference as to what works and what doesn't.

However, I assume you are looking for a more detailed answer than that.  Well, that gets tough for a newbee.  There are no automated tools that can validate an algorithm as "secure" (as secure means that no one can come up with a creative method to attack it, and automated tooling has difficulties with "creative").

So, you would need to have a human look at the cipher.  You could try to get an expert cryptographer to look at it, however (and you might find this shocking) there are no groups of expert cryptographers that are eager to attack ciphers from newbees.  And, even if you do get someone to look at it, you'll run into the next difficulty - they'll point out exactly how to break it; you'll tweak the cipher to stop that exact attack, and you'll have no idea whether tweaked cipher is any stronger than the original (except for that exact attack); indeed, the tweaked cipher could easily end up being weaker.

The alternative is to invest the time to become an expert yourself; the way to do that is to break ciphers yourself.  Yes, that's quite a commitment (becoming an expert in any subject is pretty much by definition hard work); but if you are serious about designing ciphers, that's what you have to do.  You might start with Stanford's course (note: I haven't gone through it myself); Schneier has an intro-to-cryptanalysis course here; or you might want to start by attacking your own ciphers.

The last isn't as silly as it sounds; here's a few suggestions:

Can you attack a 'reduced strength' version (say, with a reduced 'byte size')?
Suppose that the attacker can encrypt messages of his choosing (which is actually a standard cryptographic assumption)?  How can he use that?  For example, for your first method, suppose he asks for the encryption of thousands of repetitions of the same character?  What can he deduce from the ciphertext?
Once you can figure out how to break it with chosen plaintext, how can he attack it if he knows some of the plaintext (but obviously not all)?  How can he attack it if he doesn't know any of the plaintext, but he does know that it is, say, English-ASCII?

To give you a target, I suspect that against your first method, I could decrypt the encryption of perhaps a 10k English-ASCII message, or a 200 byte English-UCS-2 message.  And, no, I won't tell you how; that's for you to discover (hint: why do I need so much less text with UCS-2?)


Sharing a secret key between many users I would like to know if there is any security issue in sharing a secret key (of an asymmetric cryptography) between several users.

I know that this secret key is no longer "secret", so it's no longer valid for signature.

The advantage of doing that is to allow a user to send a message to many others (all those sharing the secret key) at a time by encrypting it with the corresponding public key.

But I don't know if this will induce security problems.

The only security issues that I can think of when sharing the same key among several users (in an asymmetric encryption system used to broadcast messages) are:

We can't revoke a single user without impacting all the others.
We loose the flexibility to encipher to an arbitrary set of users (which, for large messages and when using hybrid encryption, has moderate overhead).
If the key is determined to have leaked to someone not authorized, we no longer know from which user (or user's device) it has leaked from.
If the ability to decipher messages is determined to be available to someone not authorized, we can no longer selectively disable users to try to determine which user (or user's device) is involved in the leak.
If extracting the key form one device requires making a large number of experiments, and that's practically not possible to an adversary (due to a usage counter, or the time required, or because the experiments are destructive), an adversary in a position to use multiple devices with the same key is in a better position than if each device had a unique key.
This is an issue in side-channel protection of Smart Card (where resistance is quantified in number of power traces allowing to recover the key), and some fault-attacks that similarly require many experiments. As an extreme example, if an adversary could force any chosen key bit to 0 or 1, and when that has changed the key the device self-destructs together with all the key bits, and the adversary can find that, then there is a simple attack finding about $2n$ bits of the key shared by $n$ devices, when there is no threatening attack to any individual device.


How to combine a PRG and a non-PRG to design a PRG? I'm trying to solve the following exercise:
Let $G_1, G_2: \{0,1\}^\lambda \to \{0,1\}^{\lambda + l}$ be two deterministic functions mapping $\lambda$ bits into $\lambda + l$ bits (for $l \ge 1$). You know that at least one of $G_1, G_2$ is a secure PRG, but you don't know which one. Show how to design a secure PRG $G^*:\{0,1\}^{2\lambda} \to \{0,1\}^{\lambda + l}$ by combining $G_1$ and $G_2$.
I think that $G^* := G_1(s_1) \oplus G_2(s_2), s_1, s_2 \leftarrow_{\\\$} \{0,1\}^\lambda$ could be a valid PRG. Anyway, I don't know how to prove it; probably with OTP?. How could I prove it using reduction?

I agree that indeed $G^*(s_1, s_2) = G_1(s_1) \oplus G_2(s_2)$ should be a valid PRG if one of $G_1$ or $G_2$ is a PRG.
The common definition of a PRG requires two properties: being expanding and pseudorandom.
Expanding: $G^*$ is expanding if $l > \lambda$ because then $\lambda + l > 2 \lambda$.
The more interesting part is whether $G^*$ is pseudorandom. Depending on how narrow your definition of a reduction proof is the following might fit it or not.
Pseudorandom: We know that at least either $G_1$ or $G_2$ is a PRG. Call the secure one $G_i$, we don't need to know which one because this will work in both cases.
The pseudorandom property of $G_i$ says that its output on uniform random input is computationally indistinguishable from random.
This means that we could replace the output of $G_i$ by a uniform random string and call the resulting PRG $G^{**}$
$$G^{**} = u \oplus G_{1-i}(s_{1-i}), u \leftarrow_{\\\$} \{0,1\}^{\lambda+l} $$
No (computationally bounded) adversary can distinguish this new $G^{**}$ from $G^{*}$ by pseudorandomness of $G_i$. The formalization of this step actually requires a reduction.
After this you can apply can use an OTP like argument and conclude the proof.
We use techniques reminiscent of game hopping proofs here. Game hopping is pretty common in cryptography proofs. For further reference: A good survey that helped me understand it is this paper


why is index "a non-negative integer less than $2^{64}$" in the KDF for UMACs? https://tools.ietf.org/html/rfc4418#section-3.2.1 describes the parameters for KDF as follows:

   Input:
     K, string of length KEYLEN bytes.
     index, a non-negative integer less than 2^64.
     numbytes, a non-negative integer less than 2^64.

My question is...  why is index defined as "a non-negative integer less than $2^{64}$ when the largest value that's ever passed to it is $4$?

It's called in the PDF function with a parameter of $0$:

  K' = KDF(K, 0, KEYLEN)

...and in the UHASH function the highest parameter that it ever goes to is $4$:

 //
 // Define total key needed for all iterations using KDF.
 // L1Key reuses most key material between iterations.
 //
 L1Key  = KDF(K, 1, 1024 + (iters - 1) * 16)
 L2Key  = KDF(K, 2, iters * 24)
 L3Key1 = KDF(K, 3, iters * 64)
 L3Key2 = KDF(K, 4, iters * 4)

So why not say that it's an integer that can have a range between $0$ and $4$?

Because of this:

   T = uint2str(index, BLOCKLEN-8) || uint2str(i, 8)

uint2str obviously creates an encoding of an unsigned integer of at least 64 bits, given that the block size is at least 128 bits / 16 bytes. So for a 128 bit block size you can have a number between 0 (inclusive) and $2^{64}$ (exclusive) before you run out of bits.

It's a better question why numbytes is not below $2^{64} \cdot 8$ or $2^{67}$ as there is clearly some space left, how much depends on the block size. Of course, neither variable needs to go very high in practice, as this is a KDF, not a stream cipher. For the KDF to be secure, it is just important that $T$ is unique...

As I expected, I quickly found this quote to cement my suspicions:

  In any case, BLOCKLEN must be at least 16 and a power of two.

although AES - and therefore a block size of 16 bytes / 128 bits - is assumed. So there you are: the index must be less than $2^{64}$ because that's all there is space for within this scheme.

Note that "str" usually refers to an octet string - also known as a byte array or simply a span of bytes in memory - in specifications such as this one.


ANSI X9.9 Cryptography Standards I'm trying to create a ISO8583 Rev93 message.
What is the standard way of generating MAC key in ANSI X9.9
DES-CBC encryption algorithm is used to encrypt the message and generate the MAC.

How many bytes should I take from the encrypted byte array based on ANSI X9.9 standard? 8 or 16? I think I should take 4 bytes (8 ASCII characters) and place them on field 128 (MAC). But very doubtful about that.
The MAC key that the customer has provided me is 16 characters. (like 1234567890123456). Should I convert it to an 8 byte key? or a 16 byte key? (Based on ISO8583 Rev93 and ANSI X9.9)

Thank you.

without doing your homework for you: did you check the open-source implementations of ISO 8583? is the answer somewhere in there?

DL-ISO-8583, in C
jPOS ISO-8583 Framework, in Java
j8583, also Java
PHP ISO-8583 Parser

Retrieved from wikipedia (strangely, the Spanish page, a good tip for finding more external references is changing the language tab)


Single Ciphertext which can decrypt with multiple keys Say we have a public key system where we have 2 users, Alice, and Bob each has a public and private key. We also have a publicly available server which stores a message.

I want to encrypt this message (M) for Alice and Bob only once. such that either Alice or Bob can decrypt the message with their private key.

The easy and well-studied way to do this is to generate a random symmetric key and encrypt the message with that key, then I can encrypt a small message (SM) For Alice and Bob with their public keys which gives them the symmetric key, with this they can now both decrypt the Message M available on the server.

However is there any known way that I can encrypt the message M, where both Alice and Bob can decrypt M without needing an additional symmetric key? I have looked briefly into double trapdoor encryption and Broadcast encryption but I don't think these schemes suit the purpose?

TL;DR One Ciphertext that can be decrypted by multiple Public, Private keypairs, without deriving an additional symmetric key

One trivial solution is to let the message be:
$$M = (c_{\text{Alice}}, c_{\text{Bob}}) = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m))$$
Whether this counts as a "single message" or not is difficult to say.
Even if it does, it has the (unfortunate) property that Alice/Bob can't distinguish between:
$$M = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m)),\quad M' = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m'))$$
for $m'\neq m$ (so an adversary could "encrypt" something different to each of them, and provided the underlying scheme is CPA secure neither Alice nor Bob will be able to detect the adversarial behavior).

If you want to reduce the communication overhead of your scheme, hybrid encryption (encrypting the private key under both public keys) is likely the best choice, because after this initial "setup" phase you can switch to solely symmetric crypto under this new key.
Symmetric crypto tends to have a lower communication overhead than asymmetric crypto (the term to look at here is the "rate" of the encryption scheme).

That all being said, it's unclear precisely what your threat model is, and even hybrid encryption could easily allow for an adversary to encrypt different keys under Alice/Bob's public keys (so they initially disagree on their secret keys).
How this could be leveraged to mount a larger attack I don't know, but without fixing a particular threat model it's difficult to discuss what security would even mean.


Encryption-then-encode or encode-then-encryption? I have this question in which I m struggling. I have read in many sites about encrypt-then-mac etc.

If the confidentiality for transmission is needed, discuss the feature for the order of encryption and encode by error correcting code (ECC), i.e., 1) encryption-then-encode, 2) encode-then-encryption.

With some modes you can encode then encrypt, specifically stream cipher modes (CTR, OFB). Bit errors during transmission translate to identical bit errors in the encoded plaintext, and error correction will work as intended.

However, with standard block cipher modes (ECB, CBC), the entire block is encrypted, and a 1 bit error in the ciphertext creates many bit changes to the decrypted block due to the avalanche effect. Depending on the type of correction used, this may be correctable, but it is generally better to apply the code to the ciphertext.


How to pad a 448 bit message for SHA256? I recently implemented a very simple SHA256 hashing program in C++, since the SHA256 hash function's block size is 512 bits or 64 bytes, and messages less than that size have to be padded as per the FIPS standard, I implemented a padding function following their exact rules.

$(K+1+L) = 448 \mod 512 $ , where $K$ is the number of $0$ bits that should be appended after the $1$ bit, previously appended to the message.

I was testing my code with test vectors that I received from this website : https://www.di-mgt.com.au/sha_testvectors.html

and unfortunately it failed for the test vector of 448 bits:
abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq
but worked well for the previous test vectors.
Here is a simple snippet of C++ code that I made which is responsible for padding, obviously, there is an algorithmic flaw in it out of my misunderstanding!

int blocks = 0;
if (len % 64) // len is the message length
{
    blocks = (len + (64 - (len % 64))) / 64;
}
else
{
    // I realized (the hard way) that messages that are of size 512 bits or its multiples have an additional block that contains padding info and they run through the compression function.
    blocks = (len / 64) + 1;
}
unsigned char *s = (unsigned char *)calloc(blocks * 64, sizeof(unsigned char)); // Internal storage for the message with padding.
for (int i = 0; i < len; i++)
{
    s[i] = m[i]; // m is the message passed to the function, that has to be hashed.
}
int K = 0;
uint64_t L = len * 8;
uint64_t size = L;

K = (448 - L - 1) % 512;
if (K < 0)
{
    K += 512;
}

s[len] = 0b10000000; // or 0x80
K -= 7;
for (int i = 0; i < (K / 8); i++)
{
    s[i + len + 1] = 0; // The zero bytes...
}
    // Append the length of the message as a 64 bit big endian integer
for (int i = 0; i < 8; i++)
{
    s[blocks * 64 - 1 - i] = (unsigned char)(((uint64_t)size & (uint64_t)(0xff << i * 8)) >> 8 * i);
}

I would like to create a padding method that conforms to the FIPS standard for any bit length whatsoever...
I realize that with a message of length 448 bits, my padding will overflow to the other block.
Should the other block be padded in the same way a message would be padded?
What changes should I make in the algorithm to fit all message lengths?

The padding method for SHA-256 is (assuming you're byte oriented - it appears you are) is 'append an 0x80 byte, and then add 0x00 byte's until the length modulo 64 bytes is 56.  This implies that if the original message length modulo 64 is 56 or larger, you'll need to do one more hash compression operation.

That means that your computation of the number of hash compression operations you'll need:

if (len % 64) {
    blocks = (len + (64 - (len % 64))) / 64;
} else {
    blocks = (len / 64) + 1;
}

is wrong; if len=56 (in this case), this sets blocks=1 (and thus you don't allocate any space for the padding).  More correct would be:

/* Compute the number of bytes of the message plus mandatory padding */
plen = len + 9;   /* 1 for the 0x80 byte, 8 for the length */

/* Number of blocks is the number of message plus padding bytes */
/* div 64, rounded up */
blocks = (plen + 63) / 64;

Also, the number of 0x00 bytes you'll need to add between the 0x80 byte and the length field is precisely 64 * blocks - plen


Finding the Input if Hash Value, Hash Function, and Key are known Let's assume that we have a hash value $h$ is calculated by using HMAC-SHA256.

We have the key $k$. We also know some information about the input:

It contains a pattern like 15 numbers where first 7 are known;

Question: Is it possible to find at least one input $m$ such that $h = \operatorname{HMAC-SHA256}(k,m)$ without generating all possible patterns?

First of all, HMAC is not exactly a hash function. The Wikipedia clearly states that;

  In cryptography, an HMAC (sometimes expanded as either keyed-hash message authentication code or hash-based message authentication code) is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key.

In case of HMAC-SHA256, the hash function in the HMAC is SHA256.

Remember that, Cryptographic hash functions are not invertible functions, and we require that they have pre-image, second pre-image, and collision resistance.

There is still an ambiguity in the question; I'll try to answer in two ways.

The input is exactly 15 numbers where first 7 are known.

In this case, the input space is limited, 8 unknown numbers this makes $10^8 \approx 2^{27} $ and this input space can be tested very quickly even with a raspberry pi.

What about finding a $m$ without generating the pattern. Actually, this means that, you are looking for pre-image for HMAC-SHA256. There is no known attack for HMAC. For alone SHA-256 there are pre-image attacks, for example:

Advanced meet-in-the-middle preimage attacks require $2^{248.8}$ complexity with 42 rounds.

This will be infeasible. Note that practical collision attacks for SHA-256/512 is possible with reduced rounds 26/64 and 27/80, respectively.
The input contains 15 numbers where first 7 are known.

In this case, we have a structure as;

    ppp...pppfffffffrrrrrrrrsss...sss

Knowing some part of the input may help with testing each value. Unfortunately, there is no information about the prefix (p) size and suffix (s) size. So, one has to consider cases.

What about finding a $m$ without generating the pattern. The pre-image status is the same as in the first case.


Security of Randomized Encryption Scheme I have the following question which I'm struggling with

  Suppose we are interested in encrypting bit strings. Consider a
  randomized encryption scheme that always produces ciphertexts of the
  same length as the plaintexts.

  Show that this scheme cannot be IND-CPA secure

Intuitively to me this kind of scheme shouldn't even be decryptable if the randomness lies in the mapping between plaintexts and ciphertexts. How can a single plaintext map to multiple ciphertexts (of the same length) without avoiding collisions and whilst also being decryptable? Am I misunderstanding what it means for an encryption scheme to be "randomized"?

I remember seeing a rough solution once which used the idea of mapping plaintexts to sets of ciphertexts but can't see how that would work / solve the problem.

Ciphertext Indistinguishability means that if you encrypt a message many times, each time the ciphertexts must be different.

For example, think about a device that searches flaws in a dam. Every time, when this device traverses, it will send "Yes" or "No" signals that it means for a receiver that the device has found a flaw or not. If an eavesdropper sniffs these signals, because of the number of "no" signals are more Than "yes" signals, he could understand the meaning of these signals even though they are encrypted and could not break their encryption. This weakness happens because the encryption algorithm is DETERMINISTIC and it means that always it produces same encryptions for "YES" signal and same encryptions for "NO" signals, in other words, the attacker could distinguish these encrypted messages without knowing the nature of the encryptions.

The solution for making messages resistance against distinguishability is using Non-Deterministic encryption and use parameters like IV and so for make ciphertext Random and each time giving the same message, it produces different ciphertexts and the attacker could not distinguish them.


CSPRNG in JavaScript using Audio and Video I ported GnuPG to Javascript using Emscripten (not released yet).
Now I need a good replacement for /dev/random//dev/urandom.
New browsers support window.crypto.getRandomValues() but for older browsers I need something else.
I was thinking about recording some audio using HTML5 and calculating the sha 512-bit digest.
Then splitting this digest into two halfs and using them for AES 256-bit encryption (256-bit IV and 256-bit key) of a photo taken also with HTML5.

Is it safe to use this encrypted image as a replacement of /dev/(u)random?
Which mode should I use for AES encryption?

window.crypto.getRandomValues() is the best you can do.  Unfortunately, at the time of writing, too many browsers don't support window.crypto.getRandomValues(): see Compatibility of window.crypto.getRandomValues().

The alternative is to use fallback methods.  However, those fallback methods are kind've hacky, of dubious security, slow, and have other limitations.  For more on the available fallback methods, see Generate cryptographically strong pseudorandom numbers in Javascript?.

Therefore, life kinda sucks.  Basically, the best you can do is test for the existence of window.crypto.getRandomValues() using feature testing.  If it exists, great! use it.  If it doesn't exist, fall back to one of the fallback methods -- in that case, life is unhappy, but what can you do, there's no better option.


Is there a practical security difference between XXX-bit encryption? I know I'm treading in dangerous waters asking this - my comprehension of cryptography math is sorely lacking. On the flip side it gives me massive admiration for what many of you are able to do.

From my understanding of crypto functions, a password is typically used to create a xxx-bit secret key. This could be 128-bit, 256 bit... 2048-bit (aka xxx-bit encryption) etc. This key is then used to encrypt the data via whatever algorithm is chosen (AES, etc). As I understand it (I could be wrong) you can either decode the information by supplying the correct secret key, or by supplying the correct password which produces the correct secret key.

Given that typically something like an 8 digit alpha numeric case sensitive password would supply 30 bits of entropy, my assumption is that in almost all cases the password would have significantly less entropy than the cryptographic secret key, hence the logical target for brute force attacks. Because of this weak point, which is independent of the encryption key length, is the target of the attack, is there any practical advantage of going for longer bit encryption schemes in keeping data safe?

Caveats

Being very new to cryptography, I probably have gotten terminology wrong. Feel free to correct me but don't get hung up on strict interpretation of what I've said, more the 'theme' of the question.
If I've gotten anything wrong about how the encryption process works please let me know.
This question is targeted towards encryption / decryption with human interaction rather than say SSL certificates. Let's assume a password exists and is used.
I'll try and follow any math you give, but you might lose me!

Thanks so much crypto. First question here, sorry if I've missed anything.

Edit: As an obvious follow up after two answers have been provided showing I'm largely on the right track with my thinking - What's the virtue of choosing longer keyspace algorithm? Again basic understanding is it would give "more" security at the cost of computational intensity in calculating the key. Why do we worry about 1024-bit and 2048-bit encryption? Aren't they both essentially unbreakable anyway?

From my understanding of crypto functions, a password is typically used to create a xxx-bit secret key... Given that typically something like an 8 digit alpha numeric case sensitive password would supply 30 bits of entropy, my assumption is that in almost all cases the password would have significantly less entropy than the cryptographic secret key, hence the logical target for brute force attacks.

First, many (if not most) secret keys should be generated by a cryptographically secure source of random numbers. This will generate a key with maximum entropy: 128 bits, or 256 bits, depending on the size of the key. This is well out of the range of brute force.

If you do need to generate a key from a password, there are algorithms like PBKDF2 which attempt to increase the cost of brute-forcing the key. They have a configurable work factor which, when increased, exponentially increases the amount of computing power required to turn a password guess into a key. You still should avoid using trivially weak passwords, but if the work factor is configured such that each brute force attempt requires around one second to compute (using today's hardware), it would take 17 years on average to break an 8-character alphanumeric key.

That's still obviously far short of the amount of time it would take to brute force a 128-bit randomly generated key, so the use of strong passwords is still absolutely mandatory. Something like a 10-digit password consisting of any of the glyphs on a standard US keyboard would take over 800 billion years to crack given a work factor requiring roughly one second to generate a key from each password guess, given today's hardware.

  Why do we worry about 1024-bit and 2048-bit encryption?

The strength of a key given a certain size is based upon how that key is generated. For 128-bit and 256-bit keys, we are almost inevitably talking about symmetric encryption. For these types of algorithms, the key is randomly generated.

Asymmetric (public/private key) encryption is a different beast. For algorithms like RSA, the key is not simply a very large random number: it is a very large semiprime. In simplified terms, your private key typically will consist of two large prime numbers, and the public key is the 1024-bit or 2048-bit semiprime that results from multiplying those two primes. The difficulty of breaking the key is the amount of effort an attacker would need to spend to factorize the public key in order to discover the two primes that make up the private key — this is a task we believe to be extremely hard.

Based on how hard we think that problem is, we currently believe the effort to factorize a 1024-bit semiprime to be roughly equivalent to brute-forcing a 128-bit keyspace. Likewise for 2048-bit semiprimes and 256-bit keyspaces. There are other asymmetric cryptosystems that rely on other "hard" mathematical problems, and their key lengths are likewise based on how hard we believe those problems to be.


How is the zero-knowledge proof definition violated, here? I'm confused about the definition of an interactive zero-knowledge proof (the simulator-transcript-thingy).

Assume the following setup:

$P$ and $V$ do a Diffie-Hellman key exchange to generate the shared secret S. They then both compute the hash $H(S)$.
$P$ computes $\sigma = sig(sk, H(S))$ and sends $\sigma$ to $V$.
$V$ checks whether $ver(pk, H(S), \sigma) = 1$ and iff it is, assumes $P$ to have proven its identity.

For simplicity, let's assume the base to be $2$.

$sig$ is defined in such a way that its output has $k$ bit and

$∀σ∈\{0,1\}^k, sk∈\{0,1\}^n : (∃S∈\{0,1\}^ℓ : sig(sk, H(S)) = σ)$

where $n$ is the length of the private key and $ℓ$ is the length of the secret created via Diffie-Hellman.

We actually need to require that

$∀σ∈\{0,1\}^k, sk∈\{0,1\}^n, a∈ℤ_q, S∈ℤ_q : (∃b∈ℤ_q : sig(sk, S \mod p) = σ, S = g^{a\cdot b}))$

where $g$ is the primitive root of Diffie-Hellman, $p$ is prime, and $q$ is the order of the group $<g>$;. I merely wrote the formula above so it's easy enough for everyone to understand. The jump from the weaker definition above to the one described by the second formula doesn't seem too big.

As with all signatures, an attacker who knows many $sig(sk, M)$ for different $M$ but the same $s$k can learn about $sk$.

This protocol therefore is obviously not zero-knowledge. However, it seems to fit the definition as I can't think of any argument as to why for any PPT attacker $A$ knowing only about $pk$ communicating with $P$, it's not possible to find a PPT $S$ only knowing about $pk$ which simulates the transcript between $A$ and $P$.

Furthermore, I don't see how the transcript contains information about $sk$ (which after all is what the zero-knowledge definition is about). What I think I have done (and am btw pretty sure I didn't do as the definition of zero-knowledge was created by smart people, so I'm quite aware that I made a mistake somewhere (and I want to know where)) is to give $V$ information about $sk$ without there being information about $sk$ in the transcript.

One could even just let $P$ send $pk \oplus H(S)$ to $V$, giving the secret to $V$ without anyone who can only look at the transcript being able to tell whether the entity {creating; participating in the creating of} the transcript knows the secret ($pk$ which can be regarded as a password, no signature function required).

As with all signatures, an attacker who knows many $sig(sk,M)$ for different $M$ but the same $sk$ can learn about $sk$.

I guess you mean "can't learn anything about $sk$". Yes, that's right, but that's not the security definition of EUF-CMA (existential unforgability under chosen message attack). Informally speaking, it means that the attacker can not generate any valid signature on any message (excluding those he queried in the security game).

As you stated correctly, you can't simulate $P$: The existence of a simulator would be a direct contradction to the assumption that the signature is EUF-CMA: The simulator needs to be able to generate valid signatures with non-negligible probability without knowing the signing key, and in order for the signature to be EUF-CMA such a forgery must only be possible with negligible probability.

  However, it seems to fit the definition as I can't think of any argument as to why for any PPT attacker $A$ knowing only about $pk$ communicating with $P$, it's not possible to find a PPT $S$ only knowing about $pk$ which simulates the transcript between $A$ and $P$.

Yes, you can replace the verifier $V$ with a simulator, and this is actually zero-knowledge. However, this is quite trivial, if you look at your protocol: $V$ does not send any message in dependency of the secret value. It only does a DDH key exchange and then finishes the protocol by accepting the identity. In an exchange with an honest $P$ this will work out - it's more complicated if $P$ isn't considered to be honest (but that would also require the protocol to be different).

But what does it actually mean? Well, $V$ doesn't have a secret value. So there is no information kept secret. Zero knowledge does not mean, the other side doesn't learn anything - it means that the simulator can act like the party he replaced. And that's pretty much trivial if that party has no secret value.

But more importantly: This only states that $V$ doesn't send any information, which isn't in the protocol. It does not state anything about $P$ sending $sk$ in the protocol. For that you would have to replace $P$ with a simulator - which is impossible without breaking the security of the signature scheme, see above.

  Furthermore, I don't see how the transcript contains information about $sk$
  (which after all is what the zero-knowledge definition is about).

$sk$ is a secret value, so yes, a zero knowledge proof replacing $P$ with a simulator would prove that - if it existed. I think there is a misconception here: The main argument of the zero-knowledge proof is that you can create a valid transcript - but the corresponding party doesn't have the secret value. That means the transcript itself doesn't depend on the actual secret - the simulator doesn't know it. If you leave $P$ in and replace $V$ with the simulator, that doesn't change anything and you don't know if the transcript leaks $sk$ or not.

  .. is to give V information about pk without there being information about pk in the transcript.

The verification key $pk$ is public - you don't need to give that to $V$, he already has it.


What exactly is a digital signature? I am aware of basics of public key encryption algorithms , for eg. RSA.
If A wants to send a message to B, A uses the public key of B to encrypt the message A wants to send to B, and only B can decrypt the message using his private key.

What I don't understand is that what exactly is the digital signature, if for eg. A is sending an email to B? Is it the email id? The message that A wanted to send to B? IP address? Is it a random text or string? If it's random, how does B know it was A who sent it?

$\newcommand{opn}{\operatorname}$
Formally, a digital signature scheme is a triple of algorithms $(\opn{KeyGen},\opn{Sign},\opn{Verify})$ where the first two are probabilistic and the last is deterministic such that the following logical statement holds except in a negligible amount of cases:
$$\forall \lambda\in\mathbb N:\forall (pk,sk)\gets \opn{KeyGen}(1^\lambda):\forall m\in\mathcal M:\opn{Verify}(pk,m,\opn{Sign}(sk,m))=1$$

That is, by its very definition, the receiver can verify the signature of a message using a public key associated to a specific private key. If you are looking for standard security definitions, have a look here.

So, how can we instantiate these triples? As you already know RSA, I shall discuss this using RSA-Full Domain Hashing (RSA-FDH), which is conceptually the easiest, provably secure signature algorithm.

$(pk,sk)\gets\opn{KeyGen}(1^\lambda)$, this is the non-deterministic algorithm, that given a security parameter $n$, returns a public ($pk$) and a private key ($sk$) for use with the cryptosystem. For RSA this would be $(n,e)$ as the public key, with $n$ having length $\lambda$-bits, as well as a note on which hash algorithm is to be used. The private key would be the public key with $d$ added.
$\sigma\gets\opn{Sign}(sk,m)$, this is the (potentially) non-deterministic algorithm that given a secret key $sk$ and a message $m$, returns a signature $\sigma$. For RSA-FDH this would be $\sigma =H(m)^d\bmod n$ with $H:\{0,1\}^*\to\mathbb Z_n$ being essentially a hash function that outputs a hash as large as $n$. Practically one can use SHAKE128 (the arbitrary-length version of SHA3) here.
$b=\opn{Verify}(pk,m,\sigma)$, this is the deterministic algorithm that given a public key $pk$, a message $m$ and an alleged signature $\sigma$ on $m$ decides whether $\sigma$ is indeed a valid signature, produced using the private key associated to the given public key on the given message. The result is a yes/no answer, encoded as 1/0 in $b$. For RSA-FDH this would be $\sigma^e\bmod n\stackrel{?}{=}H(m)$.

As for the correlation between a signature and a sender, assuming we have a trusted binding between the public key and the sender and assuming the sender hasn't leaked their private key, only they could potentially have created a valid signature for the given public key, meaning we can be sure this message is from them.


Is it OK to use a hash of the key as nonce for AES GCM? I don't see an immediate risk of using the hash of the key as the nonce for AES GCM. Is there something I could be overlooking?

I assume you mean AES-GCM.

Nonces must be unique for any use of a key. Given that $n = H(k)$ is constant for constant key $k$, this implies that such a nonce may only be used once, ever. Nonce reuse is particularly catastrophic in GCM mode (as with any other CTR-based mode), as it causes the keystream to be identical.

Essentially, you wind up with two (or more) ciphertexts $C_0 = K \oplus P_0$, $C_1 = K \oplus P_1$. An attacker can trivially compute

$$
\begin{align}
C_0 \oplus C_1 &= K \oplus P_0 \oplus K \oplus P_1\\
&= P_0 \oplus P_1 \oplus K \oplus K\\
&= P_0 \oplus P_1 \oplus 0\\
&= P_0 \oplus P_1
\end{align}
$$

If an attacker can control the contents of any plaintext, it's trivially game over. Even in the event that an attacker can't, knowing the XOR of two plaintexts is almost inevitably enough to reconstruct the originals.

In general, nonces and IVs for any mode must be unique for any given key. In CTR-based modes, uniqueness is the only constraint placed on the nonce. Other modes may have more stringent requirements; for example, CBC requires IVs to be unpredictable by an attacker. Failure to follow these requirements can result in a complete break of the  of the cipher.


What happens if the plaintext $m1$ from the first block of CBC is known to adversary? The adversary is has unlimited access to the encryption oracle. My thinking is that upon receiving the ciphertext C = $<c_0,c_1,c_2...,c_n>$ it will just use $c_0$ to XOR it with $F_k(m_1)$ to get the first ciphertext, which does nothing. The subsequent blocks remain undecrypted, right?

For any modern cipher (including a block in CBC mode) with proper implementation, nothing harmfull happens when any part of the plaintext gets known to the adversary. This adversary's knowledge does not extend to other bits of the plaintext.

Argument: any algorithm that could extract some additional knowledge could be turned into one breaking CPA security. For CBC, CPA security can be proven from security of the block cipher, under the assumptions that the IV is random, the number of blocks enciphered remains low enough (like, less than $2^{b/2-n}$ where $b$ is the block size in bits and $n$ is a security parameter), and the decryption side does not leak information about the deciphered plaintext (such as, incorrect padding).


How to generate a random point on an elliptic curve without knowing it's corresponding scalar private key Given an elliptic curve with generator $G$, is it possible to generate a random point on the curve $Q = a \cdot G$ without knowing the secret value $a$ that generated it? Note that just using an $a$ to generate $Q$, and then "throwing away" $a$ (forgetting about it) isn't a valid solution. Also note that $Q$ should be uniformly distributed over all valid values (i.e. as if $a$ was chosen uniformly between 0 and $n-1$).
A toy application I have is about making some "fake" Diffie–Hellman secret exchanges, where 1 party can't get to the secret because they don't know their key $a$ (and weren't just be trusted to "throw away" the value of $a$ after generating $Q$). This is all to ultimately enable "playing poker over the phone".

Pick a random $x$ value. Calculate $y^2 = x^3+ax+b \bmod p$. Then try to form $y$ by taking the square root $\bmod p$. If the square root fails then no $(x,y)$ pair exists on the curve. If the square root works, flip a coin; if tails form $y = p-y \bmod p$.
This is how public key compression works. Only the low bit of y is saved. Form $y^2$, take the square root (which had better work). If the low bit of $y$ is wrong then form $y = p-y$.


Visualization of cryptography I think CrypTool is great software. And what I find most useful in it is visualization of algorithms such as Caesar, Vigenere, AES, DES. And my question is: does anyone know other tools which are intended for visual explanation of basic cryptography and related topics such as prime numbers, elliptic curves, finite fields, factorization etc? I am looking for short videos, games, animation, comics, presentations, popular science films. I am lecturer at University, and my goal is to awake students' interest in cryptography and convince them that it's one of the most exciting disciplines. What would you recommend me?

Check out the videos from Art of Problem  there are some amazing videos on cryptography. Short and good visual ones they nail the point, am sure you would love them.


Want to generate numeric coupon codes? We want to generate coupon code series and then encrypt those coupon code in numeric only, and that must also be decipherable.

We will be sharing encrypted code as coupon code with customer.

These are the conditions:

Encrypted code must not be in series or not easily able to guess;
Encrypted code must be numeric.
Encrypted code must be having a specific number of digits (think: size/length).

Example :

We generate coupon code from 1 to 100 (needs in millions and plainCode will be either numeric or alphanumeric doesn't matter).

We want share encrypted numeric coupon code with specific digits to user.
i.e. if code is 52 then encrypted code gives us between 10000 to 99999 (if 5 digits are specified or it need to be fix number of digits)

We are also able to decrypt the same.

Note:

Above is just an example. possibilities are in millions.
Security is not a major concern. just not able to guess is matters a lot.
encrypted code must be in numeric.

Question:

Is there an established, cryptographical secure way to do this? If not, what would we need to do to handle this?

Any suggestions or ideas are more than welcome.

We have looked and FPE. Any good algo for the same recommended which return in specific number of digits. We have one which gives encrypted numbers less than specified number but we want in between specific range to maintain number of digits without 0 appending.

I have an almost identical requirement for location identifiers I use in a custom inventory system. I have a 35-bit code, which is displayed as 7 5-bit elements, which need to be human readable and unique. The method to generate the codes does not necessarily have to be format preserving, that can just be a side effect of the algorithm used.

The method I use generates a 7 character code, with each character being alphanumeric 0-9 and A-Z, omitting OIZS because they are too similar visually to 0125. Internally the algorithm is a block cipher called Bromine with 5 7-bit elements in a generalized Feistel network, which is based on the round structure of the HIGHT block cipher. The input is a numerical sequence, and the output is a pseudorandom alphanumeric sequence:

JE4HV9W
JPNJ4NE
V20MUP3
QCKCVWU
QTR7FUC
5E94W9J
4HYWH14
9W1229T
PT6JJTV
MEWTT68
91ACL19
....

Because the input sequence is numeric, there are only 10 million output combinations for the given 34.36 billion possibilities for a 35-bit value. This limits the number of ciphertexts available to reverse engineer the algorithm or determine the key used. The algorithm is simple but has enough rounds to be secure given the key size (in theory). The use environment has no requirement for this kind of security, but it allows it to be used for other applications if needed. The numeric input is a security and usability requirement, and not a limitation of the algorithm.

If used to generate coupon codes, certain input elements or bits can be fixed, and those fixed bits can define the coupon type or discount. The system would only need to keep track of used coupon codes, and decode them to determine the type and validity. Only 1/3436 codes entered randomly will decode to a valid input, and the number of coupons from valid inputs can also be limited further.

For example, your input could be structured as XXYYYYZ, where XX is the coupon type, YYYY is the value, and Z is a fixed element such as 0. Coupon 01 would be assigned to a 5% discount with only 100 allowed coupon uses before it expires. When entered into the system, it is decoded, its structural validity is determined (is numeric and Z=0), XX is determined to be a valid coupon, and YYYY is determined to have not been yet used for a given XX. If all requirements are met, the discount is given, and XXYYYY is saved for comparison with further coupons. Only 0.003% of this example format meets the required structure and only 1% of these decode to the desired coupon type.

If a longer code is required, variants of such a cipher are easily generated in other sizes. The 40-bit version extends the subwords to 8-bits, and is displayed as an 8 character code. A 42-bit version for display as 6-bit 7 character codes is created by extending the 5 subword 7-bit Feistel structure to 6 subwords, and the 48-bit version extends its subwords to 8-bits.


Pohlig-Hellman and Shanks algorithm on ECC First, sorry for my english which is not my natural language and secondly, I hope I am posting on the right section.

So let's explain my problem.

I am trying to implement the Pohlig-Hellman algorithm based on elliptic curves with the Baby-Steps-Giant-Steps for each iteration.

My Python implementation use a curve on finite field with a smooth prime modulus $N = 2*853*3593*4339$.

With the curve : $y^2 = x^3 + 521x + 1331$ on $\mathbb{F}_{26596586063}$

And the generator $G = (20197258757, 24233149744)$

In theory, and if I understand correctly, the worst complexity in the Baby-Steps-Giant-Steps phase will be $\sqrt{4339}$, right ?

My implementation seems to work (I have the right solution) but I don't have the right complexity : the Polhig-Hellman problem reduction seems useless because I have the same complexity with the Baby-Steps-Giant-Steps running alone.

When I try to solve the discrete logarithm : $H = xG$, my implementation run with a complexity of : $O(\sqrt{x})$ approximatly.

I don't understand my mistake and I am very confuse...

Thanks for your answer.

Here is my implementation (in Python):

def baby_step_giant_step(curve, G, H, order):

    m = int(math.ceil(gmpy2.sqrt(order)))
    L = {}

    # Baby steps
    for j in range(0, m):
        P_tmp = curve.mul(j, G)
        L[str(P_tmp)] = j

    mG = curve.mul(m, G)

    # Giant steps
    for i in range(0, m):
        P_tmp = curve.mul(i, mG)
        if not P_tmp.isInf():
            P_tmp = ecc.Point(P_tmp.x, (-P_tmp.y) % curve.p)

        P = curve.add(H, P_tmp)

        index = str(P)

        if index in L:
            return (L[index] + i*m) % curve.p

    return None

# Solve the equation : G^x = H (mod curve.p)
def pohlig_hellman(curve, G, H):
    N = curve.p-1
    factors = decompose_order(N)
    x = 0

    for i in range(len(factors)):
        ni = factors[i][0]**(factors[i][1])
        tmp = N//ni
        G_prime = curve.mul(tmp, G)
        H_prime = curve.mul(tmp, H)

        # Now, use the Baby Step Giant Step algorithm to solve :
        # H_prime = x_prime*G_prime
        x_prime = baby_step_giant_step(curve, G_prime, H_prime, ni)
        while x_prime == None:
            order *= 2
            x_prime = baby_step_giant_step(curve, G_prime, H_prime, ni)

        # Use the CRT to solve the equation x_prime = x (mod ni)
        (gcd, x0, x1) = xgcd(ni, tmp)

        x += x_prime*x1*tmp

    return x % N

# (A, B, N)
curve = ecc.Curve(521, 1331, 26596586063)
G = ecc.Point(20197258757,24233149744)

H = curve.mul(523151, G)

x = pohlig_hellman(curve, G, H)
print("x = %s" % x)

PS : don't be afraid by the WHILE loop, it was only for debuging purpose.

Although I was not able to run the scripts (perhaps my fault, my Python skills are mediocre at best), let me try to elaborate (slightly) on fkraiem's comment.

You are indeed right that the complexity of Pohlig-Hellman is lower than the complexity of BSGS (for a curve of smooth order). However, your parameters are relatively small. Looking at the definition of the big-$O$ notation, we see that this line of reasoning will ignore some constants. That is, roughly, the complexity $O(\sqrt{x})$ means that there is some constant $c$ such that for large parameters the complexity will be $\leq c\sqrt{x}$. This is however only a statement about large parameter values, and does not have much meaning for specifically chosen (small) parameters. For example a situation where an algorithm with complexity $O(t)$ is slower than an algorithm with complexity $O(t^2)$ for a specific instance is easily possible. Note that the definitions of small and large here depend very much on context.

Having said that, I am not sure whether that is actually the problem here. Iirc Pohlig-Hellman does not behave very poorly for small parameters, nor does BSGS. Perhaps you should be careful how you are measuring your complexity. Is it running time, number of curve operations, number of field multiplications, etc.? It could be that there is some overhead unrelated to the algorithm which affects the complexity.

Edit:
Okay, there are some confusing parts in your question. Let's get the details straight. We are assuming a curve $E:y^2=x^3+521x+1331$ over the field $\mathbb{F}_{26596586063}$. As you say, the points on this curve form a group of order $N=2*853*3593*4339$, with some generator $G$. Suppose there is some $H\in E$ such that $H=\ell G$ for $\ell\in[1,..,N]$. I deliberately name the scalar $\ell$ as opposed to $x$ to avoid confusion with the curve variable $x$. Let's compare the two ways in which we can solve this DLP (with a bit of abuse of notation):

BSGS: Doing BSGS on a group of order $N$ has complexity $O(\sqrt{N})$ and will give us $\ell\pmod{N}$.
Pohlig-Hellman:  Doing PH will cut the DLP up into four parts. We solve four smaller DLP's with respective complexities $O(\sqrt{2})$, $O(\sqrt{853})$, $O(\sqrt{3593})$ and $O(\sqrt{4339})$ (these are your $ni$'s), to get $\ell\pmod{2}$, $\ell\pmod{853}$, $\ell\pmod{3593}$ and $\ell\pmod{4339}$. We then use the CRT to recover $\ell\pmod{N}$. Hence we have complexity $O(\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339})$ for the small DLP's. Note that we are forgetting about the cost to actually reduce to these small-order DLP's.

What we conclude is that for BSGS we have a complexity of around $\sqrt{N}\approx 163085$ while for Pohlig-Hellman we only have a complexity of around $\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339}\approx 156$.


Are side-channels possible in KDFs Are KDFs such as PKDF2 and HKDF vulnerable to side-channel attacks such as static and dynamic power analysis including the hash type used internally?

Technically speaking, a side-channel attack by definition doesn't attack a KDF but a specific implementation of it. An example of an implementation would be the way macOS turns a user's password to a disk encryption key with PKDF2. A gZip application may execute the PKDF2 in a slightly different fashion.
The answer to your question is yes, because you can never know if a developer made a mistake, or something like that. If that isn't what you meant please clarify.


Negative exponents in Shoup's threshold RSA? I'm trying to implement threshold RSA operations, starting with decryption based on

  Peeters, R., Nikova, S., & Preneel, B. (2008). Practical RSA Threshold Decryption for Things That Think. Retrieved from http://www.cosic.esat.kuleuven.be/publications/article-1178.pdf

and running into problems where it seems I would have to raise by a negative exponent. The formula is on page 9:

$$
w = \prod_{j\in S} x_j^{\lambda_{0,j}^S}
$$

Peeters et al. reference

  Shoup, V. (2000). Practical threshold signatures. Advances in Cryptology—EUROCRYPT 2000, 207–220. Retrieved from http://link.springer.com/content/pdf/10.1007/3-540-45539-6_15.pdf

for definitions, which to me seems to have the same issue. I'll quote Shoup page 212:

  Let $\Delta=l!$. For any subset $S$ of $k$ points in $\{0, \ldots, l\}$, and for any $i \in \{0, \ldots, l\} \setminus S$, and $j \in S$, we can define $$ \lambda_{i,j}^S = \Delta\frac{\prod_{j^\prime \in S\setminus\{j\} }(i-j^\prime)}{\prod_{j^\prime \in S\setminus\{j\} }(j-j^\prime)} \in \mathbf{Z} $$

(which Shoup defines as equation (2), but I couldn't get the embedded LaTeX to do that)

Shoup uses $\lambda$ on page 214:
$$w = x_{i_1}^{2\lambda_{0,i_1}^S} \dots x_{i_k}^{2\lambda_{0,i_k}^S}$$

(where $x_i$ were previously calculated to be in $Q_n$, e.g. the subgroup of squares in $\mathbf{Z}_n^*$, n being the RSA modulus, though I'm a little bit out of my depth as to what consequences this has. In any case, Peeters et al. don't use the subgroup of squares.)

My problem is: $\lambda_{0,j}^S$ is negative quite often. Simple example $l=3, k=2, S=\{1,2\}, \Delta = l! = 6$.

For $j=1$: $\lambda_{0,1}^S = \Delta \frac{ (0-2) }{ (1-2) } = 6 \cdot 2$

For $j=2$: $\lambda_{0,2}^S = \Delta \frac{ (0-1) }{ (2-1) } = 6 \cdot -1$

How am I supposed to use that in an exponent?

There is nothing wrong with any negative exponent $\lambda$, just modular division for $(-\lambda)$, modulo $n$. That is, one would calculate modular exponentiation for positive $(-\lambda)$ first and modular inverse (division) next.


Is this a valid scheme to authenticate through a 'human-readable' certificate? Let's say Alice wants to talk securely to Bob over the internet, and Eve is not only eavesdropping, but has managed to get into a MITM position.
In this scheme Alice and Bob exchange $n$ (example $n = 2$) plaintext questions, at least one for both parties (these are toy example questions):

Alice, what brand of car did I ride you to the airport with last December?
Bob, what's the serial number of the flashlight I gave you yesterday?

Is it then secure for Alice and Bob to attempt to use authenticated encryption under key $H(A_1 || \dots ||\ A_n ||\ S)$ where $A_n$ is the answer to the $n$th question (both parties will include the answers to their own questions), $S$ is a cryptographically strong salt, and $H$ is a slow key derivation function like scrypt?
This will only work if the answers are the exact same, so let's assume the answers have exact unambiguous answers.
Then, using this (seemingly temporarily secure) authenticated channel, can Alice and Bob exchange long-term proper crypto authentication certificates to foil Eve's future attempts at MITM?
Obviously, security can only be as good as the quality of the questions, so let's assume that Eve does not know the answer to any of the questions until the long-term exchange has completed, but we must assume Eve will be able to figure out the answers at a later time.

No, it is not. There are several misconceptions with your scheme.

First, your question/answer pairing does simply not contain enough entropy. This is much less entropy than your common "please choose a password" input, because you can't just use all words/numbers/common symbols. You have to stick to answers that make sense. This is what Ricky Demer hinted at in his comments. Even using scrypt or another password based KDF will be able to negate this fundamental issue.

Secondly, your 'salt' is entirely pointless. Salts are used to prevent attacks (multi user setting, rainbow tables), which are not considered in your scenario. You assume Eve to have only access to the communication network.

Thirdly (and most important): Your scheme mixes key exchange and authentication, but has vulnerabilities with both regards: Neither Bob nor Alice have a way to determine, if a question is from the other partner or was actually modified by Eve. She can just swap out the questions to those she is knows the answers to (possibly from a previous exchange, where she researched the correct answers). The question/answer format is not a suitable challenge-response mechanism, because there is no intractable computational problem (e.g. Diffi-Hellman) involved.

From a computational point of view, this has no security at all, because the questions are sent in the clear, knowledge of a question almost immediately implies knowledge of the possible answers, and then you just throw a hash function on top. And Eve can do that all by herself as well. And even worse, she can just take her time, find out the correct answers to the easy questions and decrypt everything afterwards.

The only way to use this would probably be to use the "unique serial number" from the pen you mentioned, and limit its usage to a single time. That means, basically you got something like a one-time-password and use it to seed a CSPRNG. But if you limit yourself to that, you can just leave out the clunky non-secure question/answer game.


Prove if it is a CCA secure Commitment Assume we have a IND-CCA-secure PKC (Public-Key-Cryption) and we construct a commitment-scheme(commit, reveal) with that IND-CCA-secure PKC (so that commitment should be IND-CCA-secure too). But how can I prove that? I am a beginner and have absolute zero idea how such a proof works.
My idea: "the reveal-step" from commitment-scheme is uselss. so we can cut it? I heard something about reduction. But how does it work? Can anyone explain the reduction by using the example above step by step? Thank you!

The security property IND-CCA does not fit with commitment schemes. The IND-CCA game is specified in a certain way, and is usually used w.r.t. encryption schemes. However, a commitment scheme can be more general, because you don't need to be able to reverse the process like decryption.

A very simple model for a commitment scheme is that you have a one-way function with two inputs. One of them is the element you are commiting to, and the other is random. In the unveil phase you show them both, and it can be verified by applying the one-way function on those inputs. Those random coins are required for some security properties.

For the security properties of commitment schemes, there are two properties to look at:

Hiding property: If it is computationally hiding, then it is a difficult problem to find a matching input. If it is unconditionally hiding, then there exists a way to unveil a commitment to every valid input. Basically this is similar to the principle of perfect secrecy.
Binding property: If it is computationally binding, then it is hard to unveil a commitment to any other element, which was not the original input. If it is perfectly binding, then it is not possible to unveil an element to anything else than the original input.

It is easy to see, that unconditionally hiding and perfectly binding are contradictions to each other, and in fact it is impossible to have them at the same time. But there are commitment schemes which are unconditionally hiding and computationally binding, and there are schemes which are computationally hiding and perfectly binding:

$G$ is a prime order group where the DLOG problem is hard, with generator $g$. Then commit to an integer $x$ (in matching bounds) as $Com(x) = g^x$. Unveil is just showing $x$. This is computationally hiding and unconditionally binding.
Pedersen commitment: $G$ again a prime order group where the dlog problem is hard with two generators $g,h$, commit to $x$ as $Com(x,r) = g^xh^r$ with a random integer $r$. In order to unveil, both $x$ and $r$ are shown. This scheme is unconditionally hiding, because if you knew $log_g(h)$, then it would be possible to unveil any value $x$ by calculating the matching value $r$. However, under the assumption that the commiter does not know that discrete logarithm, the scheme is computationally binding.

Besides that, it was one of the first results shown in the UC framework, that it is impossible to realize UC-secure commitments. But it was also shown, that the additional assumption of a common referecne string allows the construction of such a UC-secure commitment scheme.


What is the most secure/reliable CSPRNG currently available? In terms of period length, uniformity/distribution, what is the most secure/reliable CSPRNG currently available?

The most secure CSPRNG would be one which produces a stream indistinguishable from random data without knowledge of the key, and which takes a key large enough that an exhaustive search of the key space is impossible. It turns out that there are many such CSPRNGs, so there's more than one answer:

ChaCha and Salsa20 are 256-bit stream ciphers which can output $2^{64} \times 512$ bits of data per key.
AES in CTR mode is secure, but becomes distinguishable after generating about $2^{64} \times 128$ bits.
HMAC_DRBG and Hash_DRBG are NIST standards that use a secure hash function, but are slow.

There are many more which I could list, but not all are popular. ISAAC for example is a secure CSPRNG with no known weaknesses, but it hasn't been the subject of a large amount of research for this reason.

If you are asking which CSPRNG is least likely to be the subject of major cryptanalytic breakthroughs in the future (i.e. which have the highest security margin), then the answer would be complex enough to fill entire cryptography journals, and indeed, they do. In general, ChaCha20 (ChaCha with 20 rounds) is currently thought by many to have one of the highest security margins. But they're all unbreakable.


FHE Block ciphers' usage There are currently FHE implementation for

AES
Simon
Speck, and may be more.

Except for speed testing, amortized or not, one meaningful usage is mitigating form side channel analysis. Intel, AMD, or ARM can implement this algorithms secured from known side channel attacks and even from cache attacks and , actually, we can have such software versions, too.

Are there any other meaningful usage for FHE block ciphers?

The main advantage I have heard is reducing the amount of data the client has to send to the cloud.

As said in A Comparison of the Homomorphic Encryption Schemes FV and YASHE:

  [...] ciphertext expansion (i.e. the ciphertext size divided by the
  plaintext size) of current FHE schemes is prohibitive (thousands to
  millions). For example using techniques in [CNT12] (for 72 bits of
  claimed security), sending 4MB of data on which the cloud is allowed
  to operate, would require to send more than 73TB of encrypted data
  over the network.

And to solve this issue, clients could encrypt their data with some block cipher instead of encrypting with a homomorphic encryption scheme.

Then, clients would just send their FHE public keys with the encrypted data.

On the other hand, the cloud would have to encrypt with the FHE scheme the ciphertexts received (using the clients' public key) and homomorphically decrypt them (running the block cipher's decryption function homomorphically) before they are processed.

Since block ciphers have very small ciphertext expansion, sending the data encrypted with AES (for instance) plus sending the public key means sending much less data then sending only the data encrypted with a FHE scheme.

This is also the application commented in Homomorphic Evaluation of the AES Circuit.


ZKP: Asymmetric encryption with confidential message and known hash I'm searching for a ZKP package that supports asymmetric encryption so I can implement the following scenario:

Carol encrypts message $m$ with Alice's public key and sends the ciphertext to Alice. Bob and Alice both know $\operatorname{hash}(m)$, but because $m$ is encrypted by Alice's public key Bob doesn't know $m$--only Alice knows $m$.

Here is the part that needs ZKP: Alice wants to prove to Bob that this ciphertext is actually the encryption of a message whose hash is $\operatorname{hash}(m)$.

In other words, I want to be able to prove that I have a value whose hash is equal to y = hash(a), and whose encrypted form is z = enc(a), but I don't want to reveal a.

I searched in ZKP packages thoroughly, but none of them can implement encryption, so I take it that ZKP isn't the solution.

Do any of the available packages support what I am trying to do?

If you wanted to prove a statement like hash(a) = y, I would recommend you to use a generic  zero-knowledge protocols which proves the computation of a boolean circuit using a witness w like presented here and here. The authors first paper even published a reference implementation of SHA256 on github. Even though it's not impossible to additionally prove a statement like z = enc(a), I would recommend you not to do that for several reasons:

The performance will likely be poor due to the expected circuit size and depth.
Considering the adversary model you want to be secure against and the algorithm you choose, it may be still possible to create attacks if you don't pay attention.


How to practically find solutions to a discrete logarithm? Are there any ongoing or current practical attempts to solve instances of the discrete logarithm problem of the order of magnitude used in cryptographic applications, for example with a 256 bit modulus and 160 bit exponent? I am interested in efforts similar to the work of members of the Mersenne Prime forum  and the RSA factoring challenge, but for the discrete logarithm problem.

What principles and techniques are involved? Do any of these solutions yet approach a realistic time frame? I am mainly looking for working software implementations of any attempts.

I checked some links given in Wikipeda's Discrete Logarithm records page, in particular GGNFS. Can someone help compiling and testing it?

I also found a similar question: https://crypto.stackexchange.com/questions/100/modern-integer-factorization-software. Does this software also allow what I want?

Here is some test data (all in decimal form):

base: 47
modulus: 112624315653284427036559548610503669920632123929604336254260115573677366691719
result: 107169838909122878937980510796152643759453843830224828060309998762431169006781

You have to find 160 bit exponent.

256-bit discrete logarithms on a prime field are definitely not of the order of magnitude used in cryptographic applications. Secure sizes for this problem are in the thousands of bits, very much like integer factorization.

To break that example discrete logarithm, you probably want to use Index Calculus, more specifically the Linear Sieve. Resorting to the Number Field Sieve is probably overkill for such a small prime field, and GGNFS is not prepared to solve discrete logarithms, although much of it could be reused to do so.

Note that 256-bit sizes are OK for problems with less structure, where only generic discrete logarithm algorithms, like Pollard's Rho, work --- such as elliptic curves over a 256-bit prime.


Substitution-permutation network visualizer I'm doing differential analysis of a toy block cipher in which I've to extract the differential characteristic of the first n-1 rounds.

However, I can't do that very well as I can't see the network itself. Basically, I wonder if there is a software which generates a SPN network automatically given round permutations&S boxes and presents it visually. This would make the analysis much simpler.

I know of no software that lets you visualize an arbitrary SPN network; however, many of us on the semiconductor side of things have their verification tools output visualizations based on the bit states.  We used these to compare the SPICE output to the software simulated.  My Simon Cipher and AES verification tools print out bit grids.  My AES tools are async, but the simontool program gives synchronous outputs and will give you an example of how to generate these types of bit grids if you dig into the code.  As a tractable example using the SIMON32/64 test vector:

simontool -e -b 32 -k 64 -s 1918111009080100 -t 65656877 -l log.e.32.64.txt -x simon-e-32-64

That dynamically creates a LaTeX file that contains a bit grid based on the input vector.


What is the best way to put a backdoor in an encryption system? How can you put a backdoor into an encryption algorithm? Are there any techniques that can be used to reduce the time it takes to break a key?

I am looking for practical examples encryption schemes that have backdoors, because they were designed to or new techniques exposed them. It is my understanding that you can use a lack of entropy and diffusion in block ciphers which will reduce the necessary time that it takes to break a key. This is especially true with s-boxes, which can be designed to not increase the strength of the key. As for one-way algorithms, using none-primes can make it easier to reverse keys. What are other decisions that can be made to make a broken encryption algorithm?

The goal is find examples that can be used for encryption pedagogy, by collecting a sample of weak ciphers to practice on.

Schneier's "A Self-study Course in Block-Cipher Cryptanalysis" is an excellent resource for what you are looking for. In particular, FEAL-4 would be a promising cipher to look at as it is breakable by almost every cryptanalysis technique.

One thing you will notice when going through Schneier's course (or when looking at cryptanalysis research in general) is that a lot of times it is helpful to restrict the block cipher by decreasing the number of rounds. Decrease the number of rounds enough, and every block cipher is probably breakable. This will teach you a lot.

Once you are familiar with standard cryptanalysis techniques, it shouldn't be too hard to come up with a cipher that is breakable (where you'll know how to break it).


Order of OTs and commitments in Yao's Protocol for malicious adversaries I was reading the book Efficient Secure Two-Party Protocols by Y. Lindell and C. Hazay. Page 92 of the book says

  This check is crucial and thus the order of first running the oblivious transfer and then sending the circuits and commitments is not at all arbitrary

I don't understand what difference would it make in the security if OTs are done after the commitments.

In the simulation, the output of the corrupted party is needed by the ideal adversary/simulator BEFORE the commitments and circuits are sent. Otherwise, the simulator is unable to generate values that will be indistinguishable from those in a real execution. In order to obtain this output, the simulator must send the corrupted party's input to the trusted third party (ideal functionality) and then get back the output. Since the corrupted party's input is extracted by the simulator in the OT phase, the OTs must be run first.


Frequency analysis secure language Let’s say there’s a language that has all the letters of the alphabet evenly distributed.

Is this language then secure against frequency-analysis or could there still be some soft of weakness, i.e. by using too short keys?

Substitution cipher (e.g., Caesar) and polyalphabetic substitution cipher (e.g., Vigenere) are deterministic encryption schemes. The same plaintext will always result in the same ciphertext. So, they are not secure in the sense of indistinguishability under chosen plaintext attack (IND-CPA).

It may be possible that "all the letters of the alphabet are evenly distributed", but it is very unlikely that all the 2-grams, 3-grams, etc., are evenly distributed (because some of them may be meaningless in the language). In this case, the frequency analysis can still work.


Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes? In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the group with the order $p$ and need a subgroup with order $q$.
This is for security reasons (discrete logarithm calculation algorithms) or for computational optimization?

The group you're working with does not have order $p$. In discrete log schemes, you're not working in a finite field, $F_p$, but rather a multiplicative group $1,...,p-1$, which has order $p-1$. Since $p$ is a prime, $p-1$ is composite (as long as $p > 3$). Group theory tells us that there is a subgroup of size $d$ for every $d$ that divides $p-1$.$^{1}$ By choosing a subgroup of order $q$, where $q$ is prime, we ensure that there are no (non-trivial) subgroups. This avoids small subgroup confinement attacks.

As mentioned in the other answer and comments, there are easy ways to find suitable $p$ and $q$. One is by using primes, $p$ and $q$, such that $p = 2q + 1$. Such a $p$ is called a safe prime. Another is by setting $p  = qr + 1$, where $r$ has (potentially) unknown factorization. The group generated by this $q$ is called a Schnorr group.

$^1$ This claim is not true in general. It is true for the group of a finite field. See this Wikipedia section Existence of subgroups of a given order for the gory details in the general case. This math.stackexchange answer is a nice proof for the group of a finite field.