Is there any serious discussion about using blinding intermediaries in digital currency scenarios? A digital currency system like Lucre (OpenTransaction) creates a coin by a mint blind signing the output of a hash function, which the payer then unblinds and pairs with the input to the has function.

In this way, the coins themselves cannot be used to identify the payer; however, the payee and the mint are free to correlate their information about the payer's identity through side channel information, such as IP address and rebuild the payer's identity.  There are afaik two orthogonal partial solutions to this problem :

The payer may reduce side channel information, say by using Tor, not giving one party a real name, etc.  This potentially offers good security, but imposes a great burden upon the payer.
The protocol and payer may instead insist upon an intermediary between the payee and the mint, i.e. the payer blinds the coin using his intermediary's daily public key, the payee blinds the coin using the mint's key, and the intermediary unblinds the coin before delivering it to the mint.  This prevents the mint form ever reestablishing that the payer held that particular coin.

I could imagine a few uses for #2 but I haven't seen much discussion about it.  Is it interesting?

It may be an interesting avenue to explore. I've read the highlight reel of the digital cash literature but I do not know it well enough to know how well these issues have been addressed.

A few things to consider for #2:

In a quick read of Lucre, it seems that the payee does no verification before passing the coin onto the mint. It seems, if the mint has a known public key, that the process may be improved if the payee can do some basic verification (is it actually signed?) before asking the mint if it has been double spent. Your solution #2 would make any payee verification difficult since it is working with a blinded value.
As I understand it, the payee submits the coin for verification but does not consider the transaction complete until they hear back from the mint that the coin is valid. For this reason, the verification must be realtime. This creates a timing attack problem (the same basic one that exists in all proxy systems including Tor) where a corrupt payee sends the coin at time $t_0$ and the corrupt mint receives the coin from the intermediary at $t_0 + \Delta t$. If $\Delta t$ is small and not many transactions happen within the window, the mint and payee can still trace the coin through the intermediary. In particular, the payee could adjust when they send the coin if it would help the attack. There are countermeasures in the Tor and mix network literature on this.
The #2 attack is made worst if there are more than one intermediary and users choose whichever they trust. The payee knows which intermediary the blinded coin is sent to and the mint knows which one it has received a coin from, so this information reduces the anonymity set of the possible origins of a given coin. It is now the set of coins per intermediary sent within a small window of time, and this is more likely to be a singleton set. Perhaps there is an alternate architecture where the user sends the coin to the intermediary instead of the payee, however be mindful of the next consideration.
Since the mint and payee are no longer directly communicating with each other, they can not mutually authenticate. How does the mint establish who the payee is? The mint has to credit the amount to the payee. It seems the user would have to sign a transaction saying to credit the coin to the payee, and only the user can do this because this singed transaction itself would also have to be blinded (alongside the coin). In this case, it seems the payee can be cut out of the first part of the protocol. The user sends the coin and transaction through the intermediary to the mint, the mint verifies everything and then credits the payee, then the mint informs the payee the amount that has been credited, and the payee releases the purchased goods to the user.

Anyways, the fact that there are maybe a few challenges with using an intermediary actually makes the question more interesting, rather than less interesting. It is no longer a simple clean-cut solution; it requires some thought and would make a better contribution if you could iron out all the issues.


OpenSSL - What Data Is Used To Create A Certificate's Digital Signature? I am coming up-to-speed on OpenSSL certificates.  In all of my research I see where "data" is hashed to create a hash value that is used as the basis for a certificate's digital signature. This hash value is encrypted using the sender's private key, at which point it becomes the certificate's digital signature.

What "data" is hashed?  Is it specific information from the certificate?  Is it all certificate information?  Does the the data include the certificate's public key?  Or, is the data some random number or string that is generated by OpenSSL when the certificate is created?  I'm assuming that the "data" is certificate data since one of the functions of PKI is to validate that the contents of a message (in this case a certificate) haven't changed since the message was created.

This applies over the entire certificate data. Per RFC 5280, section 4.1.1.3:

   The signatureValue field contains a digital signature computed upon
   the ASN.1 DER encoded tbsCertificate.  The ASN.1 DER encoded
   tbsCertificate is used as the input to the signature function.  This
   signature value is encoded as a BIT STRING and included in the
   signature field.  The details of this process are specified for each
   of the algorithms listed in [RFC3279], [RFC4055], and [RFC4491].

   By generating this signature, a CA certifies the validity of the
   information in the tbsCertificate field.  In particular, the CA
   certifies the binding between the public key material and the subject
   of the certificate.

So every single field of the certificate is part of the signature (except of course for the signature). This is to guarantee that no element of it was tampered with (there is pretty much no field in the certificate that is not important. Even if one were, it's easier to require everything to be signed regardless of the use).

About public keys:

subject public key is definitely included. Note the last sentence I quoted. This is one of the critical parts of the certificate: who it was issued to.
issuer public key is not included in the certificate and therefore is not part of the signature. Instead, the subject field of the issuer is included as well as the Certificate Authority Key ID which can be found in the issuer's certificate under Subject Key ID. This is used in path building.


Using a one-time pad with a block cipher The one-time pad is often described with a simple XOR cipher.

This is nice for showing the theoretical strengths of the one-time pad, but not so great in real-world scenarios where key reuse is a danger.

So, is it feasible to use an n-bit block cipher with an n-bit key to replace the XOR operation (which itself is a 1-bit block cipher with a 1-bit key)?

So the encryption operation becomes

for each pBlock is n bits of plaintext
     take kBlock as the corresponding n bits of the key
     encrypt pBlock with kBlock as key using the block cipher and the result is cBlock
     append cBlock to the ciphertext

Decryption is the same.

Am I correct that this will make it more resistant (but not fully) to key reuse and known plaintext attacks than using the simple XOR? Or did I add a big vulnerability into the scheme?

Well, no.

What you are describing is ECB mode of operation. ECB mode of operation is insecure as repeats of plaintext blocks leads to repeats of ciphertext blocks. This is a leak of information so it breaks confidentiality. So even if you would leak less information because of key reuse, you would still leak information if it happens.

Furthermore it is possible to find out if a key is (likely) correct by validating a ciphertext block against partial information within plaintext blocks. To that breaks the perfect secrecy provided by a One Time Pad.

I'll try and explain that last section further.

Note that there aren't $2^n$ possible permutations, there are $2^n!$ possible permutations. To be perfectly secure you should allow each one of them (with the same probability, no less).

That would mean that for any sensible $n$ the key size would grow out of proportion. Furthermore, you would have to have a cipher that would map all those keys to exactly one permutation, something that is not true for usual block ciphers.

So even if you have a key of n bits with m < n bits of known plaintext then it is likely that you can tell with a probability higher than $0.5$ if it is the correct one or not, breaking perfect secrecy for the remaining n - m bits.


Decrypting files with an unknown method but a known result I am assuming there is a very simple way of working this out by brute force, but I am not sure if there is a better way.

I have a file of data that I wish to get (my data, generated by a machine). This file is encrypted by some method that I have no details of (and the company has folded).
However, as well as the encrypted file I have an unencrypted file by the same machine for a different date range. Looking at the file it is easy to see that the encryption is in blocks of 8 bytes, as most of the header is zeros, so where the new file says 00 00 00 00 00 00 00 00 the old file says B5 B4 24 EF 45 BC 68 C5.

So I know what 8 0s are like, and 8 ffs and a few other items. I also know it is a block as a an area that is 7 0s and one digit is completely different.

Do I just assume it is RSA or something and make a brute force on the password?

No, don't assume it is RSA as it likely isn't based on the information.

You already have a possible block length. 64 bit block length could mean DES (or one of its variants such as 3DES) or blowfish. Another possibilty is that there was an 8 byte pad used in repeated XOR fashion. I'm sure there are other possible block ciphers with 8 byte block size.

Next I would look for repeated blocks. Anywhere in the plaintext file where the data is the same, see if the ciphertext data is the same. This would suggest either repeated XOR or ECB mode. If this is not the case, other modes (CBC, etc) are likely. The absence of repeated cipher blocks (where there are duplicate plaintext blocks) would seem to eliminate repeated XOR.

If that is all the information you have, your next step would be to brute force. If repeated XOR is a possibility, and since you know the header is 00 00 ..., the ciphertext would be your XOR pad. So try that and see if the decrypted file looks as you would expect.

Otherwise, I'd start with DES as it is probably the more popular of the two ciphers.


3DES security when K1=K3 I am mainly looking for security on 2-key $\operatorname{3DES}$ implementation where $K_1=K_3$.
How hard or easy is it to crack $\operatorname{3DES}$ when $K_1=K_3$?

TL;DR: the official $2^{80}$-something theoretical security of 2-Key Triple DES w.r.t. key search¹ is still practically good enough in most of its many uses in 2020; but security authorities rightly do not condone it in new applications.

"3DES when $K_1=K_3$" is formally known as TDEA keying option 2 in FIPS 46-3 or 2TDEA or 2-Key Triple DES. It is still very common in current (2020) commercial applications, including Smart Cards, and its security is thus an important practical concern.
It's vulnerability to key search depends on many things, the most decisive being:

both components $K_1$ and $K_2$ of the key have been chosen independently and uniformly at random (we assume that, and thus disregard attacks on key derivation);
how many matching plaintext/ciphertext pairs are available for the attack;
whether it is targeted a single key $(K_1,K_2)$, or any of many such key (and then how many, and if the available plaintext/ciphertext pairs share a common block).

Study case 1: single key, little plaintext
With two or three plaintext/ciphertext pairs enciphered under a single key, the best attack I know is brute force², with expected success probability $\approx2^{-112}\,n$ after work² totally dominated by $n$ DES encryptions with incremental keys.
By October 2020, the sizable fraction of the global resources devoted to bitcoin mining is reportedly achieving $144\cdot10^{18}\,\text{SHA256d}/s$, where one SHA256d is two SHA-256 compressions, each doing 64 rounds on a 256-bit state. DES does 16 rounds on a 64-bit state, so I'll count $2\,\frac{64}{16}\,\frac{256}{64}=2^5$ DES for one SHA256d, which gets us to $2^{\approx97}$ DES/year. Thus after a year, the probability of success is $2^{\approx-15}$ or ≈0.003%.
Conclusion: there are few applications where this attack should get a rational decision maker bothered for the near future.
Study case 2: many keys, little chosen plaintext for each
On another extreme, if $m=2^{28}$ (270 million) Smart Cards have been issued with random keys, and adversaries having infected card loading devices managed to obtain ciphertext blocks for the same two or three plaintext blocks encrypted under each key, then they can mount a multi-target attack. It finds an expected $\approx2^{-112}\,n\,m$ keys after work² dominated by $2\,n$ DES operations and $n$ searches of a 64-bit result among a table of $m$ values using roughly $64\,m\,$bits for the portion that needs to be high speed.
Compared to the previous attack, the number of DES operations for a certain probability is reduced by a factor of $m/2$ (down to complexity of $2^{85}$ DES operations), and the bottleneck becomes search.
I can vaguely imagine an IC where a 2GiB table fits, subdivided into $\approx2^{8}$ sub-tables each searched at $2^{28}\,$Hz (3.7ns latency). Throw $2^{24}$ (17 million) such ICs at the task and after a year ($2^{\approx25}\,$s ), it's expected to find $2^{\approx8+28+24+25+28-112}\approx2$ keys, and the probability of getting a least one is high.
Further increasing $m$ may reduce the cost, but much slower than proportionally. With foreseeable technology, it seems the sweet spot is when the table to search fits one IC, and when we increase $m$ we must use a denser memory technology, thus slower for the best technologies available at a given time.
Conclusion: recovery of a few of the many keys can't be summarily dismissed as impossible for well-founded adversaries that design, build and operate custom ASICs. But in a system with the capacity to blacklist cards, that's most likely an acceptable risk.
Study case 3: single key, much plaintext
Here, "much" means up to $2^{\approx32}$ blocks ($32\,$GiB). Even approaching that threshold is not advisable for any 64-bit block cipher anyway. Attacks combining a lot of RAM (like textbook Meet-in-the-Middle for 2DES) and iterated collision search (the practical variant of MitM for 2DES, wich uses little RAM and can be bade "embarrassingly parallel") can reduce the number of DES operations considerably compared to case 1. The standard reference is Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption (in proceedings of Eurocrypt 1990).
Circa 2012 I tried to determine if that attack had become feasible. My tentative conclusion was that a then unreasonable amount of RAM was needed to get below $2^{90}$ DES operations, even if we ignore a lot of costs, including for communication between the RAM nodes.
This is reexamined by Chris J. Mitchell, On the Security of 2-Key Triple DES (in IEEE Transactions on Information Theory, 2016 and arXiv, 2016). It brings an improvement: for chosen plaintext, using the DES complementation property halves the cost. As in van Oorschot and Wiener, more plaintext does not help much, and the bottleneck is the cost of memory and accesses to it (much like in 2).
My opinion is that this attack still remains (2020) extremely hypothetical, harder than that of case 2 with current technology; but we would have to analyses factors beyond RAM availability (like energy for their operation, and communication costs as tentatively explored in this) to conclusively repel the attack as infeasible in the next 5 years for well-funded adversaries; and I know no such analysis.
Study case 4: many keys, significant plaintext for each
That could be the situation e.g. in a VPN that changes session key regularly, and only limited known plaintext is available for each key.
The above Mitchell reference argues that the total amount of ciphertext necessary for a given probability of finding at least one of the many keys at a given cost is largely independent of how many keys are targeted. As far as I see, we're back to case 3 and it's hardness if we follow Mitchell, and case 2 if we do not.

I did not consider cryptanalytic attacks like linear or differential cryptanalysis, because I've not found that they are applicable to 3DES, even with 2 keys; but that's far from a proof that they are not!

Official status
NIST has deprecated use of DES including all keying variants of 3DES/TDEA. It still mentions that 2TDEA used to offer 80-bit security. The superseded SP 800-57 Part 1 Rev. 4 gave more details:

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.

An official French regulation (Référentiel Général de Sécurité version 2.0, annexe B1) explicitly recommends against 2-key TDES for use envisioned after 2020, with mention of insufficient block size and vulnerability to known-plaintext attack of complexity $2^{80}$ (resp. $2^{100}\,$) for $2^{40}$ (resp. $2^{20}\,$) plaintext/ciphertext pairs.  Their $2^{80}$ something is roughly in line with Mitchell's conclusions.
NIST's measure of complexity appears to be DES encryptions, and I guess the same for the French source. Neither gives a reference to the attacks considered.

¹ as opposed to key extraction from physical devices holding keys, thru the like of exploitation of implementation errors, fault injection, micro-probing, DPA, DFA…; and attacks on the mode of operation that do not target key recovery, perhaps by exploiting the 64-bit block size.

² That "embarrassingly parallel" attack can go:

obtain two distinct plaintext/ciphertext pairs $P_0/C_0$ and $P_1/C_1$
for each of $2^{56}$ keys $K_1$

compute $A=E(K_1,P_0)$ and $B=D(K_1,C_0)$
for each of $2^{56}$ keys $K_2$

if $E(K_2,B)=A$ (occurs for one computation out of $\approx2^{64}$ )

if $E(K_2,D(K_1,C_1))=E(K_1,P_1)$, output $(K_1,K_2)$

The first output (if any) is most likely the key, with a probability of the contrary $\approx2^{-16}$ on plausible heuristic grounds.


A website that identifies an RNG from its output This happened during a discussion of RNG entropy, and the difficulty of verifying the level of entropy in a long sequence of bits (e.g. a private key.)

A colleague of mine told me about a website that, given a sufficient quantity of output from an PRNG, had been able to deduce which application the PRNG was from. As an example, he told me that he had submitted data from OpenSSL's random number generator and the website had identified "Open SSL" as the source.

This was about three years ago. He encountered the website at a previous company he worked at.

I can't find this site by googling, and my colleague may not be able to find the URL (he's looking it up.) Not surprisingly, I'm very worried if the output from supposedly-cryptographically-secure-PRNGs is vulnerable to a distinguisher attack with trivial complexity!

If anyone here recognises this website, could they please post an answer containing its URL?

A colleague of mine told me about a website that, given a sufficient quantity of output from an PRNG, had been able to deduce which application the PRNG was from.

As you correctly identified this would present an immediate and probably devastating attack to any cryptographic PRNG as it indeed would allow you to easily distinguish a random string from a PRNG output, something cryptographers try to make impossible efficiently.

However, there might be some truth to the story. Here are the two cases I know of where it would be possible:

The website identifies the output to be from the infamous OpenSSL Debian bug.
The site is given an RSA public key and can tell which implementation produced it as the prime-search strategies vary a bit in a secure way between different libraries. This was presented at Usenix Security 2016 (PDF) and perhaps someone converted this into a website.


Hashing a uuidv4 + time to create a unique id First, I am no crypto expert although I am doing the MOOC.

I have an item which has as id: uuidv4

When I create this item:

I create a new uuidv4
check if it already exists
and if not, I store it in the db.

Now this item can be deleted. So lets say that there could be a conversation 'about' this item. And in that conversation is stored the id of the-just-deleted-item. After the item has been deleted, the conversation is not automatically deleted.
If some user now creates a new item (get new uuidv4) and passes the check-if-already-exists test, it could still reference an already existent conversation. THAT'S WRONG

To battle this, I was thinking of appending a UNIX timestamp (in secs) to the uuidv4 when it is created, then hash that, then store the hash. so the same uuid later on will have a different timestamp, and thus be different!

Question(s):
Which hashing algorithm to use?

Or maybe just concatenate the uuidv4 + UNIX timestamp (in secs)?

You know, technically an uuidv4 is already designed to be unique. That's what it's for. In other words, the probability of you generating the same uuidv4 is supposed to be virtually zero. So why are you checking for duplicates?

The whole point of uuid's is to make sure nobody ever gets assigned the same one even if they all do their own separate thing without going through a central authority which keeps track of where each uuid is. So if you're using an uuid, it's questionable to expect that you will ever generate the same one twice.

Which leads me to believe that you haven't correctly identified your actual need. Do you need to bind this uuid of the item to the conversation somehow? If so, you want something similar to a deterministic hash of the item name, which will make sure that if you ever delete, say, "Item57", and then eventually add "Item57" back, you will still know which conversations are associated with this item (and no other). This way every item references only the conversations concerning it, even after they are deleted.

If you just need uniqueness and don't want (or care about) dangling references then uuidv4 already provides that, you should trust it rather than cobbling together your own scheme. If you don't trust proven algorithms, how can you ever trust your own?

Briefly, what are you trying to battle against, exactly, from a high level point of view?


x509 Certificate Signature I've got a question about the signature of a CA.

As I understand, the CA takes the public key of the client and signs it with
his own private key by using "md5WithRSAEncryption" (like explained here: http://en.wikipedia.org/wiki/X.509#Sample_X.509_certificates".
What does it mean exactly?
Can you give me a formal explanation for better understanding?
Does the CA use both algorithms?

Second question
In the first certificate example from wikipedia in section 'Subject Public Key Info:' there is defined the 'RSA Public Key:'
Is that the plain public key which the CA got from the Client or is there something done on it?

Please give more hints for better understanding if you can.

Thanks before

Signing with "md5WithRSAEncryption" means CA calculates MD5 hash to get an integer first and apply his private RSA key next to produce the signature. A DER-encoded string is the input to the hash. Client (Subject in X.509 parlance) data, including public key, is described with ASN.1 language, "to be signed" part of specification. Certificate extensions (v3) are also included into "to be signed".

"Plain" public key, as received from client, is encoded according to X.509 specifications. See ASN.1 description at PKCS 10, "certificate request".

Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile
Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile


counter to indicate hotp count I was trying to figure out how HOTP kept from wrapping over, when I saw this explanation of how it works, by Thomas Pornin [source]:

  The intended scenario is the following: the client has a handheld device which outputs the
  successive passwords, one new password per button-press. The client may press the button a
  few times between two login attempts. The server "bets" that the client will not press the
  button more than, say, 100 times before attempting to log in again: so the server uses $w \leq100$. If you let your 3-year-old nephew play with your HOTP device a whole afternoon, chances are that it will be too much desynchronized, and login will not work any longer.

Assuming the user didn't have to input the OTP value or counter number(lets assume its something akin to a yubikey), what would be the downside of having the device feed the site with what the counter number is on, before giving the resulting OTP to check against?

Your question starts from an assumption that often isn't valid.  You write:

  Assuming the user didn't have to input the OTP value or counter number

but in fact, for cost reasons, often these devices don't haven't any way to send the counter number to the server; the user would have to input it.

If the counter value is actually based upon the time, so it doesn't need to be sent, then yes, the quote from Thomas Pornin doesn't apply.  For those kinds of tokens, yes, the server can use the time and we don't have the issue with it getting desynchronized if you press the button 100 times.  The server does still need to make sure that the token's time approximately matches the server's time, and that the number only increases (to avoid replay attacks).


What is Reverse Trapdoor Function? In wikipedia on Digital_signature:

  but rather, the message to be signed is first hashed to produce a
  short digest, that is then padded to larger width comparable to N,
  then signed with the reverse trapdoor function

I could not find the term reverse trapdoor function neither by web search not here on SE, what does it mean?

Definition of trapdoor function from Wikipedia;

A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor".

The reverse trapdoor function is just the reverse usage of it.
Normally, for encryption, we want the encryption easy but the decryption is hard without the key. Consider the RSA encryption.
In the signature, we want the reverse, hard to produce without the key - i.e. forgery, but easy to verify.  Consider the RSA signature.

Consider RSA, given $(n,e)$ public key then $E(m) = m^e$ is trapdoor (actually trapdoor permutation) without the private key.
Forward usage: With the public key and $m$ it is easy to compute the $E(m)$, encrypt. But given $c = E(m)$ and public key it is difficult to compute $E^{-1}(c)$ without the private key.
Reverse usage: Given $(n,d)$ private key then $S(m) = m^d$ is the reverse trapdoor. Given $s = S(m)$ and public key it is easy to verify but difficult to compute $S^{-1}(c)$ without the private key.

Note 1: usually people confuse RSA decryption with the RSA signature. No, it is not. For proper RSA encryption, you need PKCS#1.5 or OAEP padding schemes and for signature you need RSA-PSS padding scheme. And in practice, it is not advised to use the same key for both.
Note 2: As pointed by Tylo, actually Bleichenbacher's attacks and its variations (DROWN, ROBOT) showed that the RSA PKCS#1.5 padding is not secure.
Note 3: PKCS#1 v1.5 padding has no formal security proof but RSA AOEP has.


Software interface for KDF and PBKDF? I'm working on an implementation of Krawczyk and Eronen HKDF from RFC 5869. From Krawczyk's original paper, he identifies four inputs to a KDF in Cryptographic Extraction and Key Derivation: The HKDF Scheme. The four inputs are:

base keying material (secret or seed)
context information (binds security parameters)
public salt (optional, provides uniqueness)
length of derived key

I'm trying to reconcile the differences between a KDF (used in, say, a Diffie-Hellman based scheme) and a PBKDF (used for, say, digesting a password into key material) to provide a common software interface. I think the difference are:

KDFs generally enjoy higher entropy seeds, and don't use an iteration count
PBKDFs generally lack higher entropy seeds, and use an iteration count to help with some attacks. Sometimes they use a purpose byte, sometimes they use a salt, etc. (The purpose byte seems to be a specialization of contextual information).

Adding PBKDF to the requirements, I think the list becomes:

base keying material (secret or seed)
context information (binds security parameters)
public salt (optional, provides uniqueness)
length of derived key (optional)
iteration count

I want to ensure that the security parameters are well represented in a extensible way, which leads me to two questions:

Is it fair to say a PBKDF is a specialization of KDF?
Will a software interface that support the five parameters above be sufficient?

(Sorry about wandering into software design. I need the help and expertise of folks who understand the cryptography, and not the [purely] software architects).

Is it fair to say a PBKDF is a specialization of KDF?

Sure. A PBKDF is a KDF, just one that uses a password/passphrase as the entropy source.

OTOH, a KBKDF (key-based KDF, if you want to call it that) is also a specialization of a KDF. A different specialization, which is why it may not be a good idea to treat them as a single thing.

  Will a software interface that support the five parameters above be sufficient?

There are a couple of common parameters that are missing:

Many password hashing functions have a second cost parameter indicating how much memory will be used. (E.g. scrypt, most of those from the currently running Password Hashing Competition.)
Another relatively common parameter is a pepper. You can just include it as part of the salt if needed, but then the same is true for your context information parameter.

I also don't think your parameters, even with the above additions, are the best way to define such an interface.

For one, I don't think a salt should ever be left out, so I don't see why it should be optional.

For another, there is a significant difference in how a key derivation function is normally used, compared to how a password hash is used:

With a key derivation function, you are going to need a key of a certain size as output.
With a password hash it is useful to get an opaque return value that can be passed as the only additional parameter into a verification routine:

verify(password, combined_hash)

(Cf. Modular Crypt Format.)

This way the iteration count, salt, etc. is easily stored with the hash, and different hashed can have different parameters, allowing one to upgrade the strength with time as attackers' computational power increases.


Simplified AES S-box multiplication - calculation error I have a problem to calculate the S-box in S-AES. The affine transformation is defined:

I read that it is a normal matrix multiplication. I chose the bits $0101$ and built the inverse $1011$. $b_0$ is my least significant bit. So I define my inverse $b_0 = 1$, $b_1 = 1$, $b_2 = 0$, $b_3 = 1$.

Then I start to multiply with the first row:

$$(1*b_0) + (0*b_1) + (1*b_2) + (1*b_3) +(1) =\\ (1*1)+(0*1)+(0*0)+(1*1) + (1) =\\ 1+1+1 =\\ 1$$

The second row : $$(1*1)+(1*1)+(0*0)+(1*1) + (0) =\\ 1+1+1 =\\ 1$$ and that is wrong. The result is $0001$.

So where is my mistake?

Endianness strikes again! Quoting the S-AES paper

  we associate the nibble $b_0 b_1 b_2 b_3$ with the polynomial $b_0x^3+b_1x^2+b_2x+b_3$.

The nibble $0101$ maps to $b_0=0$, $b_1=1$, $b_2=0$, $b_3=1$ associated to the polynomial $x^2+1$. Its inverse modulo $x^4+x+1$ is $x^3+x+1$, associated to the nibble $1011$ that maps to$b_0=1$, $b_1=0$, $b_2=1$, $b_3=1$ rather than$b_0=1$, $b_1=1$, $b_2=0$, $b_3=1$ in the question.

Note: this comment voices puzzlement that coefficients of a polynomial are numbered differently (and in reverse order) than the corresponding powers of $x$. There are two reasons for this convention:

Technical: it is common in telecoms to both receive bits sequentially with their number initially unknown (naturally numbering them starting from 0 onward), and perform on-the-fly a Cyclic Redundancy Check by division of the polynomial associated to the message by a shorter fixed-size polynomial. Polynomial division is performed starting from the high-order coefficient of the dividend, hence the convention. Analogy: finding $d\bmod 97$ by performing Euclidean division while given integer $d$ of initially unknown magnitude as a stream of decimal digits in usual reading order.
Precedent: the block cipher DES numbered bits from left to right starting from 1 onward in inputs, output, and internal variables including S-box-index (on page marked 14 of FIPS 46-3 the numbering of bits grows as their weight in base 2 decreases, and doing otherwise would have required shuffle of the S-boxes). Time and reason largely shifted practice towards numbering from 0 in fresh cryptographic work, but the numbering direction sticks. Modern practice is to number things according to binary weight up to some size, then the other way around (the threshold is often octet for the external form of large integers as used in RSA and ECC; in FIPS 180 it is 32-bit in SHA-256, 64-bit in SHA-512, with an exception in the padding).


hyperelliptic curve scalar multiplication F = GF(next_primt(2^80))
x = F['x'].gen()
f = x^5 + x^3 + 1
H = HyperellipticCurve(f, 0)
J = H.jacobian()(F)
P = H.lift_x(F(3))
D = J(P)             # divisor

Is D the divisor? And can it be multiplied by a random integer to generate a secure parameter like the one used with elliptic curves?

And if this is correct, why is ECC time = 13.2 milliseconds, but HECC time = 185 milliseconds?

Is D the divisor? And can it be multiplied by a random integer to generate a secure parameter like the one used with elliptic curves?

Well...you're asking if the discrete logarithm problem can apply to hyperelliptic curves. The answer is yes. But it's a bit more complicated than for the elliptic curve case. This is a great introduction. I sketch out some details below if you want to take the plunge.

The problem is more complicated to formulate for hyperelliptic curves than for elliptic curves. This is because there is no natural group structure for points on the hyperelliptic curves like there are for elliptic curves. (Note that elliptic curves are a special case of hyperelliptic curves, with genus $g=1$.) However, you can formulate the discrete log problem over a group associated with hyperelliptic curve, called the Jacobian group. You have Jacobians in your Sage code, for example.

To understand Jacobians, you have to understand divisors. A divisor is a formal sum over points on the curve: $D := \sum_{P \in \mathcal{C}} c_P [P]$, where $c_P \in \mathbb{Z}$ and the number of nonzero $c_P$ is finite. By "formal sum", I mean bookkeeping. For example, if $P,Q,R$ are points on a curve, then a divisor may be $D = 2[P] + 4[Q] - 7[R]$. That's it.

You can also have divisors over functions. If a zero is a point where a function vanishes and a pole is a point where a function is undefined, then the divisor of a function $div(f) $ is a way of bookkeeping the relative number of zeroes and poles. For example, if $f(x) = \frac{x-a}{x-b}$, then you have a zero and a pole, and could write the divisor as $D = 1[a] - 1[b]$. (Notice poles are negative in the sum.) A divisor is called a principal divisor if it's equal to the divisor of a rational function. The set of principal divisors $Prin(\mathcal{C})$ forms a group.

The degree of a divisor is the sum of the divisor's coefficients. So in the above example, the degree is $1 - 1 = 0$. The set of divisors of degree zero is important and is called $Div^0(\mathcal{C})$. Since rational functions have as many zeroes as poles, they all have degree zero, which means $Prin(\mathcal{C}) \subset Div^0(\mathcal{C})$.

Finally, we can define the Jacobian group as the quotient group  $Div^0(\mathcal{C}) /Prin(\mathcal{C})$. You can "add" two divisors using Cantor's theorem. Now that we have elements and addition, we can talk about the hyperelliptic curve discrete log problem:

Given a hyperelliptic curve $\mathcal{C}$ of genus $g$, two divisors $D_1$ and $D_2$, both in the Jacobian group, with $D_2$ in the subgroup generated by $D_1$, and the order $q$ of $D_1$, find the scalar $s$ (modulo $q$) such that $D_2 = s\cdot D_1$.

It's harder to visualize, but the Wikipedia article has an example. It looks like you are using some Sage code. I haven't used Sage for this, but this documentation talks about how to do "divisor addition" (using Cantor's theorem on the Mumford representation of divisors). They reference another great introduction.


Selecting an appropriate key for HMAC I'm writing a symmetric encryption scheme for a product that I'm working on which doesn't store sensitive data (license validation data). I'd still rather do it right and reuse it than do it wrong and make something useless.

I have some concerns about HMAC after encrypting and making sure that the HMAC actually serves its purpose. I read this article on avoiding mcrypt vs OpenSSL which pretty adamently promotes the concept of MAC-after-encryption.

Now here is my current process for encrypting the data (you can imagine how the decryption side works):

//PHP7
function encrypt($message, $key){
  $method = 'aes-256-cbc';

  if (mb_strlen($key, '8bit') !== 32) {
    throw new Exception("Needs a 256-bit key");
  }

  $ivsize = openssl_cipher_iv_length($method);
  $iv = random_bytes($ivsize);

  $ciphertext = openssl_encrypt(
    $message,
    $method,
    $key,
    OPENSSL_RAW_DATA,
    $iv
  );

  $hmac = hash_hmac('sha256', $iv . $ciphertext, $iv, true);

  return base64_encode($hmac . $iv . $ciphertext);
}

My concern is that the HMAC key is the same as the IV which is prepended to the data stream. In theory, anybody attempting to break this can figure out that the first 32 bytes are the HMAC, the second 16 bytes are the IV, and the rest is the cipher text, since it seems to be an industry standard. Somebody running a Vaudenay Attack could potentially modify the cipher text and regenerate the HMAC easily using the IV.

So would it be more secure to use the AES key for the HMAC since that is not passed or stored? Or maybe something different like the XOR of the AES key and the IV? Or a completely new key using another round of random_bytes()?

Should the MAC key be treated just like the AES key in terms of secrecy?

This post titled "Why Can't I use the same key for encryption and MAC" suggests that it is not appropriate to do for AES-CBC mode, lets assume that AES-CBC-MAC is not available to me (because the decryption side is a different library and language).

Sending the MAC key with the message pretty much negates the point of a MAC, since anyone can modify the message and regenerate a new MAC using the key. Nothing theoretical with that. You might as well omit the MAC entirely.(1)

So yes, the MAC key should be considered a secret, just like the encryption key.

I think the answer in the question you linked pretty much answers the rest of your questions: Yes, you should use independent keys for the encryption and the MAC, because otherwise you run the risk of subtle interactions between the algorithms foiling your scheme. Though in the case of AES and HMAC-SHA256 you'll likely get away with it, but it would still be good hygiene to use distinct keys. Run your master key through a KDF (or just a strong hash like SHA-512) to get separate keys for the encryption and the MAC.

Of course you could generate the MAC key from random bytes given by your system's RNG, but you'd still need to transfer the key to the other end. That would need to be done similarly to how the encryption key is transmitted, not at the per-message logic which you've shown.

(1) Though an unkeyed hash would still serve to detect accidental corruption.


Is Diffie Hellman key exchange based on one-way function or trapdoor function? I have a question for my information security lab, which I am not able to find online.
As the title says, is Diffie Hellman key exchange based on a one-way or a trapdoor function?

In case of RSA I would say it is based on a trapdoor function, since it is hard to factorize the modulo, if you don't know p and q.

Is Diffie Hellman also based on a trapdoor function, since it is hard to reverse the discrete logarithm, if you don't know the secret key?

No, the mathematical problem that is used for Diffie-Hellman is the Diffie-Hellman problem or DHP which is different from the trapdoor function that is behind RSA.

One way functions are for instance cryptographically secure hash functions.


Strength of Hash obtained by XOR of parts of SHA3 I create a hash with SHA3-384. I split the resulting array into two. The first called head has the first 320 bits and the second called tail  has the last 64 bits.

Next, I XOR  head and tail. Which in fact means I XOR the last 64 bits of head with tail. This gives me a new hash of length 320.

The question is how is this resulting hash in terms of collision resistance compared to SHA-256 on one side and SHA-384 on the other side.

My goal is to produce a 320-bits hash. Is there a better way you would go about this?

Truncating a hash does reduce the collision resistance. Mixing in an independent string does not.

$$
\text{random thing} \oplus \text{independent thing} \to \text{random thing}\\
\text{random thing} \oplus \text{independent random thing} \to \text{random thing}
$$

Truncating hashes is common and the reduction is relative to the bits lost. The truncated $\text{sha3}_{384[320]}$ should be stronger than $\text{sha2}_{256}$ and is weaker than $\text{sha3}_{384}$.

I recommend that you do not try to mix in the truncated $64$-bits.


Are there comprehensive alternatives to RSA? If we wished to, is there a comprehensive alternative to RSA?

I say comprehensive as I wonder if there is one which does both encryption and digital signature like RSA?

If not, simply what alternatives are there?

Yes.

You can use RSA for both signatures and encryption, but you need different algorithms for that. E.g. RSAES-OAEP is an encryption algorithm, while RSASS-PSS is a signature algorithm. Both use the RSA cryptosystem and have similar keys, but otherwise the algorithms differ. Textbook RSA has the "same" algorithm for both but is not secure.

There are alternatives where something similar is possible. Elliptic curves are the most practical and widely used option. The same curve can be used for encryption (e.g. ECIES) and signatures (e.g. ECDSA).

Note that using the same key-pair for both encryption and signatures is not necessarily secure, even if the algorithms allow it. So in practice you could use completely different algorithms for signatures and encryption without too much overhead, but you may save e.g. code size by using related algorithms for both. And you may rely on fewer hardness assumptions that way.


ECDHE generates a key pair? From my understanding of the basic Diffie Hellman scheme, the final result is 1 key that is known to both sides and now can be used for symmetric encryption.

From my understanding of ECDHE-RSA scheme which provides PFS, a pair of ephemeral DH keys are created instead of another RSA pair because of computational considerations.

I can't seem to understand how does the process of ECDHE-RSA which creates a DH public + private key pair is similar to the basic Diffie Hellman scheme which results on 1 key, and not 2.

Is the actual basic Diffie Hellman scheme as described with simply with colors in wikipedia is being used in SSL/TLS?

I'm confused by the issue as it seems that the ECDHE-RSA process is actually an "RSA-RSA" process, only that the generation of keys is by DH (?)?

All Diffie-Hellman (including EC) uses two keypairs and produces one shared secret. The colors in the wikipedia article are only a metaphor; the actual process for original DH, now retronymed 'integer' or 'finite-field' DH if necessary to distinguish, uses a sufficiently large generated subgroup of the multiplicative group of integers modulo a prime (in current practice, a 2048-bit prime), while Elliptic-Curve DH (ECDH) uses an elliptic curve satisfying certain criteria, or to be precise the group generated on the curve by a base point.

Ephemeral is only(!) about timing. DH requires the parties each have a keypair (private and public key) at the time of the key agreement operation (for TLS, the handshake that creates a session). It cares nothing about how long before the operation these keys were created, or how long after the operation they are retained. You can create one DH keypair and use it all your life assuming it is strong enough and you keep it secure, or you can create a new keypair every millisecond, and the DH algorithms (integer or EC) work exactly the same either way.

However, in practice to use a keypair longer than a few minutes or hours at most you normally need to store it somewhere, because computers occasionally fail or must be shutdown for various reasons. There is always some risk a stored keypair can be compromised, although a wide variety of methods can be and are used to try to prevent compromise.

Ephemeral mode of (EC)DH does not store the keypairs and thus avoids this risk. They are created (at each end) immediately before doing the key agreement and discarded (securely!) immediately after. This provides Perfect Forward Secrecy, or just Forward Secrecy. Unless you have a bug like Heartbleed, or other side channel such as shared-VM interaction, that allows an adversary to get that information during the brief period it is in memory.

Yes ephemeral DH and ECDH are used in TLS, including but not limited to DHE-RSA and ECDSA-RSA which are authenticated (signed) with RSA as @SEJPM noted, instead of ephemeral RSA, mostly because generating RSA keys is more costly and in particular usually too costly to do at session initiation, while it is very practical to generate RSA keys used on a long-term basis (typically a year or more) for authentication.


How can I simulate and measure brute force hacking using RSA? I want to implement brute force hacking using RSA. How can I simulate and measure time duration? What software (or software-based simulator) would be needed?

Firstly, I assume we are talking about classical computers

Implementing a brute force attack on a RSA may not be the most sensible thing, unless of course the security parameter of your target system is small.. (160 bit numbers! )

Even then you may not want to implement a brute force here.. try using Fermat's Factoring or  Pollards $\rho$ method.

If you just want to measure time try to do a more theoretical research, i.e. use the time take per multiplication op. and the no. of operations your computer can perform in a sec to determine exactly how long will it take you to brute force a $n-$bit security.

To sum it up, YOU CANNOT BRUTE FORCE THE (properly implemented) MODERN DAY RSA (~4096 bit numbers) even if you use all computers in your state.


AES-CBC with zero IV and a unique first block Is it safe to generate the IV for AES-CBC as the following?

It's like the real IV is all zeros.
The first block of data will be a low-entropy but unique data.
Once the first block is encrypted, the ciphertext will look like a random sequence of bytes that will automatically serve as IV of the second block

This would allow to save space since we don't have to store a "real" IV in addition to the low-entropy data of the first block that we need to store anyway.

Is it safe to to this thing?

If the IV is all zeroes, then you basically have ECB for the first block.  Basically you're proposing to use this first block's encryption as the IV for the second block.  You're implying that the first block will always be unique, but low entropy, which sounds like a counter or time stamp.  There are attacks when the IV is predictable, and while this is a step away from that, it may still be useful information for an attacker.


Which of those functions are PRFs? Assume that $F: \{0,1 \}^n \rightarrow \{0,1 \}^n$ is PRF. Examine if the following functions are PRFs:
$$
\begin{align}
1. \, F_1(k,x) &= F(k,x) \oplus x \\
2. \, F_2(k,x) &= F\left(F(k,0^n), x\right) \\
3. \, F_3(k,x) &= F\left(F(k,0^n), x\right)|| F(k,x)
\end{align}
$$
where $||$ denotes concatenation.

Attempt:
For $1.$ a standard distinguisher would be: $x_1 \oplus x_2 == y_1 \oplus y_2$, where $x_1, x_2$ are two inputs and $y_1, y_2$ are their outputs respectively. So $F_1$ is not a PRF.
For $2.$ I believe that $F(k,0^n) = k'$ acts as a key, so $F_2(k',x) = F(k',x)$ should still be a PRF.
For $3.$ I would say that the concatenation of two PRFs would still be a PRF, since you combine two pseudorandom outputs together to yield $F_3$'s output.
Can you verify my results?

Since @fgrieu was interested in question 2, I'm going to break with site policy and give a full answer for that part, even though this is almost certainly homework.
Theorem.
Let $F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a PRF. Then, $F_2 : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, defined as
$$F_2(k,x) := F(F(k,0^n),x)$$
is also a PRF.
Before we give a formal proof, let's build some intuition why this should be the case. Note that the inner invocation of $F$ is not on some part of the input, but instead on a constant (i.e., $0^n$). This means that once we fix the key $k$, the key used by the outer invocation of $F$ for all evaluations of $F_2$ is a fixed key $k' := F(k,0^n)$. Since $k$ is not used elsewhere in the construction, $k'$ should, by the security of the underlying PRF, be indistinguishable from a uniformly random key $k''$, as long as $k$ is chosen uniformly at random. This would mean than an oracle evaluating $F_2(k,\cdot)$ and an oracle evaluating $F(k,\cdot)$ should in fact be indistinguishable. Since $F(k,\cdot)$ is already known to be indistinguishable from a uniformly chosen random function $f(\cdot)$ and indistinguishablity (in the asymptotic sense) is transitive, it would follow that $F_2$ must also be a PRF.
So let's formalize this intuition.
Proof. Let $A$ be an arbitrary PPT algorithm with
$$\Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|=\epsilon(n).$$
We are looking to give a negligible upper bound for $\epsilon$. To do this we will prove a series of claims.
Claim 1. $\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$
Consider the following adversary $B$ against the PRF security of $F$.
Upon input $1^n$ and given access to an oracle, $B$ queries $0^n$ to the oracle an receives back a value $k'$. It then invokes $A$ on input $1^n$. Whenever $A$ sends a query $x$ to its oracle, $B$ responds by computing $y:=F(k',x)$. Eventually, $A$ will output a bit $b$ which $B$ also outputs.
It is easy to see that $$\Pr_k[B^{F(k,\cdot)}(1^n)=1] = \Pr_k[A^{F(F(k,0^n),\cdot)}(1^n)=1]$$ and $$\Pr_f[B^{f(\cdot)}(1^n)=1] = \Pr_f[A^{F(f(0^n),\cdot)}(1^n)=1].$$
Further, since $F$ is a secure PRF, it must hold that
$$\Bigl|\Pr_k[B^{F(k,\cdot)}(1^n)=1]-\Pr_f[B^{f(\cdot)}(1^n)=1]\Bigr|\leq \mathsf{negl}(n)$$
and the claim follows.
Claim 2. $\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] = \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]$
To see that this is the case, it is easiest to think of $f$ as being lazily sampled when queried. Since $f$ is only ever invoked on $0^n$, sampling $f$ is equivalent to simply sampling $f(0^n)$ once as a uniformly random value $k\in \{0,1\}$, which is identical to the right hand side.
Claim 3. $\Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$
This claim is in fact just a restatement of the assumption that $F$ is a PRF and thus follows trivially.
Using the triangle inequality, we can conclude
\begin{align}
  \epsilon(n) =&\quad \Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|\\
  \leq&\quad\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr|\\
&+ \Bigl|\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] - \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]\Bigr|\\
&+ \Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr|\\
&\leq 2\cdot\mathsf{negl}(n)
\end{align}
and the theorem statement immediately follows.$\tag*{$\square$}$


Encryption algorithms and the "One-Time pad" I am not well versed in the field but I believe I know the basics.

All encryption algorithms that I know of utilize direct data manipulation to encrypt a message (string of bits) such as shifting, cycling, etc. in specific patterns utilizing the encryption key.

Is there any algorithm that instead of touching the data-to-be-encrypted in any way instead generates a secure one time pad using a reasonably short key?

I suppose technically in this scenario you would call the key a seed for a pseudo-random number generator.

So my question is this, does such a generator exist in a secure form and with an algorithm that can turn a phrase into a key or just generate such a key.

If there is such a generator I suppose you will point out the weakness of a one time pad on changing/multiple data, but suppose it isn't a concern due to pad use markers or simply because there is no other data or changes.

There is an entire class of ciphers that do exactly this. They're called stream ciphers. At their most basic, they pretend to be a one-time pad. You give them a small key and they generate a stream of seemingly random bits. You then XOR these bits with your plain-text to make ciphertext.

You can add bells and whistles to this basic behaviour but what I've described is the essence of the stream-cipher.

The most famous of these stream ciphers is probably RC4. If you ever used SSL at all then you will have used this steam cipher.

Equally, if you've ever used a mobile phone you've probably had your voice traffic "protected" with A5/1.

There are people who are experts in just this area of cipher design.

There's nothing more to say really other than that this is a well established branch of cryptography with a very well developed body of research and many fielded designs.


Are cryptographies based on bitwise operations considered secure? I have recently been reading (and writing) a lot off ECC on top of TCP via pythons sockets. I've stubbled across a couple of things mentioning how elliptical curves are more secure with the same key length as other algorithms. Just to humor myself I made a simple associate/communicative function and used it to with a 'base point' and played around making some public, private, and shared keys. The operation I was using is as follows:

"(x, y) => x | y"

I based my process around having a base point as a domain parameter (call it 'g') and creating a private key 'd' with its public key partner 'dg' (found by plugging d and g into the function above). Then one can encrypt by picking a new private key 'n' and using 'ndg' or 'dng' as the shared secret. Just slap 'ng' at the front of the message and the decrypter can go ahead and use their secret key to go from 'ng' to 'dng' which can be used as a shared secret for something like Rabbit. All these public and private keys can just be integers of some length.

What is insecure in this system?

If I understood correctly (using uppercase notation for public keys and $\lor$ instead of "|" to indicate the logical or) your scheme is:

Public Domain $g \in \mathbb{Z}$
Alice Private Key $a \in \mathbb{Z}$
Alice Public Key $A=a \lor g$
Bob Private Key $b \in \mathbb{Z}$
Bob Public Key $B=b \lor g$

Shared Secret = $a \lor B = b \lor A = a \lor b \lor g$

Then I would say your system is insecure as an attacker can recover the shared secret using only the public keys as:

Shared Secret = $A \lor B = (a \lor g) \lor (b \lor g) = a \lor b \lor g$
(Given the property that $x \lor x = x$)


What is the difference between PIR and OT? A private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved.
An oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of the potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred.

As the Wikipedia said, PIR is a weaker version of 1-out-of-n oblivious transfer, but I do not really know why is a weaker version.

In general, PIR mainly guarantees that the server should not know which item is retrieved, as does OT. However, in contrast to PIR, OT also guarantees that the user should not learn information about other items.

----update based on Lindell's comment----

Another difference between PIR and OT is the requirement of sublinear communication cost for PIR. Note that PIR with linear communication is trivial and hence not interesting as the server can simply send the whole database to the user. However, this does not work for OT because sending the whole database reveals all other database items to the user.


Is salt required in Argon2 I have software that generates user login keys randomly, we store the argon2 hash on our server. The generated keys are very strong, 64 pRNG hex characters. Right now we just use an empty string as the salting parameter in argon2 since we figure salt is not even needed since our passwords themselves are not prone to a dictionary attack.
I don't know much about the internals of how argon2 works though... is there some internal reason to generate a random salt in which argon2 becomes insecure without it... or is it just an optional parameter provided for protecting against common strings being hashed, but can be ignored if none of your strings will be common?

If you use a fixed salt all your passwords can be attacked concurrently.
Though argon2 is designed to be slow and thus hard to do a dictionary attack I see no reason to give your attacker a speedup factor of the number of users.
This will obviously be on top of any other advantages the attacker may have(e.g superior hardware or cryptographical advancement).
On a system with 100 users, using a salt gives you a 100x advantage over an
attacker doing a dictionary attack on the hashed password. You can use this to slow her down or alternatively tune the security parameter to make your legitimate hashing faster and less resource intensive.
Using a salt is an easy win.


What is meant by the probability distribution of a verifier? I'm having trouble understanding the role of probability distributions in the definitions of computational/statistical indistinguishability, especially in the definition of zero-knowledge.
From A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm:

An interactive proof is called perfect zero-knowledge if the probability distribution generated by any probabilistic polynomial-time verifier interacting with the prover on input a
theorem $\phi$, can be generated by another probabilistic polynomial time machine which only gets $\phi$ as input (and interacts with nobody!).

This I would understand if "probability distribution" were replaced by "computable function", such that zero-knowledge means that we cannot compute anything beyond what we can compute anyway after the proof because we did not gain new knowledge besides the truth of the theorem. But why "probability distribution"? And what is the subject of distribution here, the random coin tosses of prover and verifier? Because that would not make sense to me.
From The Knowledge Complexity of Interactive Proof Systems:

Consider a pair x, y in QNR and say that A follows the protocol. Can B obtain any additional knowledge? For the moment, assume that B follows the protocol. B "sees" [$\{b_i\}$, $\alpha$, $\{ w_i\}$, $\{c_i\}$] distributed according to a particular distribution. Without any help from a prover, we can quickly generate a random string according to this distribution: just choose $\{b_i\}$ and $\alpha$ randomly, and then compute $\{w_i\}$ from them; then compute $c_i = b_i$ for each $i$.

Here we have a very concrete example of the "subject of distribution" I mentioned above, namely [$\{b_i\}$, $\alpha$, $\{w_i\}$, $\{c_i\}$]. However, I don't quite get the usefulness of that.
Is it just that the verifier, does not know anything for certain, so he looks sort of through a "probability-distribution lens" to make sense of the world?

A probability distribution is how the verifier's knowledge of the unknown value is summarised. This idea is usually easier to grasp for Bayesian statisticians than classical ones.
Suppose that the unknown value $x$ is just a $n$-bit string, a verifier might start out with no information about $x$ and thinks all $2^n$ possible values are equally likely: a uniform probability distribution on $2^n$ values. After an interaction with the prover, the verifier might say "I now know that $x$ is not one of these $k$ values" and their knowledge could be summarised as a uniform distribution on $2^n-k$ values. Or they might say "I now know that $x$ has even Hamming weight", giving a uniform distribution on $2^{n-1}$. They might say that "I am now 90% sure that $x$ has even Hamming weight" and give a two-valued histogram distribution with probability $1.8/2^{n}$ on even Hamming weight values and $0.2/2^n$ on odd Hamming weight values. They might even say "I think that interpreted as an integer $x$ is (truncated) Poisson distributed with mean $\mu$". All of these are different types of knowledge that the verifier might infer about $x$ based on their interactions with the prover.
The important thing about a zero-knowledge proof is that whatever the verifier infers from their interactions with the prover, they could generate the same information and inferences on their own.


How to securely store and validate a 4-digit PIN used on a mobile device? I want to be able to securely (1) create and (2) validate a PIN, typed by a user primarily in a mobile app. There is no 'typical' password, although there is another 2nd factor.

The starting point would be something based on OWASP standards for passwords:

get salt_1 (send to user device)
hash PIN on device using salt_1 and bcrypt
send over HTTPS to backend
get salt_2
hash the received hash using salt_2 and bcrypt
save resulting hash or compare against previously saved hash

Now, this scenario obviously has a limited viability and robustness due to low PIN entropy (4 digits), so typical approach for passwords requires at least some alterations.

My ideas for additional security measures would be:

salts should be treated as secret and stored securely and separately from hashed PINs (as in this answer )? If yes, sending it, even briefly, to user device is compromising this security a lot? Can I do something more here?
limiting retrials of PIN validation appears to be more crucial than with passwords

Is there any other approach or enhancements to existing approach that I should consider?

There are, obviously, at least 3 perspectives: backend leak, MITM and device leak and the last one is the one I am least confident with, but maybe I should leave this to the user if he "chooses" to compromise his device security?

PIN check is bound to rely on trusted device or security by obscurity.

If a 4-digit Personal Identification Number is stored and validated in an device (possibly composite, like combination of server and mobile device) of known construction, and an adversary acquires/extracts all the data stored in the device, including the (possibly encrypted or hashed) PIN and try counter, then that adversary is able to find the PIN with at most 10000 times the effort/energy it takes to try a wrong value of the PIN. Argument: the adversary simulates what the device does to test a candidate PIN, and when wrong just fires another simulation. The multiple PINs can be tried in parallel, thus the time it takes can be down to a single PIN try.

All ways around move the PIN and counter into a trusted device: security IC (Smart Card, Subscriber Identity Module, Trusted Platform Module...) for offline solution, or online server. The appropriate logic for a PIN check in a trusted device is:

if the error counter is below a threshold (typically 3)

increase the error counter in non-volatile memory, and if that succeeds

compare the proposed PIN to the stored PIN, and if it matches

reset the error counter to 0
authorize access until some event, such as a reset or a timer elapsing.

Historical section: Implementers sometime got that wrong. My deceased friend and Smart Card inventor Roland Moreno can be seen (audio in French) demoing a device that finds the PIN code of a bank card as was used in France in the early 1990s or slightly earlier. That particular one:

Used PROM (implemented as UV-EPROM with protection against UV erase) for the PIN error counter, and relied on a separate VPP power contact to program that, allowing an adversary to inhibit the writing by supplying too low a voltage.
Used an array of bits for the counter, with a scheme maximizing the number of PIN presentations considering the physical impossibility to erase a bit: the position of the programmed bit told if the count was reset or incremented, with the counter determined by the pattern on the frontier at the left of the right zone of unprogrammed bits (* = programmed, . not programmed, x = any)

xxxxxx**................ 0
xxxxxx**.*.............. 1
xxxxxx**.*.*............ 2
xxxxxx**.*.*.*.......... 3

Towards the goal of choosing which bit to program, performed the PIN comparison before the increment.
Leaked the result of that comparison thru a side channel. It happened that a byte characteristic of the PIN comparison was in a RAM buffer also used for communication, and readable after a warm reset that did not clear that byte, using a standard command.

I was told that a different model of card using comparable technology, and immune to this exact attack, still allowed to recover the result of PIN comparison before counter update, thru some timing attack.

Practical section:

  Can I do something more ?

Two main cases (with the question about the second):

The PIN needs to be checked locally on the mobile device: crypto mostly does not help!

Offload the PIN check security functionality to the mobile device OS, which is in a better position than an application programmer to use the underlying hardware. If there's no such explicit service, it might still be possible to replace PIN authentication by the mere unlocking of the device, leaving it to the user to decide if that's with a PIN or otherwise.
OR use security by obscurity in the mobile app.
OR/AND, under the plausible assumption that (D)RAM is harder for an adversary to read than something more permanent, and if there is some form of more secure user login (even a password), and it is acceptable that the user makes use of that at each boot: hold the PIN hash encrypted/protected under that more secure user login credentials when on disk, and decipher it in RAM on boot. The makes the PIN as secure as the other login form when the user device is powered down to the point that (D)RAM content is lost.

The PIN only needs to be checked in an online scenario: crypto helps but is not a silver bullet!

Have the mobile device carefully validate the remote server in charge of PIN check and counter maintenance, e.g. thru a pinned TLS certificate, and send the PIN keyed-in by the user in a TLS tunnel with the server for checking. Additionally sending messages (e.g. PIN or a derivative) encrypted with another server public key devoted to PIN, along a server challenge preventing replay of the cryptogram, is theoretically redundant with TLS, but complicates attack. An alternative (with little if any benefit) is a PAKE such as SRP (tags: pake srp) to send and store the PIN on the server.
AND, use a long-term secret on the mobile side, if it is functionally possible that a user resetting the device or using a different one prevents login with PIN only. That can help protect from Denial of Service (where an attacker submits wrong PIN to prevent the rightful user to log-in), and make it impossible to find the actual PIN from server-side data (which is useful when a user reuses the same PIN on multiple servers).
A possibility is that the user device draws and stores a fresh ECC private key and a random secret integer $S\in[0\ldots9999]$ each time the PIN is changed, with public key and Randomized Identification Number $\text{RIN}=(S+\text{PIN})\bmod10000$ stored on the server side. At each login the server sends a random challenge $C$, the device asks the PIN and gets $\text{PIN}'$, the device computes $\text{RIN}'=(S+\text{PIN}')\bmod10000$ and sends $\operatorname{Sign}(C\mathbin\|\text{RIN}')\mathbin\|\text{RIN}'$ encrypted to the server (see 2.1 for how). The server extracts the signature and $\text{RIN}'$, increments the transaction counter only if the signature matches that of $C\mathbin\|\text{RIN}'$, then in the affirmative tests if $\text{RIN}'=\text{RIN}$ to decide if the counter should be reset and access granted.
Note: that provides functionality similar to that other answer with 35 bytes per user stored on the server side instead of several kilobytes.
AND take computer security precautions so that the server does not leak its storage, which (combined with long-term secret on the mobile side if any) is bound to allow finding the PIN with little effort for a competent attacker (the mere ability to roll back a backup of the PIN state counters unavoidably makes such attack possible). Precautions must include trustworthy server administrators with robust access control to administration, encrypted offline backups (preferably with a public-key), and can include making the PIN/RIN check and counter update in or with the help of a security device such as an HSM or security IC.
AND it can only help that the PIN or RIN of 2.1 is stored (on disk/NVM/(D)RAM/database..) on the server side as a password should be: hashed with a purposely-slow memory-hard entropy-stretching hash such as Argon2, together with random salt (stored along the hash) and semi-secret pepper, and ample security parameters (number of iterations, RAM). But again, that's not an even passable protection, for 10000 attempts is sure to allow to find the PIN (for who knows hash, salt and pepper, and long-term secret on the mobile side if any).


Is the following s-box more linear or more non-linear? I am trying to figure out whether the following simple s-box configuration I created is more linear than non-linear or vice versa more non-linear than linear?

The parameters for this 16*4 table of 64 values, is it takes any arbitrary 6-bit binary string, and uses the left-most column for the outer-bits (first and last) and top-row for the inner 4-bits as lookup values, to output a 4 bit final value.

Example: a binary value of 101010, starts with 1 and ends with 0 so the third row would be used for part of the coordinate lookup value, and the inner bits of 0101 correspond to the sixth column and point to the coordinate 1111. So an binary value of 101010 would transform to 1111.

This s-box was created using a deterministic process involving XOR and one of the conditions it meets for non-linearity is that each output has 4 pre-images, but I am otherwise not sure if it is totally linear or to what degree, if any, it has non-linearity and other desired s-box properties such as discussed here: Desirable S-box properties

Sidenote: It also has a balanced hamming distance of all values, not sure if that is applicable either helping or hurting it one way or another.

P.S. There have been other questions about s-box linearity but those used AES-'s s-box How are the AES S-Boxes calculated? or the one from DES S-box basic question.

Yes, your table is perfectly linear: The output is the sum of the inner four bits plus left outer bit*0101 plus right outer bit*1010.


Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?) Suppose $S \in \mathbb{Z}_q^{m \times m}$, and the norm of $S$ is less than an upper-bound $\beta$.
Additionally, $A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n}$.
Here, $k \geq m>n$, and $q$ is a large prime.
And $S$ is unknown.
The following equations are satisfied
$SA_1 = C_1$
$SA_2 = C_2$
$\vdots$
$SA_k = C_k$
Can I solve this problem by using Gaussian elimination or any method of system of linear equations?
Note that I think this problem is similar with the lattice hard assumption - SIS.
I am not sure whether this problem has a solution.

Let $A' := [A_1 ~ | ~ \dots ~ | ~ A_k ] \in \mathbb{Z}_q^{m \times n k}$
and
$C' := [C_1 ~ | ~ \dots ~ | ~ C_k ] \in \mathbb{Z}_q^{m \times n k}$.
Then define $A \in Z_q^{m\times m}$ as the matrix whose columns are the first $m$ columns of $A'$. Likewise, define $C$ using the first $m$ columns of $C'$.
Then, $S$ satisfies $S \cdot A = C \pmod q$, thus, you can find it by computing $A^{-1}\cdot C \pmod q$.

Side note: why do you think that this problem is similar to the SIS problem? Notice that the SIS problem has a parameter $\beta$ that is an upper-bound to the norm of the accepted solutions and Gaussian elimination is likely to output solutions whose norm is above $\beta$ (thus, not valid solutions).


Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1) I have a question about Pseudo Random Functions.

Let $f:\{0,1\}^m \times \{0,1\}^n → \{0,1\}^n$ be a secure PRF.

Define $F(k,x) = f(k,x) - f(k, x-1 \bmod 2^{n}) \bmod 2^{n}$.

Is $F$ is a secure PRF?

Not if the attacker is given enough time to ask for the values $F(k,x)$ for all $2^n$ values of $x$.  We have

$\Sigma_x F(k,x) = 0$

which is distinguishable from random.


Stateless user-generated one-time passwords I've been working on my course project lately and got stuck with the problem which I reduced to the following abstract protocol:

Alice generates an ID key and gives it to Bob.
Bob generates some random data, combines it with that ID key to produce a token and sends it back to Alice. It is essential that data is random, i.e. Bob does not maintain any state.
Alice verifies that token is generated by Bob and also is able to tell whether it was used before. This can obviously be achived by keeping all previous tokens in a database, but if we are talking about passwords for example, it would be great to maintain as little state as possible.

The idea behind these requirements is that existing one-time password schemes require either interaction with the service (challenge-based OTPs) or maintaining some state (TOTP, HOTP, etc). What I would like to do is, basically, to generate a new password for every session, be able to generate those passwords upfront and be sure that once used, password can never be used again.

Is there any one-time password scheme that would satisfy these requirements?

What you are asking for is demonstratively impossible.

Say you only have some initial shared state, for instance a shared secret key and some values. Now you are asking to disallow a previously used authentication; however without additional state, there is no way that you can even detect that a previous authentication has happened.

So you need some kind of state, even if it is just a simple counter, for instance to identify which one-time-passwords have been used.


For Diffie-Hellman key exchange method, what are examples of very poor a and b values? For Diffie-Hellman key exchange method, what are examples of very poor $a$ and $b$ values? Given that $g$ and $p$ values are both large prime number and the formula is

$$g^{a . b} \bmod p$$

In Diffie-Hellman key exchange, the values of the secret exponent like $a$ (or equivalently $b$) must be generated in a way such that from $g$, $p$, and $g^a\bmod p$ (which will get public), it can not be found $a'$ with $g^{a'}\equiv g^a\pmod p$, or equivalently $a'\equiv a\pmod q$ where $q$ is the order of $g$. This condition is necessary, because guessing $a'$ is as good as guessing $a$, and breaks the DH protocol.

This condition implies that some ways to generate $a$ are bad. In particular, any value of $a$ known or guessable by the adversary is bad, including small values of $a$.

As an illustration of the above, and that choosing $a$ randomly in a large set is not good enough, it would be bad to generate $a$ as $r_{80}+q\cdot r_{256}$ for some 80-bit and 256-bit random $r_{80}$ and $r_{256}$: in this setup, DH could be attacked with algorithms requiring only $\sqrt{2^{80}}=2^{40}$ effort (including a simple variant of baby-step giant-step, now detailed in the last section).

Also, if it happened that the order $q_a$ of $g^a\bmod p$ was small (which is possible if the order $q$ of $g$ has small divisors), DH would be vulnerable; for example, to computing ${(g^a)}^j\bmod p$ for increasing values of $j$, allowing a guess of ${(g^a)}^b\bmod p$, as soon as $j\equiv b\bmod q_a$. Thus for maximum safety, $a$ should be such that the order $q_a$ of $g^a\bmod p$ is large. This explains why $q$ is often chosen to be a large prime: $0<a<q$ then insures $\gcd(a,q)=1$ and that $q_a$ is $q$ (thus large) without any explicit check.

Assume that the order of $g$ is a large prime $q$; perhaps $q=(p-1)/2$, or some other large prime dividing $p-1$, with $q>2^{2k}$ for $k$-bit security. It is then safe to generate $a$ uniformly randomly in range $[1\dots q[$. That criteria is used in the weakest form of the Diffie-Hellman assumption (thus the safest, and common).

It is demonstrably very nearly as safe to allow $a=0$, or/and generate $a$ uniformly randomly in range $[1\dots p[$ (which is also common and safe if the order of $g$ is $p-1$ with $(p-1)/2$ a large prime, rather than $g$ of prime order).

Another common method is generating $a$ as a string of at least $2k$ random bits; that's relying on a stronger form of the Diffie-Hellman assumption (thus less demonstrably safe, but still conjecturally safe).

Following (now gone) comments, here is how a choice of $a$ as $r_{80}+q\cdot r_{256}$ for some 80-bit and 256-bit random $r_{80}$ and $r_{256}$ (where $q$ is the order of $g$) could be attacked, with $\sqrt{2^{80}}=2^{40}$ work (essentially that many pairs of modular multiplications modulo $p$, and searches in a huge table):

Giant steps: tabulate $g^a\cdot{(g^{-(2^{40})})}^i\bmod p$ for all $i$ with $0\le i<2^{40}$, requiring about $2^{40}$ modular multiplications and comparatively negligible extra work.
Baby steps: for $j$ increasing from $0$, compute $g^j\bmod p$ and search it in the previous table until it is found; that will happen precisely for $j=r_{80}\bmod 2^{40}$, and the match will be with the value tabulated for $i=\lfloor r_{80}/2^{40}\rfloor$ (the proof uses that $g^q\bmod p=1$); it thus requires at most $2^{40}$ modular multiplications and searches.
We thus know $r_{80}=i\cdot2^{40}+j$. This is enough to compute $g^{a\cdot b}\bmod p$ as ${(g^b)}^{r_{80}}\bmod p$ and break DH.

Techniques exist to considerably reduce the amount of memory needed.

Note: $r_{256}$ is there as an (admittedly artificial) way to make the set of allowable $a$ large, but brings no actual security; the constant 256 is entirely arbitrary.


What data Certificate Authority encrypt for CSR? I have been searching for a detailed explanation but can’t seem to find a low level one.

1) When CA sign the data with its private key, the encrypted data is APPENED to the csr or the whole cert itself is the encrypted version? Does the encrypted data include contain public key or the whole CSR is encrypted?

2) if it is appended, why do we still need to keep original data in the cert? To check that data has not been altered when signature is unlocked by CA public key? Why can’t we just unlock CA signature and use the data inside there?

3)if it is replaced, how do we know which CA does this certificate belongs to?

4) does the client rely on IssueBy field to know which CA public key to use or they just try all the public

In the X.509/PKIX certificates used for SSL/TLS as tagged, but not necessarily for (many) other types of certificates:

A CA doesn't encrypt anything; it signs certificates. Signing is not encryption, although some people are confused by the fact that for one algorithm (RSA) one part of signing is similar mathematically to one part of encryption. The certificate is not the same as the CSR and a certificate is not a signed CSR, although the certificate includes some important data from the CSR: always the public key and often the subject name and sometimes some extensions.
A party who uses a cert (in SSL/TLS usually the client using the server's cert) validates it partly by verifying the cert's signature using the CA's public key (for which the CA usually has and provides another cert, the CA cert). I'm not sure I understand the rest of your question; we need to validate any cert to be sure it's valid and not faked, and an SSL/TLS client needs to validate the server's cert in order to be sure it's communicating with the correct server and not an imposter.
"if it is replaced" -- what is "it"? Do you mean a 'Man-in-the-middle' changing the handshake to include some other cert (or chain) instead of the server's cert (or chain)? If so, see #2.
Yes, the certificate contains a field Issuer which identifies the CA that issued (signed) the cert, and the Issuer field is used to locate the CA cert containing the CA public key used to verify the cert. However, there are other related values that can be and usually are in the cert as well:

AuthorityKeyID (AKI) extension identifies either the signing key (by copying its SubjectKeyID/SKI) or the signing cert (by its issuer and serial)
CRLDistributionPoint extension identifies where the CA, or an agent of the CA, issues Certificate Revocation Lists (CRLs)
AuthorityInfoAccess.OCSP (Online Cert Status Protocol) extension identifies where the CA, or an agent of the CA, provides revocation information online
AuthorityInfoAccess.CAIssuer extension identifies where the CA cert is available online (although in SSL/TLS the prover = server is required to send it so this normally shouldn't be needed)


Pseudorandom vs quasi-random I'm implementing an encryption algorithm that requires me to use a random number to mix up the values. However I'm caught in between if I should use quasi-random or pseudorandom.

These are the things I'm thinking about:

quasi-random isn't really a random number generator by definition but it's a good substitute for a uniform random  number generator, especially in the area of sampling across a plane and mathematically speaking it's more uniform compared to a uniform number generator.
pseudorandom on the other hand by definition is random. But if the attacker knows the seed its clearly not random also. And because it is less uniform compared to quasi-random it presents a certain bias towards a certain group of numbers.

So is randomness or the uniform distribution more valued when generating a random number? Should I choose a PRNG or a quasi-random number generator?

I'm implementing an encryption algorithm that requires me to use a random number to mix up the values. However I'm caught in between if I should use quasi-random or pseudorandom.

It may sound counterintuitive, but what works best within an encryption algorithm does in fact depend on the details of that algorithm.  It may be that, for your encryption algorithm, a uniform random distribution has a nonnegligible probability of creating a weak transform, and a tailored nonuniform ("quasirandom") distribution is better.

I assume you have spent a lot of time exhaustively cryptanalyzing your encryption algorithm; what does that analysis say?

And, by the way:

  And because it is less uniform compared to quasi-random it presents a certain bias towards a certain group of numbers.

Actually, that's not accurate; the definition of a uniform distribution (which is the name of the distribution that an unbiased random number generator generates) is that it doesn't have a bias.  For example, consider the probability that a generator proceduces two consecutive outputs $7, 7$.  If the generator was uniform, the probability of those two outputs is precisely the same as the probability of producing any other two specified outputs.  However, if the generator is quasirandom, the probability may be significantly smaller (even 0), if the quasirandom generator was biased away from repeating outputs.


Can Shor's algorithm compromise RSA when both the public and private key are secret? If RSA is to create a public-private key pair and encryption is performed on plain test P to create ciphertext C, given P and C could Shor's algorithm be used to find either of the public and private keys? You have both the plain text and cipher text but neither of the keys.
The fact that it seems pointless to use RSA if both the public and private keys are secret has come up a few times now so let me explain. I would like to use RSA because it has the property that if plain text P is encrypted with key K1 and the result is encrypted with key K2, assuming K1 and K2 have the same modulus base, this will produce the same ciphertext as encrypting P with K2 then K1.
If there is another more secure encryption scheme that has this property then I would be very interested in knowing about it. Otherwise, I will need to use RSA which is why I am asking about RSA's strength against quantum computers.
Also, the module base would be publicly known as well. The only secret information would be the exponents in the key pair.
Purpose
It has been asked what the value of key commutativity is. It allows one party to encrypt a secret text P (known only to party A) with the secret key K of another part (known only to party B). This is how:
let P = plain text (known only to party Alice)
let C = ciphertext (known only to party Alice)
let K = key (known only to party Bob)
let U = intermediate key (known only to party Alice)
Alice encrypts P with U and sends it to Bob. Bob encrypts this with K and sends this back to Alice. A removes the initial encryption (using U's decrypting pair) getting C.
C is the same as if P were encrypted with K without the involvement of the intermediate key because the keys commute.
Schematic:

Alice and Bob can only see things that are on their "side" (both the keys and the texts). the wall of equal signs represents this separation. the arrows represent text being transferred from one place to another and the keys intersecting the arrows represent encryption of the text traveling through them. I hope this is a clear explanation of this process. I'm not familiar with any traditional way of drawing these sorts of schematics. I someone could direct me to some information on how to draw one I would be happy to learn it and rewrite my schematic in that format.

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$.

We know that $P^e = C \bmod N$; that's equivalent to $P^e - C = kN$ for some integer $k$; if $e$ is small, then Shor's algorithm might be able to factor $P^e - C$; allowing you to recover $N$.  Alternatively, if you have two plaintexts/ciphertexts from the same key, then all you need to do is $\gcd(P_1^e - C_1, P_2^e - C_2)$, which can be done on a conventional computer.

Now, for public key encryption, we never use determanistic encryption.  However, for generating signatures, we sometimes do; this might actually be applicable there.

I would also second Maarten's comment that if you really intend to keep the public key secret, then there are symmetric algorithms that are far more practical (not to mention Quantum-Resistant).


In q-SDH problem, where are those points $\frac{1}{\beta+x}g_1$ or $g_1^\frac{1}{x+c}$ on elliptic curve? For the q-SDH problem, given the generator $g_1$ as a point on the elliptic curve, I can picture the $\beta g_1, \beta^2g_1, ..., \beta^qg_1$ since we can simply do the point adding $g_1$ multiple of $\beta$ times.
However, I cannot picture the point $\frac{1}{\beta+x}g_1$ (for some $x \in Z_p $). Is $\frac{1}{\beta+x}g_1$ a point on elliptic curve?
Moreover, in this q-SDH paper, there is a notation $g_1^{1/(x+c)}$. Is this $1/(x+c)$ equal a fraction $\frac{1}{x+c}$?
I cannot picture this $g_1^\frac{1}{x+c}$ either.

The linked paper is not about Elliptic Curves which relies on additive groups. It is about the multiplicative groups. For both of them the discrete logarithm is defined. There are common notations that confuse people about them.
In the multiplicative version, the division is actually not a division like in the reals. It is the inverse in the group and sometimes written both way.
$$\frac{1}{\beta+x}g_1 = (\beta+x)^{-1}g_1$$
Similarly $$g_1^{1/(x+c)} = g_1^{(x+c)^{-1}}$$
If you want to convert the idea in to elliptic curve you need to replace the exponent with the elliptic curve scalar multiplication. We can see this from here
The power in the multiplicative group is actually a definition by
$$g^x := \underbrace{g \cdot g \cdots g}_{x-times}$$
and similarly the scalar multiplication in elliptic curve is also a definition by
$$ [x]P : = \underbrace{P + P + \cdots + P}_{x-times}$$
Both have faster calculation methods see the Wikipedia Pages.

For multiplicative groups see the Exponentiation by squaring
For Elliptic curves see the Elliptic curve point multiplication


Coding of unsigned int to prevent guessing next ID Suppose we are assigning records an unsigned integer ID from a N-bit space (say 32-bit) in a sequential manner. Is there a way we can code this ID before showing it to the public such that someone can't guess the next ID in the sequence. It should be two-way, such that given the coded int, we can determine the original ID and 1:1 such that every ID has exactly one corresponding coded int (ideally of the same bit-length).

This doesn't need to hold up to any kind of brute force attack, but should be non-obvious to viewers if two coded integers represent IDs close together or far apart.

Any ideas? The simpler the implementation the better.

swap-or-not seems perfect for your use case.


The purpose of digital envelopes Why would you want to use a digital envelope? As I understand it, a plain-text message is encrypted using a secret key and then the key is encrypted with the receiver's public key. The encrypted message and the encrypted key is sent as the digital envelope. Now, what I don't understand is why one just don't encrypt the plain-text message with the public key in the first place? The literature I have been reading states that the secret key used to encrypt the message is a one-time key, so wouldn't this render the digital envelope unnecessary? I would understand the purpose of a digital envelope if it was to encrypt the secret key for continued communication, but according to the literature, this does not seem to be the case.

why one just don't encrypt the plain-text message with the public key in the first place?

If you want to send more than one message, the client and server need a shared secret that they can both use to encrypt and decrypt with.

Speed is very important. Encrypting with a symmetric key is much faster than using a set of asymmetric keys when the plaintext becomes longer.


Can encrypting well known files hurt the security of the key? I wanted to know if mass encrypting files (both well known and not so well known) on my external HDD would somehow hurt the security of my private key.

As for the details: I am using GPG with a key that is 4096 bytes with RSA and DSA set as the algorithm. I am also using a long passcode on the key. I am mass encrypting these files using a bash script I wrote up earlier today as these files were long overdue to be encrypted and I did not want to encrypt the whole drive, just parts of it.

I took a look at this question, but I am not sure that this is the same thing as my question as this talks about hashes. I appreciate the patience as I know almost nothing about cryptography.

TL;DR : Can encrypting well known files (think "known plaintext attack" etc.) hurt the security of the key?

Fgrieu answered my question in a comment to show that my key will be protected even despite the fact that I encrypted well known files.

  As a general rule, any modern encryption program should aim at security under chosen plaintext attack, and that's a goal of GPG, thus encrypting well known files should not hurt the security of your private key or otherwise compromise the confidentiality of your encrypted files; other causes with a much higher potential for that abound. [edited]


Equivalence of Secret IV and Secret Prefix MAC I read that the secret $IV$ and secret prefix $MAC$ methods are equivalent. Intuitively, this sounds reasonable because the $IV$ and the secret prefix are both the foundation of the inner state at the point of time when the actual message is hashed/compressed.

E.g. in "MDx-MAC and Building Fast MACs from Hash Functions" (link) by Preneel and Oorschot. Section 4.1 The Secret Prefix Method: "If the key consists of a complete block, this corresponds to a hash function with a secret IV."

With secret $IV$ $MAC$ I mean that the key is written into the $IV$ variables / the internal state before the message is hashed.

With secret prefix $MAC$ I consider the function $H(k\ ||\ m)$ where $H$ is a hash function, $k$ is the secret key, $m$ is the message and $||$ denotes concatenation.

I guess the security properties of these two schemes are indeed equivalent but how does this work in practice? For example some attacks against $MD4$ $MAC$s involve the work of offline $MD4$ computations. I can do that on messages with standard $MD4$ in the secret prefix $MAC$ setting (just leaving the unknown key out), but how can one do an offline computation when the secret $IV$ is unknown. How should the hash function be initialized and how (if at all) are the attacks applicable?

Examples of such attacks are:

New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5 (this targets $HMAC$ instead of secret prefix $MAC$, but I guess the attack is adaptable)

Password Recovery Attack on Authentication Protocol MD4(Password || Challenge) (... must leave out the reference here, due to missing repudiation)

There are a number of assumptions being made here, and I will make them explicit in case this was not what you had in mind.

The first assumption is that we are using a Merkle-Damgard hash. That is, given a compression function $C(h, m)$, we have (assuming a properly padded message)
$$
H_{\text{IV}}(m_0 \| m_1\| \dots \| m_n) = C(C(C(C(\text{IV}, m_0), m_1), \dots), m_n).
$$

The secret-prefix MAC is simply $H_{\text{IV}}(k \| m)$. I also assume that secret-prefix MAC uses the entire first block, that is, the secret key $k$ is the same size as $m_0$ above.

The secret-IV MAC sets the $\text{IV}$ to be the key: $H_{k}(m)$. But notice we can easily convert a secret prefix into a secret IV by setting $k' = C(\text{IV}, k)$. Therefore if you have a key-recovery attack on a secret-IV MAC, the process is exactly the same with secret-prefix, except the output you obtain is $C(\text{IV}, k)$ instead of $k$. Likewise, an attack on secret-prefix MAC is highly likely to target $C(\text{IV}, k)$ and not $k$ directly. To define the IV, you cannot use the standard APIs for hashing (e.g., md4_init(&ctx)), but will likely have to write your own code.

Recovering this secret IV, in either case, will allow you to forge any message and completely destroy the security of the MAC. In the secret-prefix case, however, recovering the IV does not immediately translate to recovering the original key.


Pseudo-random Number generation for Passwords I am looking for a good pseudo-random number generation algorithm for passwords.

My scenario is that I have to generate 5K pseudo-random bits from a user-supplied password (6 characters). What are possible options and which one would be able to cover for my purposes?

Scrypt is the best function for key-stretching we have. With such a bad password, you'll need all the stretching you can get, so make sure to use a large work parameter and a fast implementation.

But you should really consider using a stronger password. 10 random characters are much better than only 6.