Zero Knowledge Proof AND Diffie Helmann? From my research, I think what everything says is that the result of a zero knowledge proof (ZKP) is that the participants end up with a shared secret that can be used as a session key for a further symmetric encryption session between those two parties.  And then, all of the articles say that you follow this up by starting up something like a Diffie-Helmann (DH) session.

If I just got a secure key from the ZKP - why do I need DH?  Why don't I just expand the ZKP result and go from there?

From my research, I think what everything says is that the result of a zero knowledge proof (ZKP) is that the participants end up with a shared secret
  …
  If I just got a secure key from the ZKP - why do I need DH? Why don't I just expand the ZKP result and go from there?

You obviously misunderstood ZKP at its core.

Zero knowledge proofs are interactive or non-interactive protocols or schemes for proving membership of a common input in a formal language (or the analogous thing for promise problems).

In the basic ZKP setting, there are only two parties, in which case something that is unknown to one party is simply not a shared secret. For proofs (or for arguments), the verifier is only necessarily convinced that a valid secret exists, not that the prover has one. Also see proofs of knowledge.


rotor machines: secrecy of wiring During the heydays of rotor machines, the internal rotor wiring was always a closely guarded secret. Even fully cleared repair staff was not allowed to do anything that could reveal it.

As the wiring seems to be considered part of the algorithm 1 and not some form of long time key, would it be even possible to design a secure rotor machine that fully follows Kerckhoffs's principle?

I've found conflicting reports on this. On the other hand, there are still unbroken Enigma-encrypted messages, even though the details of the Enigma are known nowadays.

Off the top of my head, I see no obvious theoretical reason why a hypothetical Enigma-like rotor machine cipher with publicly known rotor wiring couldn't be secure, even by modern standards.  It would presumably need many more rotors and a much more complex stepping scheme than the WWII Enigma had, but that's just engineering detail.

A basic rotor machine cipher can be described mathematically as consisting of two alternating types of layers: the rotor wiring itself, which is an arbitrary (but fixed) invertible map applied to the symbol being encrypted, and the offset between the rotors, which is a simple linear shift of the symbol space that depends on both the key (i.e. the initial rotor positions) and the position of the symbol within the message.  That is, mathematically, we can write the encryption process as:

$$ \begin{aligned}
x_0 &= p, \\
x_i &= f_i(x_{i-1} +_A s_{i-1}) \quad\forall i \in \{1,\dots,n\}, \\
c &= x_n +_A s_n,
\end{aligned} $$

where $p$ is the plaintext input symbol, $c$ is the corresponding ciphertext output, $n$ is the number of rotors, $+_A$ denotes addition modulo the cipher alphabet size $A$, the invertible function $f_i: \{0,\dots,A-1\} \to \{0,\dots,A-1\}$ denotes the fixed non-linear permutation of the cipher alphabet applied by the $i$-th rotor wiring, and $s_i = s_i(K,t)$ is the relative offset between the $i$-th rotor and the next one at message position $t$ with the initial key $K$ (with $s_0$ and $s_n$ denoting the absolute offsets of the first and the last rotor respectively).

(Note that the abstract rotor machine described above doesn't even try to include various Enigma-specific features like the reflector or the plugboard, since those are really just tricks for squeezing extra encryption complexity out of the limited number of rotors the Enigma had.  With enough rotors, you won't need them.)

Here's a schematic drawing to better illustrate the description above:

Looking at the schematic above, you might note that it looks vaguely similar to various modern block cipher designs, such as a substitution–permutation network like AES.  In fact, we can regard the abstract rotor machine described above as a kind of a tweakable block cipher operating on blocks of one symbol, with the wheel wiring $f_i$ acting as an invertible S-box (applied to the whole block at once, so that an explicit P-box is unnecessary) and the key-dependent stepping scheme serving to $s_i$ mix the initial key $K$ and the per-symbol tweak $t$ with the cipher state between each S-box application.

As far as I know, there exists no general attack on the structure described above even if the permutations $f_i$ are publicly known.  In fact, if I'm not mistaken, with sufficiently many rotors and a sufficiently complex stepping scheme, the abstract rotor machine described above can in principle compute any permutation of the cipher alphabet even if all the rotor permutations $f_i$ are identical and completely trivial (e.g. swapping a single pair of symbols and leaving everything else unchanged).  Thus, it would seem that any attack must necessarily exploit either some weakness in the stepping scheme (or in the number of rotors) and/or the limited size of the cipher alphabet.

For a typical modern block cipher, of course, the alphabet size of a typical Enigma-like rotor machine (corresponding to a block size of about 5 bits) would be utterly insufficient, as an attacker could trivially enumerate the permutation the cipher computes based on just a handful of known ciphertext / plaintext symbol pairs.  On the other hand, a mechanical rotor machine with an alphabet size of, say, $2^{64}$ or $2^{128}$ symbols (like in DES or AES) would be utterly impossible to manufacture.

However, to compensate for its small block size, a rotor machine has one major advantage over typical block ciphers: the rotors rotate.  Thus, each symbol in any given message is effectively encrypted with a different permutation of the cipher alphabet.  With a sufficiently complex stepping scheme, this should effectively scramble the permutation between each encrypted symbol, so that even an attack with access to an encryption oracle will only receive one plaintext/ciphertext symbol pair for each $(K,t)$ pair, and will hopefully have no effective way of correlating these pairs to obtain any useful information about the key (or about past or future messages encrypted using it).

The tricky part, of course, is coming up with such a sufficiently good stepping scheme, especially if you need it to also be simple enough that it could be practically implemented without modern electronics.  That's the part that I will leave as an exercise for the reader. :)


How many random bits are required to create one RSA key? If we were observing how many bits are taken from a random number source, what is the total number of bits required for creating a 4096 bit key using a current RSA implementation?
This means the total of the number of bits for finding the random primes P and Q, and the random number for the OAEP (padding), and any other random bits that might be needed that I'm not yet aware of.

Thanks!

For creating an RSA key pair you need an undefined number of random bytes from the source. The reason for this is that finding primes is indeterministic and hence it may be required that multiple random large numbers are required. In the end this also depends on the details of the key pair generator used.

However, it is possible to use a well seeded DRBG / PRNG for the key pair generation process. A PRNG is a deterministic or pseudo random number generator; it depends on the entropy of the seeds to generate a computationally random stream of bytes. That is: only the seed is truly random, but to an attacker the output of the PRNG is indistinguishable from random.

If a secure PRNG is used then using 256 bits of seed is all you need; for constrained systems you could even bring this down to 128 bits (at the cost of a lower security margin, of course). So if your system has issues generating large amounts of randomness you could seed your own PRNG and inject it into the RSA key pair generator - if that's possible for your runtime.

OAEP is a padding scheme independent on the key pair generation. That is: the calculations performed for key pair generation do not rely on the calculations performed by OAEP. OAEP may be performed on any secure RSA key pair, as many times as required. As per specification it uses hLen random bytes per usage, which means 32 bytes when SHA-256 is used and 64 bytes for SHA-512.


Double Ratchet Algorithm - What if the receiving wants to send the second message before the initiator? I'm studying about Signal Protocol and I had a doubt in Double Ratchet Algorithm. This section describes how to derive the receiving and sending key messages. But in this scenario, only Alice can send the second message.

The X3DH Protocol establishes a shared key between Alice and Bob where Alice is the initiator and she send the first message through this protocol. Double Ratchet only allow Alice send the second message because Bob doesn't have the public ratchet key from Alice (She will send him with the second message).

I don't know if I understand the Double Ratchet Algorithm well, my question is How Bob can send the second message to Alice after they establish a shared key (Alice is the initiator)?

I read again and again and I figure out how.

According to this section:

  (This assumes Alice begins sending messages first, and Bob doesn't send messages until he has received one of Alice's messages. To allow Bob to send messages immediately after initialization Bob's sending chain key and Alice's receiving chain key could be initialized to a shared secret. For the sake of simplicity we won't consider this further.)

So, actually Bob's sending key chain and Alice's receiving key chain are initialized with a shared key. This allows Bob send the firsts messages of the Double Ratchet step (second+ messages).


How are subkeys, in Feistel block ciphers, derived for each round? I'm bit confused about the subkeys that are used in Feistel ciphers. I know that all the subkeys ki are derived from the main key K, but how?

Say I have a simplified Feistel block cipher of i rounds, is it then correct to say that each key ki is the K/i part of the key?

So if the key is 4 bytes and there are 4 rounds, then I use the first 1 byte as subkey for the first round, then the second byte as subkey for the 2nd round and so on?

I can't seem to find this information when looking at articles/explanations of the Feistel cipher. I'm trying to solve an exercise and want to make sure that I can make the assumption that the key should be divided by the number of rounds and then use subkeys from this.

Note: It is specified in the exercise that the Feistel cipher uses 8-bit independent round keys ki. I'm not sure if this aligns with my assumption above.

I know that all the subkeys $k_i$ are derived from the main key $K$, but how?

However the cipher designer feel like.  The Feistel design gives guidance as to how the block is processed (and in a way to make inverting the cipher easy), however it gives no guidance as to actually generate the subkeys.  The designers can do anything they like, and still call themselves a "Feistel Network".

  It is specified in the exercise that the Feistel cipher uses 8-bit independent round keys ki. I'm not sure if this aligns with my assumption above.

The point of that instruction is that you aren't supposed to assume any necessary relationship between different round keys.  It might be because they're from independent part of the keys; it also might be because the subkeys are generated via an noninvertable function.  How it happens is irrelevant to the exercise.


Extract adversary's secret input in simulation based security proofs I am trying to understand the simulation-based security proofs (as well as the UC framework), I find that there is a basic assumption when proving the security, i.e., the simulator could extract the secret input of corrupted parties, even if the corrupted parties' input is encrypted or in secret shared form. I have two questions:

Is there any additional requirement or restriction along with this assumption?
Why can/should we rely on this assumption? Currently, I only focus on the semi-honest setting.

Any advice and explanation would be highly appreciated. Thanks.

@WYC, I suggest you take a look at the Lindell tutorial on https://eprint.iacr.org/2016/046.pdf

To answer you #1 question, I'll get from that tutorial the following requirements for the simulator:

It must generate a view for the real adversary that is indistinguishable from its real view;
It must extract the effective inputs used by the adversary in the execution; and
It must make the view generated be consistent with the output that is based on this input.

To answer your #2 question: the simulator is doing a mimic of the adversary. We can say it is a comparision: whatever the adversary do in the real world the (simulated) adversary must be able to do in the ideal world. Therefore, do not read this as a proof of the protocol's flaw. The point is: do you agree that the adversary chooses its inputs? So how simulate it in an indistinguishable way?


Decrypting AES encrypted file I wasn't sure where else to ask this so I will ask it here.

I work for a company that uses a rather old piece of tooling and we use customized software to control it.  We hired a guy to code the controller for us, and it works fine, however, we caught him stealing and fired him.  After we fired him, we found out that he's coded in a check that is comparing an encrypted file to the serial number of the machine so we can't use the code on any other machine on the floor(we have ten of these things).  I looked at the code in hopper, and it appears that this is simply the serial number AES encrypted somehow.  Knowing this, would it be possible to reverse engineer the file so that we can create this file for each of the machines?

AES is a symmetric cipher — it needs the same key for encryption and decryption. Thus, in order for the code to encrypt anything with AES, it must have the key stored somewhere. Find that key, and you will have completely broken the encryption.

(It's possible that the key isn't stored directly, but is derived from some other data stored in the program code. It's even possible that the key depends on the machine number in some way; this would make it impossible to decrypt the encrypted number without already knowing the real machine number, but for just verifying that the numbers match this would be fine. In any case, as long as you know what inputs the key is calculated from and how, you can repeat the same calculation yourself.)

All that said, I'd really recommend tossing out the code and getting someone more trustworthy to rewrite it for you. You already know that the original author cheated you, obfuscated their code and included at least one hidden booby-trap in it. Do you really want to take the risk of bypassing that trap and using the code, only to find out that the next trap will physically damage your machines? Besides, with only an obfuscated binary, you won't be able to fix the code when (not if!) you find a bug in it, anyway.


Mechanism to get 10 pseudo-random positive numbers up to maximum from a seed (32-byte hash)? I have learned new crypto words, so I rewrote the question:

I have quite random 32-byte hash which I want to use as a seed for generation of 10 pseudo-random positive numbers up to some maximum number, the generation must be reproducible. I would prefer, if those 10 numbers would differ from each other.

There is an example:

hash=Pkq5skE7tp=j#{y"+R$6~mg!z"4g/Utwand I need to reproducibly generate count=10 pseudo-random positive numbers up to say max=500.

So approaches that came to my mind:
1) I can take first 8 bytes Pkq5skE7 and cast them to 64-bit integer, then use modulo 500 on the result and have first number, then take other 8 bytes starting 1 byte right kq5skE7t, cast it, modulo it and get second number and I can get all 10 number like that.
Would those numbers seem pretty random or would they have some pattern?
There is not preferable effect of having 2 numbers the same.
2) I can take first 8 bytes Pkq5skE7 and cast them to 64-bit integer, then use modulo 500 on the result and have first number, then calculate other numbers with adding 500/10=50 to the result. So if the result of the cast would be 475, then other numbers would be 25, 75, .., 425.
I know that there is randomness only for the first number, but that would be good enough if method 1) would have some inconvinient pattern problem (like numbers distributed close to each other or something).
Compared to 1), numbers would be unique and that is an advantage.
3) If methods 1) and 2) won't be very good, I can again cast some bytes to 64-bit integer, do modulo, get number and take 9 numbers from following positions.
But that loses the random-like factor and I would prefer if the 10 numbers' would seem random and not much related to each other, the same problem can be said for 2), but it's preferable to have the numbers distributed over the whole spectrum.
4) Some other approach?

Basically I prefer 1), but maybe there is something better that can't yield the same number twice, maybe numbers from 1) can have a lot in common, because it's just shifting 1 byte right, I don't know.

I can tell it's used for something like drawing in a lottery. It is preferable that the numbers don't have relationship between each other, but I am not sure, if it's possible and maybe it's ok for those numbers to just look like pseudo-random and only the first being pseudo-random and other having not-obvious relationship to it.

Suggestions?

The best way to do this would probably be through an iterative hash, where you use that seed as an input, and from each iteration you extract a certain amount of bits for conversion to a number. A 32-bit extraction allows numbers up to around 4 billion.

I would do it as follows:

A = Hash(Seed)
Extract1 = lower 32-bits of A
Number1 = Extract1 mod (MaxVal)
B = Hash(A)
Extract2 = lower 32-bits of B
Number2 = Extract2 mod (MaxVal)
... and so on

This will prevent the numbers from having any special relationship with eachother, other than the fact they use the same seed, your suggested example means that the next number directly depends on half the previous number plus an additional 8-bits of unknown information. For a lottery that would be bad. This method means the output depends pseudorandomly on an additional 224-bits of information (assuming the hash is 256-bits).

The iterative sequence is deterministic and will always produce the same values from a given seed, and can generate both enormous numbers as well as enormous quantities of numbers, if needed.

If you want to be able to publish proof of the seed PRIOR to the lottery draw, you can post a digital signature of the seed, that way players would be assured you are not going to manipulate the seed after players are selected in order to generate winning values for a specific player. Just makes sure the signature uses a different hash function.


Strength of multiple hash iterations? Is it correct that increasing the iteration possibly decreases the cipher strength but increases the amount of time it would take to find the original hash values if using brute-force on a given hash? (i.e. from a compromised database)?

In other words, if someone accessed user password hashes would be better to protect against weaknesses in the cipher implementation or weaknesses in the amount of time it takes to calculate hashes?

public function hash_password(password, usersalt)
{
    var result = hash('sha256', usersalt . SITE_SALT . password);

    for (i = 0; i < 100; i++)
    {
        result = hash('sha256', usersalt . SITE_SALT . result);
    }

    return result;
}

Note: SITE_SALT is a value stored in a configuration file outside the document root. usersalt is a unique salt generated for each user and stored with the password hash in a database.

Yes. Iterating the hash like you do slightly increases the chance of collisions (as a hash function is not a random permutation, but an approximation of a random function): It is enough if two different passwords produce the same hash at any of the 100 steps, to produce the same final hash. (But as Thomas noted in a comment, the probability of collisions remains neglibly small.)

It is normally considered better to input the original password in the following iterations, too, this works against this effect: even if two different passwords give the same hash at step 39, at step 40 their hashes will be different again.

result = hash('sha256', result . usersalt . SITE_SALT . password);

On the other hand, iterating takes more time, and thus more computation power (both from you and a bruteforce attacker), which is good.

The bad news is that a fast hash like SHA256 is easily parallelizable, which means that the attacker can try hundreds of different passwords at a time on cheap hardware (like GPUs). Repeating the hash 100 times does not much here.

Instead, use a slow hash function which has some work factor parameter build in. One example is PBKDF-2 (which essentially does what you are doing, just with quite higher repeat counts), another example would be bcrypt (which builds on the key schedule algorithm of blowfish and needs about 4 KB of memory which will be constantly changed, thereby making implementation on standard GPUs ... inefficient), or the newer scrypt, where the needed memory is also depending on the work parameter (which means that you can only parallelize it if you have lots of memory available (and fastly accessible, too)).

Set the work factor so that the needed time is just acceptable for your users.


Can a tree hash with leaf-size of 1 byte support verification of content with elided ranges, at a cost of at most 2 supplied internal-node hashes? Perhaps someone can confirm my intuition:

A tree hash with leaves of size 1 (for example Blake2 in a tree-hash mode) would of course not be very efficient.

But it seems that it might be a suitable way (or maybe the only way?) to provide a verifier that's still useful if the underlying content is subject to intentional declared byte-range-elisions later. (That is: a form of digital redaction, where the original verifier still helps to assure that only the declared range has been altered.)

A content host performing elision would record the range, record the one or (usually) two internal tree node hashes that cover the to-be-elided range, then zero (or encrypt) the range.

When other parties want to verify the content is unaltered (except for the declared range), the host would provide the content, the declared range, and the up-to-two internal node hashes to be used in-place of the missing tree-hashed values. A root tree hash value would confirm that all other bytes in the file remain as when originally hashed.

Sound right?

Are there gotchas with this approach?

Any other better way to achieve the same end-result? (That is, use a compact-authentication value from when the content was whole, to still strongly verify unchanged ranges of content after some declared edit-range is removed?)

It is not true that there would always be at most two hashes required per elided range.

Suppose you have an eight-byte long content and want to elide all but the last. You need to supply one hash for the left half, one to cover the next two and one more to cover the last one.

Similarly, with 16 bytes of content, eliding the first 15 requires four hashes. And in general, eliding $2^n-1$ bytes out of $2^n$ requires $n$ hashes, so it is not bounded by a constant, but can grow linearly with tree height (logarithm of content length).

There is an additional problem with the scheme: a preimage search depends on the length of content hashed. Suppose that the redacted value is a random 128-bit string (encoded as just the raw 16 bytes). Unguessable, right?

Not if it falls poorly on the hash tree boundaries. It is possible that the redaction algorithm reveals the hash of the first byte, $H(b_1)$, the higher level hash of the next two bytes, $H(H(b_2)||H(b_3))$, etc. The first can be found out with $2^7$ calls to the hash function on average. The next with about $2^{15}$. The rest with $2^{31}$, $2^{63}$, $2^{7}$. Guessing the complete value requires less than $2^{64}$ work. Difficult, but much less than $2^{127}$ and probably doable.

For the redaction to be secure, a much larger block size than one byte would be needed and each redacted block would need to have enough (computational) entropy. You might be able to pair each byte of the document with a 128-bit random number and redact those as well, but clearly that would be a quite inefficient encoding (>16x expansion).


Plaintext and ciphertext block sizes How can you determine the largest plaintext block size and smallest ciphertext size if you used RSA with $n=59768553302699443$ using an alphabet with $27$ characters?

With an alphabet of 27 characters, the maximum number of characters that can fit into one plaintext block is equal to the largest integer less than or equal to $\text{log}(n) / \text{log}(27)$:

$$\bigg\lfloor\frac{\text{log}(59768553302699443)}{\text{log(27)}}\bigg\rfloor = 11$$

On the other hand, assuming the ciphertext is represented as a string of characters in the same alphabet, the minimum ciphertext length will be 12. This is because it will have to accommodate a maximum value of $n$, which is greater than $27^{11}$.


Encrypting credentials and reusing them securely I'm currently building a website where the users would enter their credentials for another web service that I'm going to scrape to get their data.

I want to make sure that when I save their credentials in my database, I'm using the best encryption possible and the best architecture pattern to ensure the highest level of security.

The first idea that I had in mind was to encrypt the data using an RSA pub key (PBKDF2, PKCS1_OAEP, AES 256bit... ???) and then allowing my scrapping script to use the private key to decrypt the credentials and use them.

Could you recommend the right/best encryption to do this?
If my server is hacked, the hacker would have access to both the database and the private key, since it will be kept on my server that runs the scrapping script and hosts the DB. I know that it's a difficult equation to solve. But maybe there is an architecture pattern that helps with this.

I'm coding in python and I believe PyCrypto is the go-to library for encryption. (Sorry I have very little knowledge about cryptography so I might be confusing technologies)

EDIT:

I'm also looking to find out how to design my server(s) to secure all this. I know that if I use RSA, I need to put my private key somewhere where it won't be reachable from internet if my server is compromised, but still the private key needs to be reachable by my scrapping script that needs internet access.

So as you can see i'm a bit lost. I'm ready to use two independant servers but I don't have any idea about the best system design to use here.

Many thanks.

The property you really want here is called Isolation.
You want all the three processes (Database, Scraper, Webserver) to run fully isolated from each other such that a compromise of the DB or the webserver doesn't end in a compromise of the passwords. So before we dive into how you can achieve this separation, let's just quickly assume we already established it and are bothered with the communication between the three modules.

Let's just quickly forget about the communication between the three modules except for when the passwords are involved (they're the most interesting part here). So you hand a public key to the webserver. Whenever a user enters his credentials for storage, you encrypt them using this public key and send the result to the database. Then your scraper will have the corresponding private key and fetch the encrypted credentials from the database, decrypt them and then fetch the data and store that in the database or send it to the webserver or whatever really.
As for the choice of primitives here: Use RSA-2048 with OAEP to encrypt a random AES key and IV and encrypt the credentials using this AES-GCM. Alternatively you may use RSA-OAEP directly on the data but this limits you to less than 200 bytes for the credentials. Alternatively you can consider using the OS's crypto services, a TPM, a secured SGX enclave or a proper HSM for private key storage.

But what does this fancy transport mechanism help you, when your webserver is compromised and an attacker can just read the private key out?
This is where isolation comes into play. Here are a few things you could do:

Clearly specify what queries the scraper and the webserver can make to the database and enforce the limitation from each individually to these queries using the database's credentials.
Consider logically or physically separating the services, ie by putting them all into different [chroot][8] jails, into separate VMs or running them on different machines.
Prefer separating the database server and the scraper script context-wise to ensure that a database server compromise doesn't lead to a credential compromise.
Depending on how often you restart the script, consider encrypting the private key of the scraper with a password, which you'd have to supply on every restart. To convert the password into a strong key, consider using Argon2d.


Is the software that uses PGP broken, or is it PGP itself? PGP is all over the news (even on TV) and there seems to be a lot of confusion about it.

For the time being, people face articles like Attention PGP users: new vulnerabilities require you to take action now which tell readers to deactivate their PGP plugins while raising concerns related to PGP beyond email client software and good, old email itself.

  A group of European security researchers have released a warning about a set of vulnerabilities affecting users of PGP and S/MIME.

Since I've been asked about the status of PGP several times today, I think a short Q&A related to this makes sense.

Do the new vulnerabilities mean that

there is a problem with PGP itself (as in: we should not use PGP encryption/signing at all), or
do the vulnerabilities "merely" point to a problem with email clients and the way they handle things (as in: PGP is fine outside or your email client)?

Differently stated: I'm asking to clarify if it is still safe to use PGP itself (eg sign/encrypt via commandline and transmit via non-email channels) or if there's a problem with the cryptographic internals of PGP.

Draft paper linked from efail.de.

TL;DR: the vulnerability is in some popular email client software, often combined with an extension simplifying the use of an OpenPGP (e.g. GnuPG) or S/MIME implementation within the said software; e.g. an extension bundled in popular distributions of GnuPG v2, thus common.

The issue is that un-validated deciphered ciphertext is made available to the email client, and it acts upon it (e.g. following HTML links to addresses that an adversary collects), yielding a decryption oracle capable of deciphering a past or current ciphertext, and exfiltrating the plaintext.

It is fine to disable decryption functionality in the email client. It should remain so until that software (and any extension  it relies on) is checked or improved to suppress (or at least not automatically act upon and preferably flag as suspect) any deciphered plaintext that did not explicitly pass the Modification Detection Code test for OpenPGP, or a similar check (to be defined) for S/MIME.

For OpenPGP, we can get back to the manual use of the bare OpenPGP tool (e.g. gpg), checking from stderr output that an MDC check explicitly passed, otherwise not acting based on what's received, be it programmatically or manually. I have no workaround suggestion for S/MIME.

From an official statement by the GnuPG and Gpg4Win teams:

  This paper is misnamed.  It's not an attack on OpenPGP.  It's an attack on broken email clients that ignore GnuPG's warnings and do silly things after being warned.
  This attack targets buggy email clients.  Correct use of the MDC completely prevents this attack.  GnuPG has had MDC support since the summer of 2000.

Update: based on that comment and other answer, and subject to dust settling, in GnuPG v2 two things are questionable, even if done on purpose so as not to break compatibility:
- Returning a status code of 0 (and a mere warning) in the absence of MDC, at least by default.
- A quirk specific to the Twofish algorithm prevents MDC error catching.


In ECC scalar multiplication, how do `add(Q, Q)` exceptions occur? Consider some scalar multiplication algorithm for a prime order (Weierstrass) curve $E$ with order $\ell$. Bernstein and Lange's SafeCurves: Completeness page mentions:

  The problem is that the standard Weierstrass "addition formulas" don't always work: in particular, they fail for the doublings Q+Q.

Now let's say my scalar multiplication properly "clamps" any secret scalars $k$ such that it is ensured that $0 < k < \ell$. We also check that $P$ lies on the curve and $P \ne \infty$. Then we implement the scalar multiplication using a standard left-to-right DoubleAndAdd algorithm:

1: function DoubleAndAdd(k, P)
2:     R = ∞
3:     for i from n-1 down to 0 do
4:         R = double(R)
5:         T = add(R, P)
6:         R = select([R, T], k[i])
7:     end for
8:     return R
9: end function

Now my intuition thinks that add(Q, Q) will never occur in this algorithm.

Observation. First observe that in $m$ loop iterations we can only compute points $R \in \{∞, P, \ldots, [2^m-1] P\}$.

Argumentation. Now, assume that add(Q, Q) indeed occurs in this algorithm. In the algorithm, P is constant, so this will happen only when R == P before executing line 5. In the same iteration, R has just been doubled in line 4. During that same iteration before the doubling in line 4, R had the value [1/2]P $=\left[\frac{\ell + 1}{2}\right] P$. This means that we can always compute $R = \left[\frac{\ell + 1}{2}\right] P$ in $(n-1)$ loop iterations.

For example, if $\ell$ is the Mersenne prime $2^n-1$, then we have computed $R = \left[\frac{2^n - 1 + 1}{2}\right] P = \left[2^{n-1}\right] P$ in $n-1$ loop iterations. After filling in $m = n-1$ we realize that $R = [2^m] \cdot P$. But this contradicts our Observation. So add(Q, Q) can indeed not occur. □

Now I am not really sure if my gut is right, or if I should trust the SafeCurves page. Using the DoubleAndAdd algorithm above, is it possible for any exceptions to occur in the addition in line 5?

In ECC scalar multiplication, how do add(Q, Q) exceptions occur?

Probability that it occurs when performing multiplication for large random $k$ (allowed to exceed $l$) and $P$ a generator is $\mathcal O\left(\dfrac{\log(k)}l\right)$ for a random $n$-bit curve, thus negligible when using actual curve parameters. Thus it can occur only when fed incorrect parameters; the cryptosystem or hardware is under attack; or using toy-size parameters making the crytosystem insecure.

  So add(Q, Q) can indeed not occur. □

I see no gap in the question's proof, now that it is explicitly stated that $P$ is on the curve, thus itself has prime order $l$.

  Using the DoubleAndAdd algorithm above, is it possible for any exceptions to occur in the addition in line 5?

No for correct execution (including, no induced fault attack) and parameters: $P$ on the curve of prime order $l$, $P\ne\infty$, $0\le k<l$.


P = NP and current cryptographic systems I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems.

My question is :

1. If P = NP is proven TODAY, will a RSA key (let say 3072 bits) be still enough to ensure a certain amount of security.

2. If not, what could we do to have at least the same amount of security (take a larger key length? a stronger algorithm?)

A proof of P = NP would prove that one-way functions do not exist. That in turn would imply, that almost no secure cryptographic primitives can exist according to the accepted definitions of security. (No symmetric encryption, no MACs, no pseudorandom generators, no signature schemes, ...)

However, it would just mean that no scheme can be provably secure. It does not mean that all schemes would be broken in practice. It might even be possible to adapt our definitions of security in a meaningful way.

In particular, it is very much conceivable that a proof of P=NP would be non-constructive. Such a proof would not help in any way. It would just mean that there exists an algorithm to efficiently break RSA (for a theoretical definition of efficiency, i.e. in polynomial time) but that does not mean that we know said algorithm. And even if the algorithm is known, it might not be efficient in practice.  An algorithm running in  $\mathcal{O}(n^{2^{100}})$ is technically a polynomial time algorithm, but it isn't very helpful.

So in conclusion, the question whether some keysize would still remain "secure" or how we could regain some measure of security cannot be answered in general, as it depends on the exact nature of the proof.


Generating shared secret random permutation There are three blind card game players. Each player does not trust any other, even prejudicing other two players may not be blind, or there may be others in the room, peeking at their cards.

In order to protect from glimpsing their hands, each player puts each of his cards into separate locked box, each box having its own key. Owners know which box holds which card, while others don't. In other words, players make a HMAC-SHA256 hashes of strings in form 'card_value:commonly_agreed_public_salt' with random key for each card, and then announce each other list of the hashes they posess.

When player makes a move, he moves one of locked box he owns to the middle of table and discloses the key, so everyone sees what card is inside. In other words, when making a move, player discloses HMAC key used to hash card value, and card value itself. This way other players can verify that this card was really owned by him.

I hope this approach makes it impossible for all the observers in the room, if any, to get any information, other than count of cards in posession of each player, am I missing something?

Now I'm stuck in how should I design retrieval of additional or initial cards from deck. I guess I should make use of preseeded PRNG similar to Mersenne Twister, to avoid duplicates, but how to make seed both secret, so one cannot simply traverse all the deck to know all the cards in the future, or to know which cards were picked by other players, and shared, so everyone will get same results while grabbing cards from deck.

Any ideas on this?

Your approach makes getting information other than count of cards in

possession of each player at least as hard as breaking the PRFness of HMAC.

To make it information-theoretically impossible "for all the ... each player",

$\;\;$ if different card_values have different lengths then use

$\;\;$ SHA256(commonly_agreed_public_salt:card_value)

$\;\;$ instead of card_value for what follows

$\;\;$ at the beginning, each player chooses a strong extractor whose output length is  equal to the length of

$\;\;$ each card_value, chooses a random seed for that extractor, and sends both of those to everyone

$\;\;$ (those choices can be reused)

$\;\;$ players compute SHA256(commonly_agreed_public_salt:secret_random_value)

$\;\;$ and Extract(secret_random_value,seed) xor card_value

$\;\;$ with independently chosen secret_random_value for each card,

$\;\;$ and then announce to each other the list of the pairs they possess

.
For retrieval of additional cards from the deck, you need to use
multi-party computation; specifically mental poker protocols.

(as already mentioned by bmm6o)


Finding subgroup in elliptic curve over finite field $ \mathbb{F}_{11}$ For elliptic curve $ y^2 = x^3 +3x+7$ I found the finite group $ E(\mathbb{F}_{11})= \left\{ \mathcal{O}, (1,0),(5,2),(5,9),(8,2),(8,9),(9,2),(9,9),(10,5),(10,6) \right\}$.

I have to find a generator of a subgroup of $ E(\mathbb{F}_{11})$, but for every point $P$ in $ E(\mathbb{F}_{11})$ when I try to calculate $[2]P$ I get a rational number. Am I doing something wrong?

For example if $P=(5,2)$ then by the formula $x([2]P)={(\frac{3x_1^2+a}{2y_1})}^2-2x_1$, where $a$ is the coefficient next to $x$ in the elliptic curve, and $x_1$ is the first coordinate of $P$ and $y_1$ is the second. But here I get $x([2]P) = (\frac{3*25+3}{2*2})^2-2*5 =(\frac{39}{2})^2-10 $. Should I just ignore the denominator and use $(\frac{39}{2})^2-10 =\frac{1521-10*16}{16}=\frac{1361}{16}$ and the answer for $x$ would be $1361$ mod 11$= 8$?

In elliptic curve algebra, operations are computed over a field.
In your case, the field is $\mathbb{F}_{11}$.

$\mathbb{F}_{11}$ is a finite field containing 11 elements ($\{0,1,2,...,10\}$), and like every field there is and addition and multiplicative law.
Theses two laws work other the ring of integers modulo 11 (often noted $\mathbb{Z}/11\mathbb{Z}$).

In $\mathbb{F}_{11}$, when we write ${(\frac{39}{2})}^2 - 10 = \frac{1481}{4} = \frac{7}{4}$ it is in fact 7 times the inverse of 4 modulo 11, which is 3 because $3*4 = 1$ modulo 11.

Calculating an inverse modulo an integer can be done with the Extended Euclidian Algorithm. The below is the inverse table;

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
x \in \mathbb{F}_{11}&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline
x^{-1} &1& 6 & 4 & 3 & 9 & 2 & 8 & 7 & 5 & 10\\\hline
\end{array}

In your example, the x-coordinate of $[2]P$ is then $7*3 = 10$, an element of $\mathbb{F}_{11}$.


Why in Android kernel CSPRNG state is saved? I am reading about the security internals of Android. In the book Android Security Internals, in chapter on Cryptographic Providers, there is a para stating:

  On Android, CSPRNG implementations are seeded by reading seed
  bytes from the standard Linux /dev/urandom device file, which is an inter-
  face to the kernel CSPRNG. As the kernel CSPRNG itself may be in a
  fairly predictable state right after starting, Android periodically saves the
  state (which is 4096 bytes as of Android 4.4) of the kernel CSPRNG to
  the /data/system/entropy.dat file. The contents of that file are written back
  to /dev/urandom on boot in order to carry over the previous CSPRNG
  state. This is performed by the EntropyMixer system service.

Can someone help me to understand why is it important to save the state of kernel CSPRNG and load it on boot? If we not save the state, is it insecure? Isn't this saving the state making it predictable. Also, why the kernel CSPRNG will be in a predictable state after starting?

If we not save the state, is it insecure?

Yes, for an answer read on:

  Isn't this saving the state making it predictable.

Yes. If an attacker manages to get access to the /data/system/entropy.dat file shortly after the kernel has loaded, he will have good knowledge of the internal CSPRNG state, could predict the random data and do nasty things.

On the other hand, if an attacker already has that high access rights to the machine predicting the CSPRNG is the least of your problems. He could just as well fool applications by providing it's own /dev/urandom device that generates pseudo random data. In that case he has perfect knowledge.

In case that the attacker does not have access rights to access the entropy file it is safe.

  Also, why the kernel CSPRNG will be in a predictable state after starting?

In an embedded device like an android phone, there aren't many things that generate entropy data. There is for example no hard-drive that you can use as an entropy source by measuring seek and access times. Right after start-up there are also few (if any) network connections that you could use as an entropy source.

Entropy gets collected much quicker as soon as the machine gets operated by a human. You can pull data from input devices etc.

This is by the way not only true for embedded devices such as an android phone but for servers that run without operator interaction as well. So you'll see the same thing done on linux servers as well.


what are the NTRU keysize and application in industry? I'm a student currently working on a research project on the NTRU cryptosystem, I've read some papers about this cryptosystem, and in those papers they are talking about keysize, is it the size of the public key or private key ?

is there any other indusctrial application of NTRU apart from CyaSSL ?

Usually, in public-key cryptography, the "key size" is implicitly referred to the size of the public key.

In the case of NTRU, both public and private keys are conveyed by the same thing: polynomials defined over a specific polynomial ring. These polynomials can be  represented as vectors in $\mathbb Z_q$ of size $N$. Therefore, raw public and private key will have the same size ($N \cdot \lceil\log q\rceil$ bits). For instance, with $N = 1171$ and $q = 2048$, which are recommended parameters, public and private keys are of size 1.57 KB.


Need for Twin Elgamal encryption What is the need for two private/public keys in twin elgamal?
I'm relatively new and would need some help.

At a purely technical level, having the two group elements and secret exponents enables a proof, in the random oracle model, that the scheme is CCA secure assuming that decision Diffie-Hellman is hard.  For regular (hashed) ElGamal, we only know how to prove CCA security in the random oracle model under a stronger assumption (in our paper we called it strong Diffie-Hellman, but gap Diffie-Hellman seems more common).

The intuition for why the two keys should help is more difficult.  At a very high level, by deriving the session encryption key as the hash of two Diffie-Hellman group elements, we are getting some "verifiable proof" that the ciphertext was either properly computed or is useless to the adversary, and allows the reduction to respond accordingly.  Looking back at regular ElGamal, the difference is that "proof" is not "verifiable".  The stronger assumption in the CCA proof of ElGamal is what technically allows this "proof" to become "verifiable".

The paper makes this argument formal.  In order to understand it better, I'd recommend starting with this paper, which gives the mentioned proof for hashed ElGamal under the stronger assumption.  Then one can contrast it with the twin construction and security analysis.


Cracking RSA ciphertext without a public key I'm looking for some clarification on whether or not I'm correct in how I'm thinking about this.

From my understanding of RSA, the public key gives you the value $n$ (large prime $p$ times large prime $q$) and the value $e$ (a value less than $n$ which is not a factor of $(p-1)(q-1)$).

The way to try to crack a ciphertext according to the RSA problem is by using the values given to you in the public key (demonstrated in this answer). However, if an attacker only has an encrypted message without the private key (an example would be getting into a system and obtaining an encrypted file but the keys were in "Cold Storage"), he/she wouldn't be able to perform this attack.

While it's possible to recover the public key if you know the ciphertext and the plaintext, given only the ciphertext, it is likely much more difficult (if not almost impossible) to find the correct prime numbers, the value $e$, and the value $d$.

Am I correct in this assumption?

Side note: I know that the public key is named "public" for a reason, but for the sake of this scenario, just assume some situation like the one presented above.

It is asked if in RSA, without the public key,

  it is likely much more difficult (if not almost impossible) to find the correct prime numbers, the value $e$, and the value $d$.

As first noted by Tylo in comment, if the RSA key was chosen competently, it will be impossible to find the prime numbers and $d$. Argument: if there was a method making that possible, then that method would also break regular RSA (with the public key available to the attacker); and that's a well-studied and unsolved problem, including if RSA is otherwise used incompetently (like, without padding as in textbook RSA).

Wether it will be possible to find $e$ depends on how $e$ was chosen, on the RSA padding, and on if sufficiently many known plaintext-ciphertext pairs are available:

If $e$ was chosen at random in a large enough set (e.g. as a random odd integer with $2<e<(p-1)(q-1)$ and $\gcd(e,p-1)=1=\gcd(e,q-1)$ ), then it can't be found (argument: that $e$ is also the private exponent in an RSA system with the public exponent $d$, and we just said the adversary can't find the private exponent).
If $e$ is small, it can be guessed (much more if it is among the usual values $e=2^{(2^k)}+1$ with $0\le k\le4$, and $e=37$ ).
If additionally there is no random padding (as in textbook RSA), and a number of known plaintext-ciphertext pairs $(m_i,c_i)$ is known, then a guess of $e$ can be verified, and $N=p\;q$ found, by computing the GCD of enough ${m_i}^e-c_i$ (where the exponentiation is not modular). Because $N$ divides ${m_i}^e-c_i$, for enough plaintext-ciphertext pairs, this GCD will be $1$ for an incorrect guess of $e$, and $N$ for a correct guess.


Are the first 4 bytes of a Ed25519 public key random? We are using the Ed25519 signature scheme (which uses Curve25519). A key pair is generated by generating the secret key from random data and then computing the 32-byte (256-bit) public key from said secret key.

The question is about the entropy (randomness) of the public key. We currently use the first 4 bytes of the public key as a "reasonably unique" ID of the public key. We have very limited space and cannot afford more than 4 bytes. Would we improve the uniqueness of the ID if we generate it differently? For example, the ID could be generated by XOR between Bytes 0-3 and Bytes 4-7 of the public key? Or using the first 4 bytes of sha-512 of the public key. Or what?

If the 32-bit ids are assigned independently, the best you can hope for with a uniform random assignment of ids is a collision probability no more than about $n^2/2^{32}$ where $n$ is the number of ids you have, if $n$ is small; once $n$ grows past $2^{16}$ the probability of a collision rapidly approaches 1.  This is the standard birthday paradox.

Using a nonuniform distribution on ids is even worse.  The distribution of bits in the encoding of uniform random curve points is detectably nonuniform—enough that it was one of the first problems reported in Dual_EC_DRBG before everyone realized there was a back door.  The low-order 32 bits are probably close enough to uniform in this case that it won't affect the collision probabilities; to alleviate that concern you could pass the encoded curve point through a hash like SHAKE128-32 first.

But you should be more concerned with what you hope to achieve using 32-bit ids in the first place!  This has been a consistent source of trouble in OpenPGP, for example—fraudulent keys have been forged and uploaded to the key servers for every 32-bit key id possible.  To avoid this trouble, you fundamentally need to:

make the id assignments non-independent, e.g. use a secret permutation of 32-bit strings so that you can have up to four billion ids
use a much larger id space, e.g. 256 bits
accept that collisions will happen and find a way to deal with them gracefully, even under adversarial inputs that are all collisions


Can you give me an example of any PKC encrytion algorithm with coins? I'm reading a Definition of Public Key Encryption and here say:

  ...
  Enc is a (possibly) probabilistic polynomial time encryption algorithm which takes as input a public key $pk$, a $m\in M$ and random coins $r$, and outputs a ciphertext $c\in C$.

But in other papers, there is no mention of coins $r$.

Can you give me examples of PKC  encrytion algorithms with coins?

All textbook PKC systems are never applied as they are described. Take e.g: RSA.
There is a random padding technique that plays the role of the coins. The coins make the scheme probabilistic. For the same reason a block cipher which is instatiated as a pseudorandom permutations takes as input an instatiation vector IV. OAEP is a commonly used random encoding scheme before applying RSA on your data.


Adding the same noise to all element of a vector is Differential privacy In Differential privacy, if we add a $N$-dimension private vector with $N$-dimension Laplace or Gauss noise, we obtain differential privacy. However, if we only generate a 1-dimension noise to add it to all element of private vector, can we obtain differential privacy?

This cannot possibly be differentially private.
Recall than a randomized algorithm $\mathcal{A}$ is $\epsilon$-differentially private if, for all datasets $D_1$ and $D_2$ that differ in a single entry, and all subsets $S\subseteq\mathsf{im}(\mathcal{A})$, that:
$$\Pr[\mathcal{A}(D_1)\in S] \leq \exp(\epsilon)\Pr[\mathcal{A}(D_2)]$$

Let $\mathcal{A}$ be your proposed mechanism, which samples $e\sim \mathcal{D}$ for some distribution $\mathcal{D}$, then maps $v \mapsto v + e(1,1,\dots,1)$.
Let $S = \{v\in\mathbb{R}^n \mid v_1 = v_2\}$ be the set of all vectors such that their first two coordinates are equal (any pair of coordinates suffices).

Identify datasets with vectors in $\mathbb{R}^n$, as this seems to be your use case. Let $D_2 = (v_1, v_2,\dots, v_n)$, and let $D_1 = (v_1, v_1, v_3,\dots, v_n)$.
Note that these differ in a single entry (their second entry).

We have that $\Pr[\mathcal{A}(D_1)\in S] = 1$, but $\Pr[\mathcal{A}(D_2)\in S] = 0$, so the inequality cannot hold.

Note that the above makes no restrictions on the entries of your datasets (a prior answer had them in $\{0,1\}^n$), nor does it make any restrictions on the error distribution $\mathcal{D}$.
So your optimization cannot ever be differentially private.


Proving item association without revealing one of the associated items I'm a total noob when it comes to cryptography but I believe this falls under the "zero knowledge" category.

I have two associated pieces of information:

tag — known by both parties. Unique per scenario.
identity — known by only one party. Potentially associated to multiple tags. Comes from a pool known by both parties.

I need a way to prevent the party with the association from changing the value of the identity. There are around 100 concurrent associations per scenario. The pool of potential identities can be relatively small, even smaller than the number of tags, but can be larger too.

The most primitive option would be to hash the tag and identity together but with a possibly small pool of potential identities I fear it would be trivial to brute force the hash...

During the scenario more and more of these associations will become public. At least at that point I should be able to confirm that the other party did not modify the association. I don't really have to confirm this before then, because unrevealed associations are not relevant. I just need to prevent the knowing party from picking and choosing at the time of revealing. And I need to prevent the other party from deducing the identity before the reveal.

Is such a thing even possible? How could it be done? How difficult would it be to implement?

What it sounds like you are looking for is a Commitment Scheme; that is, a way for Alice to compute a 'Commitment' based on a 'value', and publish the 'Commitment' to Bob (or a group of Bobs).  Just from the tag, Bob cannot deduce the value (even if he know it's one of a small set of values).  However, Alice at some point can 'open' the commitment, revealing the value; Bob can then verify that the revealed value did, in fact, correspond to the value that Alice originally committed to.

If so, well, this is quite well studied territory.  The simplest commitment method is based on a secure hash function (say, SHA-256).  We have all parties agree on a secure hash function, and the length of large random values (say, 128 or 256 bits) that will be used.  To commit to a value, Alice selects a random value for R, and then computes:

Commitment := SHA256( R | Identity )

(where | is string concatination).  She then publishes the Commitment as her tag, and saves the value of R she used.

Bob is unable to deduce anything about the identity from the tag; the best thing he can try is to iterate through the possible values of R, and if Alice chose a large enough R, he can't do that.

When it becomes time for Alice to open the commitment (that is, reveal the identity), she publishes both the identity and the value R; Bob can then verify that those two do, in fact, hash to the published tag.  He also knows that it is computationally infeasible to find two different values that hash to the same commitment (because that's a property of a cryptographically secure hash function), and so the value that Alice revealed must be the value she originally committed to.

One subtle point in this particular technique: the reason we had all parties agree on the length of R is to prevent Alice from changing her mind about it. If not, then Alice can try to cheat in this way: she might try (for example) to commit to the value 01 02, and use the R value 00 00 00 (note: this R value is too small to be secure, this is just a toy example); and so she would publish SHA256( 00 00 00 01 02 ).  However, when it comes time to reveal, she might change her mind, and claim the Identity 00 01 02, and that she used the R value 00 00; this also gives SHA256( 00 00 00 01 02 ), which is the exact same identity.  Preventing Alice from changing the length of R after the commitment stops this method of cheating.


What kind of encryption function is also used for decryption? Is there a name for the particular type of encryption algorithm or function which is the same algorithm or function used for decryption?

This is a vocabulary question, because I'm largely unfamiliar with the terminology of encryption. Expressed mathematically, if $f(x)$ is an encryption algorithm that encrypts $x$, and $f(f(x))=x$, is there a name for this particular type of encryption? An example would be a cipher that converts $A$ to $Z$, $B$ to $Y$, $C$ to $X$, ..., $X$ to $C$, $Y$ to $B$, $Z$ to $A$.

poncho and SEJPM more or less answered your question in the comments: If $f(f(m)) = m$, then the function can be revered to as a "self-inverse", or more formally, the function is said to be an "involution".

Be careful with a cipher that is an involution: There is a notable difference between a cipher that is a full involution and one that is not: Namely, if the cipher is an involution, then access to an encryption oracle is equivalent to access to a decryption oracle.

A stream cipher with exclusive-or as the key stream combining function is a notable example of an involution:

$c := E(m) = keystream \oplus m\\m := D(c) = E(c) = keystream \oplus c = keystream \oplus keystream \oplus m$


Is the member sum of a subset of $\mathbb{Z}/p\mathbb{Z}$ known (with $g^n \bmod p$)? Is it always $\mod P = 0$? Let $P$ be a prime and $g$ a value between $2$ and $P$.
Let $M$ be the set of numbers which can be generated with $g$:
$$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$
If $g$ is a prime root of $P$ all values $1$ to $P-1$ can be generated.
The sum of those would be:
$$S=\sum M = \sum_{n=1}^{P-1} (g^n \bmod P) = \sum_{n=1}^{P-1} n= (P/2)\cdot (P-1)$$

Is there also a formula for values $g$ not a prime root of $P$?
(So for generators $g$ which are only able to generate a subset of   $\mathbb{Z}/p\mathbb{Z}$)
Question: What is exact sum of such a subset?

Partly solution:
During testing around I noticed one factor of this sum $S$ seems to be $P$.
So
$$ S = \sum M = c \cdot P$$
and with this
$$ 0 \equiv S \bmod P$$

Is that always the case? EDIT: seems to be the case, see comment from  runway44 (edit end)
Any way to calculate this factor $c$?

Example: $g=13, P=23$
With $g=13$ only half the numbers out of $\mathbb{Z}/23\mathbb{Z}$ can be generated:
$M = \{13,8,12,18,4,6,9,2,3,16,1\}$
sum $S=\sum M = 92$, which is $4 \cdot P$
Why $4$ times? Any way to compute this factor?

(I observe $S=c\cdot P$ for some integer $c$.) Is that always the case?

Yes. Proof follows.

If $g=P$ then $S=0$. We'll disregard this special case in the following.

The set $M$ has $k$ elements, with $k$ the lowest strictly positive integer with $g^k\equiv1\pmod P$. This $k$ is known as the order of $g$ modulo $P$. This $k$ divides $P-1$. $M$ also is $\{g^n\bmod P, \text{ with } 0 \le n <k \}$, and in this later definition the $g^n\bmod P$ are distinct.

It follows $\displaystyle S=\sum_{n=0}^{k-1}\left(g^n\bmod P\right)$.

Therefore $\displaystyle S\equiv\left(\sum_{n=0}^{k-1}g^n\right)\pmod P$.

$g\ne 1$. Therefore $\displaystyle S\equiv\frac{g^k-1}{g-1}\pmod P$.

It holds $g^k-1\equiv0\pmod P$. Since $P$ is prime and $g\in[2,P]$, $g-1\ne0\pmod P$.

Therefore $S\equiv0\pmod P$. That is $\exists c\in\Bbb Z, S=c\cdot P$

  Any way to calculate this factor $c$?

If $k$ is even, then $c=k/2$. Argument: if $k$ is even and $x\in M$, it can be shown that $x'=P-x\in M$. We can pair the elements of $M$ into $k/2$ pairs which each sum to $P$.

If $k$ is odd, $c\approx k/2$ still holds. An heuristic argument is that $S$ is the sum of $k$ terms about haphazardly distributed in $[1,P-1]$, thus about $P/2$ on average. That's the best I can tell.

Notes:

$c$ depend only on $k$ and $P$ (not $g$), per the fundamental theorem of cyclic groups.
We can efficiently tell the parity of $k$ from $P$ and $g$: write $P-1$ as $2^\lambda z$ for odd $z$; then $g^z\bmod P=1$ iff $k$ is even (as commented by poncho).
$k$ can be efficiently found from $P$, $g$, and the factorization of $P-1$.


What is an example of elgamal homomorphic double encryption? I am looking for such an cipher algorithm that is based on assymetric cryptography where the order of encrypting is irrelevant.

For example:
There is a message "x", Bob encrypt that message with his key and passes result "zz" to Alice. Alice encrypt that message with her key and receives: "xyz".
There is a message "x". Alice encrypt that message with her key and passes result "ui" to Bob. Bob encrypts with his key and receives "xyz".

What is the most important, is that resulting encrypted text is the same.

I have heard that maybe homomorfic ciphers have such properties and have tried with elgamal but no results were ok.

I would be glad if someone could help me with some example that matches my problem.

You are looking for commutative encryption rather than homomorphic encryption. Also Elgamal is probabilistic, which means in each encryption a fresh randomness is added to the ciphertext, which means if the same plaintext is encrypted twice, the ciphertexts will be different.

For a deterministic commutative encryption scheme, you can use RSA encryption (SRA in your comment).


Would a symmetric cipher with a keylength a big as the data length be information theoretically secure? One-Time-Pad is information theoretically secure as long as the random number stream is evenly long or longer than the data stream it encrypts, for a "deciphered" message could have been any message with the same length as the given with the same probabillity. Does the same apply to symmetric ciphers, too?

For instance if I have 1024 bits to encrypt, break it into chunks 128 bits and encrypt it with AES-128, each with a different (assume: true) random key,
will that be information theoretically secure just as OTP?
Or would a hypothetical algorithm (let's assume it would be as quick as the encryption function) impact the (theoretical) security?

In other words: Does using a symmetric encryption algorithm (such as AES) lower the probabillity of a ciphertext being originated from a specific plaintext even if the used key has "OTP-length" and is completely unknown?

No, using any keyed permutation with key length equal to the block size reduces the number of possible plain texts by ~1/3

Assume first that AES reasonably approximates a pseudorandom permutation, for each block of the message, the attacker (assuming unbounded computing power) can calculate the plain text for all keys. This is equivalent to throwing 2^128 balls into 2^128 baskets randomly. There will be collisions. The chance that any plain text is not a valid solution is approximately 1/e

filled fraction = 1-((n-1)/n)^n , n=2^128

this converges to 1-1/e

this reduces the effective number of plaintexts by  about 1/3 (=0.63 ~= -0.66 bits). The reduction also tells the adversary about the probablity of any ciphertext being correct since about half the remaining plain texts got two hits instead of one with 2x the probability of being correct.

A problem with this scheme is that fooling the observer into accepting a plausible fake message requires solving for the key K which would connect the plaintexts and ciphertexts, fortunately, thanks to the recent SHA3 competition the cryptanalysis to do so has been mostly done.


Finding the cycle set of specific polynomial I have a school assignment where the problem lies in finding the cycle set of two different polynomials.

I tried to look up different tools on how to solve these problems, but I have a hard time finding it.

If anyone were so kind to help me, solve but also, understand the way to figuring things like this out.

The problem states:

Determine the cycle set for these polynomials:

$x^4 + x^2 + 1$ over $F_2$.

$x^3 + x + 1$ over $F_3$.

Thanks!

This is quite combinatorial in nature and the suggestion in the comment is exactly how one would do small examples. General results are much more complicated for arbitrary polynomials, but simple for primitive polynomials.

If the generating polynomial $f$ of degree $d$ over $F_q$ is primitive (i.e., $f$ is irreducible, and has a root in the splitting field of order $q^d-1,$) then the cycle length is maximal, and equal to $q^d-1$ for any nonzero loading, and is otherwise a single cycle at zero.

If the generating polynomial $f$ is not irreducible but is a product of irreducibles, the cycle structure can get quite messy.

Most generally, form the companion matrix $C_f$ of the polynomial $f$ of degree $d,$ which is a $d\times d$ polynomial over $F_q.$ Then the length of any cycle that can be generated by the given degree $d$ polynomial divides the order of $C_f$ in the general linear group $GL(F_q,d)$ of $d\times d$ invertible matrices where the group operation is matrix multiplication. This means that the length of any cycle will be a divisor of
$$
q^{k(k-1)/2}(q-1)(q^2-1)\cdots (q^d-1)
$$
and this is all we can say in general.


Problems with using AES Key as IV in CBC-Mode I'm a pentester and currently analysing a web application which are using some strange encryption scheme.

The point is: They encrypt using AES-128, generate a (not cryptographic secure) key and use this as encryption key AND initialization vector.

I'm not a crypto expert, but I know that this is bad (aside of the insecure generation of the key). The problem is, that I don't know what the concrete consequences are?

Can someone please enlighten me, so I can explain to the developers that this is bad? Thanks

CBC mode encrypts as follows:
$$
C_0 = E_K(IV\oplus P_0);\\
C_i = E_K(C_{i-1}\oplus P_i),
$$
where $P_i$ are plaintext blocks and $C_i$ are ciphertext blocks. Traditionally, IV must be random and is published alongside the ciphertext to enable decryption. If it is also published in your case, then this reveals the key and is trivially insecure.

If the $IV=K$ is not attached to the ciphertext, then you get a deterministic (in contrast to probabilistic) encryption  scheme. It has a number of insecure properties, such as

the ciphertext does not change if the same plaintext is encrypted multiple times.
if two plaintexts have the same prefix, then the ciphertexts will have the same property.

Maybe there are others, but these ones are sufficient to avoid using such scheme to protect confidentiality of any reasonable amount of data, except maybe for very short (16 bytes or less) plaintexts.


Protecting Ed448 against DPA and fault attacks There are some papers (1, 2) describing fault attacks in EdDSA. One suggested countermeasure is to add randomness to the input of the first hash call, which outputs a scalar.

This paper describes a DPA attack against EdDSA, and suggests a similar countermeasure. However, the randomness must be placed in a specific place:

  This can be achieved by padding
  the key with fresh random bits such that the first 1024-bit block is composed
  only by key and random value, without any bits known to the attacker.

Following their notation, that would mean changing $H(b,M)$ to $H(b,Z,M)$ where $Z$ is the random padding such that the length of $b || Z$ is equal to the block size of the hash.

However, consider Ed448, as defined in RFC 8032 (the issue I'll talk about would also apply to Ed25519ctx and Ed25519ph, but I'll use Ed448 as an example). In the Sign operation, the hash call is SHAKE256(dom4(prehash, context) || b || PH(M), 114). Prehash is a flag indicating Ed448 or Ed448ph. Context is an optional context string. The dom4 function is:

  dom4(x, y):     The octet string "SigEd448" || octet(x) || octet(OLEN(y)) || y, where x is in range 0-255 and y is an octet string of at most 255 octets. "SigEd448" is in ASCII (8 octets).

Now, my question is: what is the proper way to add the DPA countermeasure to Ed448? (And Ed448ph, Ed25519ph, Ed25519ctx)?

My first guess would be to use SHAKE256(dom4(prehash, context) || b || Z || PH(M), 114), with Z being enough bytes to fill the SHAKE245 block size. However, if the context is used, then Z could get too small. Also, the paper states that the first block must be "composed only by key and random value, without any bits known to the attacker". Would the fixed bytes of the dom4 function ("SigEd448" and so on) interfere with this? How to work around this?

Or maybe SHAKE256 is already DPA-resistant?

The, common, assumption used in that paper is that an attacker can DPA a fixed secret when it's mixed with known (to the attacker) and varying data.

The proposed solution was to add random after the key to fill the SHA-512 block size.

By doing this:

the first SHA-512 computation processes the fixed secret and varying but unknown data, so the attacker can't perform DPA.
After the first block, the result is the intermediate hash value which is unknown and varying (from message to message), so it can't be recovered through DPA when processing subsequent blocks.

Side note: if we would have padded the key with zeros instead of random, we would have mixed the fixed key with known but fixed data. The attacker in this case is not able to DPA the key. However she can DPA the intermediate hash value after the first block, which is secret and now fixed and will get mixed with the known and varying message.

Your proposed solution SHAKE256(dom4(prehash, context) || b || Z || PH(M), 114) with Z random data would work if you carefully select the size of Z and assuming the attacker can't control the context.

If the attacker control the context then she can choose varying context that together will the key (b) will completely fill the SHAKE256 block, so no random is used in that computation and DPA can be performed.

If the attacker can't control the context then you just have to make sure that Z is not too small and fills the block.

For example, given the block size of SHAKE256 of 136 bytes, if len(dom4(prehash, context) || b)=134, due to a large context, then 2 bytes for Z won't be enough and you will need to select a Z of 138 bytes (2 to fill the current block and 136 for another full block).

Update:
Please be aware that the generation of r is one way to side-channel attack EdDSA, but it's not the only one. The scalar multiplication should be protected as well from single trace attacks (technically not DPA) and the computation of $S = (r + k * s)$ could be targeted by DPA as $s$ is fixed and unknown and $k$ is varying and known.


Remove Blowfish Padding I am currently experimenting with the Blowfish encryption.

I noticed that the decrypted message and the original message doesn't have the same length.
This applies for the ECB, CBC and CTR mode.

The difference of bytes from the original message to the decrypted message are
just trailing zeros at the end of the array.
However, the zero-padding-length at the end seems to vary.

Is there :

A way to produce a decrypted output with the same size as the input message?
A way to calculate the length of zero-padding at the end
(so that I can cut them off in the end)

Is there a way to produce a decrypted output with the same size as the input message?

Yes, CTR mode should work for that. You must have a broken implementation as there is no padding required for CTR mode. You could simply use the leftmost bytes of the ciphertext though. If decryption fails because of that then you could simply pad the ciphertext with zero's, decrypt, and remove the number of (now random) padded bytes so your plaintext length matches the ciphertext length.

Note that often an IV is send as well. The IV needs to be unique for CTR mode (in such a way that the counter is always unique). This is even more troublesome for 8 byte block ciphers such as Blowfish than for 16 byte block ciphers such as AES. You would need to use a counter IV or establish the IV otherwise to make the ciphertext the same length as the plaintext.

  A way to calculate the length of zero-padding at the end (so that I can cut them off in the end).

For plaintext ASCII text you can simply remove all zero bytes at the end; zero is a control character called NUL which should not appear in printable text.

Note that there are two forms of zero-padding: one that always pads and one that doesn't always pad (which is more often used). You could encrypt a 8 byte block of plaintext to see which one you got.

Note that for binary messages that may contain a zero byte at the end that zero-padding is not deterministic, meaning that you cannot determine the exact amount of padding. You would need to implement a padding mode such as PKCS#5/PKCS#7 padding yourself if you require that.

Do not use Blowfish, use a 16 byte block cipher, preferably AES in an authenticated mode such as GCM (which does add the authentication tag as overhead though). Even Bruce Schneier - the inventor - doesn't recommend Blowfish anymore.

An 8 byte block cipher is especially harmful for CTR mode. You'd better use CFB or OFB mode if you have to stick to Blowfish. Those are also modes that turn the block cipher into a stream cipher, so they do not require padding.


Selectively opening only a few commitments I have k messages $m_1,m_2...m_k$ and I want to commit to all of them but open only a few of them -- as asked by Bob. Each message is of $n$ bits. Show how one can commit to all the $k$ messages and then later open only the messages that Bob asks her to such that the total communication is less than $O(nk)$.

I am stuck at the very beginning. I am not able to find what kind of a cryptographic object is suitable for this. Any clue will be appreciated.

Since your main concern is communication, then use something that can reduce communication cost. I can think of two possible directions.

1 Use a Merkle tree

The idea is to commit to all elements, then build a Merkle tree on top of the commitments, and send the root of the Merkle tree as the commitment of the whole set. To reveal an element, open its commitment and show the commitment is covered by the Merkle tree.

2 Use a cryptographic accumulator

  A (static) cryptographic accumulator scheme allows to accumulate a
  finite set $X = \{x_1 , . . . , x_n \}$ into a succinct value $accX$ , the so
  called accumulator. For every element $x_i \in X$ , one can efficiently
  compute a so called witness $witx_i$ to certify the membership of $x_i$ in
  $acc_X$ . However, it should be computationally infeasible to find a
  witness for any non-accumulated value $y \not\in X$ (collision freeness).

Essentially the accumulator serves as a commitment of a set, and each witness serves as the opening secret of the individual elements in the set.


Design of MixColumn Transformation in AES Why is the multiplication in MixColumn Transformation particularly by 2,3,1,1 cyclically? Why not some other numbers?

Because:

These numbers in the matrix form a Maximum Distance Separable matrix; that is, one where, if you change some bytes of the input, then the total number of bytes of input changed PLUS the total number of bytes of output changed will always be at least 5 (e.g. if you change 2 bytes of input, then you'll always change at least 3 bytes of the output).  This property is crucial for the security proof against differential and linear cryptanalysis.
These numbers make the encryption direction cheap; to compute the transform of the column $(A, B, C, D)$, you compute $2 \times A, 2 \times B, 2 \times C, 2 \times D)$, and then do a bunch of byte-wise xor's.
These numbers make the decryption direction moderately cheap, to compute the inverse transform of the column $(A, B, C, D)$, you compute $2 \times A, 4 \times A, 8 \times A, 2 \times B,$ $4 \times B, ..., 8 \times D$ (doable with 12 doublings), and then do a bunch of byte-wise xor's.


Safety of random nonce with AES-GCM? I am encrypting multiple messages using a 256 bit key with AES in GCM mode, generating a random 96 bit nonce for each message.

The small nonce size combined with random values is worrying me:

  AES-GCM takes a 96-bit nonce and NIST says that you can only encrypt $2^{32}$ messages under a single key if using random nonces. This is because if you throw $2^{32}$ balls at 2$^{96}$ buckets then you have roughly a $2^{-33}$ chance of getting two in the same bucket and NIST drew the line there. That probability might seem either high or low to you. It's pretty small in absolute terms and, unlike a work factor, an attacker can't spend resources against it, but it's a very long way from the safety margins that we usually use in cryptography.

Is this an issue? Is there something else I should prefer? For example, AES/CBC with encrypt-then-MAC construction would have a more reasonable IV/nonce size of 128 bits.

Is this an issue?

That's up to you, not us.  Is 2^-33 probability of horrible cryptographic failure acceptable to you?  Multiply that by the number of times you'll use this construction (or the rate and the product life time) to get a scarier picture but one you should keep in mind.

  Is there something else I should prefer?

"should prefer" is again subjective based on your situation.  I strongly advise you to consider AES-SIV (or AES-GCM-SIV) or XSalsa20-Poly1305.

  For example, AES/CBC with encrypt-then-MAC construction would have a more reasonable IV/nonce size of 128 bits.

Sure, for another example.  But if collisions bother you and you'd like a significantly lower probability then either 1. stop using random nonces 2. go for a nonce size that's greater than ~80*2 (a la XSalsa) or 3. Use a misuse resistant algorithm.


About salted passwords In most applications, all passwords are salted independently. In terms of security (e.g. attack complexity), what are the consequences of the following differents approaches:

All passwords are salted with the same salt.
The application does not use salting, but end users choose their passwords by appending to them a (truly random) salt. We make the assumptions that these users are able to remember this much longer password, and that an adversary has access to both the identities of users and the salts that have been used in the associated passwords.

I know that the second is impractical, but I am curious.

All passwords are salted with the same salt.

Duplicate / reused passwords will show up because the resulting password hash is identical. Cracking the password database will become easier as all the passwords can be cracked at once using a specialized rainbow table or simple comparison against all the passwords in the database.

An attacker could also setup a website with the same salt and hope that users will repeat their passwords; in that case duplicates will show up even if the username is different.

There is still one advantage left for the salt: hacking multiple databases at the same time using rainbow tables or dictionary attacks is still thwarted (unless the salt is reused, e.g. when using "007" as salt, and other implementations do so as well).

  The application does not use salting, but end users choose their passwords by appending to them a (random) salt. We make the assumptions that these users are able to remember them, and that an adversary has access to both the identities of users and the salts that have been used in the associated passwords.

That depends on the quality of the salt; but given that the users should remember them they might as well use a longer, unique password. Because they are going to forget that salt, especially if it is specified as e.g. hexadecimals.

Using a unique (hash over a) username as salt is possible, but that means that the password must be refreshed if the username is ever taken; repetition of the password by the same user may show up. You should add a static "pepper" - a secret constant salt - to this kind of salt to make it unique for your specific database.


Stopping timing attacks on AES: Why is it important to prevent the OS from interrupting the AES computation? I read the paper Cache-timing attacks on AES (by Daniel J. Bernstein), but I don't seem to understand everything. The author dedicates a long section on how to prevent the OS to interrupt an AES computation. But how does this leak any information? Yes, the calculation takes more time than usual, but it is not dependent on the input?

(This is a follow-up to AES timing attacks.)

The paper explains why.  Preventing the OS from interrupting the AES computation is part of Bernstein's proposed method of defense against cache-based timing attacks.  Let me sketch the argument for you:

The early part of the paper explains that if the time is variable, then it introduces a risk of timing attacks.  Sections 3-6 demonstrate that such an attack is practically feasible.

This raises the question of how to provide high assurance that we have stopped these attacks -- and not just the ones we know about, but the entire class of timing attacks.  Bernstein argues that the best defense against this class of attacks is to ensure that the running time for the AES computation is constant, and independent of the inputs.  See Section 8.

So, this raises the question of what we need to do to ensure that the AES computation is timing-independent.  The remaining sections identify some challenges, and outline solutions.

In particular, Sections 10-11 point out that cache effects can cause timing variability.  And, it is easy to see how this could affect security: cache effects mean that the time taken depends upon the address you look up, and the design of AES means that (if you use table lookups in the obvious way) the address you look up depends upon the key.  Indeed, this is almost certainly exactly the effect that enabled the attack in Sections 3-6.

So the next question is, how do we ensure that cache effects don't introduce timing variability?  The natural solution is: load the entire table into L1 cache, lock it into L1 cache, and make sure it doesn't get kicked out at any point during the AES computation.  However, this natural solution has a problem, on time-sharing operating systems: the OS might preempt us at any point and run some other task.  If that happens, it screws up our defense, by evicting our pre-loaded values from the L1 cache.
In particular, if our pre-loaded values get evicted from the L1 cache, we're back to the vulnerable situation where we started.  Now the total time taken depends upon the sequence of addresses looked up.  For instance, if you look up the same index in the table twice, it'll be faster than looking up two separate indices -- so we might leak information about whether table lookups use the same indices or different indices.  However, in (a natural implementation of) AES, those indices are key-dependent.  Thus, this timing leak might leak information about key-dependent values: it'll leak whether two intermediate values are equal, where both intermediate values depend upon some key material.  This leaked information can plausibly be used to learn some partial information about the key material, thus creating exactly the sort of side-channel attack we're trying to stop.

To prevent this, we need to have some way to be sure that this sort of bad outcome won't happen.  The obvious way to be sure is to somehow introduce some mechanism to ensure the AES computation cannot be interrupted.  If the AES computation cannot be interrupted, then we eliminate the risk of attacks based upon such interruptions.  So, that's what Bernstein proposes.

Bernstein goes on to argue that this is the only solution he is aware of, that meets the requirements.  In particular, the key requirement here is "we need a way to be confident (with high assurance) that there are no attacks".
Does this mean I can tell you with certainty that there is no other defense?  Of course not.  It just means that someone smart studied this and came to the conclusion that, at the moment, the highest-assurance solution appears to be preventing interruptions by the OS.  If someone else wants to argue that this is unnecessary, the burden is on them to show that their alternative is guaranteed to be free of attacks.

Please understand that an important principle of cryptography is: just because you can't think of any attacks, doesn't mean no attacks are possible.  In cryptography, there's a big difference "no evidence that an attack is possible" vs "evidence that no attack is possible".  It's not uncommon for cryptographic schemes that are justified on the basis that the designer couldn't think of an attack (in other words, couldn't find any evidence that an attack is possible) to get broken.  For that reason, cautious cryptographers often aim for the goal of demonstrable evidence that the system is secure (finding positive evidence that no attack is possible).  This is harder, but a more solid foundation for security.

That said, it's important to understand that this paper represents Bernstein's recommendations, which are somewhat at odds with the conventional wisdom of the rest of the community.  Most of the cryptographic community doesn't bother with preventing the OS from interrupting the AES computation, on the theory that they don't know of any attack that's practical enough to pose a significant risk to their system as deployed in the wild.  Basically, they judge that the risk of such an attack is low enough that they are willing to accept the risk.  They may be right.  Or they may not.  Either way, my answer above is predicated on the assumption that you want to understand Bernstein's argument, so you can form your opinion about whether you are convinced or not.  I'm not trying to take a position on whether Bernstein is right or whether the conventional wisdom is right, just trying to respond for your request for help understanding the paper.


What machine learning accuracy is assumed to be predictable for TRNG/PUF application? In regular machine learning (ML) applications, usually an accuracy of greater than 95% is desired.

In an ideal TRNG/PUF applications, unpredictable behavior (50% accuracy with ML models) is desired. How do we define the predictability in these applications? For example, is 60% predictable TRNG/PUF still a good one?
If it depends on the application, it will be so helpful if application examples  with their features can be named.

No we still idealistically target 50% inter hamming distance for PUFs, but being probabilistic and cumulative it's not set in stone.  It's just that you achieve 100% material efficiency at 50%. Or you can use the Jaccard index which should tend to zero, as in the variance of sets A and B  :-

I can't find many academic papers that claim a successful PUF implementations at a 60%/40% hamming distance or 0.5 Jaccard index.  It's even worse commercially, as technology like Maxim's ChipDNA is mired in patents and industrial secrecy.  Maxim only distributes it's security user guide for those chips on request (and I didn't).

That said, the following table lists some   tests for differing PUF constructs. Be aware though that they are not real.  They're based on Monte Carlo simulations which obviously requires pseudo random inputs.  The Flip-Flop PUF seems inefficient.  The bottom entry for the TV-PUF is what the authors are proposing, at ~50%.

From: Saha, Sehwag, V-PUF:A Fast Lightweight Analog Physical Unclonable Function. Paper.

Remember that the fuzzy extractor can do a lot with these values.  Given commercial confidentiality, it's quite hard to get to the bottom of what the physical PUF can do, and what the helper data and it's cunning algorithm glosses over.  It's easy create an extractor that will accept 128-bit input values and guarantees that challenges within 8 bits of each other will produce the same output with over 0.9999 probability .

Depending on your opinion of eprint.iacr.org, here's a DRAM PUF from Carnegie Mellon University which gives a Jaccard index < 0.25 (success). So as I opened, it's not set in stone at 50% hamming or 0 Jaccard.  You can always leverage the helper data given a large enough non-deterministic component.

It's worth noting that TRNGs and PUFs are kinda opposites. A PUF is ultimately required to be entirely deterministic, whilst a TRNG needs exactly the opposite behaviour. Non reproducibility is not   the same as non determinism.   Although it's not impossible, one construction tends not to be used for the other as that's not very efficient.


Verification of encryption for ElGamal cryptosystem Suppose Alice wants to convince Bob that ciphertext c = (a, b) = (gr, m*hr) is some properly encrypted plaintext (not just random numbers). Obviously she can use zk-proof of discrete logarithm knowledge for the first part of the ciphertext (a = gr). But what can she do with b-part?

One of my ideas: if m belongs to subgroup G (with a generator g) than we should prove that b belongs to G. But it's just a new problem.

Alice can also use exponential ElGamal (c = (gr, gm * hr)) if it makes things easier.

Actually, an ElGamal ciphertext $(a,b)$ is "valid" iff $(a,b) \in G^2$,  because for any message $m\in G$ and any $\mathsf{pk}\in G$, the encryption of $m$ will be in $G^2$, because for any $r$, $(g^r,\mathsf{pk}^r\cdot m)\in G^2$, and any $(a,b)$ chosen in $G^2$ can be correctly decrypted by any secret key by computing $m=\frac{b}{a^\mathsf{sk}}$. The proof of knowledge of the random coin $r$ is sufficient to show that you know how the ciphertext was produced.

I do not know if that answers your problem.


Given a set of numbers which return a response code, how can I find the algorithm used to produce the response? I'm working on a problem where I provide an 8 digit integer and a 16 digit integer, then a 10 digit integer response is produced.
For example 12345678 and 1234123412341234 produces 138259849
The same inputs always produce the same output.
Is it possible to find the algorithm used to calculate the response?

There is demonstrably no general solution to this class of problems. Argument: we can construct the output as a Message Authentication Code (e.g. HMAC) of the other inputs, with a random secret fixed key; and what's asked is breaking the MAC.
This class of problems is not modern academic cryptography, which assumes the algorithms are known, only the keys are secret. That's per Kerckhoffs's principle (or really, the modern reading of his second principle) .
However, sometime it is possible to solve such problem:

When the program that produces the output is available, it can be reverse-engineered¹ (de-compiled, or/and observed running in a debugger). That's often how software copy-protection is broken.
When the device that produces the output is available, telltale signs of what it does internally might leak and allow a side-channel attack.
For some classes of algorithms, including CRCs, there are general attack techniques given a number of input/output pairs.

¹ If the algorithm is simple enough. It is possible to make a program that implements a function in essentially the shortest possible way, by using it's own code as key. This program is the canonical form of the algorithm. It can sill be ported to another CPU, with enough memory.


Technical feasibility of decrypting https by replacing the computer's PRNG Intel has an on-chip RdRand function which supposedly bypasses the normally used entropy pool for /dev/urandom and directly injects output. Now rumors are going on that Intel works together with the NSA... and knowing that PRNGs are important for cryptography is enough to get this news spreading.

I personally don't believe this is true, so this is entirely hypothetical: Let's assume that indeed RdRand does what news says it does and that it indeed outputs randomness into a place where applications and libraries would look for cryptographically secure randomness.

How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels?
If the chip's manufacturer can predict the output of the PRNG to some extent, how feasible is it that they can decrypt any https traffic between two systems using their chips? (Or anything else requiring randomness, https is only an example.)

My reason for asking: http://cryptome.org/2013/07/intel-bed-nsa.htm
As said, I don't believe everything written here, but I find it very interesting to discuss the possibility technically.

1 - How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels?

A strong stream cipher's output is random and unpredictable to anyone not knowing the key. See where this is heading? Just because something looks random doesn't mean it's random.

  2 - If the chip's manufacturer can predict the output of the PRNG to some extent, how feasible is it that they can decrypt any https traffic between two systems using their chips? (Or anything else requiring randomness, https is only an example.)

If you can predict the PRNG you can basically predict the secrets used for key exchange, and from that deduce the shared secret. Then you can simply decrypt the communication.


Schnorr Identification protocol sometimes wrong? I'm implementing the Schnorr Identification protocol as part of a larger protocol. In a large percentage of cases, around 20%, my test fails. I don't think it's a code problem, although possible, but I think it's a problem with my understanding of the protocol.

Here's how I currently perform Schnorr Identification:

Using OpenSSL, I find a safe prime $p$ and subsequent prime $q = (p - 1) / 2$
I find a generator $g$ for the cyclic group $\mathbb{G}_q$ of order $q$.

This is the part I'm the most suspicious of. I've read that it's believed taking random $h \in \mathbb{Z}^{*}_{p}$ and setting $g = h^{(p-1)/q} \mod q$ will result in $g$ being a likely generator for $\mathbb{G}_q$ as long as $g \neq 1$, although it's not proven. I don't fully understand this, and it seems a probable place for my implementation to fall down.

I generate a random private key $x \in \mathbb{Z}_q$ and set $y = g^x \mod p$

With the ElGamal key now set up, I want to prove knowledge of $x$ to a verifier who knows the public key $(p, q, g, y)$.

I pick a random $e \in \mathbb{Z}_q$ and send $w = g^e \mod p$ as my commitment.
As verifier, send random $c \in \mathbb{Z}_q$ to prover.
As prover, send $s = cx + e \mod q$ to verifier.
As verifier, check that $wy^c \mod p = g^s \mod p$.

The final step is where it will sometimes fail; the equality doesn't hold. Because each test run generates new random numbers, it's hard to see what's causing the failure.

I don't think it's a code problem; I believe I have coded everything to do exactly what the above steps outline. I think one or more of the steps themselves might be wrong. Note that I have included the modulus for each calculation that I'm doing, because some papers tend to leave them as implicit.

Is my understanding of the Schnorr Identification protocol correct, and have I correctly reproduced the formulas? If so, can I do it better?

Good that we have resolved the issue (the bug is to compute $g=h^{(p-1)/q} \bmod p$ instead of $g=h^{(p-1)/q} \bmod q$).

When implementing such protocols you can take the following "rule of the thumb":

When working with group elements of the multiplicative group $\mathbb{Z}_p^*$, i.e., performing group operations, then you always do your computations modulo $p$, e.g., you compute $z=y w \bmod p$.
When working "in the exponent" and your "base element" ($g$ in that case) generates a subgroup of order $q$, then you perform the computations on these integers modulo $q$, i.e., you compute $s=cx+e \bmod q$ (Note that when you then take your group element $g$ to the power of $s$, then you do another group operation, i.e., compute $g^s \bmod p$).