Is it a vulnerability (for message authentication) to have a variable iteration-count for PBKDF2? The scenario: A user clicks on an encrypted file, and enters his password, in order to decrypt and authenticate it using HMAC (when its key is derived using PBKDF2). If the iteration-count is fixed, it's deemed secure.

What if the iteration-count is read from the file, Is it still secure? I assume that it's secure in the sense that its encryption is fine. But what about its authentication?

I'm having a hard time finding a specific vulnerability, but the fact that the key derivation "algorithm" is not completely fixed (and can be changed by an attacker) seems insecure.

No, variable message iteration count (or more generally workfactor parameters) passed in the ciphertext (including in clear and unauthenticated) is not by itself a vulnerability, to either encryption or authentication, under the following reasonable assumptions:

The adversary can only get and manipulate the ciphertexts, and get plaintexts  (with the exception of those s/he is trying to decrypt); not alter the programs used, nor spy their execution.
PBKDF2 (or more generally a sound entropy-stretching function) is well-implemented, and used to convert password and salt to wide symmetric key(s) then used for symmetric encryption and message authentication. Here, "well-implemented" and "sound" includes:

The password-streching function does not exhibit much more collisions for different passwords than a random function for any iteration count (or more generally workfactor parameters) that can be parsed from the ciphertext (and leads to bearable execution time). For PBKDF2, an iteration count of 0 (or negative, if the encoding has provisions for that) should be rejected, as specified in RFC2898 / PKCS#5 v2.0 by
    c       iteration count, a positive integer .
An hypothetical implementation accepting an iteration count of 0 and in that case giving constant output (or one depending only on salt) would be vulnerable.
The code used for decryption and authentication is not sensitive to side-channel attacks made worse by some choice of the iteration count/workfactor parameters.

There is no other implementation goof (or backdoor, perhaps disguised as goof) that the introduction of the variable workfactor can trigger.
The symmetric encryption and authentication primitives are secure, assuming their wide key has enough entropy.

Argument (not a formal proof): With the password unknown, the entropy in the symmetric keys actually used by the verifier remains high (nearly that of the password or as limited by key width, whichever is lower), including under an attack where the workfactor has been altered. The best attack for the adversary remains to find the password, and the cost of that increases with the workfactor used for a ciphertext that the adversary can intercept and is encrypted or authenticated with the right password; other ciphertexts (including any that the adversary could build without knowledge of the password) do not help towards finding the password.

The main practical danger lies in the consequences of the increased complexity introduced by variable iteration count: the code is more complex, thus more likely to contain an undetected weakness.


CTR_DRBG versus OFB_DRBG As far as I know, in the development of ANSI X9.82, there was consideration of OFB_DRBG, a pseudorandom number generator based on block ciphers like CTR_DRBG, but it appears to have been rejected of left out of the final publication, much like MS_DRBG. Is CTR_DRBG safer than OFB_DRBG? If so, is this because OFB_DRBG would be susceptible to a known-plaintext attack?

No OFB_DRBG isn't directly vulnerable to attacks.

However from a theoretical standpoint there is one point speaking against it and in favor of CTR_DRBG.

Speed. CTR can be parallelized (can encrypt counters in parallel), OFB can't (encrypting state over and over again)

So the main reason is speed I'd guess and of course adding OFB_DRBG wouldn't have added anything to the portfolio, as CTR does the same job, but better.


Reversing decryption function involving XORs and bit rotations? I am trying to reverse this equation to find the encrypted number given to it. Here is the equation:

$$y = x \oplus n \oplus (x \ggg 3) \oplus (x \lll 7) $$

$\oplus$ is the bitwise exclusive or function
$a \lll b$ is $a$ bit rotated left by $b$ bits
$a \ggg b$ is $a$ bit rotated right by $b$ bits

$y$ is a known 32 bit integer
$n$ is a known 32 bit integer but unique for every $x$ and $y$
$x$ is the encrypted message and what I want to solve for, and it is an unknown 32 bit integer

I'll demonstrate a "brute" way of doing it; should work for any XOR-rot system. Please note that indices are $\bmod 32$.

You basically write your equation in 32-vector and matrix notation:

$$
\bar{y} = M\bar{x} \oplus \bar{n},
$$ or in Einstein notation (which, in my opinion, can make stuff more readable)
$$
y_i=M_{ij}x^j \oplus n_i,
$$ where the sum goes from $i=1\dots32$.

Now, the magic part (to solve the rotation) lies in finding the $32\times32$ matrix $M_{ij}$:

$$
M_{ij}=\delta_{ij}\oplus\delta_{(i+3),j}\oplus\delta_{(i-7),j},
$$ where $\delta_{ij}$ is the Kronecker delta symbol (the unit matrix):

$$
\delta_{ij} =
    \begin{cases}
            1, &         \text{if } i=j,\\
            0, &         \text{if } i\neq j.
    \end{cases}
$$
Now your problem is reduced to inverting $M_{ij}$ (which is a one-time static thing), and calculating

$$
\bar{x}=M^{-1}(\bar{y}+\bar{n})
$$


Does the generator (base point) is preshared between the sender and receiver in elliptic curve cryptography? Or the elliptic curve and the generator point are known to everyone?

Yes.

The curve and generator point are part of the domain parameters and therefore made explicit if you use a named curve.


Can FFT be useful in encryption of dicom images? I am doing a project on dicom images. I will be encrypting the DICOM image using AES-GCM algorithm. Before encrypting the DICOM image, i thought of taking FFT. Will it provide an advantage during encryption? if so can you explain?

I had a quick look and the images are already encoded with standard image enncoding algorithms, which means DCT and other appropriate transforms have already been used, e.g., as part of jpeg, tiff, mpeg,whatever.

I see no utility to applying an FFT on top of all this effort, neither from a security point of view.


Perfect secrecy with XOR & SHIFT? I have read that XOR provides perfect secrecy, when the key is perfectly random. However it's technically hard to generate truly random numbers, especially on computers, so that is why people use AES, Twofish and other cypthers.

So the conditions for using XOR are that the key has to be true random, and the keysize must be at least as big as the message.

What if we just use a very long key, to guarantee at least as much entropy as the message size?

For instance we need to encrypt 6 bits of message, then using a 32 bit pseudo random key, should have at least 6 bits of entropy in it. Or use even 512-bit key, if the RNG is very weak, to suit our needs. Then we XOR the first 6 bits.

Now the other 26 bits are leaking out, but if the attacker doesn't know the size of the input message, then it should not be a problem.

But if the attacker does know the size of the input, then we will also shift the output bits from the right to the left by n tiles, leaving p spaces between them. Lik this:

Obviously the n and p values are also random and secret choosen by us. So we would only need to keep the XOR key, the n and the p secret.

And after 1 shift operation, the message should be perfectly secret. The XOR already provides perfect secrecy, but the shift operation also hides the needle in the haystack.

Because how can an attacker brute force the original input if he doesn't even know what cypher we are using. So randomizing the cypher parameters is what I am suggesting here.

What is your opinion, is this a viable encryption system?

Hiding which cipher you are using means violating Kerckhoff's principle. That's actually an extremely common mistake. The problem is that such a cipher becomes very hard to analyze because you have to consider all the options for an attacker to learn parts of the system.

In general we don't analyze cipher designs on this website because it is too easy to come up with a random design which is probably broken but not totally obviously so. It wastes people's time to try and attack it. Cryptographers mostly don't care about new ciphers anyway. We already have good ciphers. Exceptions are made for very specific applications.


Why is authenticated CFB mode insecure? I read that the following adaptation of the CFB block cipher mode into an authenticated mode is prone to chosen plaintext attacks, yet Im still unsure how to prove it:

Let $P_1,P_2,\ldots P_n$ be the plaintext blocks, $C_1,C_2,\ldots C_n$ the CFB encrypted ciphertext blocks and consider the authentication tag is computed as:

$$ T = E_k(C_n) \oplus  P_1 \oplus P_2  \ldots \oplus P_n$$

(this is basically appending an extra block of plaintext containing the XOR of all plaintext blocks and using this final encrypted block as an authentication tag).

Can anybody point me out what is the major mistake in this?

One obvious thing that it is vulnerable to a known plaintext attack that truncates the known message.

This attack is quite simple; suppose the attacker knows a message $(P_1, P_2, ..., P_n)$ and the corresponding ciphertext $(C_1, C_2, ..., C_n, T)$ (using some IV; we don't care what it is).

Here is how the attacker can generate a ciphertext that would decrypt and validate to $(P_1, P_2, ..., P_k)$ for a $k$ of his choosing.

First of all, he can truncate the ciphertext $(C_1, C_2, ..., C_k)$; that will obviously decrypt into the message he wants; all he needs to do is compute the corresponding tag so that it would validate.

He can do this because we already knows that $C_{k+1} = E(C_k) \oplus P_{k+1}$; this is how CFB mode works.  Because of this, he can then compute the tag:

$T' = C_{k+1} \oplus P_1 \oplus P_2 \oplus ... \oplus P_k \oplus P_{k+1} = E(C_k) \oplus P_1 \oplus P_2 \oplus ... \oplus P_k$

And there, his job is done...


Schnorr signatures: multisignature support Schnorr signature is mentioned as a promising upgrade to bitcoin to improve scalability. It support multisignature, several signatures can be aggregated into a single, new signature. But I fail to find any information on how is this made possible mathematically.

Some of my questions on the statement "several signatures can be aggregated into a single new signature":

1) Is it true that the "several signatures" can be generated using different private key?

2) If (1) is true, the "single new signature" can be used to verify all the messages that are signed by different private key? How does this work?

Is there any paper published regarding to this topic?

Here is a simple-minded Ed25519-based multisignature or collective signature scheme, in which Alice and Bob each having their own private key, kept secret from one another, must work together to create a joint signature that a verifier knowing both of their public keys, or only a joint public key, can verify.  This is a simplification of a recent IETF internet-draft, draft-ford-cfrg-cosi, presently under consideration by the CFRG.

$\newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\concat}{\mathop{\Vert}}\newcommand{\U}[1]{\underline{#1}}$Let $p = 2^{255} - 19$, a prime; let $E$ be the elliptic curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$$ over $\F_p$ (edwards25519, the twisted Edwards curve birationally equivalent to Curve25519 used in the Ed25519 signature scheme); let $P$ be the unique $\F_p$-rational point on $E$ whose $x$ coordinate is 4/5 and whose $y$ coordinate is ‘positive’, and let $\ell$ be its order; let $H$ be a uniform random choice of function from byte strings to $\Z/\ell\Z$; let $\U Q$ be some byte string encoding of a point $Q \in E(\F_p)$.

To begin, Alice picks a secret scalar $a \in \Z/\ell\Z$ and a secret 32-byte hash key $h_a$, and shares the encoding of the point $A = [a]P$.  Bob does likewise with $b$, $h_b$, and $B$.  Their joint public key the encoding of is $A + B$.

An Alice/Bob signature on a message $m$ is the encoding of a point $R \in E(\F_p)$ and a scalar $s \in \Z/\ell\Z$ such that $$[s]P = R + [H(\U R\concat \U{A+B}\concat m)](A + B).$$

How do Alice and Bob create such a beast?  First, Alice computes $r_a = H(h_a\concat u_a \concat m)$ where $u_a$ is an independent uniform random 32-byte string, and keeps $r_a$ secret but shares $R_a = [r_a]P$; Bob does similarly with $r_b$ and $R_b$.  Then they each compute $R = R_a + R_b$.  Next, Alice computes $$s_a = r_a + H(\U R\concat \U{A+B}\concat m)\,a,$$ and Bob computes $s_b$ similarly.  Finally, to commit the signature creation, they jointly compute $s = s_a + s_b$ and reveal $R$ and $s$.

This is an Alice/Bob signature, because

\begin{align*}
  [s]P &= [s_a + s_b]P \\
       &= [r_a + r_b + H(\U R\concat \U{A+B}\concat m)\,(a + b)]P \\
       &= [r_a]P + [r_b]P + [H(\U R\concat \U{A+B}\concat m)][a + b]P \\
       &= R_a + R_b + [H(\U R\concat \U{A+B}\concat m)]([a]P + [b]P) \\
       &= R + [H(\U R\concat \U{A+B}\concat m)](A + B).
\end{align*}

Unlike a naive concatenation of two Ed25519 signatures which takes a net 128 bytes of storage, an Alice/Bob signature takes only 64 bytes of storage, and that remains so no matter how many additional signers you add.  Conveniently, the resulting Alice/Bob signature is also an Ed25519 signature under the public key $\U{A+B}$, so you can use existing Ed25519 verifiers to verify it.

(Security analysis is left as an exercise for the reader.  Hints: Suppose evil Bob knows Alice's public key $A$ before the two of them collectively
publish the joint key $P$.  What nefarious deed can Bob commit in that case?  If Alice's random number generator is wedged when she makes a signature so it returns the same $u_a$ each time, how can Bob exploit that to do something nefarious with Alice?)

This scheme has various properties:

Each party's part of the signature was generated by a different private key not known to the other parties.
All parties must agree to make the signature before it will be accepted by a verifier.  We could easily extend the definition of a signature to include a list of the signers, and have a verifier require some threshold of signers before accepting it, at the cost of a little extra space to store a signature (as in draft-ford-cfrg-cosi).
If we adapted it thus to a threshold scheme, the subset of possible signers who did sign it would not be anonymous to a verifier.

There are variations on the theme of multisignatures: are the signers anonymous to one another, are there thresholds, if there are thresholds is the subset of possible signers who did sign revealed to a verifier?  You'll have to look closely at exactly what Bitcoin's scheme is to see which properties it provides.  For further background, you might read Micali, Ohta, and Reyzin's paper introducing Schnorr multisignatures, or Bellare and Neven's elaboration on it.


what is the motivation behind quantum key distribution with Continuous variable? Quantum Key Distribution protocol is a technique that allow two parties to share common secret key for cryptographic purpose and defined as being secure, by definition. But I am still wondering what is the motivation behind quantum key distribution with Continuous variable ?

It's easier to work with a lot of photons in a stream than to work with a single photon at once.  This is explained in the paper introducing continuous-variable quantum key distribution.  (With apologies for the paywall.  Ms. Greene, tear down this wall!  Or read the arXiv preprint if you're not a rebel.)

P.S.  I originally answered the question as follows, with the above paragraph at the end, and the answer was accepted.  It spawned a long discussion in comments and chat, but, while it represents my perspective on the market for quantum key distribution products today in the context of information security and cryptography, it wasn't appropriate as an answer to the question as asked, about continuous-variable quantum key distribution in the context of the basic research program of quantum key distribution in physics.  I am leaving it here for context of the discussion:

  One word: money.

  Quantum key distribution networks serve no useful cryptographic purpose.

  They do not work without classical cryptography to authenticate the peers.
  The best speeds for quantum key distribution are measured at megabits per second rather than the gigabits per second achievable by classical cryptography on $100 mass-market CPUs.
  The widely advertised security guarantees founded on laws of physics are nonsense.

  But because rich governments are apparently easily bedazzled with mumbo-jumbo about laws of physics guaranteeing security, it is highly profitable for companies like ID Quantique and MagiQ Technologies to sell packages of snake oil at hundreds of thousands of dollars a pop.

  As for the specific case of continuous-variable systems...

  (Financial disclosure: I'm not getting a piece of the pie that ID Quantique and MagiQ Technologies are splitting.  But then I'm also not getting a piece of any pie in classical cryptography either.  In fact I'm pretty bereft of pie at the moment.)


What is the difference between "asymmetric key cryptosystem" "asymmetric cryptography" terminology? What is the difference between "asymmetric cryptography" and "asymmetric key cryptosystem"  terminology?

The basic definitions from Wikipedia.

  Cryptography or cryptology is the practice and study of techniques for secure communication in the presence of third parties called adversaries.

  In cryptography, a cryptosystem is a suite of cryptographic algorithms needed to implement a particular security service, most commonly for achieving confidentiality (encryption)

  Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys: public keys which may be disseminated widely, and private keys which are known only to the owner.

Asymmetric Cryptography is the general technology to study techniques for securing communication with public-key Cryptography. Eg. public-key encryption, digital signatures.

Asymmetric Key Cryptosystem is the suite of asymmetric cryptographic algorithms applied. Eg. RSA, ECC.


Encryption with Web Crypto API (SubtleCrypto) I want to end-to-end encrypt items in a stateless environment. These items have an identifier (random string). Now I want to add encryption by adding a random key. The URL could be https://server.tld/item#key which users can share with each other.
I want to only use Web Crypto API (SubtleCrypto) without any additional libraries.
My idea so far:

Generate random key: window.crypto.getRandomValues() window.crypto.subtle.generateKey()
Base64 encode/decode for URI fragment: btoa()/atob()
Create key object: window.crypto.subtle.importKey()
Encrypt/Decrypt using AES-CBC: window.crypto.subtle.encrypt()

Now I need an iv. I thought about using the hash of the item identifier via window.crypto.subtle.digest(). However AES-CBC needs 16 bytes.
Is it a good idea to use the first 16 bytes of SHA-1 (20 bytes long) as IV?

Is it a good idea [from a security perspective] to use the first 16 bytes of SHA-1 (20 bytes long) as IV?

It depends.
For CBC, the main requirements is the IV are that it should be unpredictable for the attacker. In particular, you should never ever use the same IV more than once for encrypting messages under the same key.
This implies that, in your system, it should be impossible to edit or overwrite these items. If editing an item is ever possible, then deriving the IV from the item identifier is definitely a bad idea.
If you want to support the editing of items, you should always generate a (pseudo-random) IV. (I.e. it should not be predictable for an attacker.)


What is the difference between Paillier additive homomorphic property and addition of two paillier ciphers Paillier has additive homomorphic property that states:

if two ciphers c1 and c2, are multiplied, and the result is decrypted, it is equal to addition of the  two plaintexts.

D(c1*c2)= m1+m2

Paillier also allows two ciphers to be added. If the addition result is decrypted, we get the addition of the two plaintexts also.

D(c1+c2) = m1+m2
The two operations lead to the same result i.e., m1+m2.
However the second operation is only mentioned in Paillier python  libraries and not in the formal definition of Paillier.
What is the difference between the two and if both are valid, is it true that Paillier has many-to-one homomorphic property.
The second property is mentioned in the python library pdf as follows:
Once this party has received some EncryptedNumber instances (e.g. see Serialisation), it can perform basic mathematical operations supported by the Paillier encryption:

Addition of an EncryptedNumber to a scalar
Addition of two EncryptedNumber instances
Multiplication of an EncryptedNumber by a scalar

In standard Paillier encryption

Property 1 really is:
$m_1=D(c_1)\text{ and }m_2=D(c_2)\implies D(c_1\cdot c_2\bmod n^2) = m_1+m_2\bmod n$.
Property 2 does not hold (but see final off-topic note).

As a consequence of property 1, for all $k$ in $\mathbb Z$, it holds $D({c_1}^k\bmod n^2)\ =\ m_1\cdot k\bmod n$. Proof for positive $k$ can be by induction, proof for negative $k$ follows from group properties of multiplication in $\mathbb Z_{n^2}^*$ and $\mathbb Z_n^*$.
Note: For integers $u$, $v$ and $w$, by definition of $u\bmod v=w$, that means $u-w$ is a multiple of $v$ and $0\le w<v$. The operator $\bmod$ has priority less than $+$ (thus less than $\cdot$) but more than $=$. Contrast with operator % in computer languages, which typically has priority more than +.

Once this party has received some EncryptedNumber instances (e.g. see Serialisation), it can perform basic mathematical operations supported by the Paillier encryption:

Addition of an EncryptedNumber to a scalar
Addition of two EncryptedNumber instances
Multiplication of an EncryptedNumber by a scalar

That's correct if we take addition and multiplication modulo $n$. Given $c_1$ and $c_2$ such that $m_1=D(c_1)$ and $m_2=D(c_2)$, and a scalar $k$ in $\mathbb Z$, any party knowing the public key $(n,g)$ can

Compute $c$ such that $D(c)=m_1+k\bmod n$, by encrypting $k$ and applying property 1. That is $c\gets c_1\cdot g^k\cdot r^n\bmod n^2$ for some $r$ coprime with $n$ (possibly $r=1$ if hiding $k$ and that $c$ derives from $c_1$ are pointless in the application).

Compute $c$ such that $D(c)=m_1+m_2\bmod n$, by application of property 1.

Compute $c$ such that $D(c)=m_1\cdot k\bmod n$, by application of the consequence of property 1.

The doc linked in the question is for a library that adds a wrapper on Paillier encryption. This is the part of the source doing the crypto. The library handles negatives and floating point numbers, as explained there, by

Restricting it's plaintext integers to range $\left[\,-\left\lfloor n/3\right\rfloor,\left\lfloor n/3\right\rfloor\,\right]$, with negatives mapped to $\left[\,n-\left\lfloor n/3\right\rfloor,n-1\,\right]$ of standard Paillier encryption.
Separating mantissa (encrypted with sign as above) and exponent (which remains in clear).

Off-topic: Python allows operator + to perform anything the programmer wants when applied to objects defined by the programmer. Both in the above library and the simpler code linked in comment, + for two ciphertexts has been coerced overloaded to call an internal function that makes use of property 1, thus performs a multiplication modulo $n^2$. Similarly, * has been overloaded to call an internal function that makes use of the consequence of property 1, thus performs an exponentiation modulo $n^2$.


X3DH Protocol - How can the receiver calculate the Shared Key? I'm reading about Signal Protocol and X3DH Protocol. In the X3DH Protocol, Alice sends a initial message to Bob encrypted with a Shared Key(SK). This SK is calculated using (this section):

DH1 = DH(IKa, SPKb)
DH2 = DH(EKa, IKb)
DH3 = DH(EKa, SPKb)
DH4 = DH(EKA, OPKB)
SK = KDF(DH1 || DH2 || DH3 || DH4)

Where IKa is the Alice's identity key, IKb is Bob's Identity key, SPKb is Bob's signed prekey, EKa is Alice's ephemeral key and OPKb is Bob's one-time prekey. All these keys are public.

In the next section they describe how Bob receives this message. Bob loads his private identity key and private one-time pre key and does the same steps as Alice does before to derive the SK. I couldn't understand how this SK calculated by Bob can decrypt the message sent by Alice. Alice uses only public keys and Bob uses his private keys. So my question is: How can the SK generated by Bob decrypt the message sent by Alice?

Alice uses Alice's private keys and Bob's public keys.

Bob uses Bob's private keys and Alice's public keys.

The notation DH(A, B) means that you combine whichever private key you know between A and B with the public key of the other.  So, when Alice computes DH(IKa, SPKb), she uses the private part of her long-term identity key IKa and the public part of Bob's signed prekey SPKb; when Bob computes it, he does it the other way around.


In two-dimensional even parity, how do we determine the corner parity bit? In two-dimensional even parity, how do we determine the corner parity bit?
Here's an example:

    1  0  0  1  y

    0  1  0  0  y

    0  1  0  1  y

    0  1  0  1  y

    x  x  x  x  z

Finding the parity bits where the x's and the y's is fine, But what about the parity bit in the lower right corner (z)? Do we look at the number of 1's in the corresponding column and/or in the corresponding row?

Do we look at the number of 1's in the corresponding column and/or in the corresponding row?

Yes; you can do it in whichever direction is most convenient; it'll be the same either way.

In either direction, the parity of $z$ will be the parity of the entire data matrix (1 if there are an odd number of 1's, 0 if there are an even number).


Standard deviation of gaussian noise in FHEW scheme I've got two questions regarding the paper FHEW: Bootstrapping Homomorphic Encryption
in less than a second.

First, the final error of a ciphertext after the refresh procedure is stated as following a gaussian of standard deviation:

$\beta = \sqrt{\dfrac{q^2}{Q^2}\left( \zeta^2 \cdot \dfrac{B_{r}^2}{12} \cdot nd_r\cdot \dfrac{q}{2} \cdot 2Nd' + \sigma^2Nd_{ks}\right) + \dfrac{\|\mathbf{s}\|^2+1}{12}}$

Then, after giving their chosen parameters they conclude that $\beta = 6.94$. I don't understand where this result comes from. Even if we ignore the (positive) first term in the square root, as $\|s\| \leq n/2$ (with $n=500$ in the parameters), the standard deviation $\beta$ should be way bigger than $6.94$... Where does this result come from?

Second, they then say that the probability of error per homomorphic NAND is $p = 1 - erf(r/\sqrt{2})$ where $r = \dfrac{q/8}{\sqrt{2}\beta}$. I know that $p$ is the probability to get a sample outside of the interval $[-r;r]$, but I don't get why they set $r$ that way. What does it represent?

Apologies for seeing this question just now. For your first question, well, there seems to be a typo: I should have written $\|s\|^2 \leq n/2$, and then we have $\sqrt{(\|s\|^2 +1) /12 }  = \sqrt{251/12} \approx 4.57$.

Now, we take 2 ciphertext with LWE error of std-deviation $\beta$, and sum them. Assuming independence the std-dev of the sum of the errors is $\sqrt 2 \beta$. For correctness, we need this sum of errors to be less than $q/8$ (Here, to save every last bit, we relax the naive condition stated in Lemma 7, and directly bound the sum $q/8 + |e_0 + e_1|$ by $q/4$ rather than bounding $e_0$ and $e_1$).

answer to comment on decreasing error via swapping KeySwitch and $\textsf{HomNAND}$

Just for the sake of this explanation, let me lie about the actual noise propagation, and assume that each operation HN and KS just add a constant to the quantity of noise, denoted $h$ and $k$.

The ``easy to describe scheme'' does $\textsf{HomNAND}(KS(X_1), KS(X_2))$, which leads to an error of the form $(x_1 + k) + (x_2 + k) + h = x_1 + x_2 + h + 2k$.

The ``better but less easy to describe scheme'' does $KS(\textsf{HomNAND}(X1, X_2)) $which leads to and error $(x_1+x_2+h) + k$. That is one ks less.

It turns out that even with the actual formula, we also gain a little bit on the final error with this trick.


Idiomatic description for an adversary in possesion of a quantum computer? I was wondering what the "accepted" way is to describe an adversary who:

is in possession of a quantum computer with which they can efficiently run quantum algorithms such as Grover's or Shor's algorithm.
Is polynomially bounded with regard to solving problems for which no quantum algorithms exist (e.g. finding hash collisions).

I was thinking of something like: quantum capable polynomial time bounded adversary. But I'm not sure whether being able to run quantum algorithms while being polynomial bounded is some kind of paradox?

I think what you are looking for is an adversary that

has access to a quantum computer, and
is efficient (i.e., runs in polynomial time -> independent of the property it tries to attack).

In this case, the common way to model the adversary is just as a polynomial time quantum algorithm. Note, it depends on the security model for the property that the adversary tries to attack (e.g., collision resistance, or EU-CMA) if it gets quantum access to a primitive or not, not on the adversary model. Schemes which achieve security in terms of traditional security definitions (i.e., with no quantum access to secretly keyed resources) against any polynomial time quantum algorithm are what we call post-quantum cryptography.

As in the traditional / classical setting, the question if a certain problem like the MQ-problem still is hard when considering such polynomial time quantum algorithms boils down to an assumption again: We do not have a proof that there exists no polynomial time quantum algorithm that solves MQ / SVP / [choose your favourite PQ problem] with noticeable success probability. However, we got reason to believe that no such algorithm exists.


Password hashing alogirthm simple enough to implement myself? I'm doing a password manager for a school project and I need to hash the master password for verification but I also need to write the hashing algorithm myself. However, most the algorithms I've come across are very complicated (except for MD5 but that's overly insecure).
Are there any slightly simpler hashing alogorithms which won't take too long to write and implement without libraries? (I'm using c#).

The PBKDF2 construction is simple to implement, and can be implemented with any underlying hash function.

Unlike modern password hash functions, the end result will be computationally intensive, but won't have any resistance against parallelization. Not requiring much memory means that ASICs can efficiently brute-force passwords hashed that way.


Passphrases, Dictionary attacks and 'bit shift' How much better would a passphrase be if you swapped the first letters of each word with a shift to the left:

"correct battery horse staple" becomes "borrect hattery sorse ctaple"

This would be simple to remember because you know all the  words but how much harder would this be for an attacker?

Further, we could try this with the first and last letters of each word producing:
"torrecb yatterh eorss etaplc"
(This at least reduces the chances that swapping the first letters will still result in normal English words, like 'hattery' in the first example)

How much harder would this make it to crack, is it worth the extra effort to remember?
Do dictionary attacks consider things like this?

If you ask a computer to pick a sequence of four words out of 10 000 (with replacement) uniformly at random, there are about $2^{53}$ possibilities; an attacker can expect to guess $2^{52}$ of them before getting the right one.  (For scale comparison, the Bitcoin network guesses and tries thousands of times more possible inputs than that to a hash every second.)

If you ask a computer to pick a sequence of four words out of 10 000, and one of the 24 permutations of four elements from the symmetric group $S_4$, then there are about $2^{53} * 24 \approx 2^{57}$ possibilities, although the number of distinct outcomes will dwindle once you account for alliteration.

If you ask a computer to pick a sequence of five words out of 10 000, there are $2^{66}$ possibilities, all distinct.

Which would you rather memorize: a permutation in $S_4$ causing words to be spelled differently, or another word?  I'd take the other word—in fact, I'd take six other words and invent a mnemonic for myself, to raise the number of possibilities above $2^{128}$ so an attacker has no hope of ever trying anywhere near enough passwords to guess correctly even in an offline parallel attack.

But whatever you do, don't try to pick the words and permutations yourself in your head.  Your mind is a terrible source of entropy.


What does it mean by 'cost' in CS? I've seen the word 'cost' being used several times in describing algorithms e.g. algorithm A costs more to compute than algorithm B. What does 'cost' mean in this sense?

There is not one commonly accepted definition of "cost" in cryptography, other than the definition of "cost" in a common dictionary; this is not jargon or slang to my knowledge.

Here is the most logical definition from Merriam Webster:

  b: the outlay or expenditure (as of effort or sacrifice) made to achieve an object

I'd say that "object" is not a particular object here, it should be read as "objective".

Usually "cost" refers to CPU time, commonly counted using the number of CPU cycles as unit for a particular CPU.

Depending on the context it may also refer to memory usage requirements or even energy expenditure. For hardware it may also relay to transistor count, die size or other costly elements within chip design.


mapping point on elliptic curve good evening guys,  let us suppose that elliptic curve is given by the following equation

$y^2=x^3-x+1  \pmod {127}$
on the following table  message  $9$ is converted   to the point on curve

if i insert directly   into equation , we  will get

$9^3-9+1=721$ and  $721$ mod  $127$ gives me 86, so how 91  is  given? what is relation between  $91$ and  $9$ ? please help me

After having read the "paper", which is probably just a "publication" the relevant student had to tick off, I'm pretty sure that a standard probabilistic encoding of messages to curve points was used, which is usually attributed to Koblitz. Written algorithmically:

Pick a message $m$ of 1 decimal digit length.
Set $i\gets 0$
Construct $x=m\cdot 10+i$. If $i\geq 10$ return with an error, this has probability around $2^{-10}$.
Compute $y=\sqrt{x^3+ax+b}\bmod p$ where $\sqrt\cdot$ is a modular square root, ie $(\sqrt x\cdot \sqrt x)\bmod p=x$. If no such $y$ exists, set $i\gets i+1$ and go to 3.
return $(x,y)$

Decoding a curve point can then be achieved by finding the decimal representation and cutting the last digit off.


How do P2P clients like uTorrent maintain authenticity of files? I am very new to concepts of cryptography so bear with me and feel free to fill in any information that may seem obvious but something you think someone may not know.

At first I was under impression that people use checksums to determine if files are legit or not. Which didn't make sense for obvious reasons… for example it's not hard to get the same sum for different numbers. So all a hacker has to do is make a file with smaller sum and then fill in the rest with garbage that way file would have equivalent checksum, but completely different content. Then later on, I found out that a checksum isn't used at all for this purpose.

So, what is used instead? I’ve been reading that some asymmetric functions are used and that files are encrypted using the destination's public key.

But I am unable to wrap my head around it and say* “ok, this will work in P2P”*.

Let’s say there are files $A$, $B$, $C$ among 10 seeders and I am the receiver. And chunks of them are being sent. How does uTorrent make sure that the chunk received is the chunk it should be getting. Sometimes there is only 1 seeder. So the option of checking what most people have is out of the question…

Thinking about it ,I am not sure how uTorrent or P2P clients really work after all.

For example:

Does each torrent file has some unique ID? If, how is it generated?
Am I correct to believe that all torrents connect to a server to get the list of all other people?

The only thing that always happens in BitTorrent is that the chunks (pieces of files) are checksummed/hashed with the SHA1 algorithm and compared against the values in the .torrent file. If all the chunks match their hashes, the file is correct – unless there's an SHA1 collision.

Additionally, some .torrent files contain MD5 hashes for each of the files which the client may or may not verify.

Finally, many clients support protocol encryption, where the traffic between peers is encrypted using Diffie-Hellman key exchange, SHA1 and ARC4. This does nothing to guarantee the integrity of files, it is mostly meant to avoid throttling by ISPs and make it more difficult for eavesdroppers to see what you are up to.


How can I verify a client's identity by requesting a digital certificate? So I am registering users and I need to know they really are who they say they are. More importantly that they represent the company they say they represent.

I was told I can ask them to send me a verisign (or similar) certificate. Basically the company (the more reputable ones) emiting certificates are meant to have already made sure that person is who he says he is and/or really works for Company X Inc.

So when a user fills in his registration form, I ask for an email address, name, company name,etc. and I also ask for this certificate to be uploaded (with a short list of the actual certificates I will accept, e.g. Verisign Pro EV.)

So how do I then use this file to verify that the certificate is valid?

Ok, I'll assume you have collected the data from the form. The next step is to confirm the user's identities based on the certificates they have. For this you have two options:

Send a S/MIME signed email to you which includes a chosen-by-you challenge in the message body. For this you could randomly generate a new email adress for each user so you can distinguish them if two happen to share some information. Also make sure that this random email address is in the message body because only that gets signed. Once you receive the email, you verify the certificate signatures, verify the root CA and the intermediates, verify the signature on the mail and verify the information in the certificat against what you had on the form for this specific person. If everything passes this person is confirmed. This assumes the user can use their certificate for e-mail signing.
Run a TLS client authentication. For this you'd give each user a random link when he has completed the form. Next he opens that link, the web-server will trigger a TLS client authentication and the TLS protocol will verify that the user has a) access to the private key of the certificate, b) will take care of all the signature verifications and whatnot and c) will verify that the cert chains up to a trusted root that you explicitely set up to accept for the client authentication. Following that your application-layer should get access to the client certificate information from your TLS implementation and need to verify that all the fields in the certificate match with the expected values from the form. This assumes the user's certificate is configured to be used with the browser which is (usually?) less common.

  So how do I then use this file to verify that the certificate is
  valid?

You don't without interaction. The certificate was issued to the holder of the private key associated with the public key in the certificate. This person is guaranteed to be the person from the certificate. If you just have the certificate you don't know that the person uploading it is in possesion of the secret key and thus you don't know whether this is indeed the "legitimate owner" of the certificate, thus you need one of the above approaches (which both shouldn't be too hard to implement).


How to interpret Berlekamp-Massey algorithm? I'm trying to find a way to understand the process of the Berlekamp-Massey Algorithm. But I'm struggling in understanding the fourth step of the process, which is $B^{(r+1)}(x) = A^{(r)}/\delta^{(r)}$. I found this algorithm from this paper, "VLSI Architectures for Reed-Solomon Codes: Classic, Nested, Coupled, and Beyond". However, I don't know what this step is doing. Can anyone explain to me the purpose of having this step?

Too long for a comment.
The Berlekamp Massey algorithm is a tour de force. It has the names of two Shannon award (top information/coding theory award for lifetime contributions) recipients attached and it is quite subtle.
The step you point to is a way of correcting the discrepancy between the sequence the current polynomial would generate and the actual sequence by modifying the polynomial.
Dilip Sarwate has a nice answer on this with somewhat different notation.
Berlekamp-Massey to construct minimal LFSR
The textbooks by Richard Blahut also explain the BM algorithm. The one called “Fast algorithms..” may be the most detailed.


Time taken for a brute force attack on a key size of 64-bits You can do $2^{30}$ encryptions per second and the key size is 64 bits.

$2^{64}/2^{30}$ should give me the time taken for a brute force attack?
What if you double the key size?

How can I calculate the maximum and average time taken for such an attack.

Well, that's simple: $2^{64}/2^{30}$ is indeed correct. And since $2^{64}/2^{30} = 2^{64 - 30} = 2^{34}$ then that would be the answer. A simple recalculation would give you approximately 545 years. As you can see, 64 bits is pretty much on the border of being cracked by general computers. It is also about the same size as the SHAttered attack; these kind of attacks scale well, so just renting 640 cores for a year in a cloud service would probably do it.

Brute force basically scales linearly with the amount of keys. However, we're doubling the key size here, not the amount of keys. Growing the key size exponentially grows the amount of possible keys. It's a bigger step to go from 10 to 100 as it is to go from 1 to 10, both in decimals as in binary calculations.

545 years would however be the maximum time it would take to find a key by trying all of them. On average you'd need half of that time using a single core as the key may be either on the lower half or higher half of the key space (whichever way you split it in two equal size parts, as each key should be equally likely). Each additional bit in the key size doubles the key space. That means you could subtract a single bit from the key size to find out the average time it costs to brute force the key.

The calculation required to find out the time it takes to brute force a 128 bit key isn't that more complicated: $2^{2 \cdot 64}/2^{30} = 2^{128}/2^{30} = 2^{128 - 30} = 2^{98}$. The outcome of course is rather different though; you'd now need $10^{22}$ years. Or around 700 billion times the current life-time of the universe to try all the keys. Or 350 billion times the life of the universe if you average things out (yeah, right).

Then again, according to WolframAlpha $10^{22}$ years is only 3.3 times the half life of Calcium-76 so there may be some calcium atoms left to witness the end result. Again, you can drastically reduce the time by adding processors. However, you'd need too much processors and energy to bring it back to a value that is possible to crack in a life time. Better not try to brute force a properly randomized 128 bit key then.

Important: it may be that you're not trying to find the value of a single key, but you're trying to find the value of one of a million keys. This, of course, it much easier because the chance of finding one quickly increases. This, and the possible advance of quantum computing, may be enough reason to go for a 256 bit key strength.


Increasing Entropy of Limited Information / ID Supposed that I get an ID from third party (in this case, Telegram ID which is  the range $-2^{31}$ to $2^{31}-1$). I want to store the ID securely and privately into my database by hashing it. I don't really care what the ID is, but I do really want to store the ID uniquely without actually storing the real data.

The problem is the entropy is pretty small (32-bit). Any people can get the real ID by brute forcing it. Also it is impossible to ask user to create a passphrase (or something like that) to make a derivative key, since I only get data from API and not interacting to it. I tried to figure out salting it, but since the main problem is the entropy is too small, I don't think it might work as expected.

HashIds is not a solution because the ID comes from third party.

How should I store the hash so that the hash won't be easily bruted-force? Currently, I am using SHA-512 to hash the ID.

Edit: for clarification

I can't store plain ID to database so that I must hash it
I don't need to recover original ID, but I need to check whether the hashes ID exists or not in DB, regardless the original ID
This has nothing to do with user. Yes it was the user ID from third party, but it is no way for user interacting with it. Thus, it is impossible to ask user for a pass phrase or something like that.

To sum up, I need to hash the ID and making it harder to brute force. Is it possible even if attacker try to brute force the entire 32 bit entropy?

I tried to figure out salting it, but since the main problem is the
  entropy is too small, i don't think it might work as expected.

With your "salt" being a long, high-entropy and secret blob, it should work alright.

But even more important, don't use a single SHA512. SHAs are fast, that's bad if you want to prevent bruteforcing. There's eg. PBKDF2 or bcrypt.


Does RSA work for any message M? I decided to read the original RSA paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystem because of a question I had about RSA (which is not the question I'm about to ask, but may be a question on here at some time) and came across something I had never seen before in any textbook description of RSA (Note: this comes from the beginning of Section VI of the paper).

for any integer (message) $M$ which is relatively prime to $n$,
$M^{\phi(n)} \equiv 1\pmod{n}$

The part I don't recall ever hearing in class, or coming across in a text book, or seeing in any description of RSA I've ever read is that $M$ and $n$ must be relatively prime.
So, I decided to play around with a toy example of RSA to see what would happen. I use $p=13$, $q=31$, $e=7$ and $M=2p=26$ (for completeness: $d=103$, $\phi(n)=360$, $n=403$).
I observed the following using my toy instance of RSA: $M^e\equiv M\pmod{n}$, $M^e\equiv 0\pmod{p}$ and $M^e\equiv M\pmod{q}$.
Do these equivalences hold for all $M,p,q$ when $M$ and $n$ are not relatively prime? How would I prove this? What is the real-world effect of this?

Yes, (textbook) RSA works for any message $M \in \{0\dots n-1\}$, in the sense that the decryption procedure recovers the original message; that is $\left((M^e\bmod n)^d\bmod n\right)=M$. For this to hold, we need to assume $p\ne q$, a requirement not formally stated in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem, but true with overwhelming odds given the method suggested to generate $p$ and $q$, and always true when following the recommendation given that $p$ and $q$ differ in length by a few digits.
An easy proof is to consider $Z=\left(M^e\right )^d-M$; show $Z\equiv 0\pmod p$ and $Z\equiv 0\pmod{q}$, by using Fermat's Little Theorem and the assumed relation between $e,d,p,q$ (see detailed proof below); then, since $p$ and $q$ are distinct and prime, and divide $Z$, their product $n$ divides $Z$; thus $Z\equiv 0\pmod{n}$. Q.E.D., thanks K.G.
Note: in general, $M^e\equiv M\pmod{n}$ does not hold.
Note: if $p=q$, the cryptosystem is totally unsafe. Independently, those rare $M$ that are a non-zero multiple of $p$ are modified by encryption followed by decryption.

Detailed proof (following another question): we want to show that $Z=\left(M^e\right )^d-M$ verifies $Z\equiv0\pmod p$, that is $\left(M^e\right )^d-M\equiv 0\pmod p$, that is $M^{e\cdot d}\equiv M\pmod p$. Since $d$ and $e$ are integers greater than $1$, this holds if $M\equiv0\pmod p$; it remains to prove it only when $M\not\equiv0\pmod p$, which we assume in the following.
The original RSA article constructs $d$ and $e$ with $e\cdot d\equiv1\pmod{\phi(n)}$, where $\phi$ is the Euler totient, also noted $\varphi$; while modern expositions of RSA, including PKCS#1 of RSA Security, often use $e\cdot d\equiv1\pmod{\lambda(n)}$, where $\lambda$ is the Carmichael function. We hypothesized that $p$ and $q$ are distinct primes, thus $\phi(n)=(p-1)\cdot(q-1)$, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. Thus $p-1$ divides $\phi(n)$ and $\lambda(n)$, and for either construction of $d$ and $e$ it holds that $e\cdot d\equiv1\pmod{(p-1)}$. Since $e$ and $d$ are integers greater than $1$, it therefore exists a positive integer $k$ with $e\cdot d=k\cdot(p-1)+1$.
We can thus write $M^{e\cdot d}$ as $M^{k\cdot(p-1)+1}=\left(M^{p-1}\right)^k\cdot M$. By Fermat's Little Therorem, since $p$ is prime and $M\not\equiv0\pmod p$, it holds that $M^{p-1}\equiv1\pmod p$. It follows that $M^{e\cdot d}\equiv M\pmod p$.

Addition following comment: RSA is sometimes presented in $\Bbb{Z}_n^*$ because:

The early version of Rivest, Shamir, and Adleman's paper did.
As pointed there, that's not a serious practical limitation because so few messages are excluded.
That removes any hypothesis on $n$ and thus makes the proof simpler; by contrast, we need a square-free $n$ in order for RSA to work in $\Bbb{Z}_n$.


Is this a correct SSL explanation in layman's terms? I'm looking to provide a basic / layman's explanation of SSLs to clients and want to be sure it is correct. My explanation is below and would appreciate any feedback / corrections.

Basically, the SSL certificate provides a secure and encrypted connection between your web site’s server and the user browsing your web site. Without an SSL the data exchanged between the web site and the user can be intercepted, which includes the web site contents and any form submission details.
The contents of a web site you visit may NOT actually be the content from the site you are on if it has been intercepted, and the form details submitted may not only go to the owner of the web site, but to the hacker intercepting the transmission. Although the likelihood of this happening is low, it is still possible.

Is this correct, or am I missing something somewhere?

A TLS/SSL connection is possible if both the Web server and the Web browser are configured to recognize the same root certificate authority (CA).  Basically it's like the server telling the browser, "Such-and-Such root CA, or one of its subordinates, says that I'm OK" and the browser responds, "Any friend of Such-and-Such root CA is a friend of mine.  Trusted!"


Anonymizing a group chat I wonder if it's possible to have a peer-to-peer group chat protocol, where anybody is free to join the chat and broadcast with a chosen username to all others who have joined it, but with a strong anonymization property.  The property desired is that it is impossible, or at least difficult, for a man-in-the-middle to determine which IP address is associated with each username in the chat.  To be clear the man-in-the-middle is able (like anyone else) to join the chat and observe everything being said, and he can also be assumed able to monitor all transmissions of at least some members of the chat.
Naturally, the timing of packets could give away who is who, so it would be necessary for all users to be sending packets at regular intervals to hide which users are actually speaking.
If the chat system uses a server, the man-in-the-middle can be assumed to have access to the server.  So it's no good to simply encrypt all messages between each user and the server.
I'm thinking about a scheme where users are constantly passing "pieces" of messages between each other, and trying to assemble pieces into completed messages by XORing recent pieces, in a way that it's not clear who first sent all the pieces required for a message.  Each peer to peer link could be encrypted with the recipient's public key.
However, the man-in-the-middle may be free to create as many users as he wishes, which might defeat this scheme.  If man-in-the-middle users greatly outnumber other users, then the man-in-the-middle can trace most of what's going on.
Is it possible?

You are essentially describing instant messaging via onion routing or garlic routing.  Tox is an example of such a protocol. Tor Chat is another.

In an onion network, messages are encapsulated in layers of encryption, analogous to layers of an onion. The encrypted data is transmitted through a series of network nodes called onion routers, each of which "peels" away a single layer, uncovering the data's next destination. When the final layer is decrypted, the message arrives at its destination.

Below is a simple illustrated description of onion routing (taken from Wiki).

In this example onion, the source of the data sends the onion to Router A, which removes a layer of encryption to learn only where to send it next and where it came from (though it does not know if the sender is the origin or just another node). Router A sends it to Router B, which decrypts another layer to learn its next destination. Router B sends it to Router C, which removes the final layer of encryption and transmits the original message to its destination.

This does not completely defeat attacks, but if implemented correctly it should be difficult to de-anonymize users and interpret traffic.  The arrest of silk road creator Ross Ulbricht suggests that with enough desire, time, and luck the FBI could catch you.  But even then, you'd probably need to make some mistakes along the way.  And obviously the FBI are not your average man in the middle.


Why is using an authenticated AES mode better for in-place data protection? I always see people warning not to use unauthenticated modes of operation like CBC for AES . Why is that so ? I mean if you use  AES-CBC with a random IV you will most likely secure your data . So for what do you need MAC / authenticated modes like GCM for your files . If you cant assure that your data is tampered with on your own hard drive you are screwed anyway .

EDIT :

This question was about in place encryption . I understand the relevance of Authenticated stream ciphers like GCM in the context of sending data .

For CBC mode, the issue boils down to the fact that you cannot detect if a man in the middle modified the message. The data is still confidential, the man in the middle cannot read it without the key, but they can modify it, and it still would be decrypted at the recipient.

Ideally you want to ensure data integrity. For CBC mode in particular, you can perform the CBC byte-flipping attack. Lets assume a message is encrypted, and you know a single block. You can convert that block into any block you desire, because of how CBC chaining works. The plaintext of the next block is xor'd with the ciphertext of the previous block. So by altering the previous blocks ciphertext, you change the block that the plaintext decrypts to. Thus in exchange for getting one block to decrypt to gibberish, an attacker can control what the next block decrypts to. This is undesirable. Hence Authenticated modes such as CCM and GCM are used.

An example use-case of GCM mode when sending data over the internet between a client and a server, such as in TLS. You don't want CBC byte flipping to be a possibility. You want to ensure that the data you decrypt is in fact what the person at the other end sent to you.

Also to your point about encrypted hard-drives, being able to have evidence of any data tampering is a desirable property. CBC byte flipping attacks would only be evidenced by file corruption when looked at through its respective program. Its possible that the tampered file could be rendered as valid.


Is Encryption without knowing the input directly possible at all? I know the question is rather unusual, but let me clarify what I'm searching for:

There is one person, lets call her $Alice$. $Alice$ has $n$ plaintexts $t_1..t_n$ and $n$ public keys $pk_1..pk_n$ of other persons.

Now $Alice$ has to encrypt one $t_i$ with a $pk_j$ for arbitrary $i,j$. Each key and plaintext should only be used exactly once.
After everything has been encryptied $Alice$ should not have any means to determine which $t_i$ was used to generate one of the outputs.
There are $n$ other players to which the keys $pk_1..pk_n$ belong. The other players all can see the encrypted results of $Alice$s encryption operation and nothing else. Obviously every one of them can only decrypt the plaintext encrypted with his or her private key.

Alice should be able to prove to every other player, that she does not know which plaintext got encrypted with which key.

Is that possible at all? I possibly left something out one needs to know to hint me to a proper solution, in that case please leave a comment and i try to provide the Information.

(Sorry for my mediocre english)

What you're describing sounds a lot like mental poker.  That is, your Alice has a number of messages ("cards") that she wants to shuffle and deal to the other players, in such a way that she can prove to the other players that she does not know who got which cards.

Various protocols have been proposed for mental poker; see the linked Wikipedia article for some examples.  Apparently, there currently exists at least one practical and secure implementation of such a protocol.


Are Paillier and El Gamal encryption schemes secure against quantum attacks? I was wondering if there is a security difference between Lattice based homomorphic encryption schemes versus an partially homomorphic encryption scheme like Paillier, and El Gamal encryption schemes especially with respect to the security against quantum attacks?

Sure there's a difference between Paillier and ElGamal as opposed to lattice-based cryptography regarding quantum attackers.

Paillier's security is broken as soon as you can efficiently factor large integers which is "easy" using Shor's algorithm. This is caused by the fact that you can easily recover the private from the public key by factoring $n$.

ElGamal's security is broken as soon as you can efficiently compute discrete logarithms which is "easy" using Shor's algorithm. This is caused by the fact that you can easily recover the private from the public key by finding the $x$ such that $\alpha^x\equiv \beta\pmod p$ given everything but $x$.

With lattice-based schemes it's a bit more interesting. Some schemes, like NTRU, can hold up against quantum attackers, while others not so much, like one invented and broken by GCHQ (PDF).


UDP and AES with C++ I'm implementing different applications that will use UDP to exchange real-time data, thus a low impact on performance is very important. This system will not be connected to the Internet so I just need a symmetric encryption mechanism and one option would be AES-128. I am googling a lot but I am not finding a lot of material about the combination of AES, UDP and C++, is it not used much? Any resources would be really appreciated!

Would DTLS be an appropriate choice for this case in this private LAN far away from the internet?

I've posted a similar question on Information Security SE with more details (after the answers here came in).

Consider using Noise.  If that's too heavy, consider using NaCl crypto_secretbox, at least.

Now that we've got that out of the way: Write down a design document that articulates what you're trying to enable the legitimate parties to achieve with what resources, enumerates the powers of an adversary, and identifies the security properties you hope to guarantee in the face of an adversary.  Do this without mentioning cryptography!  You need to be specific about what resources the adversary can subvert and how—read packets on the wire, replace them, act maliciously to peers in some way—and specific about what you want to guarantee they can't do in spite of those powers.

Then you can use that design document decide what cryptography to use to provide those security properties, and anyone else studying your system can use that design document to assess whether you did it sensibly.  Simply putting the letters A-E-S or D-T-L-S in your application means approximately nothing other than that you used everyone's favorite pseudorandom permutation family or the unloved cousin of a protocol whose family gave us Heartbleed.


RSA Signature - Multiple Use Weakness I cite from Fundamentals of Computer Security (Chapter 7 on Digital Signature, Paragraph 7.3 on RSA Signatures, page 289):

  Multiple uses of the RSA Signature scheme tend to weaken it. The way out is to make subsequent signatures dependent on those previously generated.

Why is this?
Does it affect also the RSA Encryption scheme, or is it a weakness that comes from the knowledge of the message (and therefore affects only Signature schemes)?

It's hard to say from that out-of-context statement.  It may be that they were talking about signatures with obsolete padding schemes (such as ISO 9796-1), or possibly just raw RSA (zero padding, which is even worse); it is possible with these padding, if you observe enough signatures, you could come up with a forgery.

On the other hand, there is no known weakness if you generate RSA signatures using a modern padding scheme, either PKCS #1.5 (which, I suppose, is a bit hard to call modern) or PSS.


Attack of an RSA signature scheme using PKCS#1 v1.5 encryption padding My best interpretation of this question is that Java's crypto API has been subverted to perform RSA signature using PKCS#1 v1.5 encryption padding.

Assume the signature $S$ of a message $M$ is obtained by:

hashing $M$ using SHA-1, yielding the 20-byte $H$;
generating a 105-byte uniformly (true) random $R$;
forming the 128-byte $P=\text{0x00}||\text{0x02}||R||\text{0x00}||H$;
forming the 128-byte $S=P^d\bmod N$ where $(N,d)$ is a 1024-bit RSA private key.

I assume that verification of an alleged signature $S$ of alleged message $M$ is as follows:

rejecting the signature unless $S$ is 128-byte with $S<N$;
forming the 128-byte $P=S^e\bmod N$ where $(N,e)$ is the 1024-bit RSA publickey;
hashing $M$ using SHA-1, yielding the 20-byte $H$;
accepting the signature when the left 2 bytes of $P$ are $\text{0x00}||\text{0x02}$, and the 21th byte from the right of $P$ is $\text{0x00}$, and the right 20 bytes of $P$ are $H$.

Note: conversion from bytestring to number, and vice-versa, is per the big-endian convention.

What attacks are there on this scheme, easier than factoring the public modulus?

There's an easy attack against public keys with $e=3$.

Here's how it works; the attacker selects an arbitrary message $M$ that hashes to an odd value $H$ (or, more generally, a $H$ of the form $k8^n$ for odd $k$).  Since half of the potential messages hash this way, this is not a severe limitation to the attacker.

Then, the attacker looks for a perfect cube between $2\times2^{1008}$ and $3\times 2^{1008}$ and whose lower 136 bits are $0x00 || H$, that is, a cube $C$ between $2\cdot 2^{1008}$ and $3\cdot 2^{1008}$ and for which $C \equiv H\  (\bmod\  2^{168})$.  Such a cube is easy to find, just compute $x = \sqrt[3]{H} (\bmod \ 2^{168})$ (with the $H$ of the form we selected, such a value always exists), and then select a value $X$ in the range $\sqrt[3]{2\cdot 2^{1008}}$ to $\sqrt[3]{3\cdot 2^{1008}}$ with $X \equiv x\  (\bmod\ 2^{168})$; $C = X^3$ is such a cube.

The value $X$ is be a valid signature for the message that hashes to $H$; the verifier will compute $X^3 \bmod N$ (which will be precisely $X^3$, and then verify that the first two bytes are $0x00$ $0x02$, and that the right hand bytes are $0x00$ $H$.

This attack can be generalized (for this key size) to $e=5$, and can be extended to handle the case where the verifier also checks to see if there are any zero pads in the random pad.


RSA PKCS#1, v1.5 padding output If I make use of RSA PKCS#1 in v1.5 what padding length is used. Basically, it is not allowed that the plaintext is bigger than the modulus. But what if the length in bits is the same (padding to modulus size) but then the plaintext value is bigger than the modulus. How to avoid that?

The overhead of PKCS#1 v1.5 padding is at least 11 bytes. 8 of these bytes are a random value in the range [1..255]. This makes it unlikely that the same ciphertext is generated for identical plaintext input. Note that the padding is placed before encryption. The output size will be identical to the modulus size (in bytes, rounded downwards, if applicable).

Or, as PKCS#1 v2.1 puts it:

  Input:

  (n, e) :  recipient's RSA public key (k denotes the length in octets
              of the modulus n)

  M  :      message to be encrypted, an octet string of length mLen,
              where mLen <= k - 11

and, in case the plaintext message is larger:

  Error: "message too long"

(which in API's is translated into a runtime specific error, e.g. an Exception - which may well have a different error text - in Java).

Note that PKCS#1 v1.5 padding is used both for encryption as well as for signature generation. The v1.5 paddings used are however different for encryption and signature generation. I've focussed on padding for encryption as the padding for signature generation is performed over a message digest (secure hash value). Hash values are limited in size of course, so for practical key sizes the padding overhead doesn't matter.

Notes:

usually the RSA padding is simply used to wrap a newly created symmetric data/session key, which in turn is used to encrypt the data (i.e. the overhead doesn't matter much); this is called a hybrid cryptosystem.


How many field operations are needed when you compute kG in elliptic curves with a multiple additions or the double-ans-add-algorithm? For an assignment, we have to calculate how many field computations are needed to calculate kG in an elliptic curve. They want us to show this for two different ways of calculating kG. The first way:

2G = G+G

3G = 2G + G

...

kG = (k-1)G + G

The other way is the double-and-add algorithm.

The question:
Compute how many field operations (multiplications, additions, subtractions, divisions) we have to execute for both algorithms, assuming that we use affine coordinates for the elliptic curve.

I ran into some problems while trying to answer this question and I cannot quite seem to find the answer here or on some other part of the internet (I have to admit I'm not that good at googling).

Can anyone help me with this?
Thanks in advance

Given two points $P_1 = (x_1,y_1)$ and $P_2 = (x_2, y_2)$ on an elliptic curve $y^2 = x^3 + ax +b$, the sum $P_3$ of $P_1$ and $P_2$ is $P_3 = P_1 + P_2 = (x_3,y_3)$ where $x_3 = \lambda^2 - x_1 - x_2$ and $y_3 = y_1 + \lambda(x_3 - x_1)$ where $\lambda = (y_1 - y_2)/(x_1 - x_2)$ if $P_1 \neq  P_2$ and $\lambda = (3x_1^2 + a)/(2y_1)$ if $P_1 = P_2$.  The case $P_1 \neq P_2$ is called point addition and the case $P_1 = P_2$ is called point doubling.

Let $M, A, S, D$ denote the operation of multiplication, addition, subtraction, and division in the underlying field.  Then we see that with the previous formulas,

the evaluation of $x_3$ requires $1M + 2S$;
the evaluation of $y_3$ requires $1M + 1A + 1S$;
the evaluation of $\lambda$ requires $2S + 1D$ if $P_1 \neq P_2$ and $1M + 4A + 1D$ if $P_1 = P_2$ [I assume here that $3x_1^2$ is evaluated as $x_1^2 + x_1^2 + x_1^2$ ($2A$) and $2y_1$ as $2y_1 = y_1+y_1$ ($2A$)].

Hence, we obtain that

a point addition requires $2M + 1A + 5S + 1D$;
a point doubling requires $3M + 5A + 3S + 1D$.

Back to your question now,

the evaluation of $kG$ requires $k-1$ point additions using the first method, that is, $2(k-1)M + (k-1)A + 5(k-1)S + (k-1)D$;
letting $\ell$ the binary length of $k$ (i.e., $\ell = \lfloor\log_2 k\rfloor + 1$) and $h$ the Hamming weight of $k$ (i.e., the number of bits equal to $1$ in the binary representation of $k$), the evaluation of $kG$ requires $\ell$ point doublings and $h$ point additions using the double-and-add method, that is, $(3\ell+2h)M + (5\ell+h)A + (3\ell+5h)S + (\ell+h)D$.  On average, for a random $\ell$-bit integer $k$, we have $h = \ell/2$; in which case, we get $4\ell M + 5.5\ell A + 5.5\ell S + 1.5\ell D$.

It is worth noting that the first method is completely impractical for cryptographic applications since $\ell$ is typically $256$ and thus $k \approx 2^{256}$.


Determining collision resistance of a function? I am having trouble trying to understand if the function is collision resistant.  As I understand it, preimage resistance means that it is hard for an adversary to find two messages that produce the same digest, and second preimage resistance means it is hard for an adversary to find a message that produces the same digest for a given digest.  And collision resistance just implies both things.  So for the following problem, I don't understand how I would determine if the function exhibits any of the resistances?

The function f(x1,x2,...,xn) = x1 ⊕ x2 ⊕ ... ⊕ xn takes an input of n blocks, each m bits long, and produces an output of length m bits. Is this function: preimage resistant, second preimage resistant, or collision resistant?

As I understand it, preimage resistance means that it is hard for an adversary to find two messages that produce the same digest

Nope: collision resistance means that it is hard for an adversary to find two (distinct) messages that produce the same digest.  Preimage resistance means that, given a hash output, it is hard for an adversary to find a message that hashes to that value.

  second preimage resistance means it is hard for an adversary to find a message that produces the same digest for a given digest.

Close; second preimage resistance means that, given a message, it is hard to find another message that hashes to the same value.

  Is this function: preimage resistant...

Let's consider this; suppose we get a target value $M$; how hard is it to find inputs $x_1, x_2, ..., x_n$ with $f(x_1, x_2, ..., x_n) = x_1 \oplus x_2 \oplus ... \oplus x_n = M$ ?  Hint: suppose we select $x_2, ..., x_n$ to be 0, how difficult would it be to find an $x_1$ with $f(x_1, 0, 0, ..., 0) = M$?


Do random oracles are called even by honest users in the PAK protocol [BMK00]? In the full-length proof of PAK scheme, the authors made extensive use of random oracles to extract (guessed) password from the messages generated by the real world adversary for the ideal world simulator.

Questions:

Are all the random oracle calls $H_i(\cdots)$ in the real world protocol (even called by honest users) controlled by the simulator?
Does the simulator need to make responses for the requests of honest users via the real world adverary's delivering?
Does the simulator make use of the status of honest users? For example, A (either the honest user or impersonated by the real world adversary) sends a password to B and B sets the status of himself as accept or reject. Is B's status watched by the simulator and the real world adversary?
Why the password-extraction from real world messages is so imporant in simulation-based proofs? Is it indeed some kind of zero-knowledge proof for showing these password-related messages in the real protocol are as zero-knowledge as the messages in the ideal world? (as the authors suggested to use NIZK in place of random oracle)
Is there any weaker proof method (which, however, still guarantees us security practically), especially for the password-authenticated key exchange area?

In the real-world protocol there is no simulator. There is a real-world adversary and it has access to the exact same (random) oracle as the honest parties. The simulator controls the random oracle in the ideal-model simulation only.
This is not required by the definition, but is the way that things work. Essentially, the simulator plays the role of the honest parties to the real adversary. Of course, it does this without knowing the honest parties' inputs and outputs.
This depends on what information the ideal adversary/simulator gets about the status of the honest parties. If the ideal functionality provides the status to the ideal adversary, then it knows it; otherwise, not.
The natural way to define the ideal functionality is for the parties to send their password to the ideal functionality and if they match then a random session key is provided to them both. In order to simulate a real execution in the ideal model, the simulator must therefore send the ideal functionality the passwords that the adversary (implicitly) uses.
You can define "game based definitions" not via an ideal functionality. In any case, proving the security of password protocols without any setup (like a CRS or PKI) is very difficult. Proving without a random oracle is even harder.

Overall, it seems that you could benefit from taking a step back from PAKE and looking at how ideal/real simulation proofs work. Here is an answer that I wrote that tries to give a bit of an explanation. However, you really need to read some more basic papers. (PAKE is hard place to start.)


Is It Safe to Reuse the Same Salt in Bcrypt Password Hash (Specifically for Chaining Hashes) As explained in my previous question, I want to develop a scheme which would be able to increase the password hash strength without the user password.

According to Thomas Pornin it should be safe to chain BCrypt hashes to generate a new, more expensive hash. I disregarded the handling for the salt in the previous question so he warned to be careful about that.

To reiterate, I basically want to do the following:

bcrypt_hash_0 = bcrypt(pw, salt_0, work_factor_0);
bcrypt_hash_1 = bcrypt(bcrypt_hash_0, salt_1, work_factor_1);
...
bcrypt_hash_n = bcrypt(bcrypt_hash_n-1, salt_n, work_factor_n);

Possible Handling for the Salt

Let's assume I have a BCrypt function, where I can manually choose the salt. salt_0 is the salt for the initial hash, salt_1 the used salt for the chained hash which produces bcrypt_hash_1 and so on.

Option 0: Reuse the Same Salt

The most simple approach is just to reuse the same salt. This makes it quite easy to handle but it is unclear if this approach introduces severe security issues (is there a research on that?)

Option 1: Create a New Salt

The naive fix to Option 0 would be to create a new random 16 byte salt for each iteration. Unfortunately, this increases the hash output message since in addition to salt_0, the new salt_1 must be appended (etc.). This is probably fine for a single chain, but using it to chain multiple hashes, the message will get quite impractical. From the security side, it should be safe, as it uses an unrelated new salt (?).

Option 2: Derive a New Salt from the Old One (CTR)

Assume the scheme allows for chaining up to 255 hashes. We already introduced HKDF to the scheme and could use the following simple derivation:

salt_n = hkdf_expand(salt_n-1, n, 16)

where n is a counter; the n-th Bcrypt chained hash; by using n as the info parameter we create a new salt for each iteration.

By having n be up to 255, do we "use up" some entropy? Would it be sound to say we lose 1 byte of the 16-byte source salt (aka salt_0)?

Option 2.1: Derive a New Salt from the Old One (CTR+Hash)

As an enhancement of the previous scheme, which would allow deriving all future salts from the source salt, we could incorporate the previous chained hash:

salt_n = hkdf_expand(salt_n-1, n | bcrypt_hash_n-1, 16)

I'm not sure this has some actual security benefits because a salt can be public.  It would make it as expensive as calculating the hash to get the salt of the specific round basically.

Question

Which of these schemes would be safe to use? The goal is to keep the output Bcrypt hash as small as possible, without compromising the security of BCrypt (in reasonable ways)

I am not aware of any research for this problem and it is difficult to declare anything as safe without a good reason.
Probably that's why everyone holds back with answers.

Suppose, however, the main attack against these BCrypt hashes is a dictionary attack, probably with custom hardware,
I can't see a weakness in any of the solutions. Reusing the salt for different passwords weakens a scheme. That is not the case here.
For other attacks (cache-timing...) this shouldn't matter.

But you sail in unknown waters.


Question about discrete log - why can one attacker not solve for g but two colluders can? I'm reading about the broadcast encryption described in Fiat and Naor's paper, I screen grabbed the relevant part below.
My question is essentially:

If there's a secret:

$g^{abc}$ $mod$  $A$ (where $A=PQ$ (both sufficiently large primes))

why is it that one user who knows:

$g^d$ $mod$ $A$, $a$, $b$, $c$, $d$, and $A$

could not calculate $g^{abc}$ $mod$ $A$ but when you add a second user who know $g^e$ $mod$ $A$, and $e$, they can then collude to calculate $g^{abc}$ $mod$ $A$ ?

Context is provided below.

The full paper can be found here

The paper states that one user not in the privileged set could not calculate the secret, but two colluding users could (and so they rate the scheme 1-resilient).

The idea is that someone who just knows $g^d \bmod N$ and $d$, they cannot compute $g$ (because they don't know the factorization of $N$; hence this is the RSA problem); however, if they know $g^d \bmod N$ and $d$ and $g^e \bmod N$ and $e$, then (assuming $gcd(d, e) = 1$), they can (and once they have $g$, they can compute $g^{abc} \bmod N$).

That's because, since they know $d$ and $e$, they can compute two integers $s$ and $t$ such that $sd + te = 1$ (that's where the assumption that $gcd(d, e) = 1$ comes in; if that's not true, then no such $s$, $t$ will exist).  Once that have those two integers, they can compute $(g^d)^s \times (g^e)^t = g^{sd + te} = g^1 = g$, recovering $g$.  One of $s$ and $t$ will be negative; that's not an issue, as we can compute inverses modulo a number of unknown factorization.


Decrypting two XORed compressed messages? If through a previous attack, cipher misuse or two time pad etc. I receive $c=m_1 \oplus m_2$. Where $m_1$ and $m_2$ are compressed messages, for instance GZIPped English text documents. Can we recover something significant about the messages?

Obviously if we can guess two prefixes we can verify. Can we do more? Can something practical be done about the end if we fail to decipher the beginning? or even don't have the start of the message.

Since the messages are compressed I don't know of commom substrings except in the header nor do I know how to validate if a short fragment in the middle is plausible.

Update: a premise in the former answer did not resist the acid test of experiment. This whole answer was thus very wrong.

Thanks to daniel's comment for opening my eyes.


Why calculate pi to estimate randomness? Why do testing suites calculate $\pi$ (pi) using the Monte Carlo method to determine if a series of numbers are random?  As far as I can tell, the Monte Carlo method can be used to estimate $\pi$ itself (as a numeric means of calculating it).  It just so happens to use random numbers.

Why does it have to be $\pi$ if you're testing a numeric sequence for randomness?  It seems that plotting random points inside and outside a circle to get $3.1415 \dots$ achieves exactly the same as plotting points inside /outside a triangle to get $0.5$.  Is there something special about the circular shape pertinent to cryptography?

Knowledgeable crypto practitioners do not calculate $\pi$ using a Monte Carlo method to determine if a series of numbers are random.

The test alluded to in the question is a general-purpose¹ randomness test for random number generators with output a real number expected to be uniform of the range $[0\dots1[$. The test consists of drawing pairs $(x,y)$, and determining the proportion such that $x^2+y^2<1$, which should be about $\pi/4$ (because that's the area of the intersection of a square of side $1$ with a disc of radius $1$ and center in a corner of the square, and any subset of the square is expected to get a proportion of the random draws proportional to its area).

Variants of this test can be made for random number generators with bit or integer output, as used in cryptography. However this test is not particularly good, or often used.

Further, general purpose RNG tests are generally not very useful in cryptography:

If applied to the output of a PRNG, such test will declare the RNG good including for cryptographically very weak and poorly seeded PRNG (such as a LFSR seeded with all 1).
If applied to the output of a TRNG directly based on a physical phenomena (such as thermal noise filtered by removing the DC component, keeping polarity, and sampling at a relatively low frequency), many such general purpose tests will tend to fail due to minor bias in the conditioning circuitry, even though the TRNG is working as designed and perfectly usable after conditioning by a properly designed CSPRNG.

In my opinion, the only technically² justifiable use of a general-purpose¹ randomness test in a cryptographic context is to detect gross malfunction³. The archetypal tests for that are the Monobit, Poker and Runs test formerly in FIPS 140-1 and FIPS 140-2; these tests are sound in principle, but had been specified to ridiculously stringent acceptance levels, making these tests usable only on the output of a PRNG, thus largely pointless (per 1. above). After a hiccup altering the acceptance levels, reason prevailed and these tests are no longer mandatory at startup of a FIPS 140-2 device.

A sorry side effect of the above historical error is that the habit of running Monobit and Poker test sticks, hence designers of hardware TRNG strive to have their generators pass these tests to the most stringent levels, hence have an incentive to avoid exposing their inner entropy source before a fair amount of poorly documented conditioning. That makes it more challenging than needed to devise a good field test of the TRNG; that is, a test that reliably catches dangerous defects appearing in a deployed device (including purposely induced defects, e.g. when a Smart Card is cooled by evaporation of a liquefied gas in hope to literally freeze the TRNG), and do so without causing false alarms and/or permanently disabling perfectly good devices.

¹ By general-purpose I mean intended as detecting any deviation from true random, with acceptance level set accordingly. This includes NIST SP 800-22 rev 1a.

² Getting rubber-stamped is a justifiable goal in itself.

³ Detecting gross malfunction is a justifiable goal at some design stage. Validating the design of a cryptographic gizmo (or worse, algorithm) primarily on the basis of the absence of detection of gross malfunction is poor methodology.


Combination of TLS_PSK and TLS False Start I am evaluating the use of TLS 1.2 for a low powered embedded environment.

After looking at RFC 7925 (TLS for IoT) I was wondering if the combination of

the TLS_PSK_WITH_AES_128_CCM_8 cipher suite (RFC 6655)
and the TLS False Start extension (RFC 7918)

is

possible / compatible and
has additional security implications beyond those already imposed by the use of a TLS_PSK_* cipher suite.

Section 21 of RFC 7925 mentions several conditions for using TLS False Start. However, TLS_PSK_* cipher suites are not mentioned specifically.

There is no real problem with applying "false start" to PSK cipher suites. The "false start" thing is about beginning to use the negotiated key to encrypt data before having confirmation (with the Finished message) that the peer really agreed on the same key. In that sense, the peer authentication is still implicit at that point. This is not a worry for "normal" cipher suites. (Note: it might be a problem with SRP, though.)

If you want to target low-power embedded systems, you might want to use the ChaCha20+Poly1305 cipher suites (RFC 7905) which are a lot lighter than AES (especially AES/CCM, which invokes the AES encryption routine twice for each block). If you still stick to AES, and AES/GCM can also be lighter.

Also, while PSK is light (no asymmetric crypto), it has its own issues, namely the need for a shared secret, which is not the easiest thing to deploy; you might want to consider using a non-PSK system with a certificate. If the constrained system is the client, then RSA key exchange involves only public key encryption on the client, and that's lightweight, because RSA public key operations use the public exponent, which is short. Alternatively, some elliptic curves can be light enough for an embedded CPU.

Shameless plug: consider BearSSL. It's not yet ready for production use (in that I have still not made extensive automated verifications against a fuzzing SSL/TLS implementation) but can give a taste of what is doable. On a 48 MHz Cortex-M0+, my C code can do an EC point multiplication in about half a second (half that value if using Curve25519).


How to solve this ECDLP? The Problem is as follows:

$E: y^2=x^3+17230x+22699 \pmod{23981} $
$p=23981$ is prime number
point $G$
$G$'s order $109$ :  prime number

Alice creates a public key by selecting a private key $d$ ($d<q$)
public key $Q= dG= (3141,12767)$
therefore public information : $a,b,p,G,q,Q$
private key : $d$
However this curve has the following characteristic:
$$\Delta =-16(4a^3+27b^2)\bmod{p} = 0$$
That is, the discrimant is $0$.
and embedding degree is 2

Q. How do I determine if a curve is a CUSPS or a Node?
Q. How to find private key $d$ in this case?

We begin with the singular curve
$$
y^2 = x^3 + 17230x + 22699\,.
$$
This curve is singular, as can be immediately determined by its $0$ discriminant. Furthermore, it has a singular point $(23796, 0)$, where both partial derivatives vanish. We translate the curve to have this singular point at $(0, 0)$ by changing variables $(x, y) \mapsto (x - 23796, y - 0)$, after which we obtain the corresponding curve
$$
y^2 = x^3 + 23426x^2\,,
$$
which can be rewritten as
$$
y^2 = x^2(x + 23426)\,.
$$
This curve is a node, not a cusp. A cusp would have, after translation, the form $y^2 = x^3$, because it would have a triple root.

Having the curve in the above form, it becomes easy to solve the logarithm. Because it is a node, we know it maps to a multiplicative group. And because $23426=7020^2$ is a square modulo $23981$, we know it maps to the multiplicative group $\mathbb{F}_{23981}^\ast$, i.e., the integers modulo $23981$. The map is

$$
(x, y) \mapsto \frac{y + 7020x}{y - 7020x}\,,
$$

after which we can simply solve the discrete logarithm over the integers modulo $23981$.

Here's a short Sagemath script that does the transformation and finds the discrete logarithm:

sage: p = 23981
sage: P.<x> = GF(p)[]
sage: f = x^3 + 17230*x + 22699
sage: P = (1451, 1362)
sage: Q = (3141, 12767)
sage: # change variables to have the singularity at (0, 0)
sage: f_ = f.subs(x=x + 23796)
sage: P_ = (P[0] - 23796, P[1])
sage: Q_ = (Q[0] - 23796, Q[1])
sage: # show that the curve is of the form y^2 = x^3 + x^2
sage: print f_.factor()
(x + 23426) * x^2
sage: t = GF(p)(23426).square_root()
sage: # map both points to F_p
sage: u = (P_[1] + t*P_[0])/(P_[1] - t*P_[0]) % p
sage: v = (Q_[1] + t*Q_[0])/(Q_[1] - t*Q_[0]) % p
sage: # use Sage to solve the logarithm
sage: print discrete_log(v, u)
53

This method, and others, are best described in Section 2.10 of Washington's Elliptic Curves: Number Theory and Cryptography.


What should be used as a source for entropy? I have hardware-based RNG which consists of TRNG and PRNG. TRNG is giving out a 512-bit number which is being used as a seed for PRNG. RNG is generating a 160-bit random number using PRNG and reseeding is done after $2^{20}$ numbers. I want to use hardware-based RNG as an entropy source. What should be used as a source of entropy i.e. output of TRNG or PRNG?

If you need an entropy source, that's the TRNG, kind of by definition. A TRNG provides unpredictable output by physical means. An entropy source is one that provides unpredictable output; the entropy is a measure of how unpredictable.

Hardware entropy sources are rarely uniform, so they should never be used as an RNG, but as a seed to a CSPRNG, i.e. a deterministic algorithm that “smoothen” all correlations between bits.

So if you really need an entropy source, use the TRNG. But if what you're doing is anything other than seeding a CSPRNG, then what you really need is a random source; for that, use the CSPRNG seeded by the TRNG.

Having a 160-bit output makes me fear that your CSPRNG is based on SHA-1. SHA-1 is deprecated, but not broken yet. If you're using SHA-1, you should plan to replace it by SHA-256, but it isn't very urgent. What matters is primarily that you use a good CSPRNG algorithm on top of whatever hash or other cryptographic primitive you're using, hopefully NIST's Hash_DRBG or HMAC_DRBG if it's based on a hash.

  simplified formula for entropy (log2n) gives value of 7.32 for 160 bits and 9 for 512 bits. Will I be justified to claim 7.32 bit entropy if I decide to use the output of RNG?

Your calculation doesn't make sense. Think of what $n$ is in this formula! The entropy of a source with $n$ possible different equiprobable values is $\log_2(n)$. The entropy of a source that provides $k$ independent bits is $k$. If your source provided 512 independent bits then you would get 512 bits of entropy from it, but in practice physical sources have some amount of correlation that's hard to evaluate precisely, so you probably have much less. In any case, what matters with entropy is that it's sufficient to make the probability that a brute-force attack would succeed negligible. For this purpose, there is no meaningful difference between 160 bits and 512 bits.


What hash functions can be (efficiently) computed over GF(2^m)? Given an arithmetic circuit over a finite field of characteristic 2, what families of cryptographic hash functions can be efficiently computed with this circuit?

Can standard hash functions be computed? To do so, standard bit operations would be necessary. XOR is possible via addition, but are there any arithmetic operations corresponding to other necessary bit operations like SHIFT, AND, NOT, etc.? An explanation of what bit operations are possible would be great.

If standard hash functions are not suitable, are there specialized hash functions developed for use over finite fields? If so, please reference any related papers.

Given an arithmetic circuit over a finite field of characteristic 2, what families of cryptographic hash functions can be computed with this circuit?

Answer: all of them.  The combination of addition and multiplication in $GF(2^m)$ is complete.  That is, for any arbitrary function that takes $n$ inputs in $GF(2^m)$ and an output in $GF(2^m)$, there exists a polynomial in $n$ variables that produces that function.

Note that this polynomial need not be simple; however it will exist.


Can CFB mode of block cipher be used as a commutative encryption? Can CFB mode of block cipher be used as a commutative encryption?

Is it possible to use CFB mode of AES block cipher to create commutative encryption?

With CTR it is possible but not secure.

No, because CFB isn't commutative.

You can see this by looking at the decryption of double-CFB encrypted ciphertext. Even assuming a constant IV (so single-use keys), if you decrypt in the wrong order it cannot work, since the ciphertext is used as input into the block cipher and will differ from what was used with that key when encrypting.

The exception, of course, is single block messages, where CFB effectively reduces to CTR and has similar commutativity and (in)security, with the latter depending on how it is used.


Diffie-Hellman on additive group Given the finite cyclic, additive group (G, +), with |G| = n and generator = g, what are the computations and exchanged messages for Diffie-Hellman?

What I tried myself:

Alice chooses a private $a$ and sends $p(|G|)$ and $g$ (generator) to Bob.
Alice calculates $A = a\cdot g  \mod p (|G|)$ and sends it to Bob.
Bob chooses a private $b$ and calculates $B = b \cdot g \mod p (|G|)$ and sends it back to Alice.
Alice calculates $a \cdot B \mod p (|G|)$ which is the shared key.
Alice calculates $b \cdot A \mod p (|G|)$ which is the shared key.

Is this way of thinking correct? Because I'm not sure because the group is additive.

Given the additive group $(G, +)$ with $|G| = p$ and generator $P$, what are the computations and exchanged messages for Diffie-Hellman?

I use order $p$ and assuming $p$ to be prime and the generator as $P$ (as it is used in context of elliptic curve groups - since you need additive groups where the DLP and the CDHP are hard - which is not the case for $\mathbb{Z}_n$).

Alice chooses random $a\in \mathbb{Z}_p^*$ and sends $A=aP$ (this means $P+\ldots+P$, $a$ times).
Bob chooses  $b\in \mathbb{Z}_p^*$ and sends $B=bP$.
Alice computes $K=aB=(ab)P$
Bob computes $K=bA=(ba)P=(ab)P$

Note that since I assume that we work on elliptic curve groups there is no reduction modulo the group order after the additive operation.


Secure Deduplication and Encryption in a data store Assume:

We have a centralized data store that can store whatever we need
Every user is online
Function $f : File \to Key$ gets access to the store, and is the same for all users.
$g : Key \to File$ should retrieve the file so that $g \circ f = id$.
Eve can't break modern algorithms.

Then:

Eve wants to know who inserts file $A$, and has a copy of file $A$ as well as read access to the whole store and connection sniffing on all other users
Alice inserts file $A$ with function $f(A)$
Bob inserts file $A$ with function $f(A)$

Is there a suitable definition for $f$ and $g$ that:

Doesn't store $A$ multiple times
Doesn't let Eve know that Alice and Bob inserted file A.

What if we let $f$ store $A$ multiple times but then after:

Joe gets Alice and Bob's output from $f$ as well as access to the store

Can Joe deduplicate the two copies of $A$:

Without Eve knowing who has $A$?
Without causing future retrievals of $A$ by Alice or Bob reveal that they have $A$.

If Alice, Bob et al. can share a secret, for example, using some sort of key exchange protocol, it is possible to use convergent encryption in a way that fulfills the requirements. Otherwise it probably isn't.

First, assume the users know a secret key $s$. They use convergent encryption with the  key derived using $s$. For example, $k = \operatorname{HMAC}_s(\operatorname{HMAC}_s(p))$ and $c = (\operatorname{HMAC}_s(p), E_k(p))$ to encrypt plaintext $p$. $E$ could be AES in a suitable mode.

To upload a file, Alice calculates $\operatorname{HMAC}_s(p)$ and checks if the store has it. If it does, no need to transfer again, she is done. If it isn't, she uploads the encrypted file so that it can be queried using $\operatorname{HMAC}_s(p)$ which she stores as $key$. Bob goes through the same process.

Eve knows they have uploaded the same file, but knows nothing else. She cannot test if the file is $A$ because she does not know $s$. Neither can she decrypt it.

Now, assuming sharing $s$ is not possible:

  Eve wants to know who inserts file A, and has a copy of file A as well as read access to the whole store and connection sniffing on all other users

This implies that $f$ must not send the same thing over to the store when Eve sends $A$ as when Alice does. Otherwise Eve could simulate $f$ and compare the traffic to Alice's. The store can also not deduplicate the data in any way, because it has no more information than Eve does.

Thus, this is impossible:

  Is there a suitable definition for f and g that:

  Doesn't store A multiple times
  Doesn't let Eve know that Alice and Bob inserted file A.

So $f$ must store duplicate copies, and must give each user a different access key. Now, assuming that's the case and Joe has Alice and Bob's keys:

  Can Joe deduplicate the two copies of A:

  Without Eve knowing who has A?
  Without causing future retrievals of A by Alice or Bob reveal that they have A.

Joe could be allowed to say replace one of the copies with a pointer to the other + some token that allows that user to decrypt the first copy (e.g. $E_b(a)$ where $a$ is Alice's key to $A$ and $b$ Bob's). However, Eve would now know at least that the two files match.

In this case $f$ would just be encryption with a random key $r$, and $key$ would include both that key and some identifier that $g$ would use to request for the data.


Diffie-Hellman key exchange: Why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$ In a Diffie-Hellman key exchange, with a generator $g$ and a modulo $n$, and two keys $k_1$ and $k_2$, why is

$(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$

let $a=g^{k_1} \pmod n$ and $b=g^{k_2} \pmod n$. We want to prove that $a^{k_2} \equiv b^{k_1} \pmod n$. By congruence definition, $\exists t_1 \in \mathbb{Z}/\,a=nt_1+g^{k_1}$ and $\exists t_2 \in \mathbb{Z}/\,b=nt_2+g^{k_2}$. We want to prove that $(nt_1+g^{k_1})^{k_2} \equiv (nt_2+g^{k_2})^{k_1} \pmod n$. By binomial theorem, we have $(nt_1+g^{k_1})^{k_2} = \sum _{i=0}^{k_2} \binom{k_2}{i}\times(nt_1)^i\times(g^{k_1})^{k_2-i}$ and $(nt_2+g^{k_2})^{k_1} = \sum _{j=0}^{k_1} \binom{k_1}{j}\times(nt_2)^j\times(g^{k_2})^{k_1-j}$. The only time where $nt_1$ and $nt_2$ disapear is when $i=0$ and $j=0$, otherwise the two sums are $\equiv 0 \pmod n$. Thus, $(nt_1+g^{k_1})^{k_2} \equiv \binom{k_2}{0}\times(nt_1)^0\times(g^k_1)^{k_2-0} \equiv g^{k_1k_2} \pmod n$ and $(nt_2+g^{k_2})^{k_1} \equiv \binom{k_1}{0}\times(nt_2)^0\times(g^k_2)^{k_1-0} \equiv g^{k_2k_1} \pmod n$. Hence, $g^{k_1k_2} \equiv g^{k_2k_1} \pmod n$.