Any advantage of multiple salts/keys for single password when using PBKDF for multiple secrets? Background: I'm putting together a personal project to store multiple short message protected by a master password. This is more to learn and demonstrate that I understand how to use some standard cryptographic primitives than for practical use.

I am using HMAC_SHA256 inside a standard pbkdf2 function (part of OpenSSL). I have ended up with a choice between two designs for data model when it comes to deriving an AES key from a master password:

Store a pbkdf2 salt for each message, and derive a different AES key for each one.
Store a single pbkdf2 salt for the whole database, and derive a single AES key used for all the messages.

I am using a cryptographic RNG for salts and for initial values in AES 256 CBC. I store the salts and ivs in the clear in the database, the threat model is attacker has copy of all encrypted text, salts and ivs, but not the master password. Attacker is not able to request encryption, but they may observe any existing encryptions and may correctly guess one or more plaintexts.

As far as I can tell, both schemes have the same level of secrecy for the data at rest. The use of random initial values and the short messages mean that there is no real need to have a different key per message. There is no known plaintext attack that could take advantage of the fact that the key is shared in scheme 2. Both schemes support re-keying without changing the password, although I don't think that is particularly useful.

I think scheme 2 offers some advantages in performance - the costly pbkdf2 is only used once for multiple messages. It doesn't make brute-forcing the password any easier. It does mean ignoring the password and brute-forcing the key is potentially more damaging, but I think that is entirely unrealistic for AES 256, and that the password is the most vulnerable to attack secret in my project.

Have I missed anything? Is there some additional reason why I would choose one approach over the other?

Store a single pbkdf2 salt for the whole database, and derive a single
  AES key used for all the messages.

This is the better approach.
I'm confident to say that, because if you derive a new key using a proper password-based key derivation function (PBKDF) for each and every entry, you have to set the cost parameters for the PBKDF to not frustrate the user. But if you do this, then an attacker only needs to break a single one of the weaker password hashes to recover the password. So rather go with only one PBKDF operation, but make that one costly (maybe 100ms - 1s on the user's machine).

Additionally you can use a key-based key derivation function (KBKDF) to derive a new key for each entry from your master password-derived key. This KBKDF should be HKDF using most of its features (salt? key identifier? personalization string?), but if HKDF is impossible for you, simple HMAC should do as well.

There are a few gripes though with the choice of the primitives you mentioned, namely:

HMAC-SHA256 for PBDKF2. SHA-256 is based on 32-bit operations and thus performs best on 32-bit machines. If possible you should use SHA-512 because it is based on 64-bit operations and not only will perform better on 64-bit machines (your clients?) but will also be more costly for an attacker to implement in a parallel fashion because most of these devices can do 32-bit operations much more cheaply than 64-bit (especially GPUs are today always 32-bit processors)
Don't use PBKDF2 if possible, use Argon2, scrypt or bcrypt. The latter three PBKDF are modern successors to PBKDF2 and are more hardened to attacks by GPUs, FPGAs and ASICs than PBKDF2 ever could be. Also see the canonical answer on Information Security SE about this topic.
Use authenticated encryption. You have OpenSSL and as such you can use its authenticated encryption implementations, especially AES-GCM, which will give you better security than plain AES-CBC. Note though that plain AES-CTR provides less security than AES-CBC, because it is even more easier and targeted malleable, e.g. if you know where the data to change is you trivially flip the bits with CTR, with CBC you at least screw up the previous block.


Statistical distance in distributions I have two questions regarding to statistical distance in distributions.

1: If $Z$ is uniform random variable over $N$ consecutive integers and
$m < N$ then $Z$ mod $m$ has statistical distance at most $m/N$ from the uniform
distribution over $[m]$ ($[m] = {0,1,2,...m-1}$). How this statement is true based on the definition of statistical distance

2: For independent random variables $X_1, X_2, Y_1, Y_2$ the distance between
the joint distributions $(X_1, X_2)$ and $(Y_1, Y_2)$ is at most the sum of statistical distances of $X_1$ from $Y_1$ and $X_2$ from $Y_2$. Similarly, if these variables are group elements in $G$, the statistical distance between $X_1$ ·$X_2$ and $Y_1$ ·$Y_2$ is no greater than the sum of statistical distances of $X_1$ from $Y_1$ and $X_2$ from $Y_2$. How can we prove this statement?

These questions are a part of the RSA accumulator paper by Dan Boneh et al.
Thank you for your help.

If $m$ divides $N$, then you get the uniform distribution over $[m].$

Let $k=N-\lfloor N/m \rfloor m.$ Note that $k\geq 0,$ with $k>0,$ if $m$ does not divide $N.$ When you reduce $Z$ modulo $m$, due to wraparound, the smallest $k$ values $0,1,\ldots,k-1$ are "hit" an extra time, as $Z$ varies from $0$ to $N-1.$
Thus the probability distribution of $W=Z \pmod m$ is:

$P[W=u]=\frac{1}{N}(\lfloor N/m \rfloor +1)\quad w\leq k-1,$

and

$P[W=u]=\frac{1}{N}(\lfloor N/m \rfloor)\quad k\leq w\leq N-1.$

Now sum these values absolute difference with $1/(N/m)$ which is the value of the uniform distribution at each point.

For part 2, group via row or column for each marginal distribution and apply a similar technique, to get the individual distances. Now look at the joint taking care to scale correctly when you sum over the whole array for the statistical distance of the joint from the uniform.


Is it possible to generate a secure permutation F over 32-bit integers even if F(0) ... F(n) is public knowledge? I'm currently interested in the problem of generating random-looking URLs from sequential database IDs, like how they do it in link shorteners. One way to do this is to encrypt the sequential database ids using a 32 bit block cypher and base62 encode the result so it can be written to the URL.

For example:

foo.com/1       foo.com/2        -- Original sequential IDs
foo.com/142365  foo.com/226340   -- Encrypt IDs using a permutation function
foo.com/b2D     foo.com/wse      -- Encode in base62 format - looks random + compact.

Now here is the catch: Whenever we encrypt the a new database ID and publish the URL, that plaintext-ciphertext pair become public knowledge. Is it possible to create an encryption system that makes it hard to guess what will be the next URL we will generate? That is, can we make it so the attacker can't guess the value of $F(1000000)$ even if he knows the values of $F(n)$ for $n \leq 999999$?

Some things that I think are important to note:

The cypher must have a 32 bit block size. Otherwise, the resulting URLs get too long.
The secret key is allowed to be any size.
Each number is only be encrypted once and all the messages I encrypt are 32 bits in length. (None of the stream-cypher stuff applies)

My actual use case – and most people's, to be honest – won't really need that kind of security. A bijective mapping from sequential IDs to URLs that looks scrambled at first glance is good enough. However, I am now curious if that unpredictability requirement is possible to achieve. In my searches, I found a lot of people saying that 32 bit blocks are too small due to the birthday problem but I am not sure that caveat applies here. On the other hand, none of the 32-bit block cyphers I found say anything about their resistance to known cyphertext attacks…

Yes, it is possible to implement the primitive asked, with a 32-bit block cipher that is secure (indistinguishable from a random permutation) no matter how many input-output pairs are known, keyed with a fixed secret randomly-chosen key. That's a standard building block in Format Preserving Encryption.

One such block cipher is: Louis Granboulan and Thomas Pornin, Perfect block ciphers with small blocks (in proceedings of FSE 2007).

Emil Stefanov and Elaine Shi's FastPRP: Fast Pseudo-Random Permutations for Small Domains (Cryptology ePrint Report 2012/254) claim a speed improvement, and review some earlier work.

Update: Ricky Demer kindly pointed another recent paper: Ben Morris and Phillip Rogaway, Sometimes-Recurse Shuffle, Almost-Random Permutations in Logarithmic Expected Time (Cryptology ePrint Report 2013/560).


Empty message Hash length I am learning Hash Algorithms and in a presentation (PDF) about these algorithms I read that:

  Length of $h(m)$ much shorter then length of $m$.

Now my question is:
What if we talk about an empty string, is it true that hash length is shorter than the length of message?

I searched the internet and  found that:

  The MD5 Hash of an empty string is:d41d8cd98f00b204e9800998ecf8427e

The presentation probably went along with a more verbose lecture.

I would assume there was some discussion about message lengths there, since that statement is obviously incorrect. In most applications, the "message" length is longer than the digest, and the average message length is also most likely longer. Think file verification, or processing of an actually message, instead of of a password.

In that statement, substitute "much shorter" to "usually much shorter"


Encryption scheme for social-network-like data sharing data via untrusted server? I am thinking quite a lot lately abut the problem of secure, privacy-preserving social networking. Distributing the network among trusted, preferably self-hosted servers (like Diaspora, GNU Social etc. attempt to do) is obviously not a good solution for the the large majority of non-technical users, so my thoughts currently focus on cryptography-based approaches that allow the secure sharing of data even if it hosted on "unstrusted" servers. However, I am stuck with the following problem:

Suppose that Alice has three picture albums - A, B and C - and likes to share them with Bob and Carol. Album A  should be accessible with both Bob and Carol, while albums B and C are for Bob only. For several reasons, she needs to do this with webspace hosted by a suspicious friend of a friend named Chuck, which Alice doesn't trust at all and thus wants to protect the pictures from.

Now, Alice could do the most obvious thing and encrypt the data before storing it on Chuck's server. Now she could give Bob and Carol the encryption key and configure her webspace to serve album A to both and albums B and C to Bob only (distinguishing both by e.g. password-based authentication). That way, Chuck couldn't view the pictures, and Bob and Carol can view the appropiate sets of pictures.

However, there are serious problems with this approach: If Chuck decides to be stupid and send picture albums B and C to Carol for the fun of it, she is able to view them because all albums are encrypted with the same key.

The only solution to this problem I can see is to give Bob and Carol two different keys and encrypt B and C with Bob's key. However this means that there need to be two versions of album A, one encrypted with Bob's key and one with Carol's. This wastes space, though, especially if more peers come into play; a combinatorial explosion of copies could be the consequence.

Is there any encryption scheme that can remove these problems?

Yes, it's trivial. You encrypt each item with its own random key. You then need only encrypt the key to each album for Bob and Carol.

A typical way to do this is to publish an encrypted per-user keyring -- one for Bob and one for Carol. Bob and Carol can each decrypt their keyrings to get the keys to all the objects they are supposed to access.

The reverse way of doing this is to attach to each group of objects with common permissions a per-group keyring. This is usually used in conjunction with a public key for each user. The key to the group of objects is encrypted with the public keys of every user authorized to access it and those encrypted keys are stored with the group of objects.


What exactly does s2k do in gpg So I recently discovered the --s2k mode in gpg.
Sadly it is not very well-documented. I mean, what is s2k even supposed to mean?

Could someone explain to me the purpose and detailed function of s2k?

Is --s2k-cipher-algo even necessary in a symmetric encryption scenario where you define the cipher separately?
What exactly  does --s2k-count do?
What does the number after --s2k-count do? What does it indicate and why is 65 million the highest number? 65 million of what? What is done so many times?

The "s2k" options correspond to the String-to-Key specifiers. An s2k transform turns a human-compatible symmetric secret (a password or passphrase) into a symmetric key suitable for a symmetric encryption or MAC algorithm.

Turning passwords into keys is tricky business because passwords that human can remember and accept to type tend to be weak with regards to exhaustive search (often called "dictionary attacks" in that context, since we are talking about words). Thus, we need a "strengthened" process which is often called "password hashing" or "password-based key derivation". To be brief, a good password hashing process must:

be unique to each case, to prevent precomputations and cost sharing;
be awfully expensive, in a configurable way.

Read this answer for an introduction to the relevant concepts of password hashing.

The s2k-count parameter is used only when the s2k method is "3", i.e. Iterated and Salted S2K in OpenPGP terminology. This password hashing method basically hashes together multiple copies of the salt and the password, concatenated, until the total byte count reaches the specified value. With the maximum value (65011712), about 65 MB worth of data are thus hashed; a modern machine (even a "small" one like a smartphone) should be able to do that in a fraction of a second (say, less than half a second), so this is tolerable from a user interface point of view. However, the attacker will also need to do that heavy hashing for each trial of a potential password; and for him, there is a huge difference between half a second and a millionth of a second, because he has many potential passwords to try.

Now that S2K is not the best in town, because smart attackers will get a substantial boost in their attack by using some GPU (GPU are very good at running hash functions like SHA-1). But this is the best one defined so far in the OpenPGP format.

The --s2k-cipher-algo is about informing the S2K transform about the kind of key it must produce: while symmetric keys are mostly bunches of bits, their length still depends on the intended algorithm (e.g. a key for AES-256 must have 256 bits in length).


Deciphering text encrypted with a changing cipher I know there are many ways to crack basic ciphers were each letter is mapped to some other letter, but what ways are there to decode something that was encrypted using a cipher that changed after every letter, in a way that is based on the letter just coded?

For example, imagine using a Caesar cipher where the number of letters the alphabet was shifted over changes by $n$ after every letter coded, where $n$ is the position in the alphabet of the letter just encoded.

That would seem to null the efficacy of observing letter frequency, double letter patters, common short words, etc.  How would a code like this be cracked?

Sorry, I might have been unclear.  The Caesar cipher was just an example, but say that the positions shift over $f(n)$ letters instead of just $n$, how would $f(n)$ be determined?

It's insecure because the algorithm you described has essentially no key. You just have to try 25 different offsets for the first character, then run the algorithm and see if plaintext comes out.

Have a look at Kerckhoff's Principle, and try to understand why there needs to be a secret key in addition to an algorithm.


RSA:Plaintext block has a common factor with modulus I've seen a couple of posts stating the following fact: If $(n = pq,e)$ is the public key of an RSA instance and some plaintext block $m$ has a common factor with $n$, then also the corresponding ciphertext block $c$ has the same common factor with $n$.

Yet, I could not find any formal proof of this statement. I tried to come up with one by myself, but I could not quite make it. What I have so far:

As $m<n$, $m = p * z$ or $m = q*z$ for some $z \in \mathbb{Z}$. Assume w.l.o.g $m = p * z$. Then $c = m^e \mod n = (p * z)^e \mod n$. I don't really know how to continue. One could rewrite this further as $c = ((p^e \mod n)  * (z^e \mod n)) \mod n$ but that didn't help me either. Does someone have a hint for me?

Any help is appreciated! Thank you.

Here's one way to argue for this property using the Chinese Remainder Theorem:

Let $m,e,n=pq$ be arbitrary with $\gcd(p,q)=1$. Let's assume $\gcd(m,n)>1$ and more precisely wlog $\gcd(m,n)=p$. Now we shall apply the Chinese Remainder Map $\theta:\mathbb Z_n\to\mathbb Z_p\times \mathbb Z_q:x\mapsto(x\bmod p,x\bmod q)$ which will yield $\theta(m)=(0,y)$ for $y:=m\bmod q$. Now, $\theta$ is a ring isomorphism, meaning that it preserves multiplication and addition, that is $\theta(m^e)=(0,z:=y^e\bmod q)$. Because $\theta$ is a bijection, its inverse is unique and the solution $c\in\mathbb Z_n$ to the following set of equations:

\begin{align*}
c&\equiv0\pmod p\\
c&\equiv z\pmod q
\end{align*}
And as you can easily verify, $c=zp$ satisfies these equations, meaning it is the encryption of $m$ and thus a multiple of $p$.


Is it possible to create a ciphersuite for TLS 1.3 using only the Keccak-sponge/duplex? Now that Keccak has been chosen as SHA-3 we see that there have been defined quite a few related modes, including authenticated cipher modes, the KMAC message authentication mode, XOF's and whatnot. However, it is unclear to me how much this fills all the gaps for symmetric cryptography. Could we for instance define and implement a TLS 1.3 cipher suite to use just constructions solely based on the Keccak-sponge/duplex as primitive? Simple bit operations and loops are of course permitted to tie everything together.
So besides KMAC we'd likely need to have a well defined and preferably standardized KDF and a secure random number generator (preferably one that can be reseeded). Additional points go to the answer that also manages to indicate a method of authentication (hash-based signatures?) and, possibly more tricky, a key agreement scheme to replace (EC)DH.

First for the scope of such a ciphersuite, to quote RFC 8446 Section B.4:

A symmetric cipher suite defines the pair of the AEAD algorithm and hash algorithm to be used with HKDF.

Now to the first question:

Could we for instance define and implement a TLS 1.3 cipher suite to use just constructions solely based on the Keccak-sponge as primitive?

With the above definition of what a cipher suite is, this seems easy enough, we just pair either of Keyak or Ketje with SHA-3 or KangarooTwelve. One of the first two mentioned AEAD schemes would be mostly used for bulk encryption and one of the latter two hash functions via HKDF for key derivation. I'm not sure how much customization TLS 1.3 allows but it might also be possible for an RFC to define Keccak based ciphersuites to use a different KDF than HKDF, though this would most likely lower acceptance.

Additional points go to the answer that also manages to indicate a method of authentication (hash-based signatures?)

Indeed it would be possible to use either of the hash-based NIST PQC Round 3 Alternative candidates for this. In fact Picnic is already based on Keccak (and LowMC to build a MPC-based signature scheme). Additionally SPHINCS+ is also specified for SHAKE-256 for the NIST PQC.

and, possibly more tricky, a key agreement scheme to replace (EC)DH.

Constructing key agreement (or public-key encryption) from hash functions is very unlikely even for theoretical constructions (assuming collision-resistance). It is very much impossible to do so generically only assuming the existence of black-box One-Way-Functions as shown by Rudich and Impaglazzio in STOCS 1989's "Limits on Provable Consequences of One-way Permutations" (PDF).


What is the difference between, and security of $Z_p$ and $F_p$? While reading some papers, I found that sometimes $Z_p$ was used but sometimes $F_p$ was used ($p$ is prime). Usually, the author will only use their subgroups like this: choose a big prime factor of $p-1$ , denote $q$, and set $G=\langle g \rangle$.

My questions are :

Why do we only use the subgroup while $Z_p$ OR $F_p$? Or maybe we can choose a $p$ such that $p-1$ is prime and now if $Z_p^*$ or $F_p^*$ can be directly used?
What's the difference of using $Z_p$ and  $F_p$?

You should read the Wikipedia article on finite fields. For each prime $p$ and for each $n >0$, there is a unique field of order $p^n$ (up to isomorphism). This field is usually denoted $F_{p^n}$.
Now, for $n = 1$, the field $F_p$ can be identified with the set $\mathbf{Z}/p\mathbf{Z}$ of  integers modulo $p$, which is also sometimes denoted $\mathbf{Z}_p$. However, the notation $\mathbf{Z}_p$ is also used in number theory to denote the ring of $p$-adic integers and this may create a potential confusion.

The multiplicative group of every finite field is cyclic, that is, is generated by a single element. This multiplicative group is often used in cryptography.


How is Diffle Hellman with RSA immune to man in the middle? Alice and Bob want to exchange keys, Alice sends his half (the public key of the ephemeral key pair) signed with his private key and makes the public key available. Eve is bridging the connection so he intercepts the message uses the public key and verifies the half. He then sends his half to Alice signed  and establishes a connection. Now Alice is communicating with Eve and Eve is decrypting the message and sending to Bob.

Isnt this exactly same as the raw Diffie Hellman ? How are we exactly preventing man in the middle attack if Alice thinks the whole time that Eve is Bob ? Is it correct to assume that the message(half key) is not encrypted ? Is a certification authority also required for ephemeral diffie hellman ?

Please correct me if I have misunderstood Ephemeral Diffie Hellman

He [Ed: Eve] then sends his half to Alice signed and establishes a connection. Now Alice is communicating with Eve and Eve is decrypting the message and sending to Bob.

Eve can only sign with her own private key. So your attack only works if Alice accepts the signature from Eve. That means that:

Eve's public verification key needs to be trusted and
that Alice doesn't check that that public key belongs to the intended party, i.e. Bob.

Some kind of PKI is usually involved, and PKIX is the most common PKI. But you can establish trust by e.g. sending the public key and then validating the fingerprint of it over the phone. I'm not sure if you can call that a PKI because of the simplicity of the protocol and the lack of other participants.

So no, this is not the same as raw Diffie-Hellman - unless the necessary verification steps are missing, of course.


what can attackers do between two end hosts I have one question that I couldn't come up with a nice solution.

So let's have this analogy, I have a box full of money and I want to deliver to this my friend. Here if we think of a potential attacker there are two possible ways, first the attacker would be between us , so called postman or he could pretend like he is the recipient.

This being the case, what are the properties of both type of attackers?

For the first attacker in the role of the postman, he could simply observe, modify or block the delivery of the box(message in cryptography). And my question here is what could he do if he disguises as a receiver unlik the postman attacker?

and what other kind of attacks could these both attacker types do?

Attacks like this can be prevented by TLS.
Quote from Wikipedia:

The TLS protocol aims primarily to provide privacy and data integrity between two or more communicating computer applications.2:3 When secured by TLS, connections between a client (e.g., a web browser) and a server (e.g., wikipedia.org) have one or more of the following properties:

The connection is private (or secure) because symmetric cryptography is used to encrypt the data transmitted. The keys for this symmetric encryption are generated uniquely for each connection and are based on a shared secret negotiated at the start of the session (see TLS handshake). The server and client negotiate the details of which encryption algorithm and cryptographic keys to use before the first byte of data is transmitted (see § Algorithm below). The negotiation of a shared secret is both secure (the negotiated secret is unavailable to eavesdroppers and cannot be obtained, even by an attacker who places themselves in the middle of the connection) and reliable (no attacker can modify the communications during the negotiation without being detected).

The identity of the communicating parties can be authenticated using public-key cryptography. This authentication can be made optional, but is generally required for at least one of the parties (typically the server).

The connection is reliable because each message transmitted includes a message integrity check using a message authentication code to prevent undetected loss or alteration of the data during transmission.


Can GnuPG be used with a login system? I was thinking about creating a proof of concept for the following type of website login system.

Instead of passwords being used, on account creation, a public GnuPG key is uploaded to the server, and that serves as the main form of authentication for a users account. To login, the user would give their username. The login app would get the usernames public key, encrypt a random string with their public key, and the user would have to decrypt that downloaded file, and used the decrypted string as the password.

Does there seem to be any flaws in that system? If the user is able to keep their key secret, I don't see why this type of system wouldn't be feasible.

What do you think?

Can GnuPG be used with a login system?

Yes, there are ways you could do that.

But…

While possible, there are two things that immediately pop into my mind:

Public key crypto can be somewhat slow, which might or might not cause resource problems on the clients as well as on your server… depending on the number of users that simultaneously try to login, and how exactly you implement things.
Expecting users to decrypt a file to get a temporary login password (as you describe) doesn't seem to be very handy from a usability and UX point of view. Yet, that doesn't mean your idea would not be possible as a "proof of concept"… I just don't think it would be very practical. After all, you're putting a lot of burden on the client here (additional work of decryption, introducing additional steps since client first needs to download the encrypted password file, etc.) which – if you think about your idea twice – is rather unneccesary if you use a secured (read: HTTPS) connection. And you need to, otherwise, your Public-Key-Login-Adventure might be an easy target for MITM attacks. Sure, you can try to work around those too… but why invent a square wheel (your idea) if there is a good, secure, and working round wheel (SSL/TLS) available already.

I'ld say this boils down to a case of "just because you could, doesn't mean you should".


linear cryptanalysis of hash function I have studied linear cryptanalysis for block ciphers, but i did not understand how it works on hash functions. Can you give me an explanation of this attack on hash functions?

The use of linear cryptanalysis for unkeyed hash functions seems to data back to the article (available here) below

Handschuh H, Knudsen LR, and Robshaw MJ, Analysis
of SHA-1 in encryption mode, published in the Cryptographers' Track-RSA Conference, Naccache, D. (Ed.), LNCS 2020, Springer-Verlag, Berlin, pp.70-83, 2001

The authors state:

  SHA was never defined to be used for encryption. However, the compression
  function can be used for encryption. Each of the 80 steps of SHA-1 (divided into
  four rounds, each of 20 steps) are invertible in the five A, B, C, D, and E variables
  used for compression. Therefore, if one inserts a secret key in the message and a
  plaintext as the initial value, one gets an invertible function from the compression function by simply skipping the last forward addition with the input.
  This is the encryption mode of SHA considered in this report. The resulting block cipher is named SHACAL and has been submitted to NESSIE by Naccache and the first
  author.


What kind of attack does the current brokenness of SHA-1 allow? I understand that the following is becoming feasible, or already is:

Find any 2 data (d1 and d2), for which SHA1(d1) = SHA1(d2)

However, it is not entirely clear to me if there is evidence of the feasibility of:

Find d2 for a specific d1, such that SHA1(d1) = SHA1(d2)

My difficulty in understanding the available literature is that I typically see the attack referred to as "seeking collisions" rather than "seeking a collision"; implying that what is being identified is two data that happen to share a SHA-1, rather than finding a datum which shares the same SHA-1 as a specific target datum.

EDIT: My question is partially redundant to, though more specific in purpose than, this question Second pre-image resistance vs Collision resistance

That's true. There should not be any publicly known attack on SHA-1 that allows for a given $d1$ to find a $d2$ such that $h(d1) = h(d2)$.

SHA-1 is vulnerable  for finding a pair of $d1$ and $d2$ such that $h(d1) = h(d2)$.

The same, however, applies to MD5, which is unusable for SSL/TLS certificates and a successful attack has been performed. So, this kind of collision can allow (under some circumstances) more that you might think.

The notable difference between SHA-1 and MD5 attacks is the cost of such attacks. For MD5, the attack is very fast. For SHA-1, the attack would be very expensive, but for some groups (e.g. governments) feasible.

(There might be also some more differences that I am not aware of. However, both of them use the Merkle–Damgård construction, which implies some common security characteristics.)


Interesting implementation practices in popular crypto library So reading through the salsa20 implementation for the crypto library for go-lang, I noticed something interesting. Specifically this portion. It looks like something I would expect from someone learning programming. They took 80 lines of code of what could have been easily done using an array and iteration. Looking up other implementations I found this unofficial one, which does use iteration. Looking at other they all choose to do this portion using a loop. But these are not the official ones. So why doesn't the official one use the more terse, but equivalent way?

My question really is, is there some security benefit to doing things without an extra array and loop? Is it speed? Is there some attack when you have an extra array and loop?

This appears to be a simple case of Loop Unrolling, which is a generic software optimization. Implementations of crypto algorithms are often times "unrolled", which means taking the statements that normally go in a loop and hardcoding them in the order they would have happened. This is a performance optimization: The loop counter requires cycles to increment and compare, as well as register space to do either (which may imply additional MOV instructions as well).

So the answer is speed, not security — optimizations such as loop unrolling do not change the output of the algorithm, they are an implementation choice.

Chances are, if you describe an algorithm to 10 different people and ask them to implement it, you will receive 10 different variations of the same program - that all still produce the same output, albeit at varying speeds and implementation complexities. Especially at the C level, performance often times comes at the cost of code clarity.

Theoretically speaking, which means disregarding side channel attacks, the implementation should influence only the performance of the algorithm, not the security. In practice however, due to the potential for side channels, the implementation may influence security, though loop unrolling will most likely not be the culprit. If this was the case, the lack of security would not be visible in the output of the algorithm - side channels exploit information that is only present when the actual algorithm is physically implemented in practice, and the information is extracted via other means.

  Why is this not left to compiler optimizations

We do not necessarily like to let the compiler aggressively optimize our crypto code. - it can do things that are less than desirable. Cipher algorithms are usually relatively small and very simple in their implementation (if not conceptually so), and sometimes are implemented directly in Assembly to maximize performance or minimize code size.

Loop unrolling is used in hardware implementations as well.

  Why is this done in the official implementations

The official implementations are the ones actually being used by the largest numbers of people, and so obviously should be the most efficient ones available. This is just a common courtesy really, as CPU cycles cost dollars as well as time. This is not particular to cryptography, but is most likely true of software in general.

The "unofficial" implementations you have seen were probably written by somewhere learning the algorithm, for which clarity is a priority, rather then efficiency.


Perfect Deniability of a MAC Protocol I proposed an idea of Perfect Deniability of a MAC

I tried to come up with a protocol that satisfies those security requirements as well as the normal security requirements of a MAC

One-Time MAC

Alice and Bob pre-share a $n^2$ OTP bits, $k$ (bits that were generated the same way you would for a OTP with all the requirements met here)
Alice breaks $k$ into $n$ strings of length $n$, lets call them $k_1, k_2, ..., k_n$
For each $k_i$ Alice computes $b_i = \bigoplus_{j=0}^{n}(m \oplus k_i)$

Each $b_i$ is a bit computed from xoring all the bits in $m \oplus k_i$

Alice sends $m||b$ where $b = b_1||b_2||...||b_n$
Alice and Bob destroy k

Proof

One-Time MAC is a MAC since anyone not knowing the key can only modify the stream with negligible probability.  If someone tried to flip bits in the message then they would need to flip some unknown bits in the MAC and visa versa. They would only guess correctly with probability $2^{-n}$.

Now for the perfect deniability part.

If Eve came to Alice with $m$ and MAC($m$) = One-Time MAC($m$) then Alice can just generate $n$ random $n$ bit strings check their $b_i$ values and reorder them so that they create a "valid" key.  (Note she may need to generate more than $n$ keys if the number of $b_i = 0$ doesn't  match the number of $0$'s in MAC($m$), but odds are she will not need to generate more than $2n$ random strings)

Problems and Thoughts

I feel obligated to post issues with this protocol.

Very large key ($n^2$)
Similar issues as OTP (key management, etc..)
Could be used as a MAC for a OTP and give messages perfect secrecy and perfect deniability without the ability to be tampered with

Questions

Does this satisfy the properties of a MAC?
Does this satisfy this definition?
Could this be done with a smaller key?
For long messages can you break it into smaller messages and MAC each individually to use less key?

I would assume you would lose security since $n$ would be smaller

Does this satisfy the properties of a MAC?

No, it doesn't, however a tweak to it does.

The issue is that flipping a single bit of $m$ always changes either every bit of the MAC (if $n$ is odd), or none of the bits (if $n$ is even); hence it is trivial for the attacker to modify the message, and adjust the MAC.

What you really meant is $b_i = \bigoplus_{j=1}^{n}(m \wedge k_i)$ (where $\wedge$ is the bit-wise and operation.  This still needs a bit of tweaking (because of the all-0 message; either include an artificial 1 bit in the message, or cheaper, do a final xor of yet another $k$ vector into the final $b$ result).

This method is equivalent to selecting a random $(n \times n)$ matrix in $GF(2)$, and then doing a matrix multiplication of the message to form the output; this is a well-known universal hash method.

  Does this satisfy this definition?

With the above tweaks, yes.

  Could this be done with a smaller key?

Of course.  I suspect that most universal hash methods could be made to do this; here's one approach (polynomial hashing) that uses quite a small key.

Lets pick an integer $z$, and a field representation of $GF(2^z)$ (actually, any field of about this size can be made to work).

Then, for our one-time keys key, we pick two random $z$-bit values $h$ and $c$.

Then, we divide our $n$-bit message $m$ into $z$-bit sized chunks $m_{i-1}, m_{i-2}, ..., m_0$ (where $i = \lceil( n / z ) \rceil$, and we compute:

$$MAC = m_{i-1} h^{i+1} + m_{i-2} h^{i} + ... + m_0 h^2 + i h + c$$

The above computation is done in $GF(2^z)$

This is also a secure MAC (any modification to the message and tag will pass the checks with probability at most $(i+1)2^{-z}$; we can select $z$ to make this arbitrarily small), and it also meets your requirements (to fake a MAC, we can select an arbitrary $h$ and compute what the $c$ value had to be); using a total of $2z$ OTS bits per message.


elliptic curve multiplication with negative factor I'm learning the multiplication operation on EC. From most material I can found, the multiplication $nP$ is just:

$$nP=P+P+\cdots +P+P$$
For negative factor, i.e. $(-n)P$, by above definition and the definition of $-P$, we can write $(-n)P$ as:

$$(-n)P = (-P) + (-P) + \cdots (-P)$$

My question is: is it possible to expression $(-n)P$ as $mP$ where $m>0$ under reasonable assumption? For example, we can assume the knowledge of the group order.

I'm asking so because $nP$ on EC is analogous to exponentiation in group $\mathbb{G}$ with order $p$. And in the latter case we have
$g^{-n} \equiv g ^{k\phi(q)-n}\pmod q, \forall k\in \mathbb{Z}$ by Fermat's little. So I'm wondering if there is a similar result for EC.

If you know the order of the curve (we'll call it $q$), then it's easy.

In that case, we have the identity $xP = (x + q)P$ for any $x$.  Using that identity, we can express $(-n)P$ as $(q - n)P$; by the above identity, these are the same.  If $q > n$, this gives you your answer.

The more general answer (which works for any $n$) is $(-n \bmod q)P$, using the convention that $a \bmod b$ is that integer which is between 0 and $b-1$, and which is congruent to $a$ modulo $b$.

This is exactly analogous to the $\mathbb{G}^*$ case; in that case, the size of the group is $\phi(q)$; in this Elliptic curve case, the size of the group is $q$.


Understanding Cryptography practically I have just undergone a one semester course in cryptography. I was introduced to multiple theoretical aspects, the way several algorithms work, the methods and their stability and so on. Due to time constraint, not much of problem solving was done. I want to understand more of cryptography through practical problems. How do I go about it ? Relevant web sites can also be included. Thanks !!

If you're really interested in practical problems and want to know what people care about when actually deploying crypto in practice, then you can start by e.g. reading through the messages of the IETF Crypto Forum Research Group mailing list. The discussions cover mostly crypto standards, which means that it's as practical as it can get. Archived discussions can be found here:

http://dir.gmane.org/gmane.ietf.irtf.cfrg

You won't find any homework problems there, but you can find discussions that will lead up to future standards.


Elliptic Curve - Divide by 2 Can anyone tell me the specific equations and steps for dividing a point on an elliptic curve by 2?

For instance, I have the point $(P_x, P_y)$, and I would like to find the point $(R_x, R_y)$ which when doubled yields $(P_x, P_y)$.

It was suggested that I use the point doubling equations and solve, but I am looking for the specific equations and steps and perhaps a reference to thorough discussion of the topic.

Thanks for your time.

EDIT:  I was under the impression that it would be the same steps for all curves.  In this instance I am trying to do it on the secp256k1 curve.

There are two strategies to do what you want.

The first one being to find the group order $q$ and then compute $i=2^{-1}\bmod q$. When you then multiply your point $P$ by $i$ you get $Q=[i]P$ with $[2]Q=[2i]P=[(2\cdot 2^{-1})\bmod q]P=P$ as desired. This general strategy works for any finite group (as long as $q$ is not even) and was quickly pointed out by fgrieu in the comments.

The second way goes as follows:

Find out the equation for your curve. For secp256k1 this is $y^2=x^3+ax+b$ a.k.a. "Short Weierstrass Form".
Go to the explicit formula database and select the relevant curve.
Take the affine doubling equation and plug it into your favourite tool for solving algebraic equations and tell it to solve for the coordinates on the left side.
You should now receive a result. Because all fields are equal when it comes to the transformations carried out, you can just take the resulting formula and "easily" translate it to work over your finite field.


How to securely encrypt/decrypt data with a maximum chunk size? I am aware of the different modes so that a "raw" block cipher such as AES (ECB) can be used to encrypt more than a single block of data (CBC, OFB, CTR, etc) and modes such as AES-GCM which provide a full AEAD implementation.
When looking at the known limitations for Amazon AWS CloudHSM, there is a maximum data size restriction for AES-GCM (https://docs.aws.amazon.com/cloudhsm/latest/userguide/ki-pkcs11-sdk.html#ki-pkcs11-8):

Issue: Buffers for the C_Encrypt and C_Decrypt API operations cannot exceed 16 KB when using the CKM_AES_GCM mechanism
You cannot use the CKM_AES_GCM mechanism to encrypt data larger than 16 KB
You can use an alternative mechanism such as CKM_AES_CBC or you can divide your data into pieces and encrypt each piece individually. You must manage the division of your data and subsequent encryption. AWS CloudHSM does not perform multipart AES-GCM encryption for you. Note that FIPS requires that the initialization vector (IV) for AES-GCM be generated on the HSM. Therefore, the IV for each piece of your AES-GCM encrypted data will be different.

This question is about how to securely "manage the division of your data and subsequent encryption".
Are there any well-known, documented standards for working with such "big blocks", creating an AEAD mode from a "unit" of AES-GCM which can only encrypt/decrypt 16KB at a time? It would obviously need to protect against truncation of data (if ciphertext was N "big blocks" and only the first M blocks given to decrypt operation, this should fail) and substitution of blocks from a different ciphertext encrypted with the same key should fail too. And are there other potential concerns?
It "feels like" the same class of problem going from ECB → CBC/OFB, but obviously, we want authenticated encryption.
Tweakable block ciphers are used for disk encryption, but the substitution of blocks (same block number/rollback) isn't really protected against there.
Clearly appending the last 128 bits of the ciphertext of the first "big block" to the associated data going into the encryption of the second "big block" would prevent substitution of blocks from another ciphertext, but how to prevent truncation attacks? Would it be sufficient to append the overall data length to the associated data for the first "big block"?
I'd ideally rather not switch to CBC + HMAC (especially as the CloudHSM hash of > 16KB data ends up being done locally!)
But: is this already a solved problem? (Ideally with an IND-CCA2 proof!)

I have a solution that may satisfy you
Splitting the file into parts and chaining is a solution for you. To prevent the truncation we will use the associated data, that same for the first and last.
Assume that you divide the file into $n$ parts each around 16KB ( need adjustments). Encrypt each of them with $\operatorname{AES-GCM}$ with the following additions. Prefix each part before encryption as follows;
tag_0 = ''
borderFlag = random
for i from 1 to n
  if i == 1 or i == n
     #Third parameter is the Associated Data
     (C_i, tag_i) = AES-GCM(key, i:n || tag_i-1 || P_i, borderFlag)
  else
     (C_i, tag_i) = AES-GCM(key, i:n || tag_i-1 || P_i)

prefix each part with the part number as i:n
prefix each part except the first one with the authentication tag of the previous part.

With these, you have now a chain that can be controlled after decryption. You can detect, additions, deletions, and in the final part the truncation. The order is under your control, you can send even without the order. However, you need to check the prefix.
You can also

add the part size, and
add the time of encryption, too if you fear from the replay attack.


Can TweetNaCl box sender's private key be set to "1" without privacy loss? The use case is: I need to encrypt data such that only my own private key can be used to decrypt it, from a machine that only knows my public key.

I'd prefer not to have to create and keep track of a sender key pair in addition to my own key pair. I understand that by setting the sender private key to "1" I will not be able to properly authenticate the sender of the message as being myself, but I am happy to accept that.

Related question 1: If a proper sender key pair was used (using a random private key rather than a "1" private key), can the encrypted message be decrypted using only the sender's private key and knowledge of my public key? Edit: Clarification: The receiver (me) would be told the public key of the sender key pair. The crux of the question was about whether if the encrypted message, the sender private key and my public key were all known, could the message be decrypted without my private key?

Related question 2: Is it OK to use the same key pair for both the sender and recipient when using the Box? This would mean a third party can authenticate the message as being encrypted by me, using only the public key.

It is possible to decrypt the message using either the receiver's private key together with the sender's public key or using the sender's private key together with the receiver's public key. This means that if either private key is public, you end up with a completely broken system.

What you should do instead, is generating an ephemeral key-pair for the sender and sending the public part of it alongside the message. This essentially turns crypto_box into ECIES.

Using the same keypair for both sender and receiver is possible in principle, but silly, because then you end up with symmetric authenticated encryption and you should use the cheaper crypto_secretbox function instead.

Note that you need to know the shared key to verify, which at the same time allows forgeries. So this is typically only a workable solution if you have at most two parties. When you need a party who can verify but not sign, you should use a signature scheme instead. NaCl includes Ed25519.


Computationaly efficient distinguisher for a PRP generator Let $n$ be an integer (the motivating context had $n\approx2^{27}$). All other lowercase variables are non-negative integers less than $n$ (elements of $\mathbb Z_n$). All uppercase variables are vectors of $n$ distinct such elements, or equivalently permutations of $n$ elements.

We want to efficiently distinguish among oracles, with as few queries as possible, in an experiment where an oracle initializes, then at query $j$ outputs a permutation $V_j$, with the additional property that: $\forall i,\forall j,\forall k,\;j\ne k\implies V_j[i]\ne V_k[i]$.

Oracle 1 initializes with an empty memory of earlier outputs, then at each query outputs a random permutation uniformly distributed among those still allowed by the additional property.
Oracle 2 initializes by choosing 3 independent random uniformly distributed permutations $P$, $Q$, $R$; then computes $V_j[i]$ as $R[(P[i]+Q[j])\bmod n]$.

Both oracles meet their duty and can answer $n$ queries. Each of their output, taken in isolation, is indistinguishable from a random permutation. The scheme of oracle 2 and standard Format-Preserving Encryption techniques allow to build a PRP generator meeting the additional property, with $O(\ln n)$ memory, and direct access to any output value.

By a counting argument, for $n>4$, a distinguisher is possible with 3 queries if we disregard efficiency. But how can we build an efficient distinguisher?

Any proposal for an efficiently implementable oracle 3, harder to distinguish from oracle 1?

Additions:

As pointed by David Cary, what's constructed is known as a latin square. Terry Ritter has a literature survey, and discussions on their uses in cryptography. See also Smile Markovski Design of crypto primitives based on quasigroups in Quasigroups and Related Systems, 2015.
Possible application: decide how to lend to participant $i$ out of $n$, on week $j$, sample number $V_j[i]$ out of $n$, in a randomized manner additionally such that no participant gets the same sample twice. In that practice, permutations can be implemented as ciphers using Format Preserving Encryption.
Proof that Oracle 2 has the additional property: If $j\ne k$, then (since $Q$ is a permutation, thus injective) it holds that $Q[j]\ne Q[k]$, thus $((P[i]+Q[j])\bmod n)\ne((P[i]+Q[k])\bmod n)$, thus $R[(P[i]+Q[j])\bmod n]\ne R[(P[i]+Q[k])\bmod n]$, thus $V_j[i]\ne V_k[i]$.

a distinguisher is possible with 3 queries if we disregard efficiency. But how can we build an efficient distinguisher?

I'm not sure exactly what you mean by efficient (since $n \approx 2^{27}$ is a small number), but here is a sketch of a possible constructive attack. I'll let you tell me whether this satisfies your idea of efficiency. I figure that if you have enough time to accept a long ($n$ items) output from the oracle, you have time to do the attack I have in mind. To keep notation cleaner, I won't explicitly write the modular reductions in $R[ \alpha \bmod n ]$.

Query twice, to obtain (assuming oracle #2): $V_1[i] = R[ P[1] + Q[j] ]$ and $V_2[i] = R[ P[2] + Q[j] ]$.
Let $\Delta = P[2] - P[1] \bmod n$, which is unknown to the attacker. Still, if $V_1[i] = R[\alpha]$ then $V_2[i] = R[\alpha + \Delta]$. So the function $F$ that maps all $V_1[i]$ to $V_2[i]$ (which the attacker can compute) is a function that maps all $R[\alpha]$ to $R[\alpha + \Delta]$.

I think the cycle structure of $F$ already leads to an attack! For example, if $n$ is prime then $F$ must be a simple cycle. This is because the sequence $\alpha, \alpha+\Delta, \alpha+2\Delta, \ldots$ generates all numbers mod $n$ before repeating (so $F$ visits all positions in $R$ before repeating). But I would guess that under oracle #1, the attacker would get $F$ to be a random involution. So this already gives an attack with reasonable bias, with just 2 queries.

In general, all cycles in $F$ must have cycle length that divides $n$ (in the presence of oracle #2). Again, this seems much less likely to happen in the presence of oracle #1.

OK, but suppose that reasoning doesn't work out for some reason. In that case, make another query. The attacker can compute a new $F$ again now using $\{V_2,V_3\}$ this time instead of $\{V_1, V_2\}$. If we got lucky, and $P[3]-P[2] = \Delta$ (which happens with probability $1/n$), then the attacker will obtain the same $F$ as before! Again I have not worked out the probabilities, but in the presence of oracle #1 this event seems much less likely than probability $1/n$.


Let $N=p\,q$ be an RSA modulus such that $p>N^\beta$ and $\displaystyle p=\sum_{i=0}^k a_i\,x^i$ such that $\max(a_i)<N^\delta$ and

  $$\delta <\frac{1}{k+1}\bigl(1-(1-\beta)^\frac{k+1}{k}-(k+1)(1-(1-\beta)^\frac{1}{k})(1-\beta)\bigr).$$

Then one can factor $N$ in polynomial time (see here).

In your question $a\ne b$. Let $b=a+c$. So

  $$p=2a^2+2ca+c^2,\ q=2a^2+2c+1.$$

In this case ($q>N^{0.499}$, $k=2$)  we have $a_0=2c+1, a_1=0$ and $a_2=2$ which means that if $2c+1<N^\delta$ then we can factor $N$ in polynomial time.


Collecting entropy: can I use timing of reading as a separate source from the reading itself? I'm implementing an entropy gathering program.

For that I collect 2 bits from two gpio-pins connected to a random source.
I whiten this stream of bits using the von Neumann decorrelation algorithm. Now 2 out of 4 cases I can't use the bits because of that whitening algorithm (e.g. when both bits are 0 or both are 1). The timestamp when I have to discard bits is random.

My question now is: I use the value of the two bits, can I now also use that bit-discard-timestamp as an entropy source? Or are these (the values and the timestamps) correlated? I think they are not neccessarily correlated but I'm not entirely sure.

The values of these timestamps  appear to be determined by two components:

when your code decides to sample the GPIO inputs; and
whether a bit is to be discarded or not.

The first component is not proven to be random (and if you assume it is, you would not need to add complexity to this RNG; just create a second RNG based on CPU execution jitter).

The second component is the same information that you have already used in the whitener.
In other words, if an attacker can make some (partial) predictions about the raw GPIO inputs, then the timestamps are predictable, too.

Please note that the Wikipedia page you linked is not a complete description of the von Neumann algorithm; if you click through to Von Neumann extractor, you see that this algorithm requires that the source is a Bernoulli sequence.
Almost all physical noise sources fail this because their output values are correlated.


Why is there the option to use NIST P-256 in gnupg? I am surely not an expert on the field , but I heared some people say that NIST P-256 is somehow backdoored .

I don't know about the seriousness of this claim . Maybes it is just some conspiracry theory . But if there is some truth about it , then why is it still implemented ? Almost everyone I asked saied it is a bad idea to use P-256 . If true :

Why is it still in GPG ( as of 2017 ) .
Does it have any use ( expect legacy & compartibility ) ?
Is it really broken to the point where it is unsafe to use ( in a professional environment )

Because P-256 is the most used elliptic curve and there are no certain reasons to believe it's insecure.
It's the first standardized curve at the 128 bit security level (which is very popular).

The rumors about its backdoor came from 3 factors:

The Snowden's revelations included a generic claim of the NSA trying to backdoor NIST standardized crypto
DualEC DRBG being a NIST standard actually backdoored by the NSA
Daniel J. Bernstein trying to push for his own curve25519

But there is no backdoor connection between DuelEC DRBG and NIST Curves and we have no idea about how to backdoor an elliptic curve. Bernstein and Lange built a site claiming P-256 is not safe. But it actually boils down to the fact that NIST curves, generated in the 90s, lack some of the fancy features of more modern elliptic curves, as the fancy techniques were not known at the time.

To address your questions directly:

For compatibility reasons, since it's the most used elliptic curve.
Yes of course, e.g. TLS.
No, we believe it's secure.


X.509 CSR: Why does CA remove signature? I just read this article on Wikipedia: Certificate Signing Request

I'm not a PKI or Crypto expert. As I understand, a CSR (certification request) is always signed by the PKCS#10-Request creator.

What I don't understand is why the CA, which receives and processes the CSR, then removes this signature (I mean, without this signature a CA could possibly alter attributes of the CSR).

Why does a CA not just add the necessary attributes to the CSR and sign it with its private key?

If the CA issued something with a CSR as the dominant part of the To-Be-Signed field, it wouldn't be a X.509 certificate and hardly any existing software would know what to do with it. I guess the original CSR could be added as an extension, though.

Therefore, I suppose you are really asking why the X.509 certificate format wasn't originally specified to include the signatures of both the subject and issuer. I guess the reason was that if a PKI application trusts a specific CA, then that application trusts that the CA adds correct information (pairing a subject with a public key) in all of the certificate fields before issuing it. Adding the signature of the subject wouldn't add anything security-wise.


Are there any existing open source implementations of "id-tied" public/private key encryption? I don't quite know how to even ask the question for what I have in mind; but succinctly, I'm looking for some publicly implemented cryptosystem where messages for a user with id U can be sent to U using nothing but a single system-wide public key and knowledge of U.
I have an unusual situation where I've been asked to code support for a massive peer-to-peer computing project with no central server.  There is a central trusted authority that can email people secrets, very slowly, but isn't available at scale or in realtime to resolve issues of identity and authorization during a time when they will all be heavily active talking to each other.
Each entity in the system has a unique identifier U, which we can imagine as a positive integer.  As an abuse of notation, I'll use U to both refer to the entity, and their id.
Rather than try to publish and/or promulgate a very large number of authority-issued certificates tying U to its own public key, which I think is the normal way of doing this, I'm hoping to use a cryptographic communication scheme such that given a shared (ie, known to all entities) public key E, any party can send a private message M to U via some f[U, E](M).
For instance, based on my limited understanding of RSA, the idea is for some master to generate N = p*q, for p and q prime, and then calculate some E and D, E*D == 1 mod phi(N).  Then E may serve as a public key, and D as a private key, via (M**E)**D mod N.  If instead we use E*D*U == 1 mod phi(N), then D*U may be used to encrypt M, and E can be U's private key.  As a bonus, this remains symmetric; U can sign something using D, and anyone else can verify using U*E.
The idea is then that the central authority could pick N, not reveal p or q, promulgate N and E publicly, and email each entity U its private secret D value, by which they would later identify themselves.  From that point forward, any doubter could authenticate an entity claiming to be U, by sending challenges encrypted as E*U, and confirming the entity claiming to be U can decrypt.  (I do not worry about private keys having been compromised.)
So good in theory, but all I've ever heard is that you don't want to ever implement your own crypto library.  Is there anything like the above that already pre-exists as an open-source and battle-tested solution?

What you're looking for is probably Identity-Based Encryption (IBE).
I'm not sure if I've got the terminology correct, but here's a few concept with IBE.
IBE has a key generation center that has a function equivalent to a CA. The key generation center manages a master private key for deriving private keys for decryption users, and a master public key for which encryption users to derive the public keys corresponding to the decryption users.
The rest is pretty much the same with other public-key encryption: encryption users encrypt their messages with the public key of the decryption users and send the ciphertext to them; the decryption users decrypt the message with the private key they've obtained from the key generation center.
It is to be noted that there is the obvious problem of key escrow and difficulty with revoking exposed private keys.
China has developed the SM9 identity-based cryptography standard. An English version is available at IACR. The official version is in Chinese, and is behind paywall, some provincial administration publish free links to Baidu Netdisk file sharing service.
The OpenSSL fork GmSSL mentioned in the comment, has appears to be the most comprehensive implementations of Chinese commercial cryptography standards.


iSeries (AS/400) Database File: password encryption I am helping with a project in which an old software system on an iSeries is having a brand new .NET UI applied to it.  It's going well... except...

In order to allow users to login and maintain compatibility with the existing software installation, we need to figure out what encryption/hashing method the previous vendor was using without access to their source code.

I have a file with an ID and Password column.  The password column appears to contains only 16 characters per record, all binary.

Part of the previous vendor system was written in native green screen on the 400, and part of it was written in Microsoft ASP.Net.

What type of encryption or hash would be:

Used by an AS/400 or iSeries Green Screen app, and
Used by a Microsoft .NET app, and
Output a consistent 16 binary bytes, regardless of input length

Pointers much appreciated.  Thanks!

Wikipedia has a list of cryptographic hash functions, together with their output size. 16 bytes are 128 bits. From the list, the following ones could be candidates:

MD2, MD4, MD5
RIPEMD / RIPEMD-128
HAVAL-128

The most probable one would be MD5, so start with this.


Does this scheme break under a DHP adversary? Consider the following cryptography scheme:

We are given a prime $p$.
Alice wants to send the plaintext $m \pmod p$ to Bob.
Alice chooses $a$ s.t. $\text{gcd}(a,p-1)=1$, and sends Bob, $u = m^a \pmod p$.
Bob chooses $b$ s.t. $\text{gcd}(b,p-1)=1$, and sends Alice, $v = u^b \pmod p$.
Now Alice sends Bob, $w = v^{a^{-1}} \pmod p$, where $a^{-1}$ is the inverse of $a$ modulo $p-1$. Bob now calculates $w^{b^{-1}}$ to get back $m$.

Now I want to know if we have a passive adversary Eve who is able to solve the Diffie-Hellman Problem, gain access to $(u,v,w)$, can she get back $m$.

Now I want to know if we have a passive adversary Eve who is able to
  solve the Diffie-Hellman Problem, gain access to $(u,v,w)$, can she get
  back $m$.

Yes. But first you may want to note that this is the classic three-pass protocol, also called Shamir 3-pass protocol or Massey-Omura protocol which has been shown by Sakurai and Shizuya in 1998 to (sorry for the paywall) in general require a stronger assumption than (C/D)DH for security.

But now for the attack, which is directly derived from the above security relation result. First note that $u=m^a,w=m^b,v=m^{ab}$ and that $p$ is known. So now suppose that you have an oracle $\mathcal O$ that given $(g^a,g^b,g,p)$ returns $g^{ab}$ that is a classic Computational Diffie-Hellman (DDH) Oracle. Now for a second, call $v=g$ and note that $u=g^{b^{-1}}$ and $w=g^{a^{-1}}$. Now feed $(u,w,v,p)$ to the oracle and get $g^{a^{-1}b^{-1}}=(m^{ab})^{a^{-1}b^{-1}}=m$ back.

If you "only" have a Decisional Diffie-Hellman (DDH) oracle, note that you can still guess a message $m$, that is guess the return value of the above CDH oracle if there are only a few possible messages (not excluded in general in cryptography) and thus confirm your guess.


Triple AES-128 encryption with 2 keys We have a system where two devices communicate. Due to restrictions on one of them, we can only use AES-128 (so no AES-256) for encrypting the communication. However, new requirements on these kinds of systems have recently come up where > 200 bits encryption is required for the data communicated between the devices. So we need to adhere to it. So to my question.
Does triple encrypting using AES-128 with two different keys, using K1, K2, K1 (similar to 3DES) make the complexity (for a bruteforce MITM) go from ~2^127 to ~2^255, or are there differences between how DES and AES work that makes it not function like that for AES? If so, what would be the best suggestion for achieving this requirement with only AES-128 at hand.
EDIT
Our current implementation with double encryption is as:
C = ENCk2(ENCk1(P)) and P = DECk1(DECk2(C)). Both ENC and DEC uses aes128 and takes k1/k2, IV and C/P as input. Using MITM we can get DECk2(C) = ENCk1(P) and thus they can brute force in more or less the same time as regular aes128.
Our idea now is to use k1, k2 and IV and generate two session keys: k'1 and k'2. Could use them all as input to sha256 and use the first half of the result as k'1 and the second as k'2. This way the MITM approach would give DECk'2(C) = ENCk'1(P). What an attacker then can do is to start guessing k'1 and k'2 and eventually if the have enought C/P pairs they can figure them out. However, these session keys will be useless for any future communication. So to get the actual keys k1 and k2 they would simply have to guess for all the combinations, making it effectually ~2^2*128. Is this a reasonable line of thought?
And to clarify, perhaps it sounds stupid to use two 16-byte keys + IV in a sha256 to create two new 16-byte keys and then run aes128 twice with those two. However, our hardware limits us to aes128 so that is the reason we have to use it. We do have access to sha256 so then we can do that combination.

The academic and regulatory complexity of triple encryption with two keys is nowhere near that of a cipher with twice the key size. There is a line of thought that 2-key 3DES has like 80-bit or even down to 56-bit security in practice depending on the number of available plaintext/ciphertext pairs, see Chris J. Mitchell: On the security of 2-key triple DES, in IEEE Transactions on Information Theory, 2016, and this quote of the superseded SP 800‑57 Part 1 Rev. 4

Determining the security strength of an algorithm can be nontrivial. (..) For 2TDEA, if exhaustion were the best attack, then the strength of 2TDEA would be 56 × 2 = 112 bits. This appears to be the case if the attacker has only a few matched plain and cipher pairs. However, the security strength of 2TDEA decreases as the number of matched plaintext/ciphertext pairs increases. If the attacker can obtain approximately $2^{40}$ such pairs and has sufficient memory and computational power, then 2TDEA can provide an estimated maximum security strength of about 80 bits; if the attacker has $2^{56}$ plaintext/ciphertext pairs, with significantly more memory and computational power, then the estimated maximum security strength would be about 56 bits.

See this for a partial rationale and more references.
My assessment is that even with DES, attacks against 2-key triple encryption require so much memory and memory accesses (a fair fraction all DRAM ever built and accesses thereof) that they are extremely impractical (see this for more). And that such attacks against AES are pure fiction, for the same reasons, plus the amount of plaintext/ciphertext pairs needed. But facing a regulatory requirement, my assessment won't stand.
The best known generic attack is still essentially Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption, in proceedings of Eurocrypt 1990. Translated to AES-128, it has expected cost over $2^{256-k}$ encryptions when there are $2^k$ blocks of known plaintext.
Triple AES-128 with two keys (in K1/K2/K1 order, perhaps preferably all encryption rather than EDE) is practically safe from meet-in-the-middle attack. In an embedded context, the risks are plain negligible compared to side channels attacks and other non-purely-cryptanalytic methods of key extraction. There remains to convince whoever holds the rubber stamp. Being able to put a reasonable limit on the number of plaintext blocks corresponding to the same key that an adversary could obtain may help (see last section).

Later references that extend to variants of basic triple encryption (with 3 or 2 keys) include Eli Biham's Cryptanalysis of Triple Modes of Operation, in Journal of Cryptology, 1999; and Helena Handschuh and Bart Preneel: On the Security of Double and 2-Key Triple Modes of Operation, in proceedings for FSE 1999.

I advise against double AES-128 (as in the question's current implementation), even with a very limited amount of ciphertext per session key. No reasoning concluding that this gives near 200-bit security can stand competent examination. There is a straightforward attack, requiring only 3 plaintext/ciphertext pairs, feasibly little memory and communication, showing this can't have more than about 130-bit security, by applying techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

What would be the best suggestion for achieving this requirement («the wireless communication needs at least 200-bit encryption») with only AES-128 at hand?

A reasonable option could be:

Use as building block triple AES-128 encryption with two keys, with encryption of 128-bit $X$ under two 128-bit keys $K_1$, $K_2$ per $E_{(K_1,K_2)}(X)\underset{\text{def}}=E_{K_1}(E_{K_2}(E_{K_1}(X)))$
Demonstrate that any 256-bit key for that is used less than $2^{48}$ times, by the sheer time it would take to exceed that limit (if the overall system has no safeguard against multi-target attacks, it might be best to show that all the devices an attacker could use won't reach that $2^{48}$ limit).
Assert that this gives (with some headroom) $256-48>200$ bitof security against key recovery by known cryptanalytic attacks, citing Mitchell confirming earlier analysis by van Oorschot and Wiener, and the NIST advice (see above references). Be aware that an operative word is known, and there are many caveats, including the fact that the last AddRoundKey of an encryption step and the first AddRoundKey of the next reduce to a single one, denting any rationale considering AES-128 as a black box.

If use of the rubber stamp is decided by reason, there is good chance the focus will move to examination of if the key can leak otherwise, if IV can't get reused even facing deliberate attacks attempting to cause that, how the key is drawn and shared, and other real problems.


Homomorphic mapping between elliptic curve point and Zq I'm trying to figure out how to do a mapping between elliptic curve points and Zq without breaking homomorphic properties.
Sorry, I'll write the problem in multiplicative notation because it's easier.
I've got $a = g^bh^r \in \mathbb{G}_1$, where $g$ is a generator of $\mathbb{G}_1$, $h = g^s$ and $r, s, b$ are some values from $Z_q$. I need to have a Pedersen commitment to $g^b$, but since $g^b\in \mathbb{G}_1$ I should map it to $Z_q$ with function $F$ first i.e. $c = G^{F(g^b)}H^R$, where $G,H \in \mathbb{G}_1$ is a commitment key and $R$ is randomly selected from $Z_q$.
The point is, I need to relate $a$ and $c$, so I need to find a mapping function F such that
$G^{F(a)} = G^{F(g^b) \cdot F(h^r)}$.
Do you have any idea how to chose $F$ if $\mathbb{G}_1$ is an elliptic curve? Or if it's even possible? In the finite fields, $\bmod q$ would have worked ($q$ is prime). But with points, I'm not sure what to do.  Maybe homomorphic hash functions would work, not sure.

I think that you can use a bilinear pairing map for the function $F$. This map is defined from $G_1 \times G_2$ to $\mu_n$. This means that $F(x)=e(x,T)$ that $T \in G_2$.
The feature of this map is as:
$e(g^a,T^b)=e(g,T)^{ab}$
$e(g^bh^r,T)=e(g^b,T).e(h^r,T)=F(g^b).F(h^r)$
The amount of $\mu_n$  is in $F_{q^k}^*$. There is a map from $F_{q^k}$ to $F_q$ that is called Trace map. You can find more information about this map at "Pairing for beginners" book or http://www.m-hikari.com/ija/ija-2011/ija-21-24-2011/yadavIJA21-24-2011.pdf


Does an EC signature preserve entropy? Assume I have a perfect source of entropy, which is unknown to me, and is used to generate a private key (also unknown to me, but usable).

If I make a signature with this unknown private key on a constant piece of data (e.g. hash('foo')) and then hash that signature, is the original entropy preserved?

Put another way, does an elliptic curve signature's output probability distribution function resemble that of a perfect hash function (i.e. uniform), or do the outputs concentrate in some other function throughout the space?

Ed25519 is a typical elliptic-curve signature scheme, in a group of large prime order $\ell \approx 2^{252}$ on a curve over the field $\mathbb F_p$ for $p = 2^{255} - 19$.  A secret key is a uniform random 32-byte string; a signature is a 64-byte string encoding a point $R$ on the curve generated by the standard base point, and encoding a scalar $s \in \mathbb Z/\ell\mathbb Z$.

Since for any fixed message $m$ the key-to-signature function is a map from a 32-byte space to a 64-byte space, it can't possibly induce a uniform distribution on the output space.  In fact, for each choice of $R$, of which there are $\ell$ possibilities, there is a unique choice of $s$, so there are only about $2^{252}$ possible signatures—obviously, some secret keys share a common signature on $m$ (but there are so few collisions it doesn't matter in practice).

Further, the signatures are easily distinguishable from uniform random bit strings: the scalar is always less than $\ell$, and the encoding of $R$ contains an encoding of an integer $x$ such that $(1 + x^2)/(1 + (121665/121666) x^2)$ is a quadratic residue modulo $2^{255} - 19$.

Does the output distribution have approximately the same entropy as the uniform distribution on secret keys?  At best it can have about 252 bits of entropy, because there are only about $2^{252}$ possible signatures—but that's pretty close to the 256 bits of entropy possible in a secret key.  At worst it ought not to have substantially less than 128 bits of entropy, because if not, there would be a random algorithm with substantially better probability of success at forgery than, e.g., Pollard's $\rho$ to recover the secret scalar from the public key, at comparable costs.

As it turns out, we choose between these options more or less uniformly at random: the choice of $R$ is determined by a scalar in $\mathbb Z/\ell\mathbb Z$ chosen by a pseudorandom function of the message, keyed by the secret key.  So, to anyone without knowledge of the public key: Yes, the distribution on signatures has about 252 bits of entropy.

This is why you can make a VRF out of it, though you need a little more work like an output filter to get all the properties of a VRF, so that even knowing the public key is not enough to distinguish outputs from uniform random if you don't have the proof of output too.


Two formulas work for this three-pass exchange problem, but I can't figure out why one of them works Problem statement:
"Suppose that users Alice and Bob carry out the 3-pass Diffie-Hellman protocol with p = 101. Suppose that Alice chooses a 1 = 19 and Bob chooses b 1 = 13. If Alice wants to send the secret message m=5 to Bob, show all the messages exchanged between Alice and Bob."
Official solution:
$a_2 = {a_1}^{-1}\bmod(p-1)=79$
$b_2=77$
Alice → Bob: $m^{a_1}\bmod p=37$
Bob → Alice: $80$
Alice → Bob: $56$
Bob obtains $m$ by evaluating $56^{b_2}\bmod p=5$
Solution I made using someone's help (since I can't find very specific information about this three-pass protocol online):
Alice:
$\begin{align}
a_2&={a_1}^{p-2}\bmod(p-1)\\
&=19^{99}\bmod100\\
&=79\end{align}$
Bob:
$\begin{align}
b_2&={b_1}^{p-2}\bmod(p-1)\\
&=13^{99}\bmod100\\
&=77\end{align}$
Alice to Bob #1:
$\begin{align}
m_\text{AliceToBob1}&=m^{a_1}\bmod p\\
&=5^{19}\bmod101\\
&=37\end{align}$
Bob to Alice (#1 - there is no #2):
$\begin{align}
m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\
&=37^{13}\bmod101\\
&=80\end{align}$
Alice to Bob #2:
$\begin{align}
m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\
&=80^7\bmod101\\
&=56\end{align}$
Bob obtains the message as follows:
$\begin{align}
m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\
&=56^{77}\bmod101\\
&=5\end{align}$
My question:
Why does the official solution use $a_2={a_1}^{-1}\bmod(p-1)=79$ instead of $a_2={a_1}^{p-2}\bmod(p-1)=79$, and how can that equivalence in the context of this type of problem be justified? (I say "in the context of this type of problem" because, to my understanding, the two expressions are not always equivalent).
Any input that could help me clarify my confusion would be GREATLY appreciated!
P.S.

$a_1$ is Alice's encryption key
$a_2$ is Alice's decryption key
$b_1$ is Bob's encryption key
$b_2$ is Bob's decryption key

TL;DR: the second method works only for a vanishing proportion of primes $p$.

The question uses the same relation between $a_1$ and $a_2$ as in the Pohlig-Hellman symmetric cipher. In this:

$p$ is a public prime parameter,
the encryption key is a random integer $a_1$ coprime with $p-1$,
the decryption key is an integer $a_2$ such that $a_1\,a_2=k\,(p-1)+1$ for some integer $k$.
encryption is per $m\mapsto c=m^{a_1}\bmod p$, for $m$ in $[0,p)$,
decryption is per $c\mapsto m'=c^{a_2}\bmod p$, and it holds $m'=m$.

Proof: $$\begin{align}
m'&=c^{a_2}\bmod p&&\text{by construction of $m'$}\\
&=(m^{a_1}\bmod p)^{a_2}\bmod p&&\text{since $c=m^{a_1}\bmod p$}\\
&=m^{a_1\,a_2}\bmod p\\
&=m^{k\,(p-1)+1}\bmod p&&\text{by construction of $a_2$}\\
&=m^{(p-1)\,k}\,m^1\bmod p\\
&=(m^{p-1})^k\,m\bmod p\\
&=(m^{p-1}\bmod p)^k\,m\bmod p\\
&=1^k\,m\bmod p&&\text{per Fermat's little theorem}\\
&=m\bmod p\\
&=m&&\text{since $m$ is in $[1,p)$}
\end{align}$$
Note: Fermat's little theorem tells that when $p$ is prime and $m$ is not a multiple of $p$, it holds $m^{p-1}\bmod p=1$.
One suitable integer $a_2$, and the only one in range $[0,p-1)\,$, is ${a_1}^{-1}\bmod(p-1)\,$: the multiplicative inverse of $a_1$ modulo $p-1$. That's what's used in the question's official solution.
The textbook method to compute that multiplicative inverse is the Extended Euclidean algorithm. For practical implementations, I recommend this variant which uses two less variables and never manipulates negative quantities.

The question's other solution differs only by computing the same $a_2$ using a different formula: ${a_1}^{p-2}\bmod(p-1)$. So the question boils down to:
For prime $p>2$, why/when is it that $a^{-1}\bmod(p-1)$ can be computed as $a^{p-2}\bmod(p-1)$ ?
By definition, $a^{-1}\bmod(p-1)$ is the integer $x$ in $[0,p-1)$ with $a\,x\bmod(p-1)=1$. It is defined only when $a$ is coprime with $p-1$. It follows that the question is equivalent to:
For prime $p>2$, why/when is it that $a^{p-1}\bmod(p-1)=1$ for all $a$ coprime to $p-1$?
That's for many $p$ including the question's $p=101$, but not always. The smallest counterexample is $p=11$, $a=3$. Another it $p=103$, $a=5$. It can be verified that using the second method for these $p$ and encryption keys leads to incorrect decryption for most $m$.
These are the primes form A337119 (created for the occasion), starting with
2 3 5 7 13 17 19 37 41 43 61 73 97 101 109 127 157 163 181 193 241 257 313 337 379 401 421 433 487 541 577 601 641 661 673 757 769 881 883 937 1009 1093 1153 1201 1249 1297 1321 1361 1459 1601 1621 1801 1861 1873

These also are the primes $p$ such that $p-1$ is a Novák-Carmichael number A124240; or equivalently the primes $p$ such that $\lambda(p-1)$ divides $p-1$ (where $\lambda$ is the Carmichael function). They quickly thin out as $p$ grows.
Therefore the question's second method is wrong in general, and most primes $p$ of interest for the application at hand (since they mush be large: thousand bits). Likely it came as an incorrect extension of the following fact: when $p$ is prime, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ unless $a$ is a multiple of $p$, which follows from Fermat's little theorem.

In the question's three-pass exchange, $m'$ obtained by Bob in the end is $m$ since
$$\begin{align}
m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\
&={({m_\text{BobToAlice}}^{a_2}\bmod p)}^{b_2}\bmod p\\
&={m_\text{BobToAlice}}^{a_2\,b_2}\bmod p\\
&={({m_\text{AliceToBob1}}^{b_1}\bmod p)}^{a_2\,b_2}\bmod p\\
&={m_\text{AliceToBob1}}^{b_1\,a_2\,b_2}\bmod p\\
&={(m^{a_1}\bmod p)}^{b_1\,a_2\,b_2}\bmod p\\
&=m^{a_1\,b_1\,a_2\,b_2}\bmod p\\
&=m^{(a_1\,b_1)\,(a_2\,b_2)}\bmod p\\
&=(m^{a_1\,a_2}\bmod p)^{b_1\,b_2}\bmod p\\
&=m^{b_1\,b_2}\bmod p\\
&=m
\end{align}$$


Academic breach revealed too late Do you know if is has already happened (since 1980), that someone (academic or not) has "broken" (even in a weak sense) some cryptographic assumption, but has chosen to not first publish and directly attack some security system of the physical world?

I'm really considering the cryptographic/algorithmic level, not a human mistake in which someone didn't use the appropriate standard according to the academic world.

ps: I'm not asking about exploits which are still unknown (it would be an absurd query)

In 2004, Xiaoyun Wang's team first publicly reported collisions in MD5, and in 2007, Marc Stevens, Arjen Lenstra, and Benne de Weger reported a chosen-prefix collision attack on MD5.

Around the same time, the governments of the United States and Israel developed the the Flame malware to sabotage Iran's nuclear program.  Part of the scheme involved forging a Microsoft code-signing certificate using MD5 so that they could sign malicious software without leaving a trail pointing back to themselves.

While studying Flame in 2012, Marc Stevens discovered that the creators of Flame had used an independently developed chosen-prefix attack on MD5 (paywall-free preprint).  We can presume it is independent because if the creators knew about the attack devised by Stevens' group, why would they bother to develop a different way to do the same thing?


PKCS12 password of container and private key As I understand pkcs12 defines a container structure that can hold both a certificate and one or more private keys.

openssl pkcs12 -export -inkey test-key.pem -out test.p12 -name 'Test name' -in test.crt
Enter pass phrase for test-key.pem: KEYPW
Enter Export Password: EXPPW
Verifying - Enter Export Password: EXPPW

Read the p12 file:

openssl pkcs12  -info -in test.p12
Enter Import Password: EXPPW
<outputs certificate, followed by>
PKCS7 Data
Shrouded Keybag: pbeWithSHA1And3-KeyTripleDES-CBC, Iteration 2048
Bag Attributes
    friendlyName: Test name
    localKeyID: 92 C7 F8 7A 23 F4 03 21 0A 3B D6 CE 29 C6 45 C8 1E E0 D2 DD
Key Attributes: <No Attributes>
Enter PEM pass phrase: KEYPW
Verifying - Enter PEM pass phrase: KEYPW
-----BEGIN ENCRYPTED PRIVATE KEY-----
...
-----END ENCRYPTED PRIVATE KEY-----

For the PEM pass phrase I use the one when the private key was created. But why does the output show encrypted private key instead of private key? That's why I entered the pass phrase isn't it?

What makes it even more confusing: passing option -nodes to the openssl command doesn't ask the pass phrase anymore (as expected) but still shows the private key, this time not encrypted anymore. I would expect the opposite: without pass phrase show the encrypted private key, with pass phrase show the unencrypted private key. After all, I can only use the private key when it is not encrypted.

EDIT: hopefully it's easier if I ask smaller questions. Given the created test.p12 as shown above:

Is it correct that EXPPW is the p12 container password and KEYPW is the pass phrase to protect the private key?
Is it possible to get the unencrypted private key with only EXPPW? In other words, is KEYPW not used inside the p12 container?
If the private key is stored encrypted inside the p12 using EXPPW, why does openssl pkcs12  -info -in test.p12 not accept a new pass phrase for outputting the new encrypted private key? If you don't use the original KEYPW it fails with Error outputting keys and certificates.
Is it possible to protect the whole p12 container with password X and the private key with password Y? So that if you know X, you can still get the public certificate yet you can't get the private key?

Now that the Qs have been clarified (and yes this isn't really about cryptography, and would be more appropriate on security.SX = application of crypto in systems or superuser = use of programs including security programs like OpenSSL or maybe even stackoverflow)

  ... Given the example ... 1. Is it correct that EXPPW is the p12 container password and KEYPW is the pass phrase to protect the private key?

No. KEYPW was the passphrase on the PEM-format input file. If the input privatekey file is unencrypted (which OpenSSL supports, although it in many situations it is insecure and thus a Bad Idea) the input password is not even prompted for. It is not used in the P12; only EXPPW is used for the P12.

  Is it possible to get the unencrypted private key with only EXPPW? In other words, is KEYPW not used inside the p12 container?

Yes. That's exactly what your openssl pkcs12 -nodes (with EXPPW) does. (Again OpenSSL supports it, but the caveat above about using an unencrypted privatekey file applies.)

  If the private key is stored encrypted inside the p12 using EXPPW, why does openssl pkcs12  -info -in test.p12 not accept a new pass phrase for outputting the new encrypted private key? If you don't use the original KEYPW it fails with Error outputting keys and certificates

Try again. It should work (to use a different password on the output of the 'parse') and does for me. Note the new password must be at least 4 characters, a limit that OpenSSL does not enforce in other places, although even 4 is not nearly enough for actual security. (That area -- length and other characteristics of a good password -- is ontopic for crypto.SX and has been discussed numerous times at length.)

  Is it possible to protect the whole p12 container with password X and the private key with password Y? So that if you know X, you can still get the public certificate yet you can't get the private key?

Yes, or nearly. There are actually three operations normally done:

the whole P12 is MACed using a password,
the 'shrouded keybag' is encrypted using a password, and usually a strong or at least strong-ish algorithm like 3DES
the 'cert bag' is (separately) encrypted using a password, and usually a deliberately weak algorithm namely RC2-40

(The latter two are shown by the -info option on the parse subcommand, although you
omitted part from your post.)

OpenSSL commandline does not support using different passwords for 2 and 3, but it does support changing the algorithm(s) and in particular it supports making the certbag unencrypted which allows access to it without the password, using -certpbe NONE. This is a crossdupe of https://superuser.com/questions/1507936/openssl-encrypts-public-key-after-conversion-to-pfx . Commandline does support the -twopass option to make the MAC password for 1 different from 3 (or 2 and 3), or you can simply ignore the password for 1 on reading using -nomacver.

Caveat: software other than OpenSSL may not handle PKCS12 files with other than the usual algorithm settings and a single password.

  my goal is to understand the pkcs12 structure.

You might want to look directly at the file structure with asn1parse, rather than the interpretation given by the pkcs12 command. See an example at
https://stackoverflow.com/questions/51242721/openssl-debugging-how-to-dump-intermediate-asn-1-inside-openssl


Shake256 Infinity Collision Two diferents inputs can have the same output in $Shake256$ for every output size (for example, $Shake256(input_1, \ell) = Shake256(input_2,\ell)$ for every $\ell$)?

Two diferents inputs can have the same output in $Shake256$ for every output size (for example, $Shake256(input_1, \ell) = Shake256(input_2,\ell)$ for every $\ell$)?

Yes, it is possible.  In fact, it is inevitable that some such pair $input_1, input_2$ exists.
Shake256 maps the input into a 1600 bit state, and then converts this state into an arbitrarily long sequence.  If two different inputs map to the same state, then they're produce the same sequence (independent of how much output you ask for).
In particular, if we consider all 1601 bit inputs, there must be (by the pigeon hole principle) two different inputs that map to the same state; that observation gives us an upper bound on the required size of $input_1, input_2$.  Almost certainly much smaller pairs exist.
Now, finding such a pair, well, that's a different (and far more difficult) problem...


Are there any good examples of Contemporary Mechanical Cryptography? Are there secure mechanical cryptosystems in use today? Not necessarily alphabetic either, ie digital but mechanical?

While we obviously don't know who is using what and where, we know the U.S. phased out their last mechanical systems (the KL-7) in the 1980s.  The M-94 (Jefferson Cipher Disk) was a clever and simple implementation of a polyalphabetic substitution cipher, so there's no reason it couldn't be used today.  But the U.S. Army stopped issuing them during WW-II.

Note that none of the known mechanical cipher machines would stand up to the kind of brute force cryptanalytic attack available on today's personal computers.

A cryptanalysis of the M-209 (Hagelin machine) written by Dennis Ritchie, James Reeds, and Robert Morris, went unpublished in 1978 as they were informed by the NSA that the principles of their attack were still in use in cryptosystems of the day.  Dennis Ritchie still isn't publishing it.


What is the fastest elliptic curve operation f(P) in affine coordinates such that f^n(P)=P only if n is large? I'm working with the affine representations of points of the Secp256k1 elliptic curve (from Bitcoin).

I've read many papers that show that computing some functions, like $f(P)=3P$ can be computed faster than the standard way. Other papers say that with some pre-computation, the field inversion can be amortized if $F^1(P) ... F^k(P)$ must be computed.

I need the fastest function $F(P)$ that, when applied to the last result iteratively, generates a sequences of points whose average period is large (I don't need any proof, it can be just large in practice).
To be fast I suppose it should be computed without field inversions. I don't mind to pre-compute some values.

For example, it could be $F(P) = 1.5P+4Q$ for a fixed $Q$. It doesn't matter which function it is, because I need it to generate random points in the curve. The probability distribution doesn't matter either.
(notation: $1.5$ is the point halving of $3P$)

Motivation: Solutions to this problem may be helpful for generating vanity addresses.

With your curve, you can use the Gallant-Lambert-Vanstone (GLV) method to answer your question. Indeed, the equation of your curve is: $$y^2=x^3+7.$$ Since $p$ is congruent to $1$ modulo $3$, there are cube roots of unity modulo $p$. Let:
$$j=55594575648329892869085402983802832744385952214688224221778511981742606582254 \pmod{p}.$$ You can check that $j^3\equiv 1\pmod{p}$. The complex multiplication by $j$ sends $P=(X_P,Y_P)$ to $P'=(jX_P,Y_P)$.

Moreover, $P'=J\cdot P,$ where $$J=37718080363155996902926221483475020450927657555482586988616620542887997980018.$$

Finally, multiplication by $J-1$ can be performed efficiently (one application of complex multiplication and one addition) and has high order. Don't use $J+1$: it has order $6$.

EDIT
 $J^3$ is $1$ modulo the order of the curve, while $j^3$ is $1$ mod $p$.

This endomorphism of the curve is the projection of the complex multiplication of the curve $y^2=x^3+7$ over the rationals to the curve reduced mod $p$. This is why is is usually called the complex multiplication.

All in all, this gives a reasonably fast way to generate random looking multiples of $P$.

The full GLV method is much more than that since it speeds up multiplication by an arbitrary constant compared to regular double and add, but its basic idea relies on having an endomorphism that can be computed quickly.


Does SHA-1 meet the strict avalanche criterion? Does SHA-1 meet the strict avalanche criterion? I've been looking for a paper to cite on this, but haven't found one.

It's something that seems to be easy to check (in "On the Design of S-Boxes", Webster & Tavares lay out how it can be done), so it is surprising to not find a paper on it.  Has it been put down as a small result in some other paper?  Or has the SAC been discarded as a useful metric?  Or have I somehow missed the relevant paper (accept my apologies if so!)?  Any pointers would be gratefully appreciated.

Edit: is Hash function balance and its impact on birthday attacks relevant?  Is the "balance" metric simply a better/different way of expressing the SAC?

There is a paper "SHA-1 and the Strict Avalanche Criterion."

From the abstract:

  This work provides a working definition of the SAC, describes an experimental methodology that can be used to statistically evaluate whether a cryptographic hash meets the SAC, and uses this to investigate the degree to which compression function of the SHA-1 hash meets the SAC. The results (P<0.01) are heartening: SHA-1 closely tracks the SAC after the first 24 rounds, and demonstrates excellent properties of confusion and diffusion throughout.