Simple proof of ownership of a password I want to do a completely serverless p2p chat application on web browsers, so it won't even have a database to store accounts, but I still want to have some kind of identity system on it (an user can have a username on this chat that only they can use). To achieve this, I began to work on an authentication system a bit reminiscent of tripcodes, used on various imageboards (I don't know if this is really the way to go, I'm open for new suggestions):

the user types a password,
the application generates a public information (e.g. a hash or a public key) from this password using a one-way function,
this public information is then converted to a human-meaningful identifier using systems like tripphrases, proquint or identicons.

Examples:
"MyPassword" --(CRC32)--> "7d586a02" --(proquint)--> "hotig-muhig-donig-fubag"
"MyPassword" --(MD5)--> "48503dfd58720bd5ff35c102065a52d7" --(tripphrase)--> "interleave my calcifugous ghost"

The problem with using hashes as identifiers in a p2p system (i.e. with zero trust and no central source of truth) is that nothing prevents some user to write messages using whichever identifier they want while pretending that they obtained this identifier by hashing their password locally, like the protocol says. Thus, what I want is a way to prove the ownership of an identity without revealing the password. I can only think of one way to solve this problem:

Alice types a password,
the application derives a private/public key pair from this password,
the public key is used to generate the human-meaningful identifier of Alice,
Bob wants to verify the identity of Alice:

Bob sends a challenge (i.e. a random number) to Alice,
Alice encrypts the random number with her private key,
Alice sends the result back to Bob,
Bob decrypts the result using the public key of Alice (it can be obtained by converting Alice's identifier back to a public key),
if the decrypted number is the same than the one previously sent, then Alice indeed owns the password, otherwise Alice is lying on her identity.

But I would like to know if there is a simpler protocol than that to solve my problem. Preferably, I would like to avoid public-key cryptography altogether. As I'm doing this project just for fun, I don't really care about the following points:

the strength of the passwords,
if two users use the same password and hence get the same identifier,
if other people know the hash or associated public key of a password, which clearly gives out information on the secret password, so a zero-knowledge proof is not necessary.

Any idea?

Thank you for your help.

You can use a standard signature scheme. The user will type in a password, and receive their private key and associated username. Then, to post a message, they sign the message and broadcast the message, username, and signature. Other users will convert the username to a public key and then verify the signature.

This is the same way that bitcoin handles the identity crisis: tying messages to keys instead of real people.


Simplified Fiat-Shamir example generates wrong output I am trying to implement the Fiat-Shamir identification protocol, however the end results always fail to match. I am using algorithm's description from here.

Preparation:

Select 2 prime integers and their product:

n = 19 * 23 = 437

Select s coprime to n:

s = 242

Compute v:

v = (s^2) % n = 6

Now the round:

Select random r between 1 and n - 1:

r = 410

Calculate x:

x = (r^2) % n = 292

Choose e either 0 or 1:

e = 1

Calculate y:

y = (r * s^e) % n = 21

Now if y^2 equals (x * v^e) % n then it's accepted. However in my case

y^2 = 441
(x * v^e) % n = 4

Why don't these numbers match? What am I doing wrong here?

The problem is one of notation for modular arithmetic, at the point of the question reading

  if y^2 equals (x * v^e) % n then..

Likely the textbook is about

  if $y^2\equiv x\cdot v^e\pmod n$ then..

By definition of $a\equiv b\pmod n$, that holds if and only if $n$ divides $a-b$ (or equivalently: $|b-a|$ is a multiple of $n$). In the question, 437 divides 441-4, thus $y^2\equiv x\cdot v^e\pmod n$ holds.

Sometime, $a\equiv b\pmod n$ is written as $a=b\pmod n$, but rigorously the later means that $a$ is the set of solutions to the former. $a\equiv b\mod n$ or $a=b\mod n$ are also used, but the later is best avoided, because it is dangerously close to $a=b\bmod n$, to be read as $a=(b\bmod n)$ and thus rigorously meaning $0\le a<n$ and $|b-a|$ is a multiple of $n$. However, only a strict Vulcan would assume $0\le y^2<n$ when seeing $y^2=b\bmod n$.

Note: On this site, $y^2\equiv x\cdot v^e\pmod n$ can be written as $y^2\equiv x\cdot v^e\pmod n$. A right-click on a rendered formula then Show Math As TeX Commands will reveal the TEX code used. I often use this TEX cheat sheet.


what is the difference between proofs and arguments of knowledge? What is the difference between proofs and arguments of knowledge in the context of zero-knowledge?

I have read this sentence in this ePrint:

  It is useful to distinguish between zero-knowledge proofs, with
  statistical soundness, and zero-knowledge arguments with computational
  soundness. In general proofs can only  have  computational
  zero-knowledge,  while  arguments  may  have  perfect zero-knowledge.

It is also indicated in this article that:

  Zero-knowledge protocols come in several flavors, depending on how one formulates the two security conditions: (1) the zero-knowledge condition, which says that the verifier “learns nothing” other than the fact the assertion being proven is true, and (2) the soundness conditions, which says that the prover cannot convince the verifier of a false assertion. In statistical zero knowledge, the zero-knowledge condition holds regardless of the computational resources the verifier invests into trying to learn something from the inter-action. In computational zero knowledge, we only require that a probabilistic polynomial-time verifier learn nothing from the interaction.1 Similarly, for soundness, we have statistical soundness, a.k.a. proof systems, where even a computationally unbounded prover cannot convince the verifier of a false statement (except with negligible probability), and computational soundness, a.k.a. argument systems [BCC], where we only require that a polynomial-time prover cannot convince the verifier of a false statement.

Which I assume that a zero knowledge argument is just a zero knowledge proof that has computational soundness rather than statistical soundness.

Am I right?

Yes, you are right. In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover. Arguments are thus often called "computationally sound proofs".


Is there an authenticated encryption scheme where the recipient can attribute the message to a single sender? With a standard authenticated encryption scheme (or MAC), Alice and Bob share a symmetric key.  When Alice sends something to Bob, Bob can check that it is authentic.  At that point, Bob can deduce that the message must have been sent by someone who knows the key, i.e., it must have been sent by Alice or Bob.

How can Bob verify that the message was sent by Alice?  (not by Alice or Bob)

In particular, standard authenticated encryption only proves that the message come from someone in a trusted group (the group of people who know the symmetric key).  I'd like a scheme where the recipient can verify which individual sent it.

In other words, I'd like to get all the current guarantees of AE, plus ability to authenticate which entity sent the message (only one particular entity must have been able to authenticate the document, unless their key is compromised).  It's OK if it needs to use public-key technology.  Ideally, such a mode would be single pass (like OCB), but hopefully not patent encumbered or GPL tainted (LGPL or weaker is ok).  Getting authenticated associated data would be a bonus.

Or maybe I just need to encrypt (using a plain randomized mode, provides confidentiality only) then sign the ciphertext+associated data (which provides integrity, authentication and knowledge of the sender)?

To get non-repudiation, you must have a "proof" which can be used against the signer himself. Symmetric cryptography, by itself, will not help you there, because a cryptographic proof can only come from some "secret" which is under exclusive control of the signer, and the symmetric model assumes that there is a shared secret between two entities. The concept of non-repudiation makes sense if the signer wants to default on his signature, and the receiver of the signature sues him and wants to convince a third party (the judge) that the signature is genuine and binding. This is a scenario where both parties are adversaries with each other. In that context, there is very little provability that can be extracted from a secret value that they both know.

There are systems which provide non-repudiation and still use symmetric cryptography. That's what happens (happened ?) in payment smart cards: the cards "signs" the transaction by computing a MAC over it, with symmetric cryptography; the MAC key is user-specific, but known to both the card and the bank. Such transactions are binding in a legal way (so there is "non-repudiation") because the Law says so; but the system works in practice because it is not easy to circumvent. In particular, the bank is assumed to be honest and not to frame its customers; this assumption is not free, because it comes at the price of very heavy controls and auditing systems on the bank side.

One cornerstone of non-repudiation, as existing laws on digital signatures put it, is the notion of exclusive control. What the signer uses to sign must be proven to be usable by the signer only. In the banking smart card example, this is obtained through several mechanisms, including the inherent robustness of the card, the PIN code handling, and the expensive verifications and safeguards which are performed on the bank side of the transaction. These verifications can be made cheaper if the whole system uses asymmetric cryptography, because maintaining exclusive control of an asymmetric private key is easier than doing the same with a shared secret. For instance, in an asymmetric system, you can arrange for the private key never to leave the device on which it was generated, which makes device initialization easier, especially when already deployed in the field.

(Note that "easier" does not mean "easy".)

Anyway, non-repudiation is about people or at least legal entities; cryptography sees keys. Binding entities to key control is a complex business; one way to do it is PKI. People involved in PKI know that PKI is 5% asymmetric cryptography, 95% procedures. Getting the crypto right is the easy part. Asymmetric cryptography is not sufficient to achieve non-repudiation; and it is not strictly necessary either, but, in the current legal context, you will find that obtaining non-repudiation is even harder if your toolbox does not include asymmetric cryptography.

To say it differently, you can get non-repudiation out of an AE mode, under the same conditions that you would get non-repudiation out of a MAC. This is doable, in fact it has been done, but in a heavyweight framework of procedures, laws, controls, and a lot of money thrown at it. Banks did it with symmetric cryptography because when such systems began to be deployed (in the late 1980s in France), cards which could do asymmetric cryptography were very expensive.


Ease of breaking MD constructions If hashing algorithms such as MD5 or SHA1 both use Merkle-Damgard constructions at their cores, why is it so easy to break them, and yet so much harder to break SHA3, which is also MDC based?

MD5 and SHA-1 have been broken (from a collision-resistance perspective) due to weaknesses of their compression function, not because they are Merkle–Damgård based.

SHA-2 hashes (SHA-256, SHA-512..) are Merkle–Damgård based, but use more compute-intensive compression functions, and are so far unbroken.

SHA-3 is not Merkle–Damgård based, it uses the sponge construction. One advantage is that the result does not reveal the full state, and that makes the construction immune to the length-extension attack.


What data is saved in RSA private key? What data is saved in RSA private key in openssl? How to view it?

Wikpedia says these variables are saved.

You can print the data with (change PEM to DER if required):

openssl rsa -in Alice.key -text -inform PEM -noout

The following data is stored:

Modulus ($n = pq$)
Public exponent ($e$)
Private exponent ($d = e^{-1} \pmod{\phi{(n)}}$)
First prime ($p$)
Second prime ($q$)
First exponent, used for Chinese remainder theorem ($d_P = d \pmod{p - 1}$)
Second exponent, used for CRT ($d_Q = d \pmod{q - 1}$)
Coefficient, used for CRT ($q_{\mathrm{inv}} = q^{-1} \pmod{p}$)


Difference between SHA 512, SHA 512 Half, SHA 256 I was trying to create a python wrapper for RIPPLE crypto currency, and i ran into SHA 512 half which i have no idea or reverse googled it to no avail. Can someone help me understand the difference. Currently i am assuming its any 256 bits of SHA512.
RIPPLE Address Encoding

SHA-256 is a function with up to $2^{64}$ bits of input, which are broken into 512-bit blocks, and with a 256-bit output.  It is conjectured to be collision-, preimage-, and second-preimage resistant at (resp.) 128-, 256-, and 256-bit security levels, but it has the unfortunate property that given $\operatorname{SHA-256}(m)$ but not $m$, it is relatively easy to compute $\operatorname{SHA-256}(m \mathbin\Vert p \mathbin\Vert m')$ for an arbitrary suffix $m'$, where $p$ depends only on the length of $m$.

SHA-512 is a function with up to $2^{128}$ bits of input, which are broken into 1024-bit blocks, and with a 512-bit output.  It is conjectured to be collision-, preimage-, and second-preimage resistant at (resp.) 256-, 512-, and 512-bit security levels, but it has the unfortunate property that given $\operatorname{SHA-512}(m)$ but not $m$, it is relatively easy to compute $\operatorname{SHA-512}(m \mathbin\Vert p \mathbin\Vert m')$ for an arbitrary suffix $m'$, where $p$ depends only on the length of $m$.

‘SHA-512half’ is probably SHA-512 truncated to 256 bits.  Thus it takes up to $2^{128}$ bits of input, broken into 512-bit blocks, and yields a 256-bit output.  Like SHA-256, it is conjectured to be collision-, preimage-, and second-preimage resistant at (resp.) 128-, 256-, and 256-bit security levels.  Unlike SHA-256 or SHA-512, to compute $\operatorname{SHA-512half}(m \mathbin\Vert m')$ for any $m'$ (whether with the padding $p$ or not) given only $\operatorname{SHA-512half}(m)$ and not $m$, it is conjectured to cost at least an expected $2^{255}$ SHA-512 computations.

The functions SHA-256 and SHA-512 resemble independent uniform random choices of function, except for the length extension property, whereas SHA-512 and SHA-512half are obviously not independent since SHA-512half is just half the output of SHA-512 on the same input.  SHA-512/256 is like SHA-512half, except it it uses different initialization vectors and thus resembles another independent uniform random choice of function.


Is Type I lattice trapdoor hard to find even given oracle access to compute inverse of trapdoor function? Consider the Type I lattice trapdoor in [GPV08]: https://eprint.iacr.org/2007/432.pdf

Suppose a PPT adversary is given the LWE trapdoor function in the picture:

$g_{A^\top} (s,e) = A^\top s + e = b (\text{mod } q)$

Let T be a type 1 trapdoor for A.

Now a PPT adversary is given an oracle that does the following:
On input b', the oracle answers with a pair of (s',e') that satisfy $A^\top s' + e' = b' (\text{mod } q)$.

Can a PPT adversary find a trapdoor T by querying this oracle for polynomially many times?

Picture is from lecture notes: https://fangsong.info/teaching/s16_uw_pqc/qic891_pqc_lec3.pdf

If the adversary is a classical algorithm, then the answer  to your question is not known. But if the adversary is a quantum algorithm that can query the oracle in superposition, then the answer is yes: by making queries to the oracle on certain (efficiently produceable) quantum states, it can recover a Type-I trapdoor for $A$.

For classical algorithms, the difficulty is that we do not know how to generate a valid output of $g$ (that the oracle is obliged to succeed on) except by choosing $s,e$ ourselves and feeding them through $g$. But then the oracle’s answer is useless to us, because we already know the answer before querying it.

For quantum algorithms the situation is different. We can prepare a certain superposition over “all” valid $s,e$, feed it through $g$ to get a superposition over outputs, and invoke the oracle to get back $s,e$. Critically, this allows us to uncompute (or “forget”) our original choices, leaving us with a useful quantum state. Specifically, by taking its quantum Fourier transform we get a superposition over short vectors $x$ such that $Ax=0$. By measuring the state we get such an $x$, and can repeat to accumulate many linearly independent ones, yielding a Type-1 trapdoor.

The difficulty in the classical setting, and the quantum strategy for dealing with it, are from Regev’s original paper on LWE. The connection to SIS/LWE was first described in the GPV paper.


How to figure out DES mode used given plaintext and ciphertext? In DES, I'm given the following exercise.

  - How can I find out which part of the plaintext each ciphertext message corresponds to, and which mode they were each encrypted with?

Let's assume that we're talking about the following classic modes for block ciphers (although there are certainly more): ECB, CBC, CFB, OFB and CTR.

First of all the second message is way too long to fit into the ciphertext, so we can safely discard that possibility.

Then we can look at the size of the plaintext and ciphertext. The plaintext message is 14 character, which are generally encoded to 14 bytes. The size of the three ciphertext are 14, 16 and 14 bytes.

Now ECB and CBC are generally using padding, so that the padded plaintext and the ciphertext are Y times the block size. The other modes are streaming modes so they don't require padding, and the size of the messages are identical to the plaintext size.

So with that in mind, ciphertext one is using streaming (CFB, OFB or CTR), ciphertext two is using ECB or CBC and ciphertext 3 is using streaming again.

Can we find out more? Sure, message 1 and 3 are clearly starting with the same ciphertext.  Now for CTR only the first half of the IV was used, so it is less likely that will correspond with either of the two ciphertext. That would only be the case if the second half of the IV was set to all zeros (the initial counter value is identical to the IV) for the other modes.

That leaves CFB and OFB, and if we look at those schemes we see that the calculation of the first ciphertext is exactly identical to each other. Only after that there are differences, because one uses ciphertext feedback, while the other uses output feedback.

Can we say much more? I don't think so. We lack any information to distinguish ECB from CBC or CFB from OFB (other than knowing that if one ciphertext uses one, the other one must have been generated using the other).

If there are ways of using the blocks of one cipher to determine the precise mode of another then I don't see it. OFB and CFB start with encrypting the IV, and CTR and CBC don't do that.

Once the calculations end up with a different input to the block cipher and are permuted, we cannot learn anything from them unless we know the permutation - i.e. the key. We can just tell the blocks apart.


Practical examples of Threshold Secret Sharing? Threshold secret sharing is pretty cool, but unlike, say, public-key cryptography, I haven't really heard about it "in the wild". It appears to be confined to discussions of theoretical scenarios, as I have not found any real-world software that claims to use it "in anger".

So, are there practical examples of threshold secret sharing in commercial, or at least publicly-available, systems?

I worked on a secure document management project 20 years ago which used secret sharing. It is widely used in financial networks. Actual use cases with public details that are easily accessible include:

Threshold key sharing is used in Hardware Security Modules, for example to unlock the administrator account. In the Amazon CloudHSM documentation, this is explained in detail:
Amazon CloudHSM: About M of N
Hashicorp's Vault uses Shamir's Secret Sharing during the "unsealing" process as explained here: (https://www.vaultproject.io/docs/concepts/seal.html) This enables reading and decrypting secrets from the storage backend.


Question about SHA-2 (and potentially similar hashing algorithms) I have been educating myself recently about the SHA-2 hashing algorithm, and in the midst of this pursuit, I've encountered a question:

This algorithm uses a set of constant hexadecimal values, derived from the cube root of prime numbers, as a starting point for the process. Because these values can be known to anyone, does this not open some level of vulnerability to the hashed values? Would it not be better to use a set of less predictable values?

I don't know a great deal about cryptography, so forgive me if this question is silly in some way I do not understand, but I am very curious about the answer.

EDIT: I'm not asking why they are constant. I understand how hashing works and what it is used for. I am asking if the security of the algorithm would be increased if constant but unknowable (to the outside) values were used instead of the array of constants currently used.

Would it not be better to use a set of less predictable values?

Actually, there aren't any "unpredictable values".

SHA-2 is a hash function (actually, it's a family of 6 hash functions; we'll ignore that point for now); a hash function is designed so that anyone can compute it.

One use of a hash function is during signature generation and verification; typically, the signer takes the message, and hashes it, and then applies the signature operation to the hash.  Then, the verifier takes the message, hashes it, and then verifies the hash against the signature.  If the verifier could not compute this hash, he could not verify that the signature corresponded to this message.

Because of this, the entire specification of SHA-2 must be made public, so that the verifier (and anyone else) can compute it.  That is, any internal table values must also be public, because they are needed to compute the hash function.

Because we're going to tell everyone what the values are, they aren't, in any sense, unpredictable.


How do Quadratic Residues work and how do they relate to Diffie Hellman? Can someone explain Quadratic residues to me in english? I keep reading forums with all the math symbols and it's hard to follow. And how are they incorporated in Diffie-Hellman? Is there a difference in using them vs cubic residues?

Can someone explain Quadratic residues to me in english?

A value $x$ is a Quadratic residue modulo $p$ if there exists a value $t$ for which $t^2 \bmod p = x$.

That is, we take $t$, square it (that's the Quadratic part), and then take it modulo $p$ (that's the residue part, that is, the part that's left over after removing all the multiples of $p$), and that gives us the value $x$.  If such a process can give us $x$, we say that $x$ is a Quadratic Residue.

For example, $2$ is Quadratic Residue modulo $7$ (because if we start with $3$, square it, and then take that result modulo $7$, we end up with $2$); however $3$ is not (can be verified by computing $1^2 \bmod 7, 2^2 \bmod 7, 3^2 \bmod 7, …, 6^2 \bmod 7$)

Also, in this answer, I have been careful to always say "Quadratic Residue modulo $p$"; obviously, the same value $x$ can be a Quadratic Residue modulo some prime $p$ and not modulo another prime $q$.  Normally, you'll see the statement "$x" is a Quadratic Residue"; they mean modulo something, but that something is implicit (as they are working in a specific group, which should be obvious from context).

Important facts:

If $p$ is a prime greater than 2, then some of the values between $1$ and $p-1$ will be Quadratic Residues modulo $p$, and some will not be.  In fact, precisely half of those values will be and half will not.
If $p$ is a prime, then $a \times b \bmod p$ will be a Quadratic Residue modulo $p$ if either both $a$ and $b$ are Quadratic Residues, or both are not.
If $p$ is a prime, it turns out to be simple to check where $x$ is a Quadratic Residue mod $p$.

  And how are they incorporated in Diffie-Hellman?

Mostly, it's not.  If the Diffie-Hellman generator $g$ is not a Quadratic Residue modulo $p$, then given $g^a \bmod p$, we can determine whether $a$ is even or odd; given $g^a \bmod p, g^b \bmod p$, we can determine whether $g^{ab} \bmod p$ is a Quadratic Residue modulo $p$ or not.  On the other hand, we generally perform Diffie-Hellman using a generate that generates a large prime subgroup; such a generator will always be a Quadratic Residue modulo $p$, and so examining the values $g^a \bmod p, g^b \bmod p$ doesn't tell us anything.

  Is there a difference in using them vs cubic residues?

If $p$ is a prime where $p \equiv 2 \bmod 3$, then cubic residues modulo $p$ are uninteresting; all values $x$ are Cubic Residues modulo $p$.

If $p$ is a prime with $p \equiv 1 \bmod 3$, then a third of the values between $1$ and $p-1$ will be cubic residues modulo $p$, and two thirds will notbe.  On the other hand, the same Diffie-Hellman logic applies; if $g$ generates a large prime subgroup, then $g$ will be a cubic residue modulo $p$, and so will $g^a \bmod p, g^b \bmod p, g^{ab} \bmod p$ as well...


Does there exist a compression function (from four 32-bit words to one 32-bit word) that always detects any modification of a single word? I need a compression function $F$ that uses only bitwise operations (AND, NOT, OR, XOR, shifts, rotations) and outputs one 32-bit word $W$ from four 32-bit words $w_1 \mathbin\Vert w_2 \mathbin\Vert w_3 \mathbin\Vert w_4$. The function is required to satisfy one special property: if two 128-bit blocks

$$\begin{array}{l}
B_1 = w_{1.1} \mathbin\Vert w_{1.2} \mathbin\Vert w_{1.3} \mathbin\Vert w_{1.4},\\
B_2 = w_{2.1} \mathbin\Vert w_{2.2} \mathbin\Vert w_{2.3} \mathbin\Vert w_{2.4}
\end{array}$$

differ only in one word (that is, there exists only one number $x$ such that $w_{1.x} \neq w_{2.x}$), then $$F(B_1) \neq F(B_2).$$

But if we have a set $S$ of $y$ different 128-bit blocks

$$S = \{B_1, B_2, \ldots, B_{y-1}, B_y\}$$

such that for any pair $(B_m, B_n)$ of elements, $B_m$ differs from $B_n$ in two or more words, then the probability of
$F(B_m) = F(B_n)$ is the same as for any standard cryptographic compression function (that outputs one 32-bit word from four 32-bit words).

Is it possible to construct such a function? If yes, can anyone give an example of a function that fits the above description?

EDIT

The connection to cryptography is that some attacks on EnRUPT and XXTEA use the fact that the round function does not satisfy the property described above:

  The round function of EnRUPT is not bijective for the given key word

and

  XXTEA’s $F$ is not bijective for either neighbor

I may be missing some subtlety intended by the problem-setter, but the simple answer that satisfies the stated conditions, or damn near, is to just xor the words:

$$F = w_1 \oplus w_2 \oplus w_3 \oplus w_4$$

If we model any change to $w_i$ as xoring with a nonzero error term $e_i$, since xor is linear in $GF(2^n)$

$$F' = (w_1\oplus e_1)\oplus (w_2\oplus e_2)\oplus (w_3\oplus e_3)\oplus (w_4\oplus e_4)
\\
= F \oplus (e_1\oplus e_2\oplus e_3\oplus e_4)$$

If only one of $e_i$ is nonzero, the net error is nonzero. If more than one of $e_i$ is nonzero, independently at random, the probability that the net error is zero is almost $2^{-32}$ -- excluding zero from some of the choices throws it off slightly, but I don't remember enough probability to compute exactly how.


Can you fake messages from recorded message-history? Lets assume Eve has a lot of PGP conversation with Alice and records all those messages. Bob is also regularly communicating with PGP with Alice.

If Bob doesn't care about not having a signature from Alice, could Eve send any of those recorded messages unchanged but without signature to Bob pretending it came from Alice?

If Bob does NOT care to check signatures (as in the question), Eve can send ANY message she wants to Bob pretending to be Alice, including but not limited to messages Eve got from Alice; all Eve needs is Bob's public key (which, as the name implies, is assumed public knowledge thus known to Eve) and straight use of PGP.

Therefore the right question is: Can Eve reuse signatures she got from Alice, so that Bob concludes that a message sent by Eve is from Alice, even though Bob DOES care to check signatures?

The answer is YES, if Eve sends to Bob a message with exactly the content the message had when signed by Alice. So if Alice sent to Eve a message like "Let's meet at the bar at 11 pm", Eve can impersonate Alice and send that same message to Bob, who might conclude he has an invitation from Alice, when that invitation really was for Eve, perhaps another bar than the one he expects, and/or a past day. PGP gives insurance to Bob that the message was signed by Alice, and gives him a chance to detect a change of day (for PGP signatures include a "signature time stamp"). PGP does NOT give insurance to Bob that the message was for him.

Note: having an history of many recorded messages only helps Eve by giving her a wider choice of messages she can send to Bob pretending they came from Alice; Eve can not cut and paste fragments from past messages to compose a new one.


XTS mode of operation and authentication I'm wondering if XTS is used (Random Access is needed) what the best solution for authentication is. If I wouldn't need random access, I would take AES-GCM or AES-CBC-HMAC but random access is a must.

What mode of operation would be prefered for random access with authentication?

I assume you mean "random access" by "decrypting arbitrary part of ciphertext, operate on it, and securely encrypting it again".

The XTS mode is designed as a "Full-Disk Encryption" mode, which means it does not have the slightest concern with authentication.

From practical perspective, I recommend having a keyed tuple or tree hashing mode for authentication. Some of which are specified in NIST SP 800-185. You may also want to check out Sakura tree-hashing encoding scheme.

Update

Tuple hashing is a hashing scheme, where a sequence of bit/octet strings is hashed in such way, that guarantees the uniqueness of the output, even when otherwise their simple concatenation would have resulted in some ambiguity. For example, hashing the concatenation of "ab" + "c" would be the same as "a" + "bc", but the tuple hashing of $(\text{"ab"}, \text{"c"})$ would be different from $(\text{"a"}, \text{"bc"})$.

Tuple hashing is usually sequential, but it doesn't always have to be.

Tree hashing is an efficiently method for hashing long messages. Example include Merkle tree. During the SHA-3 competition, the Keccak team proposed the Sakura tree-hashing encoding scheme, to solve the shortcomings of various ad-hoc tree-hashing encodings.

I added the "keyed" in the previous text to mean that they're supposed to be used as authentication tag.


Non-malleability of One Time Pad Encryption Can anyone explain to me what the following means in relation to one time pad security?  It's from the book 'Serious Cryptography: A Practical Introduction' and my logic knowledge seems to have lost me here so I'm struggling :-

Given a ciphertext $C_1 = E(K, P_1)$, it should be impossible to create another ciphertext, $C_2$, whose corresponding plaintext, $P_2$, is related to $P_1$ in a meaningful way (for example, to create a $P_2$ that is equal to $P_1 \oplus 1$ or to $P_1 \oplus X$ for some known value $X$). Surprisingly, the one-time pad is malleable: given a ciphertext $C_1 = P_1 ⊕ K$, you can define $C_2 = C_1 \oplus 1$, which is a valid ciphertext of $P_2 = P_1 ⊕ 1$ under the same key $K$. Oops, so much for our perfect cipher.

The Problem

The One-Time Pad offers perfect secrecy. However, it does not protect the integrity or authenticity of the message - An adversary can flip bits of the ciphertext, and the receiver will have no way of detecting the manipulation.

Consider the case where a single bit is sent encrypted with a One-Time Pad, used to indicate a "yes/no" value as to whether or not Alice wants to have lunch with Bob. If Mallory intercepts the message $C$ and computes $C \oplus 1$ and then sends that value to Bob instead, Bob will receive the opposite of Alice's intended message - and he will have no way of knowing that it has been tampered with.

The solution

Use a MAC to ensure the integrity and authenticity of the message.


Is this ECDHE approach secure? First of all sorry if this question could be trivial, but I did some researches and it seems to me that this is a standard approach, but I want to be really sure.

I'm developing a signed/encrypted communication block channel. And, to encrypt/sign it, I chose the ECC.

Now, in order to send a message, I will do this

Download the server's public key
Generate an ECC key on the client
Create the shared secret between the server's public and the client's private keys
Calculate the hash of the shared secret (e.g. SHA-384)
Divide the hash in two parts; one will be the communication key (e.g. 32 bytes for AES-256), the other the IV (if AES, 16 bytes)
Encrypt the message with the appropriate algorithm and symmetric key
Sign the message with the client's private key
Send the client's public key, the encrypted message and the signature

Now, I have three questions about this:

Is this approach secure or there is some naive issue?
Is it better to sign the plaintext message or the ciphertext message? I'd sign the plaintext (so the server can verify if the message is correctly transmitted), but this would give the attacker a way to understand if the attack was successful
What is the suggested ecc key size for this? If I calculate the SHA-384 of the shared secret, is the same ecc key size (so using curve P-384) a good choice? Should I use the biggest key possible (P-521)? Is even a smaller one enough (P-192)?

Is this approach secure or there is some naive issue?

There are some issues, see below. Most naive ones at the top.

You need to trust the public keys to create an authenticated connection. I don't see any part of the protocol where you verify public keys.
Instead of signing "the message" you need to sign the key agreement parameters. If you just sign the message you're open to man-in-the-middle attacks. Once you've established session keys you just need authentication tags. This should also answer question #2.
Depending on the algorithm you may need an encryption key and a MAC key. Alternatively you could use an authenticated mode of encryption.
It's usually best to use separate client & server keys, assuming that you require two-way communication.
You're directly using a hash as Key Derivation Function (or, as TLS calls it, the PRF). Although that may not directly pose problems, it's probably better to use a true KDF, e.g. HKDF.

  What is the suggested ecc key size for this? If I calculate the SHA-384 of the shared secret, is the same ecc key size (so using curve P-384) a good choice? Should I use the biggest key possible (P-521)? Is even a smaller one enough (P-192)?

Using a hash of 384 bits and P-384 is nicely in balance. You can check the NIST recommendations at keylength.com, second table after >> 2030. The only thing currently worry about would be quantum computing as it could attack ECC cryptosystems in general.

Nitpicks:

You cannot generate an ECC key, you can generate a public/private key pair;
I don't see where you generate key pair for the server;

Why not take a look at the draft TLS v1.3. They specifically rewrite TLS there to make sure they solve all the loose ends of TLS v1.2. That should give a good insight in all the pitfalls of creating a transport protocol.

Of course for production purposes using TLS v1.2 is a good idea, don't roll your own.


Are there actual consequences of padding oracle attacks? I am writing a program that encrypts data in Python and heard about padding oracle attacks, but I think they are overrated (I mean, what are the real-world uses?) even for the old implementations that are vulnerable (the ones that tell if padding is right or wrong like SSLv3).
Because:

If all I need are two ciphertexts $c(n-1)$, $c(n)$ which are the last two encrypted messages blocks, and a server to tell me if the padding of decrypted $c(n)$is correct or whatever, doesn't that mean that the server just decrypts whatever you send to it (I mean, just send the whole encrypted message as you received it and read the output). I mean, this is the server bug that it doesn't take a key in the first place and check if it's correct.
Let's assume that all we have to do is send those two cipher messages to know and decrypt the last block (the padding block). This only works since the padding plaintext is known or at least not random or whatever reason.

But what about, say, c2 and c3 which are in the middle of the whole message? We know c3 and c2, but we don't know and we will never know either p3 or p2 (plaintext), nor the intermediate state IS3; i.e. we can't XOR c2 with is3 to obtain p3, so this attack I think only allow us to decrypt the padding block with the only new thing we actually knew is an intermediate state of padding block.
I am asking to know if this attack is just a one with no real-world implications and no real data decryption capabilities (actual data).

I mean this is the server bug that it doesn't take a key in the first place and check if it's correct :)

What do you mean with that? The key must be the right one, and the padding oracle attacks actually change the ciphertext encrypted with that key on the other side to perform the attack.

but what about say c2, c3 which are in the middle of whole message, we know c3 and c2 but we dont know and we will never know either p3(plaintext of course) nor intermediate state IS3

No, a padding oracle attack is able to completely decrypt a message. This is precisely because the XOR influences the next block.
Note that padding oracle attacks are just one form of plaintext oracle attack. For instance, you can also perform plaintext oracle attacks on XML-enc, even without using the padding itself.

I am asking to know if this attack is just a one with no real world implications and no real data decryption capabilities(actual data) .

Yes, that's utterly and completely wrong. A padding oracle attack can decrypt the whole message using 128 tries per byte, and other plaintext oracles can actually be even more effective.
Besides that, having the receiving end accept a changed plaintext is possibly as dangerous as loosing confidentiality. For that reason you should use authenticated encryption - or rather a protocol that utilizes authenticated encryption instead of unauthenticated CBC.


How can a random salt for a hash function work in practice? I understand the theory behind the use salts in hash functions, but when I see it  implemented, the implementations always generate the salt on the fly and the salt appears to be different for every hash.

When implementing a salt for users signing into a website, doesn't the salt need to be the same at account creation as the salt used when the user wants to log in?
In implementation, wouldn't the salt be the same every time?
I understand that the salt may be different from user to user (in my example), but when user A signs in on Monday, and again on Friday, wouldn't the salt need to be the same for both those times?

Usually, when the user registers, you will generate a random value to become the salt. Then, in the user database, you store the user's name, salt, and hash generated using the password and salt (and whatever else is relevant for a user table).

Note that doing it this way allows each user to have a unique salt. Each user having a unique salt greatly increases attack difficulty. An attacker is forced to do a brute-force attack per user instead of precomputing per-password-scheme rainbow tables (no salts) or a per-database rainbow table (a system-wide salt). It is still your responsibility to make sure the brute force attack is actually slow enough to be costly to an attacker in these days of massively parallel GPU hash implementations.

Ideally, an attacker would not even be able to see the salt on the database, but it does not have to be private if worse comes to worse.


Can OTP still be broken if there are several messages being sent with only a slight variation in a password? If an attacker were able to get a hold of 2 encrypted messages that were both encrypted in a one time pad with a password that were each similar but had one change in the first character, could it still be cracked?
Let's say my first set of data was encrypted with "1password" and my second set of data was encrypted with "2password". Could it still be easily cracked?

What do you mean 'a one time pad with a password'?  One time pads don't take passwords, they take samples of truly random data as long as the message.

If what you're doing is taking the password, repeating it N times, and using that as if it were a random one-time pad, well, that can usually be broken even if you don't send a second message.

If what you're doing is you do have a truly random pad (which you are calling the password; however if you message is 10,000 characters long, so is your 'password'), and if you send a second message with a slight modification of the pad, then yes, it can be broken; the standard attacks against a 'two-time-pad' will work well (even if the pads are slightly different).

Bottom line: if you're relying on a 'one time pad', then it is mandatory that the pad be random, as long as the message, and not related to any other pad you may use.  If you violate this, the security proof for one time pad does not apply (and you are usually, in fact, insecure).


Quantum key distribution simulation I'm looking for a simulation of the Quantum Key Distribution protocol.  Does anyone here have one that they could recommend?

There are several kinds of quantum key distribution (QKD) protocols as of today. Are you looking for a particular one?
The best-known QKD protocol goes by the name BB84 after its inventors Bennett and Brassard and the year in which they presented their work. Searching on the Internet, I found this link http://fredhenle.net/bb84/demo.php with a simulation that looks fairly nice and introductory.
As such, programming (at least) an ideal version of the BB84 protocol is not difficult. By ideal, I mean that Alice's source, Bob's receiver are perfect, and the channel is not only without Eve but also does not absorb or distort the information carriers (in case you do not have any background in quantum physics, you could also read section 2 of this paper http://arxiv.org/abs/1206.7019 that serves to explain the operation of BB84 to even non-scientists).
Otherwise, with the following steps you can simulate BB84 on your own:

Generate two random bit-sequences of length 2N and N for Alice and Bob, respectively. At the end of the protocol, Alice and Bob would share a symmetric and secret key of length n $\approx$ N/2 distilled from these bit sequences. The next 3 steps can be assumed to operate in a loop from 1 to N.

Alice uses 2 bits at a time to generate one of four quantum states denoted by Q and having the values H, V, D, A randomly (use the mapping H=00, V=01, D=10, A=11 for the BB84 protocol).

A state prepared by Alice arrives in Bob as it is, i.e., without being subjected to loss or noise.

Bob uses his bits to choose the basis B randomly, i.e., B=0=HV basis or B=1=DA basis with equal probability. Now comes the only piece of logic you need to understand. In a given instance, assume Bob's chosen basis shares a non-empty string with Alice's chosen state, e.g., Q=D and B=DA (this technically means they used the same basis). In such an instance, Bob's outcome, or the bit obtained by him due to the measurement on the quantum state, is deterministic and equal to the 2nd bit of Alice (which would be 1 in this case). On the other hand, if the basis does not match, e.g., Q=V and B=DA again, Bob's outcome could be either 0 or 1.

After Bob has finished measuring all N states, he publicly reveals his basis choice but not the outcomes he obtained. Alice applies the same logic as in the previous step -- she examines all N instances to locate those where her basis matched with that of Bob. She then informs Bob to keep these outcomes only in such instances while choosing the corresponding bits from her bit-sequence. This is the secret key.


Is there an efficient way to hide the encrypted plaintext length with a block cipher? In block cipher modes of operation for encryption on input of a plaintext of $N$ blocks (We assume that the input size is always a multiple of the blockcipher mode: $N·16$ bytes) the size of the ciphertext is $N+1$, where the extra block is the IV.

Is there an efficient way to have fixed (parametrizable) larger length output on variable length input, to hide the plaintext size?

For example, for a short plaintext of $16$ or $20$ bytes I want to generate a larger ciphertext like 128 bytes, so an attacker can't learn the plaintext size from the ciphertext size.

The only way I can think of is just to produce pseudo-random pad to increase the plaintext message to equal the size of the ciphertext you want to output.

Counter mode (CTR mode) seems like it will do what you want.  The length of the output is equal to the length of the input, plus the length of the IV.  If this is not what you want, you'll need to explain your question/requirements more clearly.

In practice, I recommend you use an authenticated-encryption mode, such as EAX or GCM etc.


TLS with NULL chipersuite In the case of using a cipher suite with all algorithms NULL  e.g.: TLS_NULL_WITH_NULL_NULL the protection against replay, swapping and filtering is guaranteed?
(I am talking about message protection, not handshake's one)

Because I have seen that the MAC uses a sequence number, so maybe this is used against replay. If I do not calculate the MAC our TLS fragments are vulnerable to replay, swapping and filtering?
Or the fact that we are using a reliable transmission protocol avoid that ( and in this case what's the point of using a sequence number in the calculation of MAC)?

TLS_NULL_WITH_NULL_NULL the protection against replay, swapping and
  filtering is guaranteed?

No. The NULL-cipher suite makes no guarantees at all and it is explicitely forbidden in the RFC that two parties negotiate this cipher suite, the only reason for its existence is to run the handshake protocol.

  Because I have seen that the MAC uses a sequence number, so maybe this
  is used against replay.

The TLS record layer indeed does use a sequence number which is covered by the MAC authentication to prevent reordering attacks.

  If I do not calculate the MAC our TLS fragments are vulnerable to
  replay, swapping and filtering?

Yes, if you don't use a MAC of some kind (either application layer or transport layer) you have no guarantees regarding authenticity / integrity of the data and thus are prone to such attacks.

  Or the fact that we are using a reliable transmission protocol avoid
  that [...]?

TLS usually runs over TCP or a similar relieable protocol, but it is not a requirement. And note especially that such "reliable" protocols are only designed to protect from network errors, such as random transmission. They are not designed to survive a malicious / targeted attack which is why we have cryptographic transport protocols like TLS.


Why is it said that if we have a duplicate ciphertext block it can leak our information? I have been recently going through a question:
https://security.stackexchange.com/questions/15767/what-do-key-size-and-block-size-mean-in-cryptography and it created in me a series of doubts. Referring to the 2nd answer you may find the information that there is 50 percent chance of repetition of a duplicate block if we receive the square root of total amount of data. If some how a block is repeated how can it be cracked? How does the information gets leaked?

The exact information leaked depends on the mode of operation that is in use.
The simplest case is ECB, where a duplicate ciphertext block means that the corresponding plaintext blocks are also equal.

For the CBC mode, when two ciphertext block are equal, i.e. $C_i=C_j$, we know that there was equality before applying the block cipher. This in turn implies:$$C_{i-1}\oplus P_i=C_{j-1}\oplus P_j.$$
Equivalently, you are learning that $P_{i}\oplus P_j=C_{i-1}\oplus C_{j-1}$.

EDIT The equality comes from the fact that in CBC mode, $C_i=E_K(C_{i-1}\oplus P_i)$ where $E_K$ denotes the block cipher in use.


Plain RSA with $3$ primes, find all integers $x$ so that $x$ is equal to $y$ when $y= e_K(x) = x^{b} \bmod n$ I'm using the notation from the book: Cryptography: Theory and Practice, Third Edition.
I have a cryptosystem with the following information:
$n = p_1 p_2 p_3$ and integer $x$ is encrypted using $y = e_K(x) =  x^b$ $mod$ $n$ and the decryption is $x = d_K(y) =  y^a \bmod n$
when $ab\equiv 1 \pmod{\varphi(n)}$
$n=231$, so: $p_1 = 11$, $p_2 = 7$, $p_3 = 3$
I want to find all $x$ so $x= e_K(x) =  x^b \bmod{231}$
I tried this:
$x^b-x \equiv 0 \pmod{231}$
$x(x^{b-1}-1) \equiv 0 \pmod{231}$
$x = 0$, $x = 1$ are solutions, to find the rest:
$\varphi(231)=120$ so $ab\equiv 1\pmod{120}$ but I don't know how to continue.
Since $120=2^{3}\cdot3\cdot5$ so $2\nmid{b}$ and $3\nmid{b}$ and $5\nmid{b}$
by following the RSA page from wikipedia: key generation:
$\lambda (231)=30$, so $1 \lt b \lt 30 $, the only integers that left from $1, 2, \ldots, 30$ are primes. then using Fermat's little theorem implies that for any integer $a$: $$a^{p} \equiv a\pmod p$$ so,
I tried to check CRT, CRT implies that $e_K(x) = x$ iff $x^b \equiv x \pmod{p_i}$ for $i=1,2,3$.
But I still don't know how to continue.
Thanks.

If I understand correctly, you are looking for the integers $x$ such that, for all $b$, $x^b \equiv x \pmod n$.

You almost have it!  You've correctly identified $x = 0$ and $x = 1$ as solutions.  If you had a solution $x$, what can you say about $x_i := x \bmod p_i$ for each $p_i$—how are $x_i$ and ${x_i}^b$ related modulo $p_i$?  Can you use the solutions $x = 0$ or $x = 1$ modulo $n$ as inspirations to find solutions modulo $p_i$ and recombine them into solutions modulo $n$?


Why does FIPS 186-4 seem to have an excessively complex q generation? So in DSA you have two primes - p and q. q is N bits long (let's assume 160 bits) and p is L bits long (let's assume 1024 bits).

Here's what FIPS 186-4 says about generating the q parameter for DSA:

Get an arbitrary sequence of seedlen bits as the domain_parameter_seed.
U = Hash (domain_parameter_seed) mod 2$^{N-1}$.
q = 2$^{N-1}$ + U + 1 – ( U mod 2).
Test whether or not q is prime as specified in Appendix C.3.
If q is not a prime, then go to step 5.

outlen is the length of the Hash output, in bits, and seedlen is any number > N.

What I'm wondering is...  why not just replace steps 5, 6 and 7 with "get an arbitrary sequence of N bits as the q" and "make the least significant bit 1"?

2$^{N-1}$ gives you the lower bound on an N-sized variable.  U adds the trailing N bytes of Hash(domain_parameter_seed) to 2$^{N-1}$ and "1 - (U mod 2)" makes the final number odd. So it seems like a poor-man's randomPrime(n-bits) function call.

This is meant to allow domain_parameter_seed to be longer than 160 bits and to allow for the "verifiable canonical generation" of domain parameters described in Appendix A of the document you linked. See A.1.1.2 and A.2.3 in particular.

A truly random seed would be acceptable to use without hashing, but using a chosen number directly would be suspicious at least. Possibility of poor RNG may also be a consideration.


Oblivious Encryption: Oblivious Transfer Based Encryption I’m aware of a couple of OT protocols, most of which use Public Key Cryptography, Key Establishment (or similar constructs) as the base. I don’t really have specific knowledge on other OT protocols, however lately we’ve been discussing post-quantum OT, which actually inspired this approach on some “new(?)” type of asymmetric encryption. Which might potentially be useful, if an OT shows up which is not built on Public Key Cryptography or Key Establishment and proven to be post-quantum secure.

Here I would like to describe some form of encryption, humbly named “Oblivious Encryption”

Encryption:
For each bit $b_i$ in Alice’s message, Bob creates two random numbers $r_{i_0}$ and $r_{i_1}$. By means of OT, Alice chooses one of these random values as $r_i$, based on the bit value of $b_i$.
Alice sends all $r_i$ segments to Bob as the encrypted message.

Note: Bob is using a PRG with a seed (the seed acts as the key, and should not be reused)

Decryption:
Bob initiates the PRG with the same seed.
For each $r_i$ segment, Bob recreates the two random numbers $r_{i_0}$ and $r_{i_1}$ picks the value, that was associated with bit $0$ or $1$, constructing the $b_i$ values for message $m$

This, in essence, is a really silly symmetrical encryption scheme (probably akin to OTP); however with the touch of OT, it becomes somewhat asymmetrical, thus named Oblivious Encryption. First of all, does this make sense? Are there similar constructs, and what can you say about the security of this scheme?

If your goal is to let Alice to securely send a message to Bob (in the presence of a passive eavesdropper), then it achieves this goal. It is not secure if the adversary is active.

Potentially you can use OT extension (if random oracle model is acceptable) instead of OT to improve efficiency, if Alice and Bob needs to communicate multiple times. Basically OT extension uses a small number of base OT invocations (involving public key operations) to bootstrap, then you can invoke symmetric key based OT functionality many times. Some References:

Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank:
Extending Oblivious Transfers Efficiently. CRYPTO 2003
Gilad Asharov and Yehuda Lindell and Thomas Schneider and Michael Zohner, More Efficient Oblivious Transfer and Extensions for Faster Secure Computation, CCS13
Vladimir Kolesnikov, Ranjit Kumaresan:
Improved OT Extension for Transferring Short Secrets. CRYPTO 2013
Marcel Keller, Emmanuela Orsini, Peter Scholl:
Actively Secure OT Extension with Optimal Overhead. CRYPTO 2015
Arpita Patra, Pratik Sarkar, Ajith Suresh:
Fast Actively Secure OT Extension for Short Secrets. NDSS 2017

That's said, your protocol is not quite efficient (for achieving the goal) and there are easier and better ways of doing that (e.g. just do a key exchange and encrypt the message with the session key).


How could Fully Homomorphic Encryption support power operations? Fully Homomorphic Encryption (FHE) enables arbitrary functions computed on encrypted data, because it supports both addition and multiplication. But I wonder if FHE supports power operations.
For example:

$$C \leftarrow E(m)$$

$$y \leftarrow 2^C$$

$$2^m \leftarrow D(y)$$

I went over some FHE schemes like DGHV, it seems they don't support that.

The answer is yes. Say we have an FHE scheme that supports addition and multiplication over an underlying field (so we are not limited to just 0,1). As in your question, assume we want to compute $Y=2^C$ where $C$ is encrypted and $Y$ is encrypted such that $y=D(Y)=2^m$.

We can do this using a basic square and multiply algorithm. Assume that we can do a bit decomposition on encrypted values. In other words, assume that given $C$ we can compute $C_1,C_2,\dots,C_n$ which are encrypted values (either 0 or 1) of the bits of the plaintext encrypted by $C$.

Then to compute $Y$ we would do:

A = E(1) # A is our accumulator
B = E(2) # 2 here since the base is 2
for i from 1 to n:
  A = (A*B*C_i) + A*(~C_i) # typical code for square-and-multiply puts this
                           # step in an if-block. If C_i==1: A = A*B. Since
                           # we can't know the value of C_i, we must do it this
                           # way. The end result is the same. If C_i=0, A=A.
                           # If C_i=1, A=A*B (the multiply step in square-and-multply
  B = B*B  # This is the square step
Y = A
return Y

where ~ is the NOT operation.

Therefore, all we need is bit-decomposition and NOT. The NOT operation is pretty simple. Since $C_i$ encrypts $0$ or $1$, $~C_i$ is computed as $(1-C_i)$.

Bit decomposition is harder. For an example of how it may be done, see the BGV paper.


RSA Protocol/Generating Primes So, Alice wants to use the RSA protocol and pays Cindy to generate the two (odd) primes p and w so she can use e=65537 and n=pw as her public key. Alice will then, upon receipt of p and w, privately, find d to use as her private key.

Cindy delivers p and w to Alice where p is prime, but she messes up and delivers a number w to Alice which is composite. This number w is the product of two (distinct) primes. (Assume (p,w)=1.) Alice doesn't realize that w is prime and under this assumption finds d. Therefore publishes her public key (65537,pw).

Amazingly, whenever a message M is sent to Alice using RSA using her public key and Alice uses her d, she always recovers the message M correctly! (Of course we assume that M and pw have no common factors).

How in the world is this possible?? What is the formula??

How do we prove that there is no such w that is 512 bits in size??

Edit: Also, how can we prove that two primes dividing w cannot have the same number of bits (in binary representation)?

How in the world is this possible?

The easiest way this can happen is if $w$ is a Carmichael number (and relatively prime to $p$).

A Carmichael number is a composite number such that $x^{w-1} \equiv 1 \bmod w$ for all $x$ relatively prime to $w$.

If you take a Carmichael number, and just insert it into the RSA machinery; that is, compute $d = e^{-1} \bmod \text{lcm}(p-1, w-1)$ (or $(p-1)(z-1)$, both works in this case), you'll get an encryption/decryption pair that works.

To make things even more interesting, there are also numbers for which $x^{w-1} \equiv 1 \pmod m$ is often (but not always) true (I personally call them quasicarmichael numbers; that might not be standard terminology); then, depending on what $p$ is (actually, it's the factorization of $p-1$ which is critical), and possibly whether you use $\text{lcm}(p-1, w-1)$ or $(p-1)(z-1)$, can also work.

  (Of course we assume that M and pw have no common factors).

Actually, we don't need to make that assumption.

  How do we prove that there is no such w that is 512 bits in size??

Actually, I believe that there are Carmichael numbers of that size.


Why is Diffie-Hellman used instead of just RSA in key-exchange (TLS, IKE)? Why should a key exchange protocol (such as in TLS or IKE) use Diffie Hellman? Why not just use RSA? For example: Alice picks a random session key, signs it, encrypts it with Bob's public key, and sends it to Bob.  Why introduce Diffie-Hellman? What does DH add?

What does DH add?

Perfect Forward Secrecy.

That is, suppose you have a secure session with the server Bob, and then you close the session down.  Then, someone steals the server (or serves a warrant to the owner).  If you use RSA to transport the random session key, well, the server still has the RSA private key, and so they'll be able to decrypt your session.

In contrast, assuming that the server and the client zeroizes the DH private values at the end of negotiation, they can't - no one is able to rederive the session keys, even if they grabbed both the client and the server.

Now, it's possible to do this with RSA (by zeroizing the old RSA private key, and generating a fresh one periodically); however generating RSA key pairs is expensive, and so no one does that - they use DH instead.


Is my pseudo-random initialization vector secure? How can I know if I am generating a secure pseudorandom initialization vector?

Currently I am planning to generate a pseudo-random initialization Vector using current date and time - is this secure enough?

If the answer depends on the block cipher and mode of operation, I am using OFB mode with AES.

Just use the build in crypto PRNG of your operating system or framework.

C# / .net: RNGCryptoServiceProvider Class
Java: SecureRandom Class
Linux: /dev/urandom
Win32 API: CryptGenRandom function

date/time might be enough for modes which only require uniqueness, but if you generate two IVs in quick succession(within 16ms or so) or if the clock is changed. It's still an unnecessary risk.

date/time is certainly not enough for modes where an unpredictable IV is required, such as some uses of CBC.


Is this SHA-256 modification still valid? We typically model a hash function (in particular $\mathrm{SHA}$-$256$) as a function $H:\{0,1\}^{2^{64}-1} \to \{0,1\}^{256}$ with some special properties that makes them useful in practice. In this case, the probability for a collision is around $2^{-256}$ which is assumed to be infeasible in practice.
Now (because $256$ bits seems too long to handle for me), I want to cut some of them off and still keeping an (almost) infeasible probability of having a collision. In other words, which is the correct amount of bits I have to truncate so that I still have a good collision resistance? It is just $2^{-m}$, where $m$ denotes the bits that you keep from the beginning?
To illustrate what I mean, Imagine that the beginning of two outputs of $H$ are $1011100...$ and $1011000...$. If I just decide to cut off $4$ bites then I have a collision ($1011$), otherwise I don't.
Where could I find when (and why) a probability is "low enough" in practice? I assume it is something related with computer's limits...

The idea behind this question is using tracking hashes easy to handle by users. An upper bound for the number of users is $2$ millions. Since $256$ bits is too large (it is still large if you use base-$16$ or base-$64$), we though to prune some amount of bits if it is secure to do that. Two users with the same pruned hash would mean a disaster.

We typically model a hash function (in particular $\mathrm{SHA}$-$256$) as a function $H:\{0,1\}^{2^{64}-1} \to \{0,1\}^{256}$ with some special properties that makes them useful in practice.

Well, that definition is indeed rather particular to SHA-256. The output size is of course depending on the hash function, and e.g. SHA-3-256 has an infinite input space.

In this case, the probability for a collision is around $2^{-256}$ which is assumed to be infeasible in practice.

No, for the function the probability for creating a collision using many tries is closer to $2^{-128}$ because of the birthday bound. You're showing the chance of a pre-image happening, and that only for a single try. Discussing collision resistance for hashes over any two distinct messages doesn't make much sense.

Where could I find when (and why) a probability is "low enough" in practice? I assume it is something related with computer's limits...

Depends on how the hash function is used and the threat model of the particular use case. If you'd ask me about a generic minimal security limit then I'd go for 128 bits (presuming only attacks using classical computers). That would mean a 256 bit hash when it comes to collision resistance - and not pruning any bits.
Now for particular use cases you may go lower. You may want to keep in mind that generating $2^{128}$ hashes is not practical; the birthday bound assumes you compare many hashes after all. So there is probably some leeway when it comes to memory requirements for any attack.
Keyed hashes (HMAC) are a different matter entirely. There you would only need 128 bits to achieve 128 bit security.


How does a key wrapping like RFC 3394 secure my cryptographic keys? So I'm messing around in the BouncyCastle library with the RFC 3394 AES Key Wrap engine and I'm trying to understand the benefit of it.

The problem I'm running into is how to store keys securely on a device like a phone or even a laptop or desktop. I need to wrap the keys so that anyone snooping around in memory can't just get those keys. RFC 3394 looks as though it's designed to help with that issue.

I can just do

$$ \bar k = \operatorname{wrap}_{k^*, IV}(k) $$

and store $\bar k$ instead of $k$, and use

$$ k = \operatorname{unwrap}_{k^*, IV}(\bar k)$$

to retrieve $k$ again when I need it.

I've written this code in C# to test it out. This seems to work okay, except for the fact that I'm trying to understand how this is more secure. At some point I have to store the key encryption key $k^*$ in memory, and it seems to me that any hacker who could get their hands on $k^*$ now has their hands on the encryption keys.

So how does this secure the encryption keys in memory?

Yes, you are correct; the keywrap algorithm assumes that you have one long term secure key, which you can use to protect other keys.  The writers of RFC 3394 assume that you do have a secure key-encrypting-key (KEK).

This doesn't appear to be a valid assumption in your case.  In your case, you need to do cryptographical operations even though someone can assume your entire memory space; this sounds like you need White Box cryptography.


Explanation and proof of a well-know probabilistic lemma Pointcheval and Stern in their paper on "Security proofs for Signature Schemes" state the following "well-known" probabilistic lemma:

  Let $A \subset X \times Y$, such that $\mathrm{Pr}[A(x, y)] \geq \epsilon$, then there exists $\Omega \subset X$ such that

  $\mathrm{Pr}[x \in \Omega] \geq \epsilon/2$
  whenever $a \in \Omega$, $\mathrm{Pr}[A(a, y)] \geq \epsilon /2$

I am not familiar with the notation used and I also can't find this result in my literature.

Questions:

Can $A$ be any set or it must be an event (measurable set)?
Does the notation $\mathrm{Pr}[A(x, y)]$ mean $\mathrm{P}\left(\{(x, y) \in A\}\right)$? Notation $A(x, y)$ could also imply that $A$ depends on $x$ and $y$, but I don't believe this is the case.
Does the notation $\mathrm{Pr}[x \in \Omega]$ mean $\mathrm{P}\left(\{(x, y) \in \Omega\times Y\}\right)$ or does it mean $\mathrm{P}\left(\{(x, y) \in (\Omega\times Y)\cap A\}\right)$
How can I prove this? Where can I find the proof?

In my definitions I assume that $A$ is an event and a subset of the sample space $X \times Y$ and that $P$ is a probability measure.

Thanks.

This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit).

First, I assume that when writing $\operatorname{Pr}[A(x,y)=1] \geq \epsilon$, then the probability is taken over a random choice of both $x$ and $y$. Now, the claim is that there exists a subset of $x$ values of a "large enough size" so that for every $x$ in this set, the probability of the event is at least $\epsilon/2$ when taking a random $y$ only.

This can be proven as follows: Let $\Omega$ be the set of all values $a\in X$ for which $\operatorname{Pr}_y[A(a,y)=1]\geq \epsilon/2$. (Note that for any $a\in X\setminus \Omega$ it therefore holds that $\operatorname{Pr}_y[A(a,y)=1] < \epsilon/2$.)

Our aim is to prove that $\Omega$ is of size at least $\epsilon/2 \cdot |X|$, since this will show what we need.

\begin{eqnarray}
\epsilon \:\leq\:\operatorname{Pr}_{x,y}[A(x,y)=1] & = & \frac{1}{|X|} \cdot \sum_{a\in X} \operatorname{Pr}_y[A(a,y)=1]\\
& = & \frac{1}{|X|} \cdot \sum_{a\in\Omega} \operatorname{Pr}_y[A(a,y)=1] + \frac{1}{|X|} \cdot \sum_{a\notin\Omega} \operatorname{Pr}_y[A(a,y)=1]\\
& \leq & \frac{1}{|X|} \cdot \sum_{a\in\Omega} 1 + \frac{1}{|X|} \cdot \sum_{a\notin\Omega} \operatorname{Pr}_y[A(a,y)=1]\\
& < & \frac{|\Omega|}{|X|} + \frac{\epsilon}{2},
\end{eqnarray}
We therefore have that $\epsilon \cdot |X| < |\Omega| + \epsilon/2 \cdot |X|$ and so $|\Omega| > (\epsilon - \epsilon/2) \cdot |X| = \epsilon/2 \cdot |X|$, as required.

I hope that this is clear.


Using the same RSA key for verifying a website and digital signature We have the (same) RSA key for verifying a website and for digital signature. A user would send a nonce encrypted using the public key, the websites returns the nonce by decrypting it using the private key. Now let's an attacker wants to have a hash to be encrypted with the website's private key. How could this work? I heard it is possible, but like technically how could this happen?

tl;dr: send to the server $enc(random) \times theHash$, and divide the value that you get back by $random$. That is your forged signature for $theHash$.

Your setup can be summarized as follows: with have a Server S with an RSA private key $(N; d)$, a Client C with the corresponding public key $(N;e)$. Furthermore the client as a value $h$ for which (s)he wishes to get a valid signature under the private key of the server, namely the client wants $h^d \mod N$. Finally the server authenticates itself by proving the knowledge of $d$(i.e computes $q^d \mod N$ where $q$ is possibly an encrypted nonce.

Observations: 1. We can assume that the server somehow checks that none of the queries is $h$, and refuses to decrypt any such query otherwise game over.
2. I wrote possibly because the client in fact doesn't need to send and encrypted query. He could send any value to the server as long as it's an element of $Z/Z_N$.

The attack: the client selects a random value $s$ such that $gcd(N, s) = 1$, and sends to the server the value $q = h\times s^e \mod N$. This is indeed a valid query. Next, the servers send back $\sigma = r^d \mod N = h^d \times s \mod N$. Finally the client computes the signature as $sig = \sigma \times s^{-1} \mod N = h^d \mod N$. So we have the signature that we wanted.


How practical is proxy re-encryption for AES? In proxy re-encryption schemes, a proxy is given special information that allows it
to translate a ciphertext under one key into a ciphertext of the same message under a
different key.

How practical is PRE? Is it possible for achieving PRE for AES?

Proxy re-encryption schemes are entirely practical. This is certainly true for AES symmetric encryption, as the proxy does little more than decryption with key 1, followed by encryption with key 2. This is called the "Naïve Way" in this lecture.

Now if PRE is suitable for a specific uses case is an entirely different matter. It depends on how secure the proxy itself is. If you require additional security in the PRE protocol itself you may have to go for a protocol that uses asymmetric encryption primitives.

Beware that a proxy more or less implies communication over insecure networks. If man-in-the-middle attacks are applicable then you should add an authentication tag to your messages.

More detail is required to answer your question for a specific use case.


Why RSA can't handle numbers above 76? I'm going to encrypt the characters Zhu, and decrypt them using RSA. I'm using the public key $\{e, n\}$ and private key $\{d, n\}$. The values of $e$, $d$ and $p$ I get from my textbook: $e = 17$, $d = 53$, $n = 77$.

It works fine when the number is smaller than 76, but in my example below, it doesn't work:

z = 90
h = 104
u = 107
e = 17
d = 53
n = 77

print z,h,u

c_z = z ** e % n
c_h = h ** e % n
c_u = u ** e % n

print c_z, c_h, c_u

p_z = c_z ** d % n
p_h = c_h ** d % n
p_u = c_u ** d % n

print p_z, p_h, p_u

The outputs are:

90 104 107
62 69 46
13 27 30

Do you have any idea what's going wrong?

By definition you cannot encrypt values greater than the modulus in RSA, because the plaintext is immediately reduced modulo $n$ which loses information. This is because textbook RSA works in the $\mathbb{Z}/n\mathbb{Z}$ congruence ring, so from RSA's point of view, as long as two values have the same remainder modulo $n$, they are effectively equivalent. So with your $n = 77$ example, RSA will not distinguish plaintexts of $10$ and $87$ since they both leave a remainder of $10$ when divided by $77$, i.e. they are equal in $\mathbb{Z}/n\mathbb{Z}$. They will produce the same ciphertext, and hence decrypt to the same value ($10$).

Put differently, RSA does not care what your plaintext is, all it cares about is its remainder when divided by your modulus. Anything else is irrelevant, all that matters is the remainder (hence everything being done modulo $n$).

You will notice "z" (90) decrypts to 13 which just so happens to be the remainder of 90 when divided by 77, as $90 = 1 \times 77 + 13$. Similarly, "h" (104) decrypts to 27, and sure enough, $104 = 1 \times 77 + 27$. And again, "u" (107) decrypts to 30... you guessed it, $107 = 1 \times 77 + 30$. Coincidence? Not at all, it is a direct consequence of the first paragraph.

Another way to think of it is that since RSA can only output values between $0$ and $n - 1$ (because the ciphertext is taken modulo $n$), then there can only be $n$ possible plaintext inputs (pigeonhole principle). It then becomes clear encrypting values above $n - 1$ is not useful.

You'll need to use a bigger modulus, or work with a different charset e.g. a = 0, b = 1, etc... instead of using the ASCII one, since in ASCII most small values are unfortunately taken up by control characters. If you want all basic characters to work properly, try this keypair:

$\left ( ~ p = 13, ~ q = 29, ~ n = 377, ~ e = 17, ~ d = 257 ~ \right )$

This should work - but do remember this is only for learning purposes.

Fun fact: this small RSA keypair is very interesting in that its encryption and decryption exponents are both prime fermat numbers, this is amazingly rare and quite surprising. Just thought I'd mention it.


List of post quantum cryptography protocols What are the post quantum cryptography protocols that have been proposed until now?

I know about McEliece cryptosystem, and LWE scheme. What are the others? Can you provide me a list or a website containing such list?

First, a pedantic point: be careful with terminology: there currently are no Post-Quantum "protocols" (TLS, S/MIME, CMP, etc). From your question, I'm assuming you are interested in PQ "schemes", or PQ "primitives" (XMSS, R-LWE, etc). This may seem like nit-picking, but we can expect NIST to standardize primitives in the next 3 - 5 years, protocols will take longer than that!

Now for your actual question. As @SEJPM points out, the research is still very young and is rapidly changing, so any links to actual schemes will very quickly go out of date. What I will do instead is link to the organizations that you should be following.

NIST

Link to their talk from the recent PQCrypto2016 conference outlining their upcoming call for applications for candidate PQ signature and encryption schemes.
See their February 2016 report, basically a "What we know at this point".
pqc-forum@nist.gov is the mail-list for discussion of post-quantum schemes and their standardization. This went live very recently so I can't find any references to it online, but you can get yourself onto it by sending an empty email to pqc-forum-request@nist.gov with subject:subscribe

NSA

See their Suite B page (at time of writing, it was last updated in August 2015).
See their January 2016 announcement of the replacement of Suite B.

PQCrypto Project

Group funded by the European Union to research and recommend PQ schemes.
pqcrypto.eu.org

IETF / IRTF's Crypto Forum Research Group (CFRG)

Draft standard for XMSS hash-based signatures.
irtf.org/cfrg


when to do elgamal exponentiation computation Recetly while studying about cryptographic primtives, I have come across below line in wiki : http://en.wikipedia.org/wiki/ElGamal_encryption

  Encryption under ElGamal requires two exponentiations; however, these exponentiations are independent of the message and can be computed ahead of time if need be.

Does "if need be" in the sentence refering to a static key? or is he saying that we can compute an ephemeral key prior to encryption and send to receiver, then later send the encrypted ciphertext at some other time.
If he is not refering to ephemeral key, I still want to know, are there any times we can really implement such a process using ephemeral.

I use the notation from the linked Wiki page.

What this means is, assuming one potential receiver's public key $h$, that you can choose $y_1,\ldots,y_k$ offline and compute offline
the values $(g^{y_1},h^{y_1}),\ldots,(g^{y_1},h^{y_1})$ and store them. Observe, that these values have nothing to do with the messages you want to encrypt (which are not yet known at this point in time).

Then, when you want to encrypt some message $m$
and send it encrypted to the holder of the public key $h$, you simply take an item from the stored list, say the $i$'th entry, set the
ciphertext as $(c_1,c_2)=(g^{y_i},m\cdot g^{y_i})$ and send it. Observe, that now this only costs a single multiplication of one of the pre-computed values with the message $m$.

After having sent this ciphertext,
you remove the $i$'th entry from the list.


Is it safe to seed a random number generator from system time? It seemed to me that the Bouncy Castle SecureRandom class for C#/.NET only uses DateTime.Now.Ticks as its seed by default.

I was wrong, but wouldn't that be unsafe to do?

Yes, it is unsafe to seed a PRNG with only with the system time.  No, that's not all Bouncy Castle's SecureRandom does.

The SecureRandom default constructor calls SetSeed(GetSeed(8)); which calls Master.GenerateSeed(length); which calls SetSeed(DateTime.Now.Ticks); which is misleading because SetSeed only adds seed material to an already existing prng (the static instance called Master).  If you look at the static declaration for private static SecureRandom Master you'll see that it actually seeds itself from a combination of Ticks and ThreadedSeedGenerator.

Why the system time is not enough

Using just the system time would be unsafe.  The whole point of a crypto random generator is to be unguessable by an adversary, and by using the system time as a seed to the random number generator, you make it easy for an adversary to guess your seed and hence your random output.

DateTime.Now.Ticks has precision of 10 million ticks per second.  Suppose an attacker knows what time you generated a key, +/- 1 second.  They only need to make 20 million guesses ($2^{20}$ or so) in order to guess your random seed.  This is likely crackable in a matter of seconds with a modern laptop.

Suppose an attacker has absolutely no idea what time you generated some key.  They only know it was after – let's say – the year 2000.  Since it's 2014 now, the entire space of 14 years occupies 51-52 bits.  log2(10000000*60*60*24*365*14) ~= 51.97…  This means the absolute highest level of entropy that you're likely to have in anything generated from system time is around 51 bits, which is small enough to be easily crackable, and realistically, you'll never even come close to that.


Have any SHA-1 collisions happened? No SHA-1 collisions are actually known, though there are a number of cryptographic attacks to weaken it.

But, how likely is it that, of all the SHA-1 hashes computed since the invention of the algorithm, there has been a collision?

Not sure how to approach this, but it probably involves the Birthday Problem?

(if there's a better SE to ask this in, let me know)

In order for a collision to happen "by chance", about $2^{80}$ hashes need to have been computed. If 1000 hashes were computed every millisecond, then this would take 38,334,786,263 years. So, I doubt that this has happened by chance.

Having said that, I would be very surprised if large government organizations do not already have SHA collisions (using better collision finding algorithms).


Random number generator issue I wrote a litte random generator using a geiger tube. I use a 16bit timer that overflows every ~1ms;
when i get a reading form the geiger (~36count/minute), i save the current timer value as "random number".

But if run the test ent i get a completly different result for the chi-squared-test, in binary mode is fine, but in byte mode it fails miserably.

This is just a side project only for a little presentation, but i would like to have an idea to understand what is wrong.

binary mode

ent lestobaremetal.txt -b
Entropy = 0.999990 bits per bit.

Optimum compression would reduce the size of this 654560 bit file by 0 percent.

Chi square distribution for 654560 samples is 9.08, and randomly would exceed this value 0.26 percent of the times.

Arithmetic mean value of data bits is 0.5019 (0.5 = random).
Monte Carlo value for Pi is 3.123203285 (error 0.59 percent).
Serial correlation coefficient is -0.001670 (totally uncorrelated = 0.0).

byte mode

ent lestobaremetal.txt
Entropy = 7.986452 bits per byte.

Optimum compression would reduce the size of this 81820 byte file by 0 percent.

Chi square distribution for 81820 samples is 899.48, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 128.1813 (127.5 = random).
Monte Carlo value for Pi is 3.123203285 (error 0.59 percent).
Serial correlation coefficient is -0.001851 (totally uncorrelated = 0.0).

UPDATE:

The random stream is generated in this way: the pulse from the GM tube is stretched by a 555 astable timer to 5mS duration. The stretched pulse is fed into the INT0 pin on an atmega328. When the external interrupt is generated, the current TCNT1 16-bit counter value is taken and sent over uart to the pc. The timer is run with prescaler 1 at 16MHz, for an overflow every ~4ms

Here you can find the binary file with the data collected in a couple of days:
lestobaremetal.txt
More about the proect:
Source code
Hardware schematics and layout

Both ent tests distinguish the files from random data with high confidence (99.84% for the bit test, >99.99% for the byte test). That follows from the "randomly would exceed this value.." reports.

It would only be an issue in actual use if the random data was directly used. Which would be bad practice in cryptography, where the rule is that the output of an unconditioned TRNG is, under operating conditions, fed exclusively to

a monitoring scheme which ensures that the unconditioned TRNG outputs some entropy;
and a PRNG processing the output of the unconditioned TRNG.

Note: if the PRNG is not cryptographically secure (which is often the case for hardware ones), its output is further processed with a CSPRNG.

With this structure the monitoring scheme's purpose should not be to try to determine that/if the TRNG is near-perfect. It should be to rule out that the TRNG is badly broken (like, insure that the entropy rate if at least 0.5).

The ent test is ill-suited to the purpose: it is not operating in real time, is not designed to ignore minor defects, and most importantly it fails to detect some huge, not-unlikely defects: if there was a triple-trigger for every Geiger event, making three identical or incremental values recorded for each Geiger event, that would not be detected by ent (except for very small input), when that's a disaster.

Still, from an engineering perspective, it is interesting to understand what makes the ent tests fail. Some ideas (before the question was updated with raw data and code):

The Geiger event determines when a free-running 16-bit timer clocked at about $2^{16}/10^{-3}$Hz (about 70 MHz) is sampled. It could be that there is some analog feedback from the counter, or from something derived from the same clock as the counter, to the sampling logic. For example, if when the Geiger event occurs near the active edge of the clock, the current state of the low-order bit of the counter influences (by e.g. capacitive coupling) the decision of the gate that determines if the event is going to be registered as having happened before or after the edge, then that low-order bit is going to be biased. It may be that ent's byte test will detect this bias more accurately than it's bit test (because the biased bit is always at the same position in a byte).
If the sampling is in software (e.g. an interrupt triggered by the Geiger event reads the 16-bit timer), then the latency in the processing of that interrupt can play a role. For example, if the 16-bit timer generates an interrupt of identical priority when it overflows, that makes it impossible that some 16-bit values (those right after the overflow) get sampled, creating a bias. I believe ent's byte test would detect that kind of issue more selectively than it's bit test.

Summary (before the question was updated with raw data and code):

The ent tests failed, and that's likely related to some minor imperfection. We can only make guesses at which.
It is no indication that this unconditioned TRNG is unsuitable to seed a (CS)PRNG, which is the Right Thing to do with an unconditioned TRNG.
The enttest is not adequate for an unconditioned TRNG source; not even in an exploratory phase, much less for the continuous surveillance of the unconditioned TRNG, as necessary in serious cryptographic uses.

Update: Mystery solved!

Summary frequency analysis of the raw data demonstrates beyond doubt that byte values 0x11 and 0x13 have been filtered out. That's what allows ent to raise alert. Certainly, XON/XOFF software flow control strikes again!

0x00 281  0x01 300  0x02 343  0x03 313  0x04 322  0x05 321  0x06 295  0x07 342  0x08 317  0x09 319  0x0A 337  0x0B 320  0x0C 328  0x0D 308  0x0E 324  0x0F 344
0x10 316  0x11   0  0x12 320  0x13   0  0x14 314  0x15 376  0x16 336  0x17 325  0x18 295  0x19 342  0x1A 325  0x1B 338  0x1C 326  0x1D 293  0x1E 324  0x1F 296
0x20 328  0x21 300  0x22 322  0x23 313  0x24 340  0x25 334  0x26 342  0x27 315  0x28 336  0x29 295  0x2A 313  0x2B 305  0x2C 322  0x2D 341  0x2E 303  0x2F 331
0x30 308  0x31 339  0x32 371  0x33 325  0x34 323  0x35 319  0x36 324  0x37 309  0x38 337  0x39 296  0x3A 323  0x3B 338  0x3C 335  0x3D 302  0x3E 335  0x3F 348
0x40 331  0x41 318  0x42 334  0x43 285  0x44 323  0x45 348  0x46 323  0x47 333  0x48 325  0x49 370  0x4A 345  0x4B 318  0x4C 338  0x4D 302  0x4E 330  0x4F 326
0x50 332  0x51 308  0x52 307  0x53 362  0x54 300  0x55 292  0x56 335  0x57 333  0x58 352  0x59 355  0x5A 317  0x5B 326  0x5C 329  0x5D 334  0x5E 316  0x5F 331
0x60 318  0x61 324  0x62 293  0x63 318  0x64 302  0x65 324  0x66 317  0x67 313  0x68 297  0x69 310  0x6A 330  0x6B 334  0x6C 300  0x6D 340  0x6E 310  0x6F 317
0x70 324  0x71 335  0x72 309  0x73 335  0x74 333  0x75 336  0x76 314  0x77 313  0x78 354  0x79 333  0x7A 294  0x7B 333  0x7C 324  0x7D 340  0x7E 343  0x7F 336
0x80 309  0x81 294  0x82 352  0x83 324  0x84 306  0x85 295  0x86 314  0x87 342  0x88 324  0x89 311  0x8A 331  0x8B 292  0x8C 305  0x8D 318  0x8E 324  0x8F 321
0x90 307  0x91 325  0x92 335  0x93 329  0x94 324  0x95 335  0x96 318  0x97 336  0x98 335  0x99 302  0x9A 310  0x9B 342  0x9C 315  0x9D 326  0x9E 290  0x9F 323
0xA0 308  0xA1 319  0xA2 347  0xA3 323  0xA4 305  0xA5 312  0xA6 336  0xA7 293  0xA8 323  0xA9 310  0xAA 352  0xAB 323  0xAC 305  0xAD 312  0xAE 340  0xAF 306
0xB0 305  0xB1 311  0xB2 334  0xB3 333  0xB4 303  0xB5 324  0xB6 343  0xB7 308  0xB8 305  0xB9 309  0xBA 331  0xBB 322  0xBC 332  0xBD 329  0xBE 311  0xBF 327
0xC0 350  0xC1 349  0xC2 352  0xC3 313  0xC4 319  0xC5 350  0xC6 282  0xC7 316  0xC8 305  0xC9 348  0xCA 316  0xCB 325  0xCC 335  0xCD 337  0xCE 295  0xCF 309
0xD0 305  0xD1 344  0xD2 325  0xD3 311  0xD4 296  0xD5 301  0xD6 349  0xD7 285  0xD8 328  0xD9 308  0xDA 323  0xDB 338  0xDC 276  0xDD 299  0xDE 323  0xDF 314
0xE0 286  0xE1 360  0xE2 315  0xE3 308  0xE4 329  0xE5 321  0xE6 302  0xE7 315  0xE8 346  0xE9 326  0xEA 315  0xEB 352  0xEC 346  0xED 319  0xEE 333  0xEF 289
0xF0 320  0xF1 309  0xF2 317  0xF3 325  0xF4 312  0xF5 366  0xF6 331  0xF7 316  0xF8 283  0xF9 344  0xFA 336  0xFB 302  0xFC 331  0xFD 310  0xFE 347  0xFF 335

Note 1: As a minor aside, the 16-bit counter is sampled by software in an interrupt, rather than in hardware by an input capture mechanism. It follows that any variation in interrupt latency influences what's sampled. In many CPUs, interrupt latency varies slightly according to foreground activity (like, a multi-cycle instruction or access to a peripheral requiring wait states increases latency). The ATMega328P has instructions lasting 1 to 4 cycles, thus this could have some minor influence, especially on the low-order bits. While I have seen the uncertainty in sampling by interrupt about halved by putting a CPU in wait/sleep mode rather than in a loop with a 2-cyles branch, that's a non-scalable kludge, and using the ATMega328P's Input Capture Unit would be best (depending on what pin the signal to sample is connected, that could be software-only change).

Note 2: putting a radioactive source nearby will have several effects:

The entropy rate (in bit/s) will increase.
The samples will get closer, and that will increase a currently minor issue: by design, the difference between a 16-bit sample and the next (modulo 65536) is biased.
Odds of upset in the nearby logic/CPU will increase, which could have dramatic negative side effects.

Note 3: Proper monitoring of the unconditioned source is best done with knowledge of which is high and low byte of 16-bit samples. This currently is possible only by timing considerations (especially with the disappearing bytes). We can solve that and make the output plain ASCII by sending a 16-bit sample as 4 characters, the first in PQRSTUVWHIJKLMNO and the others in pqrstuvwhijklmno, with the low-order 4 bits of each character equal to 4 bits of the 16-bit sample (I suggest, in big-endian order, which is the most common in crypto).

Note 4: In some cryptographic contexts, adding a proper CSPRNG somewhere will be essential. If this unconditionned generator was used as /dev/random directly, it would be easy to distinguish the output from good randomness, at least if it can be timed when the output becomes available! Proper monitoring is important too, and essential if an adversary can approach the device (sabotage is a thing; and forcing Geiger events to occur is not rocket science).


Difference between H(A)+H(B) and H(A+B) I was learning about Merkle trees and understood that if A, B, C and D are the leaf nodes, then their parents will be H(H(A)+H(B) and H(H(C)+H(D)) rsp. and the root will be H( H(H(A)+H(B)) + H(H(C)+H(D)) ). What if instead of this, the parents of the leaf node were: H(A+B) and H(C+D) and the root be H(A+B+C+D)?

I intuitively know this may not be a good choice but can someone explain it in a better way?

If + means concatenation, then $H(A+B+C+D)$ doesn't help make verification easier. You still need all leaves in order to verify any leaf, whereas the point of Merkle tree is to be able to verify individual leaves with only logarithmic cost.

If + means XOR or addition, then $H(A+B+C+D)$ is not collision-resistant so the construction fails to authenticate the leaves.


Isn't a simple Vernam cipher as secure as known symmetric key algorithms? I have just read little about the Vernam cipher and the problems of implementing it.

But, in practice, would not the key, if generated by a commonly used programming language's Random() function (like Python's or Java's random functions from their standard libraries), be enough to make the message almost uncrackable if the key is as long as the message and the key is only known by the author of the text?

The standard random number generator, in languages like Java or Python, does not generate real random numbers but pseudorandom numbers determined by an initial seed value.  If an attacker can somehow guess or determine this seed value, they can reconstruct the entire sequence of pseudorandom outputs.

Furthermore, the default pseudorandom number generators in most languages are not cryptographically secure.  In particular:

The set of possible seeds is typically rather small; for example, the seed may be a 32-bit integer, meaning that an attacker only needs to test 232 different seeds to find the correct one.  On a modern computer, this can often be done in a few seconds.
Worse yet, the initial seed is often chosen based on some fairly easily guessable value, such as the system time.  If such a seed is used, and if you know roughly when a key was generated, you can narrow down the range of likely seed values significantly.
Even if the seed is chosen securely (i.e. completely unpredictably) from a set large enough to resists brute force guessing, the algorithms used to generate the pseudorandom outputs from the seed are typically not designed to withstand cryptanalytic attacks.  Thus, for many commonly used algorithms, the seed can be fairly efficiently reconstructed from the outputs.

The first two attacks above only require that the attacker has access to some ciphertext, and can try to decrypt it with keys based on different seeds and see for which seed the resulting decrypted data makes sense.  The last attack generally requires a bit more, namely that the attacker must know at least part of the keystream — but if the attacker has the ciphertext and can guess part of the plaintext, they can easily obtain the corresponding parts of the keystream.

Of course, if you created your key based on a pseudorandom number generator that did not have any of these weaknesses, then the scheme you describe would be secure.  Indeed, that is pretty much exactly what a synchronous stream cipher is.


Why is CBC based on AES malleable in blocks other than the first block? Perhaps I don't understand the answers to Malleability attacks against encryption without authentication, so trying to be more concrete... please be patient.

If I want to change the first block and I can change the IV, I see that its easy to change the IV to IV xor old_block_0 xor new_block_0 and the first block would change.

However, if I want to change the second block block_1, I don't understand how can I do it? If I change the block before it to block_0 xor x I would garble the D(block_0), won't I?

Depending on how malleability is defined, the question actually has some merit.

Given to the Wikipedia definition of malleability, a cipher is malleable if there exists at least one function $g$ over the set of possible cipher texts, and one function $f$ over the set of possible plain texts, such that given any cipher text $c_0$, the cipher text $c_1 = g(c_0)$ will decrypt to $D_k(c_1) = f(D_k(c_0))$ regardless of which key $k$ is used for the decryption.

Given that a function by definition assigns a unique value to each argument, there only exists such a function $f$ for CBC mode that might be known in advance to the attacker and might be determined from $g$ alone, if the corresponding function $g$ only modifies the IV. If the function $g$ modifies any other block, then $f$ will either be a relation (i.e. assign a set of possible values to each argument, rather than a unique value), or it will be a function that depends also on the key $k$.

Still, non-malleability might be defined in such way that the function $f$ only has to exist, without necessarily being known to the attacker in advance. If non-malleability is defined in such way, it is not necessarily a problem that this might imply that $f$ depends also on the unknown key and not just on $g$ and the plain text.


Side-channel attack in the real wold I have a big problem to figure how the security model in papers about side-channel are relevant (briefly the attacker has a partial access to the hardware).

Why these breaches are so seriously considered?

Is there any known and famous story of a system attacked with these techniques?

Actually there are a lot of cases where side-channel are important threats.

To name a few:

IOT devices that are storing secret keys to communicate to each other or do whatever they need to do with it, and that are not supposed to be impersonated by an attacked from his computer.
Trusted Execution Environment such as TrustZone, SGX or TPMs in general. For a very recent example, see tpm.fail.
cloud computing: being able to read somebody's else secrets in memory because you are both sharing the same server in the cloud's system
Pay-TV systems or any other system where the providers is broadcasting encrypted content, that is meant to only be decrypted by authorized key holders. (Typically done using smart-cards that are supposed to be impossible to clone, and whose key should be impossible to extract.)

And it even appeared that side-channel such as Spectre and Meltdown could be remotely used through a web browser running malicious Javascript to steal your passwords!


Comparing Ciphertext when there is a change in source plaintext p1 So, i know that if there is a change in source plaintext p1, c1 and rest of cipher blocks will be affected as c is required for the calculation in cfb. What i need to know is that how can i show how many blocks will be affected when there is this error. I have tried comparing the two cipher texts(one with no change in p1, and one with a bit change in p1) using diff, but i've had no luck in showing how many blocks are affected with the change in p1. Thanks.

i don't think that there is a way to check the changes on block cipher if you are using random IV here, since the IV will go to Enc first, then the output would be totally different than before,

if you are using the same IV, then try to figure out the the block length for the block you are using, if it is 16 bytes, then change the first 16 bytes will result first 16 bytes of ciphertext to be different. Since before output the ciphertext, it is just a one-time pad.

hope it helps.


Two Round Feistel network While reading on block ciphers and DES I read that two-round Feistel network is not a secure PRP? Is there any easy to understand proof to explain the intuition behind this statement. I did search around and also reviewed this question but wasn't really able to understand why it isn't secure PRP. Any help would be much appreciated!

I read that two-round Feistel network is not a secure PRP

That's easily seen:

It holds $P_L\oplus C_L=F_0(P_R)$. That implies a distinguishable property: for any fixed $P_R$ and whatever the round function $F_0$, when we flip bit(s) in $P_L$, that flips the corresponding bit(s) in $C_L$ and leaves the other bit(s) in $C_L$ unchanged.
That property allows a break under Chosen Plaintext Attack.