Is the warning given by chrome warranted? I went to a payment page on a site recently, and chrome was warning me that the page is possibly not secure, I have a very basic understanding of crypto but not enough to fully understand why this page is possibly not secure.

The cert comes from Thawte, which from what I found on google is a well trusted CA, however the cert's signature algorithm and hash algorithm are sha1RSA  and sha1 respectively. I was under the impression that these were obsolete and have been for quite some time ?

The page uses AES-128-CBC which I understand to be relatively insecure by it's self but the messages are authenticated with HMAC-SHA1. And after reading
this I understand this to be secure given that the private key is secure which it should be given that the key exchange is RSA. So as far as I understand this makes the whole thing secure? Is that correct?

To summarize :

Is my understanding correct?
If not, why not ?
Is this page secure and why/why not?

There are four issues (basically all you can get at once I think) going on with your connection to this site which is why Chrome warns you.

The first one is quite easy to spot: The usage of SHA-1 for the certificate signature. SHA-1 is generally considered deprecated and should not be used for scenarios where collision resistance is required, like certificate hashing. A well-funded attacker may be able to create two valid certificates having the exact same SHA-1 hash, it's only a matter of time until someone presents the first such collision to us (maybe some agency?).

And to actually answer this part of the question: Yes, SHA-1 has been considered obsolete for quite some time now, but people tend not to move away from things until there's a real threat, although many CAs need do the transition. The second reason for why they may still use is that they got a 4-year certificate back in 2012 (and those tend to be expensive) and deprecating SHA-1 wasn't a thing back then as much as it is today (Google's post is from 2014).

The second warning you observe is the lack of certificate transparency. Certificate transparency is Google's action against fraudelent CAs issuing certificates to people who shouldn't be able to get those certificates. They do this by "forcing" everyone to publish the issued certificates into a set of logs so everyone can identify if his domain is subject to such attacks. This is still in the early stages and not by-default supported by many CAs. It will only remove the EV bar if you're using Chrome.

The third issue on this warning page is mixed content. This means parts of the page are served over unencrypted connections and may pose a security threat to you as they can be observed and altered by anyone in between you and the server. This may cause a noticable warning.

The fourth issue is the use of AES-CBC + HMAC-SHA1. Note that indeed HMAC-SHA1 is still safe and will be for quite some time. Note further that there indeed exists security proofs for the way TLS handles CBC+HMAC.

However, CBC failed quite a bit in the past (POODLE and others) and even some TLS implementations were vulnerable. Furthermore CBC has quite severe requirements on the IVs used for each packet (they need to be unpredictable as opposed to be "just" unique). And of course it's harder to correctly use CBC+HMAC than it is to just an AEAD scheme (such as GCM) as you have to take care of a lot more stuff (keys, call the MAC in the right place, generate correct IVs). The last point on TLS' CBC+HMAC is that the security proof is considered "bad". TLS uses MAC-then-Encrypt when using CBC which doesn't have a security proof as generic as Encrypt-then-MAC has making it potentially more error-prone. It is for these reasons Chrome considers connections made using CBC as obsolete and why only AEAD modes are allowed for TLS v1.3.

TL;DR: SHA-1 is indeed deprecated but getting rid of it takes time and AES-CBC+HMAC-SHA1 has provable security but is considered "obsolete" and error-prone for quite some reasons so Chrome issues you the warnings.


Is there any probabilistic version of RSA? I have now studying the RSA, but I think that is it possible to have some

probabilistic version like a random bit string "r" XORed with the key?

Is there any probabilistic version of RSA?

Thak you so much

Using randomization on the RSA key before encryption doesn't work as easy as a simple XOR: the key (or actually, key pair) has some complicated mathematical structure, and the public part of it (the modulus and the public exponent) need to be known by the encrypting party.

What might be possible would be to randomly chose the encryption exponent, and transmit it with the ciphertext. The receiver, knowing the factorization of the modulus, can then calculate a fitting decryption exponent and do the decryption.

Alice chooses randomly big primes $p$ and $q$ , calculates $n = p · q$, and publishes $n$ (but not $p$ nor $q$). (Alice might also calculate and store $\varphi(n) = (p-1)·(q-1)$.)
Bob gets to know $n$, and has a message $m$.
Bob chooses a random $e$, and calculates $c = m^e \bmod n$.
Bob sends $e$ and $c$ to Alice.
Alice calculates $d$ from $e$ and $\varphi(n)$ with $d · e \equiv 1 \pmod n$, e.g. using the extended euclidean algorithm.
Alice calculates $m = c^d \bmod n$.

I'm not sure if this would work quite reliably: with normal RSA a condition on $e$ is $\gcd(e, \varphi(n)) = 1$, which is easy to ensure knowing $\varphi(n)$, but less easy if it is not known. (But at least we know we need to choose an odd $e$, as $\varphi(n)$ is even.) I guess if we restrict $p$ and $q$ to safe primes ($p = 2x+1$, $q = 2y+1$ with $x$, $y$ also prime), $\varphi(n) = 2·2·x·y$, and other than multiples of $x$ and $y$ all odd numbers work for $e$.

The actual public key would then be just the modulus $n$, and the private key would be the factorization $n = p · q$.

This RSA-like cryptosystem (I wouldn't name it RSA) would likely be quite a bit slower on encryption (as you can't use a usual "small" exponent like 3 or 65537), as well as on decryption (since you first need to derive your decryption exponent, instead of using the same as always), without really offering much advantages.

The common way to make RSA encryption non-deterministic (which is needed for some formal security properties) is to use a random padding for the plaintext before encrypting it.

So the actual encryption is
$$ c = \textsf{pad}(m)^e \bmod n,$$
and the encryption is
$$ m = \textsf{unpad}(c^d \bmod n),$$
with a probabilistic padding function $\textsf{pad}$, and its (deterministic) inverse $\textsf{unpad}$.

This padding function can be something simple as prefixing the plaintext with some random bytes, or doing this followed by some (reversible) shuffling function, so all plaintext bits are affected.

In practice RSA is usually not used to encrypt a plaintext directly, but encrypts a randomly generated key for a symmetric cipher, which is then used to encrypt the actual plaintext.

In that case, you don't really need a randomization, as the plaintext is already random by itself.


Using UMAC with stream cypher I understand that most stream ciphers, due to being applied with a simple XOR, are specially fragile against data tampering, and must be used with some MAC mechanism. So I am investigating the use of UMAC for this purpose.

I also understand that UMAC works by XORing an universal hash function based on a secret key with a pseudo-random number generated with AES and a nonce:

$ Tag = U_{k1}(M_{clear}) \oplus AES_{k2}(nonce)$

The thing is: since I already have my stream cipher setup, can I just take hash $H_{k1}(m)$ and encrypt it by XORing with the pseudo-random output from the stream cypher plaintext, the same way done with the plain text?

$M_{wire} = (M_{clear}||H_{k1}(M_{clear})) \oplus CipherStream_{k2}[i..(i+len)]$

Is there any problem with this approach? Or a block cipher was chosen for some specific need?

Also, I have suggested applying the hash to the clear-text; does it make any difference applying it to the cipher-text or to the clear-text?

Accoding to UMAC RFC Section 6.1, you can use any other "cryptographic objects" instead of AES:

  The strength of UMAC depends on the strength of its underlying cryptographic functions: the key-derivation function (KDF) and the pad-derivation function (PDF).  In this specification, both operations are implemented using a block cipher, by default the Advanced Encryption Standard (AES). However, the design of UMAC allows for the replacement of these components.  Indeed, it is possible to use other block ciphers or other cryptographic objects, such as (properly keyed) SHA-1 or HMAC for the realization of the KDF or PDF.

This is how Poly1305, another MAC based on universal hashing, is used in NaCl, for example: it uses the first 32 bytes of cipher stream as a one-time key for MAC, and the rest of the stream for encryption.

The advantage of applying hash to ciphertext instead of plaintext is that you can reject invalid ciphertexts earlier without decrypting them, making rejection faster and, possibly, more resistant to side channel attacks, and implementation errors (e.g. forgetting to check the return code of decrypt() function, which indicates whether the MAC was correct).


What gives SHA-256 its preimage resistance? I was reading some guy's description of the SHA-256 algorithm and I noticed that the basic operations it uses appear trivial to reverse: addition, rotate bits, etc. When I say "reverse" I don't mean retrieving the exact input used to generate the hash, I mean finding some input which generates the same hash (finding a collision). I would like to understand why this is actually difficult.

  Preimage resistance: For a given h in the output space of the hash function, it is hard to find any message x with H(x)=h. Source

Here is an general explanation for why a function can be easy to calculate in one way, but very difficult to reverse (calculate the other way). What in particular gives SHA-256 this property? If someone tried to generate a hash collision, which obstacles would they face?

The initial values for A-H are predetermined in the algorithm. The actual input comes from W. In this sense the "initial state" can be thought of as a combination of user input and predetermined values. Does this contribute to the difficulty in finding collisions? If the initial values for A-H could be any arbitrary values, would it be trivial to find hash collisions?

You appear to be thinking "the output of the round function appears to be a simple function of the previous round, and a word from the message; why can't we select message words to steer the output to whatever we wanted".

Well, there's something missing in the simple description you gave; message expansion.  The W inputs are not just directly taken from the input message; the first 16 are, but the other 48 are linear functions of the input message.  If you modify one input word, you necessarily modify a number of the W inputs; this effectively stops this simple steering strategy, as tweaking one W input (to get a desired state) will necessarily modify others (which will modify the state you're trying to set up).

This doesn't prove the SHA-256 is secure (SHA-1 does the same sort of message expansion, and we know that's weak); however it does show that this approach doesn't appear to be fruitful.


Why is $\phi(N) = (p^2 -1) (q^2 - 1)$ here? I was reading a paper on attacks on RSA variants, and the paper equates $\phi(N) = (p^2-1)(q^2-1)$. Before, I have always seen $\phi(N) = (p-1)(q-1)$ and don't understand why it is different here.
I have added a screenshot of one part where they mention this below. Thanks :)

Gaussian integers are numbers of the form $a+bi$, where $i$ is such that $i^2=-1$. If you consider them modulo a prime integer $p$, then:

If $p=4k+1$, then $i$ exists in $GF(p)$ and so Gaussian integers simply reduce to $GF(p)$ when working modulo $p$, with the size of the multiplicative group equal to $p-1$.
If $p=4k+3$, then $i$ does not exist in $GF(p)$ but does exist in $GF(p^2)$ (that's actually a common way to construct $GF(p^2)$ - to introduce such $i$), so Gaussian integers reduce to $GF(p^2)$ when working modulo $p$. The size of the multiplicative group is $p^2-1$.

Note that $p-1|p^2-1$ so using $p^2-1$ in the first case (as a multiple of the group order) also works for RSA. Although, for the scheme it probably matters to use primes of the form $p=4k+3$ to avoid degeneration to the basic RSA.


Is Curve25519-java secure? I have only about 2 weeks of cryptography experience mostly in the form of questions on bitcoin.se.

Is Curve25519-java up to date with current Curve25519 standards?

Is Curve25519 itself secure?

In other words, is it safe to use as it a cryptocurrency key-generation and transaction signing & verification algorithm?

Related to Curve25519

Curve25519 seems to be secure so far. Yet, you have to remind yourself that Dr. Bernstein specified Curve25519 for key-exchange. Meaning: key-generation, transaction signing, and verification are somewhat different beasts – you might want to cross-check on that before jumping toward Curve25519. Sure, Curve25519-java supports signing… but I’m not aware of a thorough, well-vetted cryptanalysis of the signing side of things. There might be issues with it, which have yet to be checked for to be found.

Related to Curve25519-java

NxtCoins.NL reports that BCT user named Jesse James, also known as DoctorEvil, reviewed the Java implementation and he seems to think it is safe. Quoting his publication: “Crypto Review of Curve25519.java & Crypto.java”, last modified on 2014-03-14:

  Crypto Review of Curve25519.java & Crypto.java

  By DoctorEvil on Nextcoin.org
  Sponsored by MSIN on BitcoinTalk.org

  TL;DR

  NXT's Crypto.java and Curve25519.java look kosher aside from a signing bug that is currently being worked around.

  General Methodology

  Reviewed the primary/secondary literature on Curve25519 and EC-KCDSA to evaluate them vis-a-vis the NXT use-case.
  Re-implemented these primitives from scratch in Python (differently than the Java version).
  Scoured every line of the Crypto.java/Curve25519.java.
  Ran tests to uncover output discrepancies between my implementation and the Java version.

  Choice of Algorithm

  Curve25519+EC-KCDSA are theoretically defensible choices for NXT's use-case.  However, since cryptocurrency applications are dominated by signature verification, Ed25519 would have arguably been a slightly better pick (although no high quality Java implementations of it exist so NXT's choice is understandable).

  Signing Bug

  As I (and others) have noted before, the Curve25519.sign function has a legitimate flaw that causes it to occasionally produce invalid signatures. This flaw may have arisen because the original C code the Java was ported from used unsigned primitive integral types underlying its representation of big numbers whereas the Java port is restricted to signed types.

  BloodyRookie's proposed patch is essentially sound, although it can be simplified and made constant-time.  Here is a fixed sign function inspired by his changes:

  (Java sourcecode)

public static final boolean sign(byte[] v, byte[] h, byte[] x, byte[] s) {
    // v = (x - h) s  mod q
    int w, i;
    byte[] h1 = new byte[32], x1 = new byte[32];
    byte[] tmp1 = new byte[64];
    byte[] tmp2 = new byte[64];
    // Don't clobber the arguments, be nice!
    cpy32(h1, h);
    cpy32(x1, x);
    // Reduce modulo group order
    byte[] tmp3=new byte[32];
    divmod(tmp3, h1, 32, ORDER, 32);
    divmod(tmp3, x1, 32, ORDER, 32);
    // v = x1 - h1
    // If v is negative, add the group order to it to become positive.
    // If v was already positive we don't have to worry about overflow
    // when adding the order because v < ORDER and 2*ORDER < 2^256
    mula_small(v, x1, 0, h1, 32, -1);
    mula_small(v, v , 0, ORDER, 32, 1);
    // tmp1 = (x-h)*s mod q
    mula32(tmp1, v, s, 32, 1);
    divmod(tmp2, tmp1, 64, ORDER, 32);
    for (w = 0, i = 0; i < 32; i++)
        w |= v[i] = tmp1[i];
    return w != 0;
 }

  I have tested this patch with over 100,000 random keys/messages.

  Non-standard Algorithm Tweaks

  EC-KCDSA as implemented by Crypto/Curve25519.java does not exactly match the specification per IEEE P1363a.  In particular:

  It modifies EC-KCDSA to be deterministic.  IMHO, this is good change.  However, the implementation uses a non-standard deterministic signature nonce generation scheme; RFC6979's or Ed25519's scheme would arguably have been better choices on the basis of having been more looked at.  That said, I couldn't find anything obviously wrong with the scheme used.

  The implementation also deviates from the standard with regard to the computation of w, instead computing it as H(H(m) + x1) (using the terminology of Guide to Elliptic Curve Cryptography ).  That said, I couldn't find anything obviously wrong with this deviation; it appears sound.

  The implementation's EC-KCDSA key generation is also non-standard due to complications of Curve25519 using x-coordinate only representation.  While this ambiguous representation is not problematic in the context of Diffie-Hellman key agreement (for which Curve25519 was specifically designed), it is inconvienent for naïve EC-KCDSA.  The implementation uses a workaround during key generation to address this issue.  While I couldn't find any reference to anyone else using the specific workaround, it appears to me to be sound.

  Curve25519.verify uses a variant of a Montgomery ladder differential addition chain to calculate the curve point (vP + hG).  I can't find any reference to this variant in the literature and this is easily the most optimization-obfuscated part of the implementation.  That being said, nothing about it stands out as wrong and I can understand the performance motivation of using the variant.

  Signature Malleability and Signature Canonicalization

  It's worth noting that Daniel Bernstein, the primary designer of Curve25519, explicitly states in his paper on the related Ed25519 signature scheme that he does not consider signature malleability a part of the threat model when designing signature schemes.  This should give pause to those who think they will be able to define canonicalization conventions to eliminate all sources of malleability.  It may be possible to achieve using such conventions but it is not safe to assume without formal, peer-reviewed proof.

  As far as I can tell, NXT's fix in response to the attack I reported earlier, makes it immune to signature malleability.

  One malleability-related observation: public keys are EC x-coordinates over a field of order 2^255-19.  This means every public key has two 32-byte representations.  While an interesting sidenote, I don't see how this opens up any avenues for attack in the context of NXT.

  I'd also like to make one correction to my earlier vulnerability report.  The GROUP_ORDER constant in Curve25519 I reported as 2^252+2^124 (from misreading of a code comment) but is actually defined as 7237005577332262213973186563042994240857116359379907606001950938285454250989.  My exploit code worked anyway simply because it used the constant as defined.

  Side Channel Attacks

  The implementation leaks a small amount (up to 2 bits?) of private key information via timing during signing in Crypto.sign because this function recomputes the signing key from the passphrase each invocation (Curve25519.keygen is not timing attack resistant when used to generate EC-KCDSA keys).  I don't see any way to exploit this in the context of NXT.   However, precomputing the signing key once at user login and passing it into the sign function would be appropriate if NXT were to ever have a code path where an external observer could cause a target to sign anything on-demand and observe it's timing (e.g. like some interactive authentication protocol).

  Alternative Implementation

  As part of my analysis I developed an alternative Python implementation of the crypto primitives.  As noted, my code is pedagogical (slow and not timing-attack resistant).  However, since it uses fundamentally different EC arithmetic (affine XY coordinates vs projective XZ coordinates), it serves as a useful sanity check of the Java version's math (as well as makes for a more understandable exposition of the underlying algorithms).

  In a test with 1024 signers, it produced the same signature outputs and had the same verification results as the (patched) Java implementation.

  Other Checks

  The Curve25519 committed into NXT's repository (as of the publication of this report) exactly matches the port distributed by Dmitry Skiba. Not hugely notable, but thought this was worth checking for the sake of the tin-foil-hat crowd.

  EC-KCDSA with ECDH

  A formal proof of security that they are compatible was out of scope of this review. However, my preliminary investigations lead me to believe it is OK for NXT to re-use EC-KCDSA keys for ECDH key agreement (something which NXT currently does not do but which is implied by road mapped features).


Whatsapp E2EE - Why scanning the QR-code? E2EE can be established in Whatsapp by scanning the QR-code on the other person’s phone.

But I read on the FAQ page that this code / number can also be sent to the other person via SMS, Email, etc.

Isn’t it possible to establish an E2EE without this «increased» effort? Are they trying to make it difficult for the users? Because as far as I know the computers for an internet connection do these sort of things without these weird methods that Whatsapp uses.

Are there any advantages in scanning a QR-code?

Are there any advantages in scanning a QR-code?

Yes.
But to understand why this provides an advantage we first need to introduce the man-in-the-middle attack (MitM attack). In this attack setup, the adversary sits between you and your communication partner and you are doing your cryptographic computations (the key exchange) with the adversary who then initiates a key exchange with your intended partner and then forwards (some) of your messages to make sure you don't notice the attack. It needs to be noted that you indeed are having a session with the attacker and not with your intended recipient in this case which in particular means two things:

You will see the adversary's public key and not your intended target's and
You will share the agreed key with the adversary and not with your intended target.

On the web, i.e. when you browse websites this is mitigated by so-called certificates which effectively state in a trust-worthy manner "this public key belongs to this entity". Then an adversary can't go ahead and send his public key as the entity's key because he can't come up with the statement / certificate.

However in this scenario, i.e. instant messaging you can't have one central source which says "this key belongs to X" if you don't trust the service provider which end-to-end encryption (E2EE) is all about. So we need another way to ensure that we are actually directly communicating with our intended target. This is where the additional QR-code / number come in. They are essentially a processed version of your public key and the other party's public key. Now if you transmit this information to your intended target in an authentic manner and the information matches you know that you are using their public key and thus that there is no active attack going on.


Public SRP verifiers or public hash chain "public keys" when secret is low entropy password I want to set up the following:

An untrusted server should host user sessions and authenticate users without knowing their passwords or being capable of creating a fake user session in the user's name.
This is accomplished by making all sessions publicly verifiable by making public the information necessary to prove that the client was able to demonstrate their knowledge of a secret.
The secret the client holds is of password-level entropy.

Now, a few things come to mind here. For starters, either SRP or hash chain authentication could be used for this purpose, and would actually work pretty well if the secret was of key-level entropy.

Secondly, a password can be pushed towards key-level entropy by using key derivation.

So my question is this: Is it reckless to use a key derivation algorithm to create a secure password to use with an auth scheme like SRP or hash-chaining in which the untrusted server and the general public will know the resulting verifier or "public" key? Or are KDFs only suited for providing some hope that not all passwords are goners for when a trusted server is broken into by an attacker?

I know PBKDF2 is essentially "useless" against anyone with a GPU rig and I have read that bcrypt is "useless" to anyone with an FPGA setup. Scrypt, the final alternative people discuss is "young" and at the end of it, it seems intuitively like it's very hard to pretend low-entropy can ever truly become high-entropy, except by simply making it a bit harder for attackers of today.

So, is there any solution to this set up or is this ultimately a case where a user must have some key-like password? If so, would this be a good use case for assigned passwords that are actually keys translated through word lists? For example, if you enforce a Diceware password scheme of 10 words, you end up with what the author claims is 12.9 * 10 bits of entropy, or 129 bits of entropy which seems pretty good for being forced into remembering 10 words.

Let's also assume the users are somewhat onboard because they are motivated by the product itself but they also shouldn't have to put up with too much. They aren't lay-users being forced into a system more complicated then they are used to but they also shouldn't have a terrible experience with logins.

I know PBKDF2 is essentially "useless" against anyone with a GPU rig and I have read that bcrypt is "useless" to anyone with an FPGA setup.

Neither is useless. Newer alternatives like scrypt and the eventual PHC winner make better use of the defenders' resources, but even a thousand iterations of PBKDF2 is useful, compared to doing nothing.

If you assume that $2^{80}$ hash function invocations is infeasible for the attacker (reasonable, though not particularly conservative), then $2^n$ rounds of PBKDF2 allow your passwords to have only $80-n$ bits of entropy. Since $n=20$ is often reasonable, you would remove a fourth of the required password "length", all things equal.

  So, is there any solution to this set up or is this ultimately a case where a user must have some key-like password? If so, would this be a good use case for assigned passwords that are actually keys translated through word lists?

Still, typical user-chosen passwords certainly do not have even that much entropy, so yes, this could be a good case for assigned passwords. Even if the users are unwilling to remember the assigned password, writing it down would not let a typical eavesdropper attack it. Also, users cannot make the passwords they use elsewhere (in situations where offline attacks are prevented) vulnerable by reusing them here.

So, to answer your actual question:

  Is it reckless to use a key derivation algorithm to create a secure password to use with an auth scheme like SRP or hash-chaining in which the untrusted server and the general public will know the resulting verifier or "public" key? Or are KDFs only suited for providing some hope that not all passwords are goners for when a trusted server is broken into by an attacker?

No, I do not think it is necessarily reckless, at least with your idea of assigned passwords (which cannot cause a leak of some reused password). However, it would still be preferable to prevent such offline attacks in the absence of a compromise of the server. I.e. use a trusted server for authentication if at all possible.


Chosen plain-text Attack on DES-X with roughly $2^{64}$ DES operations Here is the quote from P. Rogaway,The security of DESX

  "the effective key length of DESX with respect
  to key search is at least 55 + 63 - lg(m) bits"

where m is the number of chosen plaintext/ciphertext pairs.

So how can I attack DES-X with roughly $2^{64}$ DES operations assume we have unlimited storage?

I know that a simple exhaustive key search(~ $2^{120}$ DES operations) can be optimized to $2^{118}$DES operations by the key complementation property.

How can this property help if we have more plaintext/ciphertext pairs?

If we have $2^{64}$ $(p,c)$ pairs, how do we use that to recover all 3 keys? I can only think of using 2 $(p,c)$ pairs to get rid of $k_2$ by simply xor them.

I'll take the question as: with all plaintext/ciphertext pairs $(p,c=\operatorname{DESX}(p))$ at hand, how do we efficiently find the DESX key $(K_1,K_2,K_3)$?

The main idea is to observe that (independently of the DES complementation property), for any fixed $\delta\ne0$, $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus \delta)$ matches $\text{DES}_{K_2}(0)\oplus\text{DES}_{K_2}(\delta)$ when $p=K_1$, but few if any other values. We can compute the second quantity as a function of a candidate $K_2$, and search which $p=K_1$ matches in the plaintext/ciphertext pairs (there's in the order of one), then check if that guess is right.

The DES complementation property states that $\operatorname{DES}_{\overline K}(\overline p)=\overline{\operatorname{DES}_K(p)}$. This suggests using preferentially $\delta=\overline0$, which helps since $\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(\overline 0)=\operatorname{DES}_\overline{K_2}(0)\oplus\operatorname{DES}_\overline{K_2}(\overline 0)$.

The attack will thus go:

Compute¹ all $\Delta(p)=\operatorname{DESX}(p)\oplus\text{DESX}(\overline p)$ for $p$ having its high-order bit clear, and keep track of them in a data structure allowing efficient search of which $p$ yields a given $\Delta(p)$. There's on average $1$ such 64-bit $p$ for each 64-bit $\Delta$, and always an even number since $\Delta(p)=\Delta(\overline p)$.
For $K_2$ with the high-order bit clear and the other $55$ significant bits varying sequentially:

Compute² $\Delta=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(\overline 0)$.
If a $p$ matches $\Delta$ (which has probability $\approx1-e^{-1/2}\approx39\%$ ):

Compute² $\Delta_1=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(1)$.
For each candidate $p$ with $\Delta(p)=\Delta$ (our data structure lists those with the high-order bit clear, and we complement to get them all):

Test¹ if $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus1)=\Delta_1$. When that holds (which is extremely rare):

Test¹,² if $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus2)=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(2)$. When that holds, we almost certainly have³ the right $K_2$ and $K_1=p$. The matching $K_3$ is $\operatorname{DESX}(p)\oplus\operatorname{DES}_{K_2}(0)$.

Expected computational cost is $\approx(3-e^{-1/2})\,2^{54}\approx0.6\times2^{56}$ DES operations, ignoring memory and memory accesses (which in practice would likely dominate). The DES complementation property has halved the work by allowing to restrict to $K_2$ with high-order bit clear.

¹ Using our $(p,c)$ pairs.

² Using a DES engine.

³ Within polarity, which we can't find, because the DES complementation property implies that DESX key $(\overline{K_1},\overline{K_2},\overline{K_3})$ is equivalent to $(K_1,K_2,K_3)$.


How to compute $x^{1/y}$? I'm reading this paper:
Traceable Ring Signature.

I see this in section 4:

$A_1=(\frac{\sigma_s}{A_0})^{1/s}$

My question is how to compute this, such as:

$x^{1/y}$

where $x$ is a generator.

$x^{1/y}$ is the $y$th root of $x$, i.e., the element $w$ that satisfies $w^y =x$.

If $x$ generates a group of prime order $q$, it can be shown that this element $w$ is unique and equals $x^z$ where $z$ is the inverse of $y$ modulo $q$. (One way to show this is to use the fact that $x^a = x^b$ if and only if $a \equiv b \pmod q$.)


On modeling a random oracle hash function which maps $\mathbb{G}_1 \rightarrow \mathbb{G}_2$ How can one model a random oracle hash function which maps $\mathbb{G}_1 \rightarrow \mathbb{G}_2$?

(Assume $\mathbb{G}_1$ and $\mathbb{G}_2 $ to be additive and multiplicative groups of prime order $q$.)

Normally, for a hash $H: \mathbb{G}_1 \rightarrow \mathbb{G}_1$, we would model it as something like as follows

pick $t ∈_R \mathbb{Z}_q$
output $tP$ ($P$ is a generator of $\mathbb{G}_1$)

Assuming that you insist that $H$ preserve the group operation, that is, if $H(A) \times H(B) = H(A+B)$ for any $A, B \in \mathbb{G}_1$, then it would be difficult to come up with an explicit representation (and in any case, the random oracle model doesn't appear to be a great fit).

I'll take the last point first: a random oracle is intended to be something that gives random answers that are consistent with answers that it previously gave.  The problem here is that once this Oracle gives one output (e.g. $H(P) = Q$, then (assuming $P \ne 0$), then this determines all other outputs that the random Oracle is allowed to give.  Any other input can be represented as $kP$ for some integer $k$ (because all nonidentity elements for a group of prime order are generators), and we insist that $H(kP) = Q^k$.

As for an explicit model of the random Oracle which can be evaluated, well, the problem that runs into is if we select a $\mathbb{G}_1$ where the discrete log problem is hard, and a $\mathbb{G}_2$ where it is easy -- any explicit representation of an Oracle (except for the trivial one $H(P) \equiv 1$) would allow us to solve the discrete log problem in $\mathbb{G}_1$; which we assumed was difficult.

If you don't care whether the model can be evaluated, then it's easy; have the random oracle pick an arbitrary $P \ne 0 \in \mathbb{G}_1$ and a random $Q \in \mathbb{G}_2$; then, whenever it gets a query for $H(kP)$, it just returns $Q^k$.


PGP signature on literal data packet I read from PGP spec RFC 1991, section 6.1 (August 1996):

The exclusion of the other fields ensures that detached signatures are exactly the same as attached signatures prefixed to the message. Detached signatures are calculated on a separate file that has none of the literal data packet header fields.

Can anyone explain this a little bit?
Suppose I got an email message, PGP would convert the msg as "literal data packet", and then sign on it. The signature could be stored in other place (i.e. detached). but the signature will be same as storing the signature with the msg, i.e. "attached signatures prefixed to the message".
Do I get it right?

You got it right.
Email consists of several components:
A "From:" address, a list of recipient addresses (To, CC, BCC), several headers used for correctly routing the email to its destination, a "subject" message, and a "body" message (which includes attachments). You likely want to guarantee the integrity of all of these, and the secrecy of at least the subject and the body.
PGP only deals with the body. Nothing else is kept secret, and nothing else is authenticated. It considers everything else (including the "subject" message) to be "data packet header fields".
This means that a PGP signature of an email message will still validate when the subject is altered, the recipient is different, the sender is different, or other headers change. EG if you forward an email and change the subject line to start with "FW: " you'll be the sender, the new recipient will replace the original in the "To" field, the rest of the headers will differ, but the signature will remain valid.
Likewise if an attacker modifies the "From" to trick you into thinking someone else sent the message, changes the subject, or just wants to read the subject or correlate who is talking to whom, they can.
Unfortunately there's no way to fix these vulnerabilities without breaking backwards compatibility with unencrypted email. I therefore recommend avoiding email encryption, and using a system designed for security to begin with such as Matrix or Signal.


Private set supporting adding elements and proving elements exist Is it possible to construct such a set that parties can

Add elements to the set without revealing the elements or knowing the elements presently in the set.
Proving to other parties that a certain element exists in the set in a way that doesn't reveal at which point it was added.

For example, I want Alice, Bob, Cindy and David to start with an empty set. I want Alice to be able to add 5 to the set without revealing 5, Bob to be able to add 6 to the set without knowing 5 is there or revealing 6, and then Cindy, who cooperates with Alice and has access to any necessary information from Alice, to prove to David that 5 is in the set without revealing whether it was Alice or Bob who put it there.

Is there any protocol that would enable such scenario?

If we put in the set $H(x||r)$ instead of x where $r$ is a large enough random value (w.l.o.g assume each x is in the same length). Then, each player can add values without revealing it and the same item can be inserted by different players without knowing it (a collision might happen with negligible probability).
Then with access of the third player, one can prove that the value is indeed in that group.


How to interpret a formula from the handbook of applied cryptography In the handbook of applied cryptography, we can find the following formula for testing PRNG. My question is what does mean 2 in the upper index of the n_00 and others? It is not power because then the formula does not make sense.

The comment by @SEJPM is correct, all those subscripted $n_0,n_{01}$ etc are nonnegative integers counting the occurrences of subsequences such as $0,01$ respectively.

So no problem with exponentiation.


Image sharing without data overhead The idea is to share $n$ images among $n$ persons so that all images can be
reconstructed by someone in possession of all shares.

However, there must not be any data overhead (which means the shares sent
to the persons must not be bigger in size than the original images. In other terms: No data overhead).

The idea is to encode two images $A$ and $B$ like this:

$$Q = A + B + Secret\\
U = A - B + Secret$$

which allows for reconstruction of $B$ through

$$Q - U = A + B + Secret - A + B - Secret = 2B\\
B = (Q - U) / 2$$

after that $A$ can be reconstructed by

$$A = Q - B - Secret$$

$Secret$ is required because simply doing $A + B$ or $A - B$ visually leaks
information about the images to the other persons. The trick is to calculate
the secret through the image $B$. (For example by calculating a hash of B
and then feed it to a PRNG and then use this PRNG to generate the secret numbers you add to each pixel (ask for a new number for every pixel)).

In Pseudo-Code:

seed = hash(B);
r = Random(seed);
for (x,y) to (WIDTH, HEIGHT):
  secret = r.nextInt(255);
  Q[x,y] = A[x,y] + B[x,y] + secret;
  U[x,y] = A[x,y] - B[x,y] + secret;

Arithmetic is $\mod(M)$ of course, where $M$ is a reasonable odd modulus for the
required color depth etc. This method can be extended to more than two images. The odd modulus is what allows one to reconstruct the result uniquely.

The question now is: what fatal security flaws does this method have, if any?

A Flaw

If you try working through your example concretely then you should see at least one issue with decoding.  Consider values mod $8$:

$
A = { 3 } \\
B = {7}   \\
secret = {5 }
$

Using your equations we have:

$
Q = 3 + 7 + 5 = 7 \\
U = 3 - 7 + 5 = 1
$

And for decoding:

$
B = (U - Q) / 2 \\
B = (1 - 7) / 2 \\
B = -6 / 2 ({\text mod} 8)
$

But what is $\frac{-6}{2}$ modulo 8?  How do we get a unique answer here?

Alternatives

Your constraints are a little unclear, but if you're OK with storing $(1 + {\text nrImages})*|{\text image}|$ (A, B, and secret) then use linear integer secret sharing in a traditional manner (below). Obviously this is a little silly seeing as you could use any symmetric encryption algorithm, given that you have a secret.

If you only want to store ${\text nrImages}|image|$ data, and not the secret, then that is harder as you'll have to derive the secret from the combined shares.  For example we could have a small feistel network:

$
Q0 = A + PRF(B)  \\
U  = B + PRF(Q0) \\
Q  = Q0 + PRF(U)
$

Now $U$ and $Q$ are your secrets, protected ONLY by the entropy of A and B and the strength of your PRF.  The entropy in the images could actually be increased without visually altering the typical image.

To decrypt:

$
Q0 = Q - PRF(U)  \\
B  = U - PRF(Q0) \\
A = Q0 - PRF(B)
$

Basic application of LISS

For LISS just generate a random secret, $s$, and compute:

$
Q = A + B + S \\
U = B + S
$

Then, once the shares and the secrets are collected, you can reverse the process via:

$
A = Q - U \\
B = U - S
$


Multiplying integers modulo $2^{255}-19$ using the Curve25519 polynomial reduction algorithm I'm reading the Curve25519 paper and I see that in page 11, under the title "Multiplying integers modulo $2^{255}-19$", it says:

  The coefficients of $x^{10}$; $x^{11}$; ...; $x^{18}$ in $uv$ are eliminated by reduction modulo $2^{255}x^{10} - 19$. For example, the coefficient of $x^{18}$ is multiplied by $19 \cdot 2^{-255}$ and added to the coefficient of $x^8$.

I don't understand why that multiplication and similar others in coefficients 17/7, 16/6, 15/5, 14/4, 13/3, 12/2, 11/1, 10/0 reduce the polynomial modulo $2^{255}-19$ as the paper says.

What is the explanation for that? Does this algorithm has a name or something so I can read its description?

The paper states

  $R$ contains $2^{255}x^{10}-19$, which represents $0$ in $\mathbb Z/(2^{255}-19)$.

In other (slightly simplified) words:
  $$x^{10} \;\;\text{is}\;\; 2^{-255}\cdot19 \text!$$
(Note that this contradicts your comment to the question: $x^{10}$ does not represent $2^{255}$.)

To understand this, recall that a value in $\mathbb Z/(2^{255}-19)$ is represented by a polynomial which has that value at the point $1$. Indeed, evaluating $2^{255}x^{10}-19$ at $1$ yields precisely the modulus $2^{255}-19$, hence identifying it with zero does not change the represented value.
Now observe that reducing modulo $2^{255}x^{10}-19$ means identifying that polynomial with zero.
The resulting relation can also be stated as
$$\begin{align*}
&2^{255}x^{10}-19 \;=\; 0
\\\iff\quad& 2^{255}x^{10} \;=\; 19
\\\iff\quad& x^{10} \;=\; 2^{-255}\cdot 19
\text, \end{align*}$$
as claimed. Thus you can always (for instance: when reducing degrees) replace $x^{10}$ by $2^{-255}\cdot19$ without changing the represented value.


If G is a secure PRG and G' is a function of G, is G' secure? For example: for secure PRG G if I have a G' s.t. G'(k) = G(k)||0, is G' necessarily secure? This question is not for the above example only but for any other possibilities as well. My thinking is that since G is secure (ADV is negligible and PRG is unpredictable), then no matter what I do with G to make G', G' is secure.

Hint: Consider the function $G'(k) = f(G(k))$, where $f(x) = 0$ for all $x$.  Clearly, $G'$ is a function of $G$.  Is $G'$ a secure PRG?


Unconditional authentication I have a few questions regarding universal-hash functions:

Is there a way universal hash functions can be used to provide unconditional authentication in the way the OTP provides unconditional security?
Assuming a TRNG is used how could this be combined to form a perfect cryptosystem, assuming PSK's  are secured?
Is there unconditional non-repudiation(acceptance by third-party) to go along with this?
And lastly, why are these hash functions not used as a SHA-#?

$\;\;\;$ Sure. $\:$ The simplest way is to OTP-encrypt the

$\;\;\;$ output of an almost xor-universal hash family.
$\;\;\;$ That could be used for encrypt-then-MAC, where

$\;\;\;$ the MAC is applied to an ordered pair that indicates

$\;\;\;$ [the message number or how far into the pad to start] and the OTP ciphertext.

$\;\;\;$ (Presumably, the pairing function would be $\;\;\; \langle x,\hspace{-0.03 in}y\hspace{-0.03 in}\rangle \: \mapsto \; $prefixfree$(x)\hspace{.04 in}||\hspace{.04 in}y \:\:\:\:$.)
$\;\;\;$ Yes.
$\;\;\;$ The tightest way I'm aware of to get provable universality while still hopefully being

$\;\;\;$ second-preimage resistant is the trivial construction that just concatenates an output

$\;\;\;$ from a universal hash family with the output from a standard cryptographic hash function.


How were one-time pads and keys historically generated? In the 20th century, it was common for various intelligence agencies and military organizations to use ciphering machines and one-time pads.

However, no source I've seen ever mentions the process of generating the keys and printouts for such use.

Were there special machines for printing / punching them onto a card?
Where did the entropy they used come from?
Were there any significant breaches due to the bad randomness of the keys used?

Your interesting questions deserve to be answered more thoroughly, but here goes:

According to a highly classified document written in 1947 and finally declassified in 2013, the Germans started using a one-time pad system for diplomatic traffic in 1925. This system (GEE) used a one-time pad of digits to encrypt codes by modulo addition. To be clear, these codes, from a large codebook, stood for names, numbers, grammatical features of German, dates, places, objects, etc. GEE traffic was first intercepted in 1934.  That was good for the Allies because World War II in Europe was around the corner, and keys for the GEE system were being generated by a complex mechanical device that was not cryptographically secure.

The German additive generator of wheels and switches had weaknesses that were brilliantly exploited by American analysts:  the phases, cycles, potential overlaps, and limits of the keys became apparent after an exhaustive analysis of captured GEE one-time pads. By March 1, 1945, the U.S. was breaking GEE traffic because the German machine did not create truly random numbers--the Americans soon made a mirror machine based on key periodicity, other weaknesses, etc.
The released document (PDF) says that the GEE keys

…could be predicted in full upon partial recovery through cribs and superimposition to give a new kind of overlap.

Breaking GEE allowed the U.S. access into German diplomatic traffic at the end of the war, especially their dealings with Japan. (See the intriguing reference to uranium in one pre-August 6, 1945 transmission.)
Interestingly, the document says that the Germans could have easily defeated cryptanalysis by changing the set-up of the 240 wheels in the machine, but they never did!  The Germans produced enormous amounts of key material without altering the basic set-up of the device. This led to "ample homogeneous material" being created.

During the Cold War, the Soviets were known to generate one-time pads by having rooms full of typists peck away "randomly."  That's not genuinely random, but still formidable because such results are--as another writer said--from different people and can be muddled further.  For those who disparage one-time pads, consider this:  the NSA refers to the day when the Soviets started using one-time pads in "...all high-level Soviet communications, including the mainline military, air force, and navy nets" for radio traffic--October 29, 1948--as Black Friday, which immediately "...ravaged the cryptologic landscape...".  (See page 19 of The National Cryptologic School's "On Watch", 9-86) Nevertheless, there are instances in which critical key weaknesses helped cryptanalysts exploit key misuse during the Cold War.

Early U.S. efforts to generate random numbers and marry those to plaintext (Telektypton, 1933) depended on a typist and keyboard, a natural but faulty way to think about the problem.  Importantly, the Telekrypton had other weaknesses, such as a looped keystream.  What is so interesting about Telekrypton is that it was widely used, highly regarded, and deeply flawed. After World War II, the idea of using noise for entropy in key generation was made and used by British Intelligence. The man who figured this out retired from GCHQ in the 1980's.  The generator based on his ideas has been regarded as the first to generate truly random keys.


Is the following aggregation scheme private? Is the following scheme private?
By private i mean an untrusted aggregator (UA) cannot reveal anything other then an aggregate function output on plaintext data

Each party holds a secret key $k_i$ and data $d_i$. It sends to the aggregator $d_i H(r)^{k_i}$. $H$ is a hash function that maps elements to a group $N$ in which  $H(r)^S \equiv 1 mod {N}$ Lets say a trusted dealer(TD) for two parties sends to the untrusted aggregator $H(r)^{S-k_1}$ and $H(r)^{S-k_2}$ and UA wants to learn the multiplication of the data of those parties. Then UA computes

$$d_1 H(r)^{k_1}d_2 H(r)^{k_2}H(r)^{S-k_1}H(r)^{S-k_2} =d_1d_2H(r)^{2S}=d_1d_2H(r)^{S^2}=d_1d_2$$

Well, it has the obvious problem that if the UA has both $d_1H(r)^{k_1}$ (from the party) and $H(r)^{S-k_1}$ (from the UA), it can compute $d_1$ directly.


Can I Implement a Well-Trusted Protocol with Well-Trusted Libraries in JavaScript securely? Just for anyone reading this: DO NOT ROLL YOUR OWN ALGORITHM.

Besides that, is implementing a well-trusted protocol with well-trusted algorithms and libraries a good idea? Is this likely to colossally fail like rolling your own crypto? Could this be used in production after enough peer review? (I know that rolling your own crypto is definitely NOT secure)

Let's say I'm trying to implement a simple JavaScript website that generates RSA key pairs, RSA encrypts, and signs, and also AES encrypts data (e.g. an asymmetric key exchange than a symmetric conversation; the simplest protocol out there). If I use well-respected libraries, respected algorithms (i.e. AES & RSA) and peer-review the website, is this likely to have vulnerabilities?

(We're ignoring all the issues of authenticity in code with JavaScript) (Also, I'm not implementing my own algorithm, i.e. AES, to keep that clear)

If you have to implement or design and implement your own protocol then using well established libraries is generally the way to do it. JavaScript is a large eco-system. For such ecosystems it is not adviced to implement your own (partial) "hazardous materials" library for the low level functionality that you require. It is much more likely that there is something out there that would be more secure.

Of course, if there already is a higher level protocol or protocol implementation out there then you should definitely try and use or improve that. Developing transport security - which is often what is tried with JavaScript - is very hard.  This is why most of the time the best solution is to use TLS underneath.


AES in ECB mode weakness In a project that I'm currently working on, we are encrypting some data using AES with ECB mode in a database. Each piece of data being encrypted is very small, no more than 10 characters long.

Very importantly, each entry of that database is encrypted using a different and unique key. Would we gain any security if we switched to AES with CBC mode in this specific scenario?

Also, imagine now that we use AES in ECB mode to encrypt the data in the database, but we now use the same key to encrypt every single entry. If an attacker breaks into our database and steals our data, how many entries would he need to exploit ECB weaknesses and be able to decrypt the information?

For this last scenario, I guess that what I want to find out is if an attacker can decrypt some AES ECB encrypted data if he only has, let's say, around 10 encrypted messages.

Thanks!

Given only what you've said, and assuming the keys are created and stored in a strong manner, using a different key to encrypt database entries mitigates the problem of ECB mode. Namely that identical plaintext, when encrypted with the same key, always outputs the same ciphertext. No security is gained by switching to CBC mode (assuming you can easily store all the keys securely, but see what @Thomas Pornin had to say about that). The practical gain by switching to CBC mode is that you only have to store one key securely. The IV's don't typically need to be protected.

In the second scenario where the exact same key is used for all entries in ECB mode, the advantage the attacker gains is that if he knows a plaintext/ciphertext pair, he now knows everywhere that plaintext appears in the entire database.

For example, lets say the attacker's own info happens to be in the database. He can look up the encrypted version of his gender. He now knows the gender of everyone else in the database (if the ciphertext is the same as his, he knows the entry is for a male, otherwise it is for a female). This same idea can be extended to other fields (age, first name, last name, etc). The key to this advantage is though that the attacker must have plaintext/ciphertext pairs.


Zero knowledge proof of data ownership Fairly new to zk proofs. I am trying to find a article or use case of zero knowledge proofs that can prove that more than one entity owns the same data without revealing the data contents.

Entity A
 - some userID
Entity B
 - same userID as entity A

Is if possible to generate of proof for the userID and ask both A and B to verify that they know what the userID is ?

any guidance would be great !

Zero-Knowledge Proofs are effectively built to prove knowledge of data without revealing it. So what you ask is very possible indeed!

Let's say that we're going to use Schnorr's identification scheme (but tons of other ZKPs exist, you can research Fiat-Shamir, Feige, Guillou-Quisquater, Schnorr digital signature; and those are only the first ones. Now there are SNARKs used in ZCash blockchain etc.).

A and B both know userID, which is converted to some secret/private number x.
Both interact with a verifier to prove knowledge of userID. (g is a public generator for some group, and all this is done modulo some prime number, but for ease of read I won't put that here. You can look the wikipedia for schnorr's identitifation protocol)

They disclose the public key y = g^x. Generate a random r, r' (for A and B respectively). Disclose t = g^r and t' = g^r'. [commitment step]

Verifier sends a number c, c'. [challenge step]

A responds s = r - cx. Verifier checks by computing g^s y^c == t [response step]

Explanation: g^s y^c = g^(r-cx) g^(cx) = g^r = t

Verifier is then convinced that A knows the secret key x, hence the userID.

Same for B: s' = r' - c'x => g^s' y^c' = g^(r'-c'x) g^(c'x) = g^r' = t'.

Both entities A and B proved knowledge of userID without disclosing it.

Hope this helps :)

EDIT: I just tilted on the "owned" part. Here we prove knowledge of, not ownership. I imagine a server could send a unique token derived from the userID and send it to A, derive another to send to B (thanks to some salt). Both A and B would prove knowledge of these tokens, which have been issued by the server, so the server would effectively be convinced of their ownership of that data.

Just an idea in case the previous thoughts weren't really answering your question ^^


Is there a consensus on what text encoding to use when hashing a string? Let's suppose we are hashing a string input from the user via keyboard. A string can be interpreted in many different text encodings (ANSI, UTF-8, UTF-16 and many others). Based on what encoding is used, the underlying binary data and therefore the hashes can be completely different, even though it seems like the same text was entered and the same algorithm was used.

However, I noticed that no matter how many hashing tools I try, hashes are always the same. Hashing apple with SHA-256 gives the same output everywhere.

Is there a consensus on what text encoding to use when hashing a string input?
If there is, how wide-spread this consensus is?
And what is the rationale behind the choice?

Hashing is done on binary, not text strings. It is the job of the character encoding to say what binary representation a string will have. After you represent the text using a particular encoding, then you can hash it. The hash process itself does not care at all about encoding, only binary.

There is no consensus as to what the binary representation a given string will be in every circumstance (i.e. how apple will look in binary), but there is a consensus as to what the hash itself uses as input, which is binary. Most strings use the same encoding (ASCII, UTF-8, etc), and since an encoding is needed to convert a string into a binary representation, the most common encodings will be used when hashing said string. This is not universal, of course. If you enter a string on a Japanese system into a hash function, you may get a different result due to it using Shift JIS or UTF-16, for example. Simply put, there is a consensus in what text encoding to use when encoding text, but it does not specify how that string will be used (e.g. passed to a hash).

Note also that many different text encoding formats are redundant for many characters. ASCII characters are represented as the same string of bits when they are encoded instead as UTF-8. The biggest difference is that UTF-8 is capable of encoding characters that ASCII cannot. Because virtually everyone is using either ASCII or UTF-8, the string apple will be the same in all of them.


How is decryption done in AES CTR mode? Since AES CTR mode uses a unique IV and counter to produce the key to XOR  with the plain text to get the ciphertext, the question is so as to how decryption is done. Since AES CTR produces a different cipher each time for the same password and plain text due to the unique key, how is it possible for the decryption function to produce the same key for a given password to get back the plain text?

Can anyone please explain me on how this is happening?

A slight correction about terminology:

The key is constant when you use CTR.
The IV/counter affect the cipher input and so the keystream varies.

The reason this can be decrypted is that the decrypter knows both the key and the IV/counter. They can calculate exactly the same function as the encrypter did, resulting in the same keystream block, which a XOR then cancels out.

The images on the wiki page for block cipher modes show how both sides compute the same thing.


Are deterministic adversaries as powerful as probabilistic adversaries? SOURCE states the following in the proof of Theorem 2:

  Without loss of generality, I will assume that A is deterministic. If A is randomized, we can determinize it by fixing a sequence of coins that maximizes A’s conditional success probability; it is easy to see that this cannot reduce A’s advantage.

Is this correct? Does it mean that we do not need to consider probabilistic adversaries in cryptographic security games?

Following fkraiem's answer, I would share my thoughts.

Generally speaking, we do not know if randomness helps, i.e., P=BPP is an open question. So probabilistic-polynomial-time (PPT) adversaries may not equal to deterministic ones.

However, it seems that cryptography always (correct me if I am wrong) focuses on advantages (or something similar) related to PPT adversaries. In this case, it is sufficient to consider only deterministic adversaries. Here is a simple proof:

Suppose you have a PPT adversary A that has advantage $p$. Then you can fix all possible random coins and get a bunch of deterministic adversaries $A_1, A_2, ..., A_n$, where $A$ runs $A_i$ with probability $p_i$. Since $Adv(A) = p_1Adv(A_1) + \cdots + p_nAdv(A_n)$ and $1=p_1+\cdots+p_n$, there exists $k$ such that $Adv(A_k) \geq Adv(A) = p$. Note that $n$ may be exponential but each adversary $A_i$ runs in polynomial time. Also, knowing that $A_k$ exists does not imply that one can find it in polynomial time.

===================

Update: The above argument can also be adapted to information-theoretic (i.e., computationally unbounded) adversaries.


RSA: How close d should be to n, given default public exponent e = 65537 For small public exponent e, private exponent d should be less than but close to modulus n.
Is there any particular test, applied in common implementations, to verify that? If so, what would be the threshold?
I have noticed that using Python's Crypto.Util.number.getStrongPrime (docs):
key_size = 2048
prime_size = int(key_size / 2)
e = 65537
p = getStrongPrime(prime_size, e)
q = getStrongPrime(prime_size, e)

the bit length difference between d and n is never bigger than 6.

Is there any particular test, applied in common implementations, to verify that private exponent $d$ is less than but close to modulus $n$ ?

Yes, for some lenient definition of close. FIPS 186-4 is a de-facto standard that some implementations follow. It prescribes$$d\gets e^{-1}\bmod\bigl(\operatorname{lcm}\left(p-1,q-1\right)\bigr)\tag{1}\label{eq1}$$which implies $d<p\,q/2$ thus¹ a $d$ at least one bit less than the modulus is. And in the end of FIPS 186-4 appendix B.3.1 additional criteria 3 lies the prescription:

In the extremely rare event that $d\le2^{nlen/2}$ (where $nlen$ is the bit size of the public modulus), then new values for $p$, $q$ and $d$ shall be determined. A different value of $e$ may be used, although this is not required.

Such test is pointless from a theoretical standpoint when both:

$e$ is chosen before $p$ and $q$, as is usually the case.
The only significant dependence about the value of $e$ of the mostly independently and randomly chosen $p$ and $q$ is that $\gcd(p-1,e)=1=\gcd(q-1,e)$.

Condition 2 should always hold for a proper RSA key generation procedure. Even if $p\bmod e$ and $q\bmod e$ where fixed public constants, condition 2 could still hold for truly small $e$ including $e=65537$, up to at least say 20 bits: revealing that little information about $p$ and $q$ appears unlikely to ease factorization.
The only technically sound rationale for $d\le2^{nlen/2}$ or other test against small $d$ is to prevent the import of an inappropriately generated private key; and in an otherwise proper RSA key generation procedure with modulus bit size $nlen\ge1024$ (the minimum in FIPS 186-4), to catch a malfunction or a bug.
In a fielded security device (Smart Card, HSM), if that test fails at key generation, the Right Thing is to fall into a safe state where the gizmo needs at the very least to be physically reset before anything else goes, perhaps after metaphorically falling on one's sword, that is burninating/zeroizing all secret material. In code under development, that test should be an assertion. If something needs to be rubber-stamped, do whatever is morally defensible to satisfy the authority with the rubber-stamp.

I have noticed that using (strong primes per some criteria) the bit length difference between $d$ and $n$ is never bigger than $6$.

It was not tried hard enough, or something is broken in the key generation procedure. There is no good reason why that would hold for $e=65537$. That's even though, contrary to $\eqref{eq1}$ mandated by FIPS 186-4, $d$ is computed per
$$d\gets e^{-1}\bmod\bigl((p-1)(q-1)\bigr)\tag{2}\label{eq2}$$
As explained in that other answer, $d$ per $\eqref{eq2}$ is expected to be roughly uniform in the interval $\bigl[(1+\varphi(n))/e,\varphi(n)\bigr)$ and we should sometime see it near the bottom, thus with 15, perhaps 16 bits less than the public modulus. However we need to perform about $e$ attempts to approach that limit.
If the test against $d\le2^{nlen/2}$$\eqref{eq1}$ is used, that should be with $d$ per $\eqref{eq1}$. Absent error, that test mathematically can't fail for $d$ per $\eqref{eq2}$ with $e<2^{256}$ and $n>2^{1023}$ as mandated by FIPS 186-4. Failure of the test is at least theoretically possible when using $\eqref{eq1}$, should $\gcd(p-1,q-1)$ happen to be huge. Which is extremely unlikely for proper generation of $p$ and $q$.
Both $\eqref{eq1}$ and $\eqref{eq2}$ are allowed by PKCS#1 since the origin, thus $\eqref{eq1}$ is unlikely to cause an interoperability problem even if a private key is moved across implementations (which should be the only case when the method used for the determination of $d$ matters, since all mathematically valid $d$ for a given public key produce the same numerical results when properly used in RSA). Contrast with the use of $\eqref{eq2}$ which has fair probability to lead to failure at key import by an implementation written with FIPS 186-4 as a reference.

¹ By definition of $e^{-1}\bmod\lambda$, and given that $\lambda=\operatorname{lcm}\left(p-1,q-1\right)$, and given that primes $p$ and $q$ are large, thus $p-1$ and $q-1$ both are multiple of $2$.


TLS Key Exchange content in DHE vs. ECDHE When the key exchnage is DHE, the server key exchange message contains the key paramteres: g^y (the server's public DHE value), g, p. Can you clarify to me what is the server key exchange content if the key exchange is ECDHE? What paramters are included there?

TL;DR: The public key and the name of the group.

RFC 4492 (especially section 5.4) has all the details for you.

What you basically do is the following:

You send a point on the curve (your public key, ie $Q=y\cdot G$)
You send a description of the curve, this is either:

Some identifier for the curve, for example 23 if you wanted to use the most-commonly used P-256. This is what happens always in practice, in fact many browsers don't even support explicit curve parameters.
A full description of the prime or binary curve, ie the relevant values to define the field, the relevant values to define the curve parameters over the field and the relevat base point.


About ORAM initalization and running out of space I have two questions about ORAM

Since at the beginning,the server allocates unused storage for ORAM cient,there are no user's data in the storage.if now client access the storage the server will know that client is writing data except that the client read empty block to achieve oblivious.some paper mention that using a third trust party to initialize the ORAM. or just deem that the client itself have finish initilization and upload the storage to server. so how ORAM client initialize the storage?
All papers I read about ORAM scheme fixed the capacity at the begin of setup,that's not fitting into the real situation. since client's data will increase with time. Are there any scheme to increase ORAM storage with time while maintaining oblivious?

Are there any scheme to increase ORAM storage with time while maintaining oblivious?

I found this paper that addresses the issue of obliviously resizing:

Moataz, Tarik, Travis Mayberry, Erik-Oliver Blass, and Agnes Hui Chan. "Resizable tree-based oblivious RAM." In Financial Cryptography and Data Security, pp. 147-167. Springer Berlin Heidelberg, 2015.

I also recall a talk by Elaine Shi where she discussed resizable ORAM, but I can't find the relevant paper.


How to recover private key in ElGamal when random value k is known Given following ElGamal encryption scheme: $\delta = M(\alpha^a)^k \mod{p}$. Assume that an attacker knows the random value $k$. How can he recover the private key $a$?

I know that it's possible to recover the message M by computing $\frac{m}{\alpha^a} \mod{p}$. But how can we now derive $a$ from this information and not end up with a discrete logarithm problem?

How can he recover the private key $a$?

They can't. First, note that $\delta=M(\alpha^a)^k\bmod p$ you can (as you already noted), recover $M$ and thus construct $\delta'=(\alpha^a)^k\bmod p$ given $\delta$, $\beta=\alpha^a$ and $k$. Now you are in a situation which is equivalent to that after a Diffie-Hellman handshake. You are given your own ephemeral DH key $k$, the generator $\alpha$ and the shared secret $\delta'$, if you now could actually find $a$, that is the other party's DH key, this would completely and utterly break any form of $a$-reuse which is assumed to be secure.

More formally:
Let $\mathcal O(\delta',k,\alpha,\mathcal G)$ be an oracle, that returns $a$ from $\delta'=(\alpha^a)^k$ in the group $\mathcal G$. Now let $(\beta,\alpha,\mathcal G)$ be an arbitrary discrete-logarithm instance, such that $\beta=\alpha^x$ in $\mathcal G$. Now note that if we call $\mathcal O$ with $\mathcal O(\beta,1,\alpha,\mathcal G)$, we get $x$ back, the discrete logarithm and have thus solved the discrete logarithm problem efficiently using this capability.

This means that if we could recover $a$ from $(\delta',k)$ we could solve the discrete logarithm problem efficiently, but as this is assumed hard, we can't efficiently recover $a$ from $(\delta',k)$. Of course you may also want to note that coming up with $(\delta',k)$ doesn't require any special knowledge, anybody who is ElGamal-encrypting $M=1$ constructs this pair.


Can I connect the hardness of a linear short integer solution problem to that of SIS problem? As we know, SIS problem is defined as: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $\mathbb{Z}_q^{r \times n}$, it is hard to find elements $s \in \mathbb{Z}_q^{n}$ with some bounded norm $||s||\leq B$ s.t. $f_A(s)$=0 for random $A$.

If I modify the above definition as follows: consider a function $f_A(\{s_i\})$=$\sum_{i=1}^{b} a_iAs_i$, where $a_i \in \mathbb{Z}_q$ are random and $b$ is an integer that is no larger than $|q|$, it is hard to find $\{s_i\} \in (\mathbb{Z}_q^{n})^{b}$ with bounded norm $||s_i||\leq B$ s.t. $f_A(\{s_i\})$=0 for random $A$ as chosen in the original SIS problem. Intuitively there seems to be a connection between these two problems. Can I reduce the hardness of this new problem to that of the aforementioned SIS problem? Thank you in advance.

I would say that, in general, your problem is actually easier than $SIS$.

Let's call your problem $LSIS_{n, q, B, m, b}$. First of all, notice that if you can find a solution $s$ to $SIS_{n, q, B, m}$, than $s_1 = s_2 = s_3 = ... = s_b = s$ is a solution to $LSIS_{n, q, B, m, b}$, which already means that your problem cannot be harder than SIS.

Furthermore, notice that for fixed parameters $n, q, B, m,$ and $b$, there are several easy instances for $LSIS$. Some examples,

if some $a_i$ is equal to some $a_j$, then $s_i = -s_j = (1, 0, 0, ..., 0)$ and $s_k = 0$ for $k \not \in \{i, j\}$ is a very short solution to your problem;
if there is short pair $a_i \ge a_j$ such that $B \ge a_i$, then $s_i = a_j\cdot (1, 0, 0, ..., 0)$, $s_j = -a_i\cdot (1, 0, 0, ..., 0)$, and $s_k = 0$ is a solution to your problem, since $||s_i|| \le ||s_j|| \le a_i \le B$;
if there is a pair $(a_i, a_j)$ such that $a_i^{-1}$ and $a_j^{-1}$ are small, then $s_i = a_i^{-1}\cdot(1, 0, 0, ..., 0)$, $s_j = -a_j^{-1}\cdot(1, 0, 0, ..., 0)$, and  and $s_k = 0$ is a solution to your problem.

Notice that for $b = 2$, if you choose the values $a_1$ and $a_2$ uniformly at random from $\mathbb{Z}_q$, then that first easy case will already appear with probability $1/q$, which means that if $q$ is polynomially big in $n$, then a random instance of your problem can be solved trivially with non-negligible probability. But $SIS$ is hard in average for $q = poly(n)$. Therefore, at least for these parameters, you cannot reduce $SIS$ to an average-case version of your problem.


Conforming Randomness To An Alphabet Imagine that we're trying to create a function to generate a random string conforming to a user-supplied alphabet. That way, users can generate random strings with given characters. Something like:

string random_string(int length, string alphabet)

Now, the alphabet could be any combination of characters from length 2 to 256. So, to generate hex characters, you'd pass the string "0123456789abcdef"...

So the question at hand is which is the better unbiased method to generate the desired random data, assuming a stream based full-byte random source (/dev/urandom, etc)...

Base Conversion

First, we compute how many "bytes" we need from the stream:

int bits_per_block = floor(log(strlen(alphabet), 2) + 1);
int bytes = ceil(length * bits_per_block / 8);

Then, fetch randomness from the stream up to the required number of bytes, and store it in a "buffer".

Now, walk the buffer and do a numeric base conversion between 256 and the destination base. Then substitute the destination base for the characters from the alphabet. That's it.

Note that you'd need to convert the entire random buffer, and then cut off the most significant part of the result to size it properly (because the ceil call can cause it to over-generate). This is good, because it means that every generated character of the result will be unbiased.

This has the advantage that you're always fetching a known amount of randomness, up to a maximum of 1 extra byte.

It has a disadvantage that it requires twice the memory (one for the buffer, and one for the return), and that it's fairly complex (base conversion is not trivial).

Here's a sample implementation in PHP of the base conversion algorithm, and here it is in action.

Value Picking

This is the standard integer generation algorithm. Basically, we'd have an algorithm like:

character generateByte(string alphabet) {
    int len = strlen(alphabet);
    int max = 256 - (len % 256);
    do {
        int byte = get_random_byte();
    } while (byte > max);
    return alphabet[byte % len];
}

Note that the max ensures that the maximum generated int is divisible by the len parameter. So if we were generating into base 10, max would be 250, and byte % 10 would therefore be unbiased.

It has the advantage that it's a lot easier to implement. But it has a disadvantage that it could not terminate, or use a LOT of randomness to generate a string, especially for some odd bases...

So, is the Base Conversion an appropriate route to take? Or should we stick with the "value picking" approach?

First of all, it's not true that, in the "Base Conversion" case, that the output is actually equidistributed.  It is easy to show that, if the size of the alphabet isn't a power of 2, and that there is a bound on the amount of entropy you can draw, that no algorithm can generate a truly equidistributed output (although you can come arbitrarily close).

In the case of your algorithm, well, we can make a fairly bad case by considering an alphabet of 127 characters, and asking the algorithm for a string consisting of a single symbol; your algorithm will set bytes = 1, and thus draw a single random byte; this means that some (most) characters will be generated with probability $2^{-7}$, but a few will be generated with probability $2^{-8}$ (that is, a factor of 2 less).  This can easily be fixed by requesting a fixed constant (say, 16 bytes) above what you actually need.  This will reduce the ratio of probabilities for various strings to at most $1 + 2^{-128}$, which is probably good enough.

That said, I would personally recommend the value picking approach.  The value of that approach is that it is simpler; and simpler means easier to get right (and to verify that it is right), and getting things right is quite important for security.

Now, one complaint with your version of the value picking approach would be that if the alphabet is small, it'll take quite a few random outputs before you come approach bytes in the correct range.  This is easy to fix if you look at only the lower $n$ bits of the random output (where $2^n$ is the smallest power of 2 greater than or equal to the string size).  With this change, the average number of random bytes the value picking approach will use will be less than twice the output size.


What benefits do substitution boxes and permutation boxes offer in DES? I understand that with more encryption rounds the more complex the ciphertext becomes due to multiple substitutions and permutations. What I don't understand is the purpose of these features.

I am under the impression that key length and the number of subkeys are the dominant factors in deciding the strength of a cipher as they are what encrypts the  plaintext. I’m not disregarding the fact that plaintext must also undergo diffusion to avoid statistical analysis and confusion to obscure the relationship between the texts.

What benefits do substitution boxes and permutation boxes offer in DES? Don't these permutations and substitutions become redundant after a few rounds? Do the effects eventually plateau?

In general, the key length and number of rounds are the dominant factors in deciding cipher strength. But you need to consider how the rounds are constructed and how the key is used.

Substitution and permutation are the bread and butter of DES. That's literally all it is - substitution, permutation, and XOR.

Here is a diagram of the DES fiestel function for reference.

The DES substitution boxes ($S1$ through $S8$ in the diagram) are the only non-linear part of the cipher. Without them, the cipher would be nothing but XOR operations. It would be easy to come up with (relatively simple) linear equations relating the key, plaintext, and ciphertext bits.

The DES permutations ($E$ and $P$ in the diagram) propagate and distribute the bits of the previous output. Without these permutations, any small change in the plaintext/ciphertext would result in a small change in the resulting ciphertext/plaintext.

Suppose $E$ and $P$ don't exist and there are two plaintexts which are identical except for a difference in the first bit.

Since the difference is in the first bit, it will be fed into $S1$. $S1$ outputs 4 bits, so at most the first 4 bits will be different.

Repeat for the 2nd round. Since $S1$ takes the first 6 bits as input, those 4 bits go through $S1$ and output another 4-bit difference.

As you can see, after any number of rounds, the difference will still only be in the first 4 bits.

Because of the Feistel structure of DES where the left and right halves get swapped through the cipher, up to 8 ciphertext bits can be different: the first 4 bits in the left 32-bit half, and the first 4 bits in the right 32-bit half. Not only does a small change in the plaintext result in a small change in the ciphertext, the differences have locality. This makes differential cryptanalysis very easy to perform.

I hope that was the answer you were looking for.


Difference on montgomery curve equation between EFD and RFC7748 There is a subtle difference between the 2 implementations for a Montgomery curve defined from the 2 following links

https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html

      A = X2+Z2
      AA = A^2
      B = X2-Z2
      BB = B^2
      E = AA-BB
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = (DA+CB)^2
      Z5 = X1*(DA-CB)^2
      X4 = AA*BB
      Z4 = E*(BB+a24*E)

https://tools.ietf.org/html/rfc7748

       A = x_2 + z_2
       AA = A^2
       B = x_2 - z_2
       BB = B^2
       E = AA - BB
       C = x_3 + z_3
       D = x_3 - z_3
       DA = D * A
       CB = C * B
       x_3 = (DA + CB)^2
       z_3 = x_1 * (DA - CB)^2
       x_2 = AA * BB
       z_2 = E * (AA + a24 * E)

This AA / BB change on the last line does affect the result of a point multiplication with same input parameters.

Is there a reason for that difference ?

This is not a bug: it arises from different choice of sign in the definition of a24 := (a ± 2)/4; the RFC uses - while the EFD uses +.

RFC, following the Curve25519 paper:

  The constant a24 is (486662 - 2) / 4 = 121665 for curve25519/X25519 and (156326 - 2) / 4 = 39081 for curve448/X448.

EFD, following Montgomery's paper (paywall-free):

  Assumptions: 4*a24=a+2.

This apparent discrepancy was raised by Paul Lambert on the CFRG mailing list during discussion on the draft.  It doesn't really matter which one you choose, as long as you're consistent about it!


Does a cofactor of an elliptic curve have to be an integer? What are the implications of a curve having a non-integer co-factor for its generator point? Is that even possible?

The implications are that someone screwed up some calculation.

By Lagrange's theorem, the co-factor must be an integer.


Are there reasonably secure online voting implementations e.g. for student council elections? Assume a university want to elect the student council. This was done via paper ballot and there is a need to reach more students for voting, so electronic voting is on the table.

While researching existing solutions I came across Helios: helios voting and agora voting

Both seem to implement somewhat peer-reviewed schemes to do a online vote, but my impression is that the devil might hide in the details.

Has anyone here experience using these schemes?
We plan to implement such an online voting scheme and would authenticate the voters via the university LDAP. Which cryptographic obstacles or security problems could we face?

In short, my answer is no; keep paper ballot, they have essential virtues unmatched by electronic substitutes; in particular, giving voters confidence that the result of the vote is not grossly manipulated.
Full disclosure: I co-founded a (French) association towards citizen oversight of voting means, essentially opposing electronic voting for political elections. I take some pride in our contribution (however little) to an observed pause in the deployment of electronic voting machines in France since 2007.
Electronic voting has two different meanings:

voting in polling stations using dedicated electronic voting machines;
voting remotely by electronic means such as mobile phone, web browser.

The question seems to be about 2, and I'll focus on that. A major problem is that it does not propose any means to discourage vote selling or voting under duress. In most proposed systems, handing over one's credentials to vote (perhaps: during the closing of the polling time-frame) will do the trick.
Contrast with the traditional voting system used for political elections (in France, and many countries with a long history of voting, thus a long history of voting fraud, and fixes to the voting code to fight that). Voting takes places according to procedures carefully designed to discourage vote selling and threats to vote in some prescribed way, by making it hard (and prohibited) that anyone but the voter knows how the vote was cast (that goal is not reached for mail voting, instead this is purposely kept marginal by requiring formal prior declaration to police that normal voting can't be performed for some reason, like traveling). Towards that goal, complex measures have evolved over time:

generally, making it illegal and difficult to act in any way such as showing how one voted, or transferring one's right to vote to another person (voting requires an official ID with photo, in all but very small towns).
requiring the insertion of paper ballot materializing the vote in an opaque envelope in a voting booth ("isoloir" = isolating device) where no one but the voter is allowed;
making paper ballots with a distinctive sign invalid (and not counted); this is a countermeasure to the practice of marking the paper ballots handed for vote under duress/pay with a distinctive sign, so that the bribed/intimidated voter can fear that if s/he does not use that paper, it will get noticed at vote counting;
often, making the paper ballots available by multiple means (at the polling station, and by mail), so that voters can be seen not grabbing a ballot from the stack X at the polling station, but still actually vote for X by using a paper ballot for X that they brought secretly (ticking a choice with a pen would be superior to paper ballots in this regard, but may bring back the previous problem; also, separate availability of paper ballots at least helps the reading impaired).

Another issue with both forms of electronic voting is that it makes fraud by a very small group of persons conceivable, when the traditional voting system makes that impossible for large-scale voting with multiple independent polling stations (this argument thus does not apply to a small local student council with a single polling station):

Votes are cast in urns which remain observable from vote start till end of counting (French urns are transparent, in reaction to fraud).
Votes are counted locally at each polling stations; anyone is allowed to obverse counting and check what the tally at the polling station where s/he voted.
The tally at each polling station is made publicly available in print, so that any observer can check that the tally at the polling station where s/he voted was not modified, and check the addition of counts thus the election result (there is a hierarchy of two levels of publication, but the principle remains valid).

Most importantly, a rational person/voter can be convinced that the traditional system does not allow centralized fraud; but electronic voting systems which manage to keep what one voted secret do not meet (or even have) that goal, to my knowledge. At best, the organizers of an electronic election can be convinced that there was no fraud; that's not the correct objective (and it is not even really met by any practical system that I have seen).
Again restricting to voting remotely by electronic means, some usually poorly mitigated risks include:

Browsers (e.g. on university computers) modified to vote as asked by the voter as far as the screen is concerned, when the vote is really cast differently on the network side; that's far from rocket science.
A server pretending to be the real voting server(s) to the voter's browser, performing Man-in-the-Middle attack at some point on the network; if the cryptographic defense is https with TLS as in normal web browsers, that's defeated with a copy of the private key of the true server (certificates emitted by certification authorities in breach of CPS, which abound, would also trick most voters, albeit with a risk of being caught by an observer comparing the certificate shown by the browser with the real thing obtained out-of-band). The MitM machine can go undetected to a real voting server (and even inquisitive client) scrutinizing IP address and routing info, if the MitM machine is appropriately inserted in the network near either the real voting server or the targeted browser, and competently programmed; a university network is ideal grounds for such attack.
In many systems, plain subversion of the machine(s) counting the votes. Having several counting machines run by multiple parties helps, but what should be the rule when they do not agree?
Denial of service; it's easy to prevent voting by attacking the voting server or network infrastructure, and conceivable (especially if observers are allowed) to create some ESD/EMP that zaps the server.
Loss of secrecy of individual votes, threatened by:
penetration of the central computer(s) running the election; that's a problem the industry hardly knows how to tackle when the computer operators are trusted; and in this situation, we'd like not to trust them!
compromise of the voter's device (this is somewhat mitigated by the diversity of devices)
brittleness of web security practices; e.g. consider an https connection used for a "please confirm your vote" page visually showing the ballot selected: if there's a jpg image shown and no special precaution is taken, it is likely that mere analysis of the length of TCP/IP packets reveals the choice made.

Note: there's a simple countermeasure, mitigating 1, 2, 5.2 and 5.3, that I have seldom seen proposed: the voter would key-in a few digits, received secretly, different according to the vote cast. That would largely remove the browser and network from the attack surface. This is not without its own security problems, but the real reason why some proponents of electronic voting dislike it is that it is low tech, and acknowledges the need to distrust high tech in matters of voting.

Addition: any voting system, electronic of not, must balance between two antagonist goals:

Keeping individual votes secret, including to whoever runs the election; because otherwise, individual retaliation could ensue.
Making the outcome convincingly representative of the intention of voters, to as many reasonable persons as feasible; because the elected needs legitimacy.

We can reach either goal by a sacrifice of the other (if all individual votes are made public along the name of the voter as the election goes, the outcome is verifiable; if we choose the election's winner by stone/paper/scissor, voting in one's mind is enough).
Electronic voting complicates both goals considerably, particularly when you consider that whoever runs the election is an adversary (in the sense of that in crypto) trying to breach vote secrecy and accurate vote counting. Simply put, I do not see an even mildly-satisfactory solution.


Birthday attack to find near collision Follow up on this question: How efficient are the generic attacks regarding near-collision-resistance?

  Let $H:\{0,1\}^∗→\{0,1\}^n$ be a cryptographically secure hash function. Let $k\in \mathbb{N}$ be $0 \leq k \leq n$. Without further details, how much effort is needed to find two strings $x_1,x_2$ such that $\Delta(H(x_1),H(x_2))\leq k$ holds? $\Delta(\cdot,\cdot)$ denote the hamming distance.

The accepted answer mentioned that it requires $\displaystyle \sqrt \frac{1}{p}$ hashes where $p=\displaystyle \frac{\sum_{i=0}^{k}{n\choose i}}{2^n}$ to have probability of $1/2$ to obtain one near collision pair. Why is that?

I tried to work out the math using birthday paradox. I get the minimum number of hashes one has to compute is something like:

$$\frac{2^{n/2}}{\sqrt{\sum_{i=0}^k{n\choose i}\cdot 2^i}}$$

Where did I go wrong ?

OK, so let's go from start to finish on this.

Note that for a hash function we can model the output bits as independent binary variables and thus apply a binomial distribution model to find out how many bits take a certain value. So the Probability that $k$ bits don't match is $\binom{n}{k}2^{-(n-k)}2^{-k}=\binom{n}k2^{-n}$ (intuitively we aggregate all possible allowed missmatches here). Now we want that at most $k$ bits don't match and thus we can sum: $\sum^k_{i=0}\binom{n}i2^{-n}$. Now note that $2^{-n}$ is a constant factor and thus $p=\sum^k_{i=0}\binom{n}i2^{-n}=2^{-n}\sum^k_{i=0}\binom{n}i=\frac{\sum^k_{i=0}\binom{n}i}{2^n}$, now finally we can use said birthday argument to find the number of messages needed to be $\sqrt{\frac1p}=\sqrt{\frac1{\frac{\sum^k_{i=0}\binom{n}i}{2^n}}}=\sqrt{\frac{2^n}{\sum^k_{i=0}\binom{n}i}}=\frac{2^{n/2}}{\sqrt{\sum^k_{i=0}\binom{n}i}}$ which is the expected result.

Note as mentioned in this answer, this result can be proven more rigourously as well, which was done in "Memoryless Near-Collisions via Coding Theory" by Mario Lamberger, Florian Mendel, Vincent Rijmen and Koen Simoens (PDF).


Is there a function similar to a hash function, but it's reversible? I am currently making a Python game where the user's high score gets encrypted and stored in a log (a text file). The reason for this encryption is because I don't want the user to be able to enter something (say, 1000000) into the text file. Is there a function that, given a string, will generate a string that looks random to the user (but it's not), and unlike a hash function, can be reversible? Does anyone know how to make one of these in Python? Thanks!

While not reversible, HMAC seem to be a plausible solution.

HMAC is a construct that adds a "key" to the hash digest, your program generates it with a symmetric key that's somewhat hidden in your program. You verify the player's scores by hashing the score with the key and compare the digest - this is a very typical tag comparison of message authentication code.


Winternitz-OTS+ with Poly1305 Would it be safe to implement Winternitz OTS+ using Poly1305 as a parameterized MAC? It's very fast and apparently very secure but with the caveat that keys cannot be used more than once, which is fine for this application. Does anyone know if Poly1305 has any features that differ from a normal HMAC that would make it unsafe for this application?

The requirement of the function in Winternitz OTS+ is a pseudorandom function family, or PRF: a family of functions $F_K\colon \{0,1\}^n \to \{0,1\}^m$ such that if $K$ is uniformly distributed in all $k$-bit strings, then $F_K$ is indistinguishable from a uniform random choice of function $U\colon \{0,1\}^n \to \{0,1\}^m$.  Specifically, the best known random algorithm $A(G)$ taking a function $G\colon \{0,1\}^n \to \{0,1\}^m$ to a true/false value and having a plausible computational cost has a negligible PRF advantage, $$\operatorname{Adv}^F_{\mathrm{PRF}}(A) = |\Pr[A(F_K) = 1] - \Pr[A(G) = 1]|,$$ which compares the probability that $A$ returns true for $F_K$ under uniform random distribution on $K$ to the probability that $A$ returns true for a uniform random function $U$.

Poly1305 is a one-time message authentication code, or one-time authenticator/MAC: a family of functions $H_K\colon \{0,1\}^n \to \{0,1\}^t$ such that if $K$ is uniform random, then given up to a single message $M$ and its authentication tag $T = H_K(M)$, an adversary has no hope of finding another message $M'$ and authentication tag $T'$ such that $T' = H_K(M')$—it resists forgery after a single message.  That is, the forgery probability for a random algorithm $A(M, T)$ giving $(M', T')$, namely $\Pr[M' \ne M, H_K(M') = T']$, is negligible.

A PRF makes a passable MAC, even a one-time MAC, although as you note Poly1305 is a much more efficient one-time MAC than a PRF.  However, a one-time MAC does not make a passable PRF.  Why not?  The adversary's algorithm $A$ in the notion of PRF advantage is allowed to call the function more than once.

To make this concrete, consider the secure one-time MAC $H_K(M)$ for $K = (K_0, K_1) \in \operatorname{GF}(2^{128}) \times \operatorname{GF}(2^{128})$ and $M \in \operatorname{GF}(2^{128})$ defined by $$H_{K_0, K_1}(M) = K_0 M + K_1.$$  (This is essentially GHASH, of AES-GCM, limited to one message block, which is a polynomial evaluation MAC much like Poly1305.  We can naturally interpret any 128-bit string as an element of $\operatorname{GF}(2^{128})$ given a choice of irreducible degree-128 binary polynomial like the standard GHASH one.)

How do we define the algorithm $A$ to distinguish $H_K$ from $U$?  We can first compute $T = K_0 M + K_1$ and $T' = K_0 M' + K_1$ by evaluating the putative $H_K$ on two different inputs, and then solve for $K_0$ and $K_1$ using secondary school algebra.  Then we can immediately distinguish $H_K$ from a uniform random function $U$ with high probability by computing the candidate function on $M''$ and checking whether we get $K_0 M'' + K_1$: with high probability, a uniform random function will give something else.

Actually, Winternitz OTS+ requires a slightly weaker notion than pseudorandom function family, namely key one-wayness: for uniform random key $K$ and input $X$, letting $Y = F_K(X)$, the success probability of the best known algorithm $A(X, Y)$ for recovering the key (or an equivalent), $$\operatorname{Adv}^F_{\mathrm{KOW}}(A) = \Pr[Y = F_{A(X, Y)}(X)]$$ is negligible, as long as it has a plausible computational cost, where $Y = F_K(X)$.  I leave it as an exercise to the reader to define such an algorithm $A$ for a polynomial evaluation MAC like the above example.


What is the malicious potential of a key-substitution-attack? What is the idea behind a key-substitution-attack?

We start from a given pair of message $m$ and signature $s(m)$. The signature can be verified by anybody in possess of the public key $y$:

$v(m, s, y)= ok$

Now, by some mathematical magic (details are not relevent for the moment), an attacker shall be able to generate a new public key $\bar y$, so that

$v(m, s, \bar y)=ok$

However, I cannot identify the malicious potential of that attack: The recipient, getting $(m, s)$ will still use the original public key $y$, to verify $(m, s, y)$, so what is going to be compromised from the attacker just having such key $\bar y$ ?

As is, the attack seems rather pointless. But one malicious potential is that because $\bar y$ allows to successfully verify a genuine message $(m,s)$, the verifier might grow trust in it and use $\bar y$ instead of $y$ in order to verify other messages. If we assume this, practical issues could arise:

That the attacker can somewhat find $(\bar m,\bar s)$ (with $\bar m\ne m$ and/or $\bar s\ne s$ (depending on definition of security of a signature system) so that $v(\bar m,\bar s,\bar y)=\text{ok}$ ; $(\bar m,\bar s)$ will be accepted by a the verifier and in effect is a practical forgery.
That the legitimate verifier handed some genuine $(m',s')$ pair (such that $v(m',s',y)=\text{ok}$, and $m'\ne m$) finds that $v(m',s',\bar y)\ne\text{ok}$, and rejects the valid message; this in effect is a denial of service.

In many signature systems where the question's attack is possible, 1 or/and 2 is possible.

Elias suggests that if making a $\bar y$ as in the question is possible, then the signature scheme looses non-repudiation. That's an interesting point of view, but mine is that the definition of non-repudiation is a convention between parties, and that it would be a slippery slope (and an unusual one) to allow exhibition of $\bar y\ne y$ such that $v(m,s,\bar y)=\text{ok}$ to be a valid reason to stop accounting the legitimate holder of the private key matching the public key $y$ as responsible for having signed $m$ whenever $(m,s)$ becomes publicly available and $v(m,s,y)=\text{ok}$.

Two technical reasons are that, without breaking the established definition of security of a signature scheme, it could be that $\bar y$ was produced

from $y$ and/or $s$, by anyone;
or additionally with knowledge of the private key for $y$, e.g. by the legitimate key holder wanting to repudiate his/her approval of $m$.

Thus is we allowed what Elias proposes, we'd need to use signature schemes with a stronger and more complex definition of security than we do, for no benefit that I can discern beyond preventing what is explained in the first part of the answer.


Can a One way function also be its inverse? This is from my homework:

Prove that if there exists a one-way function, then there exists a one-way function f such that

$f(0^n ) = 0^n$ for every $n$.

Note that now for infinitely many values $y$, it is trivial to compute $f^{−1}(y)$.

While I don't expect someone to spell the answer out for me, setting f as the inverse function, we can say the inverse exists. As a result, it is not a one-way function.

One-way function doesn't mean that it's impossible to reverse on EVERY output.
One-way function means that's it's hard to invert on an output picked at random over the set of the outputs.

You can read in more details the definitions given in the following link:

https://crypto.stanford.edu/pbc/notes/crypto/oneway.html