NIST random excursion results NIST specifies so-called random excursions test and random excursions variant test. From the description I can derive that the number of p-values should be 8 in the first case and 18 in the second. But the result table gives only one line for each test. Keeping all of them is obviously redundant due to correlations. But it is not clear for me, which string out of 8 (or 18) should I take and why only one. Plus there is a question: what if only one of them is not passed, what should that mean?

So, there are a few things here.

  8 in the first case and 18 in the second

Yes, that's correct but only if there is enough sample data.  These last two tests need looads of numbers. In fact, in excess of the recommended minimum 10 x 1 million bits.  I don't know exactly, and NIST doesn't say exactly.  If happy, the test will return something like the bottom of the print out in  Interpretation of the results of NIST (p)NRG suite, innocently plagiarised below:-

  4  12   3  15  10   4   7   6   3   7  0.011440     70/71      RandomExcursions
  6   8   6   7   8   6   7  11   7   5  0.937294     70/71      RandomExcursions
  6   6   4   4   5  12   9   9   8   8  0.491599     71/71      RandomExcursions
  2   6   2  10   9  11   9   5   7  10  0.127498     71/71      RandomExcursions
  5   7   5   8   9   8   9   4   7   9  0.881013     71/71      RandomExcursions
  6   8   4   8  12   8   3   8   8   6  0.519816     69/71      RandomExcursions
  5   5   7   5   3   7  10   7   9  13  0.275709     70/71      RandomExcursions
  3   6  11   6  14   6   6   3   8   8  0.099089     71/71      RandomExcursions
  7  13   8   4   6   4   5   8  10   6  0.339044     71/71      RandomExcursionsVariant
 11   9   6   6   8   7   7   1   6  10  0.362174     71/71      RandomExcursionsVariant
 10   8   9   8   8   6   8   3   6   5  0.781926     70/71      RandomExcursionsVariant
  9   8   7   8   5  10   9   6   6   3  0.754127     71/71      RandomExcursionsVariant
  9  10   7   9   5   5   7   9   5   5  0.808725     70/71      RandomExcursionsVariant
  5  14   8   5   2   3  11  11   6   6  0.025193     70/71      RandomExcursionsVariant
  9   3   6   5  10   8   7   7   8   8  0.808725     70/71      RandomExcursionsVariant
  6   5   5   8  10   8   7   9   5   8  0.901761     69/71      RandomExcursionsVariant
  3   9   5  12   6   6   6  10   8   6  0.437274     71/71      RandomExcursionsVariant
  3   6   7   2  10  11   6  10   7   9  0.238562     71/71      RandomExcursionsVariant
  4  10   6  12   3  13   4   4   5  10  0.033552     71/71      RandomExcursionsVariant
  7   2  15   7   7   9   7   4   8   5  0.083381     71/71      RandomExcursionsVariant
  8   6  13   6   6   6   5   9   7   5  0.577844     71/71      RandomExcursionsVariant
  6  15   6   8   6   5   8   4   3  10  0.083381     71/71      RandomExcursionsVariant
 11   4   7  10   6  10   3   8   6   6  0.437274     71/71      RandomExcursionsVariant
 11   5   4  11   5   9  10   4   7   5  0.295803     69/71      RandomExcursionsVariant
 10   5   8   6   4  13   4   7   8   6  0.339044     70/71      RandomExcursionsVariant
 10   5   6   7   5  11   8   8   7   4  0.696376     71/71      RandomExcursionsVariant

  obviously redundant due to correlations

They're not correlated, unless your data is :-)  The suite takes your sample set and partitions it into multiple streams/chunks. Each test is run on a different sequence.  That's why you need so much data.  I typically use at least 10 times the 10 x 1 million bits (~10MB). Even more is even betterer.

  what if only one of them is not passed, what should that mean?

That your sample is properly random.  Or to be mathematically and philosophically pedantic, there is insufficient evidence to suggest that your sample set is not independently and identically distributed.  Again from that example:-

The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 96 for a
sample size = 100 binary sequences.

The minimum pass rate for the random excursion (variant) test
is approximately = 67 for a sample size = 71 binary sequences.

Because randomness is quite pesky, there is no theoretical threshold that can be used as a hard cut off in the (is random?) decision process.  And the issue is confounded by multiple independent tests that might contradict each other on the same data set.

From experience, you tend to look at the results and see what sort of feeling you get.  A very few test failures probably do not mean anything adverse.  Rerunning the tests on another sample set might produce slightly different results.  Experience is required.  When your RNG is misbehaving, it will be pretty obvious with multiple p values near 0.0 or 1.0.  NIST use a 1% decision rule, but a bad RNG will be way outside that.


Implications of reversing CBC encryption What would be the security implications if we reverse CBC encyption?
Here is a picture of CBC encryption:

Here is a picture of CBC decryption:

My guess is that the encryption would work if we ran the decryption process for encryption and encryption process for decryption. However, the effect from the IV is not spread to other blocks other than cipherblock 1. Are there any other potential effects?

If I understand you correctly, you want to use the decryption process of CBC to encrypt, i.e.,

This would not be CPA secure. The problem is, as you already noted, that the IV has no influence on any block but the first one.

I.e. a CPA attacker works as follows:
Choose two random messages of length 2 blocks $(m_0^0,m_0^1)$ and $(m_1^0,m_1^1)$ and output them as the challenge messages. Receive back the challenge ciphertext $(c^0,c^1)$. Now, ask $(m_0^0,m_0^1)$ to the encryption oracle and receive the encryption $(c_0^0,c_0^1)$. If $c^1 = c_0^1$ then output $0$, otherwise output $1$.


What is Black-Box Obfuscation? I understand black-box obfuscation at some intuitive level as- "an adversary can learn nothing more from an obfuscated program/circuit/function than he or she can from a black-box access to the same program/circuit/function." But I am failing at grasping it formally.
I got the following description from this site:

Black-box obfuscation: For every adversary $A$, there is a simulator $S$ such that for every program $f$ and distinguisher $D$:
$$Pr(D(A(O(f)))) ≈ Pr(D(S^{f}(|f|)))$$

I understand most of it, but I don't get what a/the simulator $S$ is and what it is for in the definition. In other words, what has the existence of the simulator to do with?

The simulator is just an algorithm. The idea is that for any adversary $A$, you can create an algorithm $S$ that can "simulate" $A$, that is, that has the same output as $A$.
The notation $S^{f}$ means that the algorithm $S$ does not has direct access to $f$, but just oracle access, i.e., every time $S$ wants to evaluate $f$ at an input $x$, it just sends $x$ to the oracle and gets $f(x)$. This formalizes the notion of "$S$ learns nothing about $f$ but pairs of input-output $(x, f(x) )$".
The actual input of $S$ is just the "size of the program". That is why we write $S^f(|f|)$.
On the other side, we have an adversary (also an algorithm) that has as input an obfuscation of the function, i.e., $O(f)$, and can evaluate the obfuscated function by itself, obtaining $O(f)(x) = f(x)$ for any $x$, but more than that, can actually analyze $O(f)$ to try to extract extra information about $f$.
Now, when we say that these two probability distributions are the same (or are indistinguishable), we are saying that both $S^f$ and $A$ behave in the same manner, i.e., the values output by them are the same. In particular, if $A$ can output some information about $f$, then $S^f$ also can. But then that information can be learned from the input-output pairs, since that is all that $S^f$ has, which means that the obfuscation $O(f)$ is not leaking extra information about $f$, as intended.


How can I calculate the entropy of an image? I am searching how can I calculate the entropy of a image for a Capture The Flag. I know what is the entropy theory and I tried a pair of things:

Convert the jpg image on binary image and calculate the entropy of binary text.
Viewing the images and intuiting which has greater entropy

I don't know how can I solve it. What can I do?

You don't need the probability distribution of images to calculate the information entropy of an image.  That isn't how the entropy calculation works.  For example, we can certainly calculate the entropy value of a symbol - say [@] - it would have an entropy value of 0, if we add multiple symbols...[@#], then the entropy value of two distinct bits of information would be 1.0, if we add even more [@#$] then the entropy value of the three distinct bits would be 1.58 - interestingly, if you add in redundant characters to your string, then you will reduce its entropy value, because you are not adding anything new to the string that we did not already know.

Consequently we can apply the same principle to image analyses, we do it all the time.  You would just vectorize the pixel data, read the flattened vector data into a dataframe, then do the entropy calc on the dataframe.  In my case, I just use scipy library from Python (scipy.stats.entropy).  We have analyzed many images using the technique, on average an image has an entropy somewhere between 3 and 4.  You can test this concept, by calculating the entropy of a pure white image (it should approximate zero, or be equal to zero), versus a more complicated image with graphs, people, chairs, cars, etc...(should be upwards of 4)

A fun way to cross check the validity of this, is to compare the entropy value of an "image of a string" to the entropy value "of the string bits" themselves - they won't be exactly the same (the image of a string is slightly higher (especially in languages that have multiple separated symbols within a single character bit [i.e., farsi, kanji, etc...]) - but in English they are pretty close.


Is this password migration strategy secure? I want to upgrade the security of some existing databases of users' authentication tokens strictly for the purpose of making sure that if the database is stolen, attackers will not be able to guess any but the weakest passwords in a reasonable period of time.  I know there's not much I can do for people who choose "password" for their password, but I think we can protect most people who use words from a bigger dictionary, e.g. "regenerating".

Some of the databases are from the 90's and the existing authentication tokens are stored as

 MD5(salt + password)

and some of the salts are pretty weak.  Other databases use somewhat better hashes and salts, but still not strong enough to resist attacks from today's computers.  However, we don't want to wait until people login to update their database entries.  So my plan is to simply take the output of whatever hashing algorithm the password system is currently using and to feed it into bcrypt and store that result as the new authentication token, e.g.

 bcrypt(MD5(salt + password), new_secure_salt)

Does anyone see a weakness with this procedure? It seems to me that this will not be any worse than using bcrypt(password, new_secure_salt) but I know better than to rely on just myself for the evaluation of a cryptographic protocol.

I wouldn't recommend this procedure for new applications, but this method is the best I can come up with for immediately securing an entire database of insecurely stored passwords in a way that is transparent to users.

The overall idea is a sound migration strategy. The nice thing is that security for all users is upgraded in a one-shot operation, rather than at the hypothetic next login of each user. Of course, original salt and new_secure_salt shall be stored, or perhaps for some portion derivable exactly from material keyed-in by the user, e.g. user name lowercased.

Using bcrypt(MD5(salt + password), new_secure_salt) is a huge improvement over MD5(salt + password): the risk of password cracking for a given password entropy is greatly increased by the many iterations (and some use of memory) in bcrypt. Using MD5(salt + password) rather than password discard negligibly little password entropy for typical passwords (who chooses 20 random characters among 68 as password?)

However I would recommend scrypt over bcrypt. Scrypt uses the memory available during legitimate use of the password in order to further increase security; have a look at this table from the paper defining scrypt:

The single weakness I can think of relates to MD5 collisions on salt. If it was possible for an adversary to choose salt and get the resulting authentication token with the same new_secure_salt a few times, it would become possible to recover the first few characters of the password, following the line of thought in Gaëtan Leurent's Practical key-recovery attack against APOP, an MD5 based challenge-response authentication (in  IJACT, 2008).
That's likely mostly theoretical in the context, where salt turns out to be non-malleable. To rule out any possibility of that attack, it would be enough that salt be included in new_secure_salt.

The above theoretical attack exploits that it is feasible to find two 63-byte 127-byte salt0 and salt1 such that MD5(salt0 + 'e') = MD5(salt1 + 'e') with collision in the first two 64-byte MD5 blocks. Now assume we could get the authentication tokens for these salt0 and salt1; if the password starts with e, then these tokens match! And the converse is true with near certainty. This allows to construct a test for the first character of the password, and recover it in a moderate number of queries, then proceed with the second, and perhaps third character; after that, finding the collisions seem to become quite difficult.


Securing communication between limited embedded systems I am currently trying to harden communication over a limited physical communication channel on an embedded system.
The Scenario
I think the system is rather typical for small embedded applications:

The embedded systems involved are small microcontrollers without any OS, which
can be assumed to be in a secure physical environment. The connection
channel is physically accessible to aggressors, they can interfere
with messages as desired.

Different communication channels are possible: e.g. RS485 or RS232.
There is a crude protocol which handles stuff like addressing and crude
integrity (e.g. CRC16 for bitflips) on which we can build. Think of
it as being a slow TCP.

Each communication partner knows a root certificate which can
act as a CA and has an own unique certificate(+key) signed by it. Certificates are self signed, elliptic curve prime256v1

The mbedTLS library is available for these systems (with DH, AES, ..).

Most of the time there is no internet available.

The systems can keep time and can create sufficient random numbers

I want to reach privacy, authenticity and integrity.
How it might be solved
A rule in cryptographic protocols is to never implement them on your own.
Unfortunately I did not find anything that matches this use case.
I also browsed through existing questions, but nothing provided the full solution i was searching for.
Finally in this answer implementing an own protocol is given as the last option.
This is why I came up with the solution described below - but I am not entirely sure about it.
I oriented on this answer on how to authenticate a Diffie-Hellmann Key Exchange, this answer on how to check integrity and this thread giving me some ideas on how to implement such a protocol.
Protocol to secure communication
First thing to do is to randomly generate a symmetric key K.
First thing sent is a handshake message.
It has the following fields:

Field
Description

DH
The Diffie-Hellmann key exchange msg gK

Cert
The certificate(-chain) of the sending device

MsgIdNonce
A random 64-bit value

Signature
A signature of the complete message using the private key of Cert

Both devices send (and receive) such a message.
When a message is received the following is done:

Check if cert is signed by the expected CA (has to be in chain)
Check if msg is properly signed with cert and its key

When these checks succeed the sent and received DH gK messages are used to calculate a symmetric key.
From this point on, applications can send messages encrypted with AES-CBC. As messages could be lost relatively often, IV is always in the message.
This is the message format:

Field
Description
Encrypted

IV
Initialy Random IV for AES
No

MsgIdNonce
Handshake/Last MsgIdNonce + 1 or + 2
Yes

Application Data
The data/commands to protect
Yes

CMAC truncated to 64 Bit
MAC for checking integrity
Yes

For a message to be accepted it must

Have the expected MsgIdNonce (1 or 2 above last received one) - preventing replay attacks, allowing to lose 1 message
Have a valid CMAC - preventing attacks on integrity
Be received max. T seconds after the last message - preventing delay attacks

If anything is not as expected, Handshake is sent again, then message is sent again with newly exchanged parameters.
Questions
Am I on the right path or should I try something completely different?
Does this provide my security goals or do I miss any obvious vulnerabilities here?
Can this work?
I hope you can help me and other embedded engineers facing similar problems!

A rule in cryptographic protocols is to never implement them on your own. Unfortunately I did not find anything that matches this use case.

Have you considered DTLS?  That tries to address the same problem (except for time stamps; that could be added by inserting the time stamp in the datagram), and already has things thought through.  Another possibility would be IPsec; however DTLS looks closer to addressing the problem you have (unless the data traffic you're protecting is IP traffic).
That said, here are some thoughts on the protocol you outlined:

What happens if two sequential messages are dropped (e.g. received incorrectly)?  Will the two sides realize what happened, or will they proceed to drop all subsequent messages (because of the 'nonce has to increment no more than 2' rule)?

Presuming they attempt a rekey, how is this coordinated?  If one side thinks they haven't rekeyed yet, and the other side thinks they are, what will happen to messages encrypted with the old key?  We find it generally useful to include a 'which key this is encrypted under' tag with the ciphertext (in DTLS, this is the 'epoch').

Can your communication channel reorder messages?  I suspect it can't in your case, but if it can, you should think about how that should be handled.

What happens if someone injects a previous (valid) handshake message?  How will that confuse things?

In the data encryption path, you use CBC encryption and CMAC integrity.  While this is a workable solution, this is prone to various padding attacks if they aren't integrated correctly.  Current fashion is to use an AEAD mode (such as GCM or Chacha20/Poly1305) which does both.

Is the encrypted traffic unidirectional or bidirectional?  If traffic goes both ways, do you use the same set of keys to protect both sets of traffic?

"If anything is not as expected, Handshake is sent again, then message is sent again with newly exchanged parameters." - how does that work?  If the receiver decided it didn't like the message, how does the sender know to resend it?


What does approved one-way function mean? In one of their documents, NIST recommends using an approved one-way function, followed by a list of such functions, such as HMAC, KMAC, etc.. However, the wikipedia page says:

  Unsolved problem in computer science:

  Do one-way functions exist?

How does something get approved if it may not even exist? Who approves it, and what is the approval procedure?

They are talking about NIST approved one-way-functions, which they list thereafter (HMAC,  KMAC etc.). They approve those because they are thought to be one-way functions by the cryptographic community (which - for NIST - includes the NSA).

The cryptographic community believes that they are one-way because they conform to an algorithm design that is thought to provide a one-way function. Of course, there also need to be no known attacks that compromise the function (much).

Note that usually the function can be proven to be one way if the underlying primitive - usually a block cipher, hash or sponge- can be proven to be secure. However, it can be shown that it is impossible to prove that.


AES plaintext is smaller than 128 bits - how to expand? We are currently developing a little AES implementation in a crypto-course at university.

As far as I know, AES uses a 128 bit block length, so all data that will be encrypted gets split up into blocks of 128 bits (16 bytes) into a 2d-array (or 1d in implementation) with 4 × 4 fields.

I was wondering and didn't find out what to do if the entered string to encrypt is not 128 bits long? The question is going further by thinking that there will never be exactly n × 128 bits of data to encrypt.

For a smaller key given by the user (e.g. "test") I know there is a key expansion algorithm defined.

But what should be done for data that is less than 128 bits?

A block cipher is an invertible transformation that maps an $n$ bit block of bits to an $n$ bit block of bits, under the control of a key (and where $n=128$ in the case of AES)

Now, we most often need to do things other than mapping blocks of $n$ bits; how we do that is using the block cipher within a Mode of Operation.  A mode of operation is just a way to use the block cipher to solve some problem we want solving.

There have been quite a number of modes of operations defined; the most common ones are CBC and CTR (counter).  The majority of them (including CBC and CTR) solve the problem 'how do I encrypt an arbitrarily sized message'.

As for 'how to handle odd sized messages', CBC and CTR take two different approaches.

With standard CBC, we assume that the message is always a multiple of $n$ bits; so, what we do is add padding to the message before we do that actual CBC-mode transformation.  This padding fills out the message to a multiple of $n$ bits; this padding is designed so that the decryptor can easily remove it after decryption.  Note: I said standard CBC because there are fancier ways to avoid this padding within CBC mode; they involve handling the last partial block as a special case.

With CTR mode, it doesn't assume that the message is a multiple of $n$ bits at all.  It doesn't actually send the message through the block cipher; instead, it generates a keystream by sending an incrementing pattern through the block cipher (so the first $n$ bits of the keystream may be generated by encrypting the value 1, and the second $n$ bits of the keystream may be generated by encryption the value 2, etc).  One we have such a key stream, having the message not being a multiple of $n$ bits is not an issue; we just discard the parts of the keystream we don't need to encrypt.


Secret sharing scheme verifiability This secret sharing scheme takes place in the polynomial ring over a finite field $F_p[x]$, $p$ being a large prime, in the following simplified way:

The dealer chooses a private polynomial $f(x)$.
Every participant $P_i, i \in N$, has a public polynomial $m_i(x)$, with $deg(m_i(x)) \leq deg(f(x))$.
The dealer computes the private secret share of $P_i$ as $s_i(x) = f(x) \mod m_i(x)$ and sends it to $P_i$.

I need a way for $P_i$ to verify that the private secret share $s_i(x)$ was well calculated.

Suppose there is a polynomial commitment scheme that allows you to commit to a certain polynomial $p(x)$ as $p(\beta)G$.

$\beta$ is a value unknown to everyone (as well as $p(\beta)$), including the dealer, and $G$ is a point generator of an Elliptic Curve over $F_p$.

This polynomial commitment scheme also allows to produce a proof evaluation of a certain committed polynomial, i.e., you can prove that a certain point (a, b) belongs to the committed polynomial.

With this, my idea to verify the private secret share $s_i(x)$ is the following:

Since $f(x) = m_i(x)k_i(x) + s_i(x)$, the dealer commits to $f(x)$ and $k_i(x)$ as $f(\beta)G$ and $k_i(\beta)G$, respectively, and sends them to $P_i$.
$P_i$ asks for an evaluation of a random $z$.
The dealer sends $f(z)$ and $k_i(z)$ to $P_i$, along with the proofs that they belong to the committed polynomials.
$P_i$ verifies that $f(z) = k_i(z)m_i(z) + s_i(z)$.

My thinking was that two polynomials $p(x)$ and $p'(x)$, with degrees $n$ and $m$, can have at most $max(n, m)$ intersections, so if the dealer commits to polynomials $f'(x)$ and/or $k'(x)$ instead of $f(x)$ and/or $k(x)$, the probability that the equation holds for those committed polynomials, is negligible.

I don't know how to prove or disprove this, so I would appreciate if anyone can help me.

I am fairly certain, that your proposed secret sharing scheme is actually not secure in any way:

If a party receives $s_i(x)$, then the secret polynomial is of the form $f(x)=s_i(x)+m_i(x) \cdot r(x)$ for some polynomial $r(x)$. And that is not equivalent to all possible polynomials. Even worse: If you allow the parties to choose $m_i$ themselves and of arbitrary degree, the parties can choose it do that they basically get $f(x)$ in the clear.

Example: $f(x)$ has degree $d$, then $m_i(x)=x^{d+1}$ gives back $f(x)$. Even if the degree is restricted, not all polynomials are possible.

But even if we assume, the secret sharing was secure, then your proposed algorithm would break it:

If the party can verify if their share was created properly, then the party can use this very procedure to learn something about $f$ instead. For any secret sharing scheme, giving the parties additional knowledge on top of their individual share will most likely break the information theoretic security (and otherwise it has to be proven). And since you have no computationally hard problem at all in your construction, it can't even have computational security.


Can pbkdf2 be used with a fixed salt to give a deterministic slow hash? I need a password hashing function that is deterministic. Correlation attacks are not a concern. The same password must produce the same hash. I just want to protect the password against dictionary and brute force attacks in the event that the hash is leaked.

Is there a well known way to do this? Would fixing the salt of bcrypt/PBKDF2/scrypt be enough?

Yes, this is thought to be so.
The point of PBKDF2, scrypt & bcrypt is to produce the same output on the same input, otherwise they would be useless as key derivation function (KDF).
I personally prefer Argon2 since you can tweak it a bit more, it makes a better usage of RAM and computing time, etc.
As explained on Wikipedia, PBKDF2 is not the best because it can be implemented on ASIC devices, which makes brute-force attacks using ASICs or even GPUs easier than for certain other KDFs.
Using a fixed salt for all entries just allows a dictionary attack against your specific application to be mounted, although this should still be somewhat hindered by the computational cost it would imply. That's not too worrying as long as you've generated the salt yourself and are not using a generic value (such as the empty one). But in general we never recommend using a fixed salt.
Instead, note that the good practice would be either to derive the salt in a deterministic way (from the username, for example), or to store the salt in the database next to the password (so that each password has a different salt.)


Modular Arithmetic in RSA Consider the following the following RSA public key $pk = (N, e) = (1457, 1307)$.

(a) Knowing that $187^2 \equiv 1 \pmod {1457}$ find the factorization of $N$.

(b) Given the factorization of $N$ computed above, use the CRT to decrypt the following ciphertext
$c = E_{pk}(m) = 3$.

For part a) I am not sure which property of modular arithmetic can be used? I know $187$  has a multiplicative inverse $187$. I also know the Euler function. But I think I am missing how to calculate $\phi$ from this information.

For part a) of your question: In this case 2 would be the order of 187 in the multiplicative group modulo 1457. This means you could retrieve the factors of 1457 using the formula gcd($187^{2/2}-1$, 1457) and gcd($187^{2/2}+1$, 1457).

Having the factors of 1457, you can compute $\phi$ with ease.

@fgrieu: The calculation is taken from the non-quantum part of Shor's Algorithm. Basically it's the same as what you mentioned in the comments of the question. Thanks for pointing out my mistake. I mixed up some numbers in my gcd calculation...


How do I create a secure encryption scheme using addition? You have a 4 number long PIN code with each number ranging from 0 to 9 which you wish to encrypt. You are then given a random 4 digit number ranging from 0 to 9999, which when added to the original PIN should give out a perfectly secure encrypted number.

Now clearly, just adding the two numbers would give an uneven distribution (a Gaussian curve), as if for example the PIN was 0000 and the random number was 0001, you can rest assured that the original PIN is either 0000 or 0001, while if both integers add up to 9999, there are 19998 possible outcomes.

So my initial thought was that applying the mod of 10000 (because there are 10000 possible combinations) to the sum should ensue an even distribution, making this encryption scheme perfectly secure. Now I honestly really don't know how to prove this, but my main question is how can you convert this somewhat meaningless number back to the original PIN? Is this actually (maybe not effective) perfectly secure? The point of this exercise is that the two users only have common knowledge of the random number, so I don't think any modulus exponent tricks are accessible.

Your idea of addition modulo 10000 is correct.  The correctness follows from the fact that $\mathbb{Z}_{10000} = \{0, 1, \dots, 9999\}$ equipped with addition modulo $10000$ forms a (finite) group.

Let $m \in \mathbb{Z}_{10000}$ denotes a PIN code.  Now choose a uniformly random element $r \in \mathbb{Z}_{10000}$ and define $c = m + r \bmod 10000$.  It is easily seen that $c$ is a uniformly random element in $\mathbb{Z}_{10000}$.


I am trying to generate a permutation of polynomial with order m Suppose m = 5 and N = 64. How do I choose the coefficients such that the polynomial is a permutation of nos from 0 to 63.?

I believe this is on topic. In general this is a math question and there are various permutation polynomial families, such as Dickson polynomials, see Wikipedia under "permutation polynomials".

In the case $N=2^m$ (which seems to be the one you are interested in, though the term "order" instead of "degree" is problematic) there is a nice paper discussing such polynomials, by Ron Rivest entitled "Permutation polynomials modulo $2^w$ $w\geq 1.$ I state the main result.

$P(x)=a_0+a_1x+\cdots+a_d x^d$ over the integers modulo $2^w$ is a permutation polynomial if and only if $a_1$ is odd, $a_2+a_4+a_6+\cdots$ is even, and $a_3+a_5+a_7+\cdots$ is even.

See the paper for more related results, e.g., on polynomials generating latin squares mod $2^w$, just google "Rivest permutation polynomial".


collision resistant summarizer for long hash values how we can summarize SHA-256 into shorter values when we for example can't handle more than 128 bits on system? its better just use first 128bit and ignore the rest of bits or split full value and XOR them? or use another hash function that produce required bit long hashes to generate a hash from SHA-256's value (e.g SHA-1)? which way is more robust and unpredictable?

The answer is "any sane summarization function is about as good as any other; pick whichever is convenient"

To the best of our knowledge, SHA-256 acts pretty much like a random function (except for the length extension attack; that wouldn't apply here)

So, the output of SHA-256 is essentially a random 256 bit number; so, if we have a 128 bit hash function:

  Hash(M) = Summarize(SHA256(M))

then, as long as the Summarize function has $2^{128}$ preimages (of 256 bits) for each possible output (of 128 bits), it should be good.  Both the "use the first 128 bits" and "split the full value and XOR them" functions have this property.

Now, since you talk about collision resistance, you can find a collision with a 128 bit hash function with about $O(2^{64})$ effort, by the simple expedient of generating $2^{64}$ random strings and hashing them, and then looking for two hashes with the same value (and, in case you're hoping the memory requirements of this would save you, there are clever ways to reduce the memory requirements drastically without requiring that much more computation time).  As long as those random strings are longer than 128 bits, there's nothing a hash function can do to avoid a collision.  If you need stronger collision resistance than that, you need to rethink the problem.

Also, since I mentioned the length extension attack, I'll summarize it here:

If you hash the value $SHA256(M)$, and the length of $M$, then you can compute a string $A$ such that, for any string $B$, you can compute the value:

  SHA256(M | A | B)

You can compute this even though you know nothing more about $M$.

This wouldn't apply in this specific case, because for this to work, you need to know the entire $SHA256(M)$ output, and your summarize function will drop a lot (precisely 128 bits, actually) of that information.


Is it safe to use a random numbers instead of a counter in ChaCha20? Besides the IV, ChaCha20 takes a random number and a counter as input.

I couldn't find more precise information about this but it seems to be that the counter is just a safety measure in case of a bad the PRNG.

If the user has a good PRNG, would it be safe to use another random number instead of a counter in ChaCha20?

In some applications, such as P2P networks with a flooding protocol, this can be useful so I would not have to keep all these counters in memory.

I am using here the description and terminology from RFC 7539.

ChaCha20 is meant to process messages, each message being a sequence of bytes; ChaCha20 produces pseudorandom blocks of 64 bytes each, which are XORed with the data to encrypted or decrypt. The crucial security property is that all invocations of the ChaCha20 block function for a given key use distinct values for what is injected in state words 12 to 15.

In the description of RFC 7539, state word 12 receives a counter value, which is over 32 bits and incremented for each block, while state words 13 to 15 receive a 96-bit "nonce" which is fixed for a given message, but different for each message. The idea is that, for a given key:

Each message works over a new nonce value (96 bits), such that no two messages share the same nonce.
Within a message, different blocks use the same nonce but a different counter values.
No message may contain more than $2^{32}$ blocks (i.e. close to 275 gigabytes, which "ought to be enough").

Nonce values themselves can be generated in any way that offers the unicity guarantee with sufficient probability. If you generate nonce values randomly (with a uniform generator), then the risk of reuse is low as long as you do not produce too many messages; with $n$ messages, probability of reuse is about $n^2/2^{96}$. In other words, if you do not send more than 8 billion messages with random 96-bit nonces and the same key, then the risk of reusing the same nonce is less than one in a billion.

Take care that all of the above is for reusing a nonce value with the same key. If two messages use the same nonce+counter but with different keys, then there is no security issue.

In a P2P network, conceptually, messages are encrypted with keys derived from some sort of key exchange (e.g. ECDH), and each node must remember the key to use for each of its neighbours; it should not be too much a hassle to remember a counter value along with each such key, in particular if these keys are ephemeral, i.e. only in RAM.


Relationship between Elliptic Curve Discrete Log, Integer Discrete Log, and Integer Factorization I am trying to look into a relation between the following three problems which are widely used to build public crypto systems:

Integer Discrete log
Elliptic Curve Discrete log
Integer Factorization

Can any of these problems be reduced to another such that an efficient solution to one of them yields an efficient solution to the another?

Actually, there are two known reductions among these three problems:

If you can solve discrete logs in $Z^*_n$ for composite $n$, you can use that to efficiently factor $n$
If you can solve discrete logs in $GF(p^k)$, you can compute discrete logs in an Elliptic Curve over $GF(p)$.  That's because there is a known mapping of Elliptic Curves over $GF(p)$ into $GF(p^k)$ (for an integer $k$ that depends on the curve) that preserves the group operation; hence you can solve discrete logs over an Elliptic Curves by mapping the generator and the target into $GF(p^k)$, and solving the discrete log there.  Now, for curves used in practice, $k$ is large enough that, with the current discrete log algorithms, this method is actually slower than just using a generic discrete log algorithm in the elliptic curve.

Of course, neither of the above reductions would apply to the recently discovered algorithms for doing discrete logs over small characteristic fields; for the former, we're not talking about a field at all ($Z^*_n$ is a ring, not a field), and for prime elliptic curves (which is what we use in practice), $GF(p^k)$ has a very large characteristic.


How to determine the concrete security of lattice cryptosystems? I am currently reading about lattice cryptography and am interested in the cryptosystems based on the LWE problem. I understand the reductions from lattice problems to dLWE. Then we base our belief in the cryptosystem (say Regev or dual Regev PKC) on dLWE. But this is however asymptotic. From what I understand, the way this works is we believe breaking SIVP or whatever lattice problem takes time a very large function of n, and from the reduction we get a SIVP solver, so any algorithm which breaks the cryptosystem also is necessarily is a very large function of n.

What I don't understand however is how does one give parameters to these cryptosystems (for example, if I want 128 bits of security, how large should the LWE instance be)? I have read a couple of papers on this topic and have not really understood it. My comprehension is that we solve LWE like an instance of BDD. But these papers discuss basis reduction and ways of solving SVP and I do not know how to link these things together.

Sorry, my English is really bad.

Depending on whether your lattice-based cryptosystem has security reduction or not, there exists two types of parameters:

$\textbf{1. Provably secure:}$ For a cryptosystem with provable security, the parameters are chosen according to the underlying reduction. For example, suppose your cryptosystem is based on the hardness of LWE problem. Now, assuming that the desired security level $\ell$ is identical to the hardness level of the LWE problem (i.e., without involving the gap induced by the security reduction), one can determines the best known solver $D$ for the LWE problem and ensures that its corresponding
parameters offer a hardness of $\ell$ bits. In order to find also the best known solver for LWE and measure the bit hardness of LWE instances, the estimator by Albrecht et al. [APS15] can be used.

$\textbf{2. Non-provably secure:}$ If the cryptosystem is not provably secure, then identify the best known attack $A$ on the cryptosystem and select parameters satisfying $\frac{t_A}{\varepsilon_A} \geq 2^{\ell}$, where $t_A$ and $\varepsilon_A$
are the running time and success probability of $A$, respectively.

See this paper for more details.


About Cryptography in a Character Language Suppose I had a message in Chinese (or another non-phonetic language) and I wanted to encipher it.

Some of the simplest encryptions in English are substitution ciphers, but such ciphers don't seem to be a viable option for a language such as chinese (it's more similar to a code...). What would be a simple cipher for such an alphabet? (Lets assume that we don't want to transliterate it to English first).

Second, suppose that someone had used a substitution cipher on such a language (in the code sense where every word stood for another).

Would frequency analysis still work?
Are non-phonetic languages more or less secure when used with substitution ciphers?
Assuming frequency analysis is not an option, how would one break it?

For designing a cipher, one first has to decide about the alphabet.

This is a bit problematic for a language like Chinese, since it is not really clear how many (and which) characters should be used. The number of signs known by people differs greatly. You don't want that your encrypted message is un-decryptable just because you used some unknown character in the ciphertext. One possibility here would be to restrict the ciphertext alphabet to some "known to everyone" subset (while still allowing a greater alphabet on the plaintext side).

Assuming we have decided on an alphabet, we also should decide on some encoding of this alphabet, i.e. some ordering of the signs, or a mapping to numbers. This allows using some simple mathematical formula/algorithm for the actual encryption, instead of having to use a "translation table" as the key (which would be quite big in the case of a big alphabet).

Every monoalphabetic substitution cipher can be presented as a "big table", and thus breaking the big table algorithm also breaks each other (monoalphabetic) algorithm (which in fact are only ways to write the big table in a shorter way).

So, how to break a monoalphabetic cipher? Just like always. In a language like Chinese there are more frequent words (= signs), too, and more or less frequent two-word or three-word combinations, just like in our European single-sound-alphabets, too. The problem is just that there are more different signs, and thus you need a lot more text to get significant samples. Then we try the most probable words first, and try to fill in the rest, and see if it starts to make sense. Some signs used only once or twice are quite probably not decodable at all, if multiple different ones would make sense here.

The reason that modern substitution ciphers on really large alphabets (like AES) are comparatively quite secure even in ECB mode (in other modes they are not pure substitution ciphers), is that you don't get as much blocks to find many repeated ones - and that you simply can't write down the whole substitution table, for space and time reasons.


Zero knowledge proof of possession of key Suppose Alice has at some point in time produced ciphertext $C$ from message $M$ with key $k$.
Suppose Alice has then passed $C$ to Bob, and also made a commitment to her key $k$ (thanks to nightcracker for this addition).

Bob then stored it and passed it to a third party Dave, who also possesses $k$ and decrypts to get $M$, and based on $M$, performs certain operations.

Assume that Dave has no contact with Alice and Bob.

Now Alice is incentivised to lie about the contents of $M$ to Bob.

Suppose at a later time that Alice provides Bob with the message $M$. Is there any sequence of actions that Alice can perform to prove to Bob that $M$ was the message she encrypted to give $C$, without handing over the key $k$?

Is there any connection with this: Zero knowledge password proof?

Alice can prove that the decryption of $C$ is $M$. This can be done using zero knowledge proofs.

Simple example: Suppose $C = (x,w)$ is an ElGamal encryption of $M$ under public key $y$, that is $(x,w) = (g^r, y^r M)$ for some $r$. Suppose that the decryption key is $a$, that is, $y=g^a$. Then we know that $M = wx^{-a}$, or $x^a = w/M$. That is, the logarithm of $w/M$ to the base $x$ is the same as the logarithm of $y$ to the base $g$.  Conversely, if the logarithms are equal, the decryption of $C$ is $M$.

Now Alice can prove that the decryption of $C$ is $M$ by proving the equality of the two discrete logarithms. There are standard zero knowledge proofs for this.


CTR and CBC-MAC Demystified I am trying to understand the background processes within the CCMP. However the concept of CTR and CBC-MAC made me lost.

According to the CCMP Encapsulation block diagram there are inputs like Plaintext MPDU, TK, PN, KeyId, etc. What is the temporary key (TK)? Which part of the diagram represents CTR and which one is for the MIC computation (CBC-MAC)? Construct Nonce from the image constructs the nonce for the MIC or for the counter computation?

If I've understood well, counter is a 128-bit value derived from Source MAC address, Packet number, Flag, Priority and Ctr which increment by 1 for each MPDU. Each message is broken into 128-bit chunk of data and then XORed with the encrypted counter.

CBC-MAC is a mode used to generate 64-bit MIC. Again, each message is splitted into 128-bit message blocks. First message block is derived from the nonce which is constructed from Source MAC Address, Priority, DLen and Packet Number. This message block is encrypted with AES and its result is then XORed with second message block and the result of XOR operation is encrypted again. This keeps repeating until the whole message is encrypted. Finally, this forms 128-bit MIC which is then discarded to 64-bit MIC.

I've got lost in RFCs since I've couldn't find any good explanation in my literature.

It is not entirely clear what your question is, so I just try to explain what CCMP and CCM are, and roughly how they work. Please update your question if this does not answer it.

First of, remember that CCM is a general purpose mode-of-operation for authenticated encryption, while CCMP is a specific way of using CCM within the context of IEEE 802.11 (WiFi).

CCM

CCM is a general purpose mode-of-operation for authenticated encryption defined in RFC 3610. However, since your question is asked in the context of CCMP I specialize the description of CCM to that setting. CCM is a combination of CTR mode encryption and CBC-MAC in a variant of MAC-then-Encrypt. Within CCMP, it uses AES as the underlying block cipher,
and takes as input a 128 bit key $K$, a plaintext $P$, associated data $A$, and a 104 bit  nonce $N$.

To process $P$ and $A$, CCM first computes a CBC-MAC over $A$ and $P$ to produce a tag $T$. It then encrypts $P$ using CTR mode encryption to produce a ciphertext $C'$. Finally, it encrypts $T$ using a single CTR block to produce an encrypted tag $C_T$. The output of CCM is $C$ and $C_T$.

What is missing from this description is how CCM constructs the (128 bit) IV block for CBC-MAC and the (128 bit) initial counter value for CTR mode. Both of these are constructed from the 104 bit nonce $N$ as follows:

$\begin{align} IV &\gets Flag_1 || N || Length(A + P)_{16} \\
CTR_0 &\gets Flag_2 || N || 0^{16}
\end{align}$

where $Flag_1$ and $Flag_2$ are two distinct 8 bit values (you can look up their definitions in the RFC).

CCMP

CCM is a stateless authenticated encryption scheme. As such, it cannot protect against replay attacks. Essentially, the purpose of CCMP is to add replay protection on top of CCM by introducing some state. In particular, CCMP  maintains a 48 bit counter called the packet number (PN in your diagram) which is incremented for each encrypted IEEE 802.11 frame. Since CCMP uses CCM, one of its responsibilities is to create the 104 bit nonce $N$. This is what is shown in your diagram above. Basically, $N$ is created from the 48 bit MAC address of the sender ($A2$ in your diagram), the 48 bit packet number PN, and a 8 bit flag $Flag$ which encodes various IEEE 802.11 settings, in the following way:

$\begin{equation}
N \gets Flag || A_2 || PN
\end{equation}$

Thus, when this 104 bit nonce is feed into CCM, the 128 bit IV and 128 bit initial CTR value, will look like this:

$\begin{align} IV &\gets Flag_1 || Flag || A2 || PN || Length(A + P)_{16} \\
CTR_0 &\gets Flag_2 || Flag || A2 || PN || 0^{16}
\end{align}$

This is essentially all that is happening in your diagram above. The value TK corresponds to what I called $K$ as the input to CCM.


Fastest way to compute iterates of SHA1 It's well-known that computing lots of hash functions (like SHA1) in parallel involves the use of GPUs in most cases.  However, when doing something serially, such as computing sha1(sha1(sha1(...sha1(x)))) parallelism would not seem to be that useful.

I ran into this very problem recently, and I started running a program on my Mac laptop using python, at about 270k hashes/sec.  Moving to a C implementation, I was able to get 750k hashes/sec.  And strangely, using VirtualBox with Kali and the same C implementation, about 1.3m hashes/sec.

(There is some discussion one can find online regarding why a Linux version of SHA1 code might be faster than a Mac OS version, even when the former is through a virtualization layer, but this is beyond the scope of my question.)

Question: If I want to compute SHA1 as fast as possible and parallelism is not helpful, what's the fastest way to do it?  I suppose the answer involves special hardware?  Or buying a desktop with a good CPU and overclocking?

There is no known mathematical trick to compute iterates of SHA-1. Getting high throughput in software involves:

Use of parallelism if at all possible; that is, if starting from multiple points. Depending on why one computes iterates of SHA-1 that is possible, or not.
Specializing the code to compute the hash of a 20-byte message obtained as as hash, removing endianness conversion and padding in the main iteration. That is, to compute an $n$-iterate of a message per SHA-1:

hash the message per normal SHA-1;
convert the (bytestring) result to 5 native-endian 32-bit words, yielding the current iterate;
repeat $n-1$ times:

perform a single SHA-1 round, starting from the SHA-1 Initialization Vector 0x67452301 0xEFCDAB89 0x98BADCFE 0x10325476 0xC3D2E1F0, hashing the 16-word block consisting of the 5 words of the current iterate, 9 zero words, the word 0x000000A0 (for 160 bits), and a zero word; yielding the new value of the current iterate, manipulating 32-bit (or wider) quantities only;

convert the current iterate to (bytestring) result.

Coding and micro-optimizing carefully, perhaps in assembly. That a 73% throughput increase was achievable merely by changing compiler is telling that this counts. Among techniques likely to help:

Fully unroll the 80 rounds
Take advantage of constant words in IV and 16-word block hashed
(b&c)|((~b)&d) is ((b^c)&d)^c and that might help (or not) for rounds 0..19
(b&c)|(c&d)|(d&b) is ((d|b)&c)|(d&b) and typically helps for rounds 40..59
Schedule and choose what goes into what register wisely.

Update: on selected CPUs, there are special instructions; see this Intel whitepaper and reference code.

For the ultimate in speed, there's FPGA; an ASIC would be even faster, but wasteful.


Why send a challenge with CHAP? I have been reading about the Challenge-Handshake authentication Protocol (aka CHAP).

Why send a challenge to the user and ask them to hash that challenge with the symmetric key and send that hash back to the server? Why not just ask for a hash value of a symmetric key? And what is the point of this protocol at all when you both have symmetric keys?

The Wikipedia article points out a good reason for using a random challenge value: preventing replay attacks.

If the hash was always the same (as the hash of the symmetric key would be), then having listened in on one challenge-response cycle, a malicious listener could pass further handshake tests.


Definition of authenticity I came across various definitions of what authenticity means in cryptography. I would like to know which one is correct.

The first definition - the one I always used - is the following:

  Data authenticity means that the initial message sender is who he/she claims to be.

According to this definition, we can have data authenticity without data integrity.

The second definition defines authenticity as authentication + integrity.

It is hard to have message authenticity without integrity. To authenticate the message you need to know what message is being authenticated. If you could change the message the authentication tag should become invalid. Message authenticity means that you can establish that the message originated from a trusted entity. For this reason message authenticity often implies integrity.

This doesn't go the other way around because of checksums. Checksums can be used to protect integrity of a message. Checksums however do not protect against active attacks as anybody is able to calculate a checksum. If you need to protect against active attacks then the message is usually authenticated as well.

I'm not sure that "data authenticity means that the initial message sender is who he/she claims to be" is a correct definition. That seems the definition for entity authentication. The data may not be an identifying aspect for the entity. I would rather say that message authenticity proves that the message originated from a specific entity. In that case - as explained in the first section - integrity is probably implied.

As an example, say we find a bunch of paintings all bearing the same signature. We however do not know who created the paintings. All we know is that there is some unknown painter that painted the messages - the identity of the painter is not really established. What we do know however is that all the paintings belong to a single painter. That says quite a lot about the paintings themselves.

If you look at entity authentication then no explicit message needs to be involved, so data integrity may not be required. So there you are: authentication without integrity.

Authenticity and integrity are different concepts, even if used in the context of data/messages. It doesn't make sense to mix those concepts even if one implies the other. So I try to write "message authentication and integrity" instead of just "message authenticity" or "message integrity".

In text you have to distinguish between message and entity authentication. If you have message authentication you know that integrity is very likely implied. This is not the case for entity authentication. So you do need to look at context to see if integrity is implied.


Can I achieve data authentication with ChaCha20 without MAC? My case is rather special. I need to send data in small chunks, each under 32bytes. ChaCha20 state is 64 bytes.

Since I will be receiving data stream in chunks, id like to verify it on the fly (i.e. after I receive each chunk, make sure it was not tempered with).

Using MAC is a bad choice, as I'd have to compute MAC every time I send my 32byte chunk and append it to the message. And I don't think this is a standard approach as with Poly1305, where as I understand, you compute MAC only once when ALL the data is transferred, not sending intermediate MACs.

So I got this idea: instead of computing MAC (with Poly1305 or other), why not just use the 32byte data twice, make a 64byte chunk that can be XORed with one state of ChaCha20.

Upon deciphering, I verify that the first 32 bytes are equal to the latter 32 bytes. If yes, there was no modification. If no, there was some tampering / transmission errors.

So my questions are:

1. Does repeating ciphertext twice compromise security of the stream cipher? (Assume attacker knows this)

2. Is there some standard way how to provide message authentication with stream ciphers without this "hack"?

Thanks for answers and opinions!

You're in luck!  According to your question, you have 64 bytes of bandwidth per 32-byte message available.  The authenticated cipher crypto_secretbox_xsalsa20poly1305 has a ciphertext expansion of only 16 bytes—that is, the ciphertext is only 16 bytes longer than its plaintext, no matter how long the plaintext is, so in this case it will use only 48 bytes and leave you 16 bytes under budget!

Just use crypto_secretbox_xsalsa20poly1305 for each 32-byte message before you act on it—if you use NaCl/libsodium, you won't even be allowed to get at the decrypted plaintext if it's a forgery—and you'll be good to go.

If you already have a message sequence number, use that as the crypto_secretbox_xsalsa20poly1305 nonce; if not, you can use 8 of the remaining 16 bytes available to you for a message sequence number.  If you ever repeat a nonce with the same key, the security vanishes.

No need to worry about stream ciphers (which can fail to protect confidentiality if you act on forged messages), MACs (which don't protect confidentiality at all), HMACs (which are a specific kind of MAC), etc.  Focus on authenticated ciphers like crypto_secretbox_xsalsa20poly1305 or AES-GCM.


Do RSA keys contain a checksum mechanism? I'm new to cryptography, and I was making an experiment a few minutes ago, but I want to have some deeper knowledge about RSA public and private keys.

I have a set of keys

One begins with

-----BEGIN RSA PRIVATE KEY-----
MIIBOgIBAAJBAOlnH1jZ2YLfWuYMop1a4N9jsUPK......
-----END RSA PRIVATE KEY-----

and another with

-----BEGIN PUBLIC KEY-----
MFowDQYJKoZIhvcNAQEBBQADSQA....
-----END PUBLIC KEY-----

I've parsed them using Java and I can make use of them, as RSA private and public keys respectively.

But the question I have is....

Are there some checksum mechanisms built into RSA keys ?

I ask this because, I'd like to know what happens if, by error or intentional, one or more characters from the encoded PEM are modified.
Does this breaks the key ? Or changes the key internally, without breaking it ?

No, there is no checksum built-in to the RSA keys per se. There is no need for that.

  Does this breaks the key ? Or changes the key internally, without
  breaking it ?

[EDIT] It was rightfully pointed out to me that at least one of the statements I typed (in haste) was plain wrong. Now that the answer has served its initial purpose, I've removed my badly worded and therefore wrong statements and just duplicating here the link to a much better explanation of things (which I really liked):
Why does my SSH private key still work after changing some bytes in the file?


Why are MACs in general deterministic, whereas digital signature constructions are randomized? The fact is I'm not quite sure if my question statement is true, however all the MAC constructions I know of (e.g. CBC-MAC, CMAC, HMAC) are deterministic, whereas many constructions for digital signature are randomized (e.g. DSA, ECDSA, RSASSA-PSS). I also know that RSASSA-PKCS1.5 is deterministic but still considered secure (though not recommended in favor of RSASSA-PSS).

Why is it the case that most MACs are deterministic whereas most digital signature schemes are randomized? Are there randomized MACs that I simply don't know about, and do they provide any advantages over the deterministic approach? Is there some fundamental difference between MACs and digital signatures that makes the randomization more desirable (but still not required) for signatures?
Are there randomized constructions for MACs or digital signatures that breaks badly if the randomizer output is not indistinguishable from random, or do they all simply reduce to a still secure deterministic scheme?

One rationale for avoiding randomized schemes in general, and in MACs in particular, is that the random in such schemes tends to increases the size of cryptograms or reduce the size of the payload. An example is scheme 2 in ISO/IEC 9796-2 RSA signature with message recovery, where the size of the random/salt field is directly antagonist with the amount of data recoverable from a signature.

Also, a randomized scheme typically opens a "subliminal channel" backdoor that can't be detected in a black-box testing of an implementation, and could funnel out sensitive information. E.g an RSA (SSA-PSS or ISO/IEC 9796-2 scheme 2) signature blackbox could leak a factor of the private key, CBC-encrypted with random IV and a backdoor-key in the field supposed to be random.

Given that MACs do not seem to need to be randomized to be secure, the above is reason enough that most MACs are deterministic in their definition. Notice however that in practice, the MACed message itself often contains a random component, or/and that (in order to resist side-channel attacks on implementations) the key could be a random session key, in effect randomizing the MAC.

If the random source in a randomized digital signature scheme is bad, that often weakens the scheme. The best example might be [EC]DSA and the PS3 signature fiasco, see this, including comment #2.


Is there an algorithm or hardware that can sign/verify natural time? PGP/GPG can used to sign text, others use public key to verify them. So one could say, that these cryptographic algorithms deal with space.

Are there any algorithms that can deal with time? E.g. I sign a document at 2011-12-31 23:59:59, others can verify this document is really, truly signed at 2011-12-31 23:59:59.

I know there are solutions based on a common trusted time source (a notary), but is it possible that a pure algorithm solution exists? Or perhaps some amazing dedicated piece of hardware can do this? (E.g. half-life of certain well-known material, etc.)

In a simple way: Can we give nature a private key and ask nature to sign our documents using a natural timestamp?

A pure algorithmic approach does exist, however it only provides a fuzzy bound. It is related to the proof of work / client puzzles I described in this answer.

The signer will sign the message using a normal digital signature, and use the message and signature to instantiate a "cryptographic puzzle." A cryptographic puzzle is a moderately hard function that takes a certain number of CPU cycles (or memory accesses) to compute. The signer will then immediately begin to solve the puzzle.

Later, if a dispute arrises as to when the message was signed, the dispute can be resolved when the signer eventually produces the solution to the puzzle. The verifier checks that the solution is correct and then backdates the creation of the puzzle according to how hard it is (e.g. a solution to a puzzle that takes a year to solve means the puzzle must have been created at least a year ago). Since the exact puzzle being solved is specific to the message and signature, the message and signature must have been created before the puzzle.

Conceptually, the scheme is neat but it has a number of practical drawbacks:

You can't put an exact bound on the resources available to the signer and therefore cannot timestamp accurately
No puzzle of this type is known that is (a) inherently sequential (parallel computing does not help) and (b) can be created with the solver not knowing (or efficiently computing) the solution. For example, time-release crypto has (a) but not (b). Hash-based proof of works (like in Bitcoin) have (b) and not (a).
The signer must devote an entire CPU to solving the problem for as long as it takes


Are there any quantum-resistant symmetric encryption schemes? It seems that quite a few currently available encryption schemes will possibly be broken by quantum computing. Are there any symmetric encryption schemes that will remain unbroken (either because of their design or by increasing the key size)? In particular are there any such schemes that may be used with a single key in a non-deterministic manner?

Yes; virtually all of them. Quantum computers give a quadratic speedup on a general search problems (so key lengths need to double), but I don't know of any symmetric schemes in actual use for which quantum computation gives a bigger speedup.


Factoring kind of problem Let's say we will choose some 256-bit random $b$ and we will find the smallest $d$ such that:
$\frac {2^{d}-1}{b} = s$
Now compute $z \equiv s \pmod{2^{128}}$. If I will give you only $z$ - is it possible to compute $b$ in some acceptable time? Is it hard problem? Do we know some algorithm to compute it? Is it save enough to use $z$ as a public key and $b$ as a private key?
EDIT:
I made one mistake, $z$ should be compute in another way - just take $s$ and cut all bits except $128$ least significant. So $z$ is composed of $128$ least significant bits of $s$. It does not change much, probably.

We know that $b$ is 256-bit number with
$$2^d - 1 = b\cdot s$$ and
$$z \equiv s \pmod{2^{128}}$$ use the modulo knowledge
$$z = s + k\cdot 2^{128}$$ for some $k \in \mathbb{Z}$ then
$$s = z - k\cdot 2^{128}$$ combine
$$2^d - 1 = b\cdot (z - k\cdot 2^{128})$$
$$2^d - 1 = b\cdot z - b \cdot k\cdot 2^{128}$$
take modulo $2^{128}$
$$ -1 \equiv b\cdot z  \pmod{2^{128}}$$
Therefore we learned 128-bit information about $s$ with simple arithmetic. It is not a good way to hide the private key.


Is $q(n)=1/n$ a negligible function? By definition - $q(n)$ is a negligible function if for every positive integer $c>0$ there exist an integer $N_c$ such that for all $x>N_c$  :

$q(n)<1/x^c$

So for the function $1/x$, if we take the positive integer $c=1$ then we need to find some $N_c$ such that for every $x>N_c$:

$1/x<1/x$

$=>$ Definitely such $N_c$ does not exist then $1/x$ is not a negligible function.

Is that sufficient?

Yes, that is sufficient.

I realise this isn't the most helpful of answers, but I'm not quite sure how we're supposed to deal with questions that lend themselves so neatly to one word answers. Certainly it seems wrong that something that has been solved should continue to sit in the 'unanswered questions' column!


Schnorr's identication protocol Schnorr's identification protocol is said to be a honest verifier zero knowledge protocol. Does it imply it will not work if the verifier is dishonest?
I'm wondering if this is the case, it would mean that a honest prover will always be denied authorization by the misbehaved verifier.

No, this is not the case. We can't guarantee an honest prover is verified by a dishonest verifier (they could always lie and say "no, you failed"), but they could very well be authorized by the dishonest verifier (in addition to lying and saying "you passed" for everyone, they could act like the honest verifier if it's to their advantage). A dishonest verifier can generally do anything, so it's impossible to say anything about whether the prover will be verified by them. In addition, the most likely sort of dishonest verifier (the one who seems to be following the protocol, such that a third party seeing the messages doesn't know they're dishonest) will always authenticate honest provers.

What "honest verifier" refers to is not the authentication bit; it's about zero-knowledge. We can't stop a dishonest verifier from refusing to authenticate an honest prover; however, we might be able to keep them from learning about the secret. For honest verifiers, who select the challenge at random, we can prove that the honest verifier cannot be learning anything about the secret. But this proof doesn't work with a verifier who selects the challenges very carefully; there's no known proof that they can't learn about the secret (other protocols have proofs that a cheating verifier can't learn anything, but Schnorr does not). That doesn't mean we know they can learn something; we don't know one way or the other.


Is an android encrypted SDcard readable/decryptable easily by a desktop machine? If I encrypt my SDCard on my android phone using the built-in encryption software, and my phone dies for whatever reason, would I be able to easily by just using the pin/password to access that data later on my desktops [OS X, Windows and Linux]?

The Android developers page on Full Disk Encryption seems like it has all the info you want, and more! It talks about encryption on the main internal disk (/data), I will assume that it uses the same mechanism for encrypting the external SD Card.

In a nutshell:

When your turn Android Disk Encryption on, it generates an AES-128 key which it uses to encrypt the drive (called the master key). It then takes your Pattern / PIN / Password and uses that to derive a second AES-128 key which it uses to encrypt and store the master key on disk. You know how the first thing Android does during boot-up is ask for your PIN / Password? That's because it needs it to decrypt the master key so that it can decrypt and mount the main filesystem. The reason for having two AES-128 keys is that if you change your Pattern / PIN / Password, it just has to re-encrypt the master key file, not the whole disk.

Is it decryptable on a desktop?

Theoretically, yes.

The location of the master key file is no secret, so if you know the PIN / Password, and you know which key stretching function Android uses to turn this into an AES-128 key then you should be able to decrypt the master key, and then dercrypt the disk. Whether there is freely-available desktop software to do this, or you would have to write your own, I have no idea.

(One possible hitch is that I don't know if it stores a copy of the master key file on the external SD Card, or if there is just one copy on the internal flash memory chip. Finding a way to access the internal flash memory on the dead phone might prove to be the hard part here. You could probably check pretty easily if there's a key file on the encrypted SD Card by popping it into your laptop and looking.)


Can I convert $F_{q^{12}}$ to $F_q$? I seeing a paper about Elliptic curve based proxy re-encryption.
And I want to implement this through BLS12-381 Curve.
However, When looking at the documentation for paring or the library, the value of $F_{q^{12}}$ is output as the output of pairing.
The paper requires:

Let e : $G_1$ × $G_1$ → $G_2$ be a bilinear map, z = e($G_1$, $G_1$) ∈ $G_2$
And need to compute (zrG + Pm)

How can I multiply z in $F_{q^{12}}$ and $rG$ Point in $F_{q}$from "$z$ $rG$"?
Should I replace $F_{q^{12}}$ with $F_{q}$? If so, how?
And please let me know what to look for to get relevant knowledge.

The paper writes $z^r \cdot G$; however $z^r$ is a member of the extension group $\mathbb{F}_{q^{12}}$, while point multiplication is formally defined over the integers; you ask "what are we supposed to do here?"
Well, going through the paper, it appears that if we rewrite that equation to $h(z^r) \cdot G$, where $h$ is a function from $\mathbb{F}_{q^{12}}$ to $\mathbb{F}_{q}$, that works (assuming, of course, we rewrite the decryption process similarly), so we have:
$\text{Encrypt}(pk, m) = (r \cdot pk, h(z^r) \cdot G + Pm)$
$\text{Decrypt}^1(C, sk) = B - h( e( A, sk^{-1}G )) \cdot G$
$\text{Decrypt}^2(C, sk) = B - h( A^{1/b} ) \cdot G$
(see the paper for explanation of the various notations, and the reencrypt process doesn't change)
Any deterministic $h$ would work (in the sense that the protocol will work), as can be seen by going through encryption/reencryption/decryption steps.  My inclination would be to use a hash function.


How long will brute force of salted SHA-512 hash will take, if salt is known and possible characters in password are known? Suppose I know that the password is composed of characters [A-Za-z0-9], length is unknown, but maybe less than 8. If I have information about the salt use to perform hashing, and also hashing algorithm(SHA-512) is known, how long will brute-forcing the password will take? what is the mathematical relationship with time for password lengths = 1,2,3,4,5,6,7,8?

So your alphabet is 26 + 26 + 10 = 62 characters. If they are completely random (they often are not completely random, but OK) then each time you add a character the brute forcing will be 62 times more difficult.

So if you have a 8 characters then you will need a maximum of 218,340,105,584,896 tries. As the password could be any of these, the average search time would be half that number.

If you need to search for multiple passwords then you would still only need a single pass - so testing more password hashes at once is more efficient. If each password is salted separately then this speedup doesn't apply though.

You can simply calculate the table using a WolframAlpha query.

Notes:

How long each try will take depends of course on the speed to check each possibility;
This problem is "embarrassingly parallel", so if you've got more computers you can simply throw them in;
The hash algorithm itself doesn't make a difference when it comes to the order of the tests (the number of tests to perform), although it of course does influence the time it takes to test each possibility.
The salt will not make a difference during testing of one password hash, except if it triggers another block to be hashed; for SHA-512 this is not likely.


Fault-based transition for crypto proof (a la Shoup) with big probability of fault - does it work? background

In [Shoup2004], Victor Shoup synthesizes the 'sequence of games' technique for proving security properties:
Roughly it consists in a sequence from game_0 to game_n, game_0 consisting in the property. You prove that for any two games the two probability of success are negligibly close, then you prove that the probability of success of game_n is negligibly close to the target probability; it follows that the probability of success for game_0 is negligibly close to the target probability, which proves the property.

Shoup identifies 3 types of transitions, namely indistinguishability-based, failure-event based and bridging step (which is a bit apart).

In the failure-event based transition, the two games are equivalent unless a failure event $F$ happens; then Shoup states:

  to prove that $Pr[S_i ]$ is negligibly close to $Pr[S_{i+1}]$, it suffices to prove that $Pr[F]$ is negligible.

EDIT writing it as a theorem could make it clearer:

Theorem(Shoup's Framework)
Let $(G_i)_{i=0..n}$ be a sequence of games with their respective "Fault" event $(S_i)_{i=0..n}$
If $\forall i ~ |Pr[S_i]-Pr[S_{i+1}]|$ negl. ("transition lemmas")
and If |Pr[S_n] - Target| negl.
Then |Pr[S_0] - Target| negl.

Lemma(Shoup's Fault-based transition)
If $Pr[S_{i+1}|$ not $F] = Pr[S_i]$
And $Pr[F]$ negl.
Then $|Pr[S_{i+1}]-Pr[S_i]|$ negl.

Question

It is not hard to prove that this is true. However I think that the requirement on $Pr[F]$ is way too strong: one can prove security with much more frequent faults.
Namely I think I can prove it holds for non-negligible $Pr[\bar{F}]$ (proba of non-fault) as soon as the success probability $Pr[S_{i+1}]$ is negligibly close to the target probability (which is 1/2 here, didn't look if it works for target 0).
The latter ("$Pr[S_{i+1}] - 1/2$ negligible") will prove right later in the proof anyway thanks to the other transitions.

Question: does the following theorem hold, and has it been added to Shoup's framework for crypto proofs ?

Argumentation

Lemma(My Fault-based transition):
(we assume Target = 1/2)
If Pr[$S_1$ | not F ] = Pr[$S_0$]
and If Pr[not F] non-negl.
and If |Pr[$S_1$]-1/2| negl
Then |Pr[$S_1$]-Pr[$S_0$]| negl.

proof

Let "OK" be then event "not F".
When a failure event happens,
the algorithm can still make a random guess before halting,
thus $Pr[S_1 | \bar{OK}] = 1/2$

$Pr[S_1] \geq Pr[S_1 | OK ].Pr[OK] + Pr[S_1 | \bar{OK}].Pr[\bar{OK}]$
$Pr[S_1] \geq Pr[S_0].Pr[OK] + ½ (1 - Pr[OK])$
$Pr[S_1] \geq Pr[OK](Pr[S_0] - ½) + ½$
$(Pr[S_1] - ½)\frac{1}{Pr[OK]} + ½ \geq Pr[S_0]$
$Pr[S_0] - Pr[S_1] \leq (½ - Pr[S_1])(1 + \frac{1}{Pr[OK]})$

Then since $(½ - Pr[S_1])$ is negligible
and $(1 + \frac{1}{Pr[OK]})$ is polynomially bounded,
$Pr[S_0] - Pr[S_1]$ is negligible which ends the proof.

Recall that the hypothesis "$|Pr[S_{i+1}] - 1/2|$ negligible" will be proven right later in the proof, so it's not a problem having it.

My experience of such proofs is that often you're proving a much stronger statement: in any execution of Game i+1, either everything is distributed identically to Game i or else F must have happened. In other words, the conditional distribution of game i+1 conditioned on F not happening is identical to the distribution of Game i.

For example, one of Bellare's applications of this technique is the "poisoned point" principle: you choose the value of a hash function or similar at a particular point. As long as the adversary does not query the function at this particular point, the new game is identically distributed to the old one. If he does query this point, you abort.

Of course what you will argue next is that since you chose your poisoned point at random, the chance of the adversary querying this exact point is negligible. But the actual game-hop doesn't depend on the probability of F happening, it only says either all is well or else F must have happened.

Failure events with non-negligible probabilities happen frequently in hybrid arguments. They tend to make for very lossy reductions of course but the principle stays the same, the hop itself is Pr[S_{i+1} = 1 | not F] = Pr[S_i = 1] and then you compute the probability of F in a separate step to get your "concrete security" constants.


Is it an example of bilinear pairing? Consider a bilinear pairing $e: G_1 \times G_2 \rightarrow G_T$. Let's assume, $G_1 = G_2 = G_T = (\mathbb{Z}_n,+)$, i.e. additive group of integer modulo $n$ and $e(x,y) = xy$ mod $n$. Isn't it an example of bilinear map?

$G_1 = G_2 = G_T = (\mathbb{Z}_n,\ast)$, i.e. multiplicative group of integer modulo $n$ and $e(x,y) = y^x$ mod $n$, is it still a bilinear map?

Can there be other bilinear map defined over $\mathbb{Z}_n$?

EDIT:

Actually all my question were to understand Groth-Sahai proof system. Here, they have recast the general equation to fit the form of a quadratic equation. (See teh highlighted part below). But, how can they remark that all maps with $f(x,y) = xy$ mod $n$ will satisfy properties of bilinear pairing?

Not only is $\mathbb G_1 = \mathbb G_2 = \mathbb G_T = \mathbb Z_p$ with $e(x,y) = x \cdot y \pmod{p}$ an example of a "bilinear group" (a triple of groups with a bilinear map) but every bilinear group of prime order is isomorphic to one of this form. So anything you want to know in principle about such groups, you can calculate on this example. I've used it myself before now as a sanity-check for some protocols.

The security of e.g. ECC implementations of bilinear groups rests on the fact that the isomorphisms to the $\mathbb Z_p$ form are not (thought to be) efficiently computable.

Of course it's cryptographically useless --- discrete logs are easy, as commenters have pointed out. But cryptographic definitions usually come in two parts, functionality and security. An encryption scheme for example is a triple (KeyGen, Enc, Dec) with a correctness property; the scheme where Enc and Dec are the identity maps is therefore an encryption scheme. Only when we introduce security requirements in a second step does this scheme turn out to be lacking. The same goes for $\mathbb Z_p$: it certainly is a "bilinear group" but not a particularly secure one.

EDIT: to answer your last question whether one can define other bilinear maps over $(\mathbb Z_p, +) \times (\mathbb Z_p, +)$: note that $1$ is a generator of $\mathbb Z_p$ so $e(x,y)$ is completely determined for all $x,y$ by $e(1,1)$. If you want a non-degenerate bilinear map, $e(1,1)$ has to be a generator of $\mathbb G_T = \mathbb Z_p$ too, and whichever generator you pick, the structures that you get are isomorphic. If you drop the non-degeneracy requirement, the map that sends everything to $0$ is a different, trivially bilinear one.


HMAC and SHA-1 weakness? Imagine the following scenario:

Select known data (known to several parties)
Mix data with secret key and generate SHA-1 hash
Mix SHA-1 hash with secret key and generate HMAC

The purpose is to verify the integrity of the data - to ensure that data has not been altered after the generation of the HMAC.

My question is:

Is there any weakness to using a SHA-1 hash rather than for example SHA-256 in this scenario?
Does the use of SHA-1 make it easier to for example extract the secret key compared to SHA-256?

Select known data (known to several parties)

If the data is already known then there is no reason to distribute it. You could just refer to it.

  Mix data with secret key and generate SHA-1 hash

That's what you use a HMAC for.

  Mix SHA-1 hash with secret key and generate HMAC

You'd normally use your symmetric key only once.

  Is there any weakness to using a SHA-1 hash rather than for example SHA-256 in this scenario?

It's got smaller output and therefore less protection against brute force attacks, but HMAC in itself isn't vulnerable. SHA-1 is however under attack, with collision resistance the first to go. If you manage to muck up step 2 then you're likely in trouble. If you use HMAC then you may not be directly vulnerable to current known attacks. But attacks only get better.

  Does the use of SHA-1 make it easier to for example extract the secret key compared to SHA-256?

No, the fact that SHA-1 may be less collision resistant doesn't mean that the algorithm is reversible.

That said, unless there are pressing requirements to use SHA-1, e.g. backwards compatibility, I would rather choose SHA-256 or SHA-512/256.


Is there a way to encrypt multiple sets of data into one result, with separate keys decrypting each set of data What I am picturing is something like this:

Block A: "Hello, how are you today?"

Block B: "The weather reminds me of summer."

I encode this, giving me two keys and a resulting encrypted block e.g.

AP: 2da93742a7340ad12372aff
BP: 023cd97d40293d7c4027947
DATA: ksdjhfksdjhf0wddfg74059r7sdhdkfh

Whereas decrypting with AP would give me "Hello, how are you today?" and with BP would correspond to "The weather reminds me of summer.".

It is possible that you have some additional implicit constraints that invalidate the following solution.
But as the question currently stands the following might give you what you are looking for:

Assume we have a authenticated symmetric encryption scheme. (Say encrypt-then-mac with a blockcipher in a suitable mode.)

We get our two messages $m_0,m_1$ and two keys $k_0,k_1$.
To make things simpler, we assume that the messages have the same length and that our encryption scheme will output ciphertexts of the same length for inputs of the same length.

We encrypt $c_0 \leftarrow \mathsf{Enc}(k_0,m_0)$ and $c_1 \leftarrow \mathsf{Enc}(k_1,m_1)$.
We then choose a random bit $b \in \{0,1\}$ and output the ciphertext $c=c_b\Vert c_{1-b}$.

To decrypt, given a key $k$ and a ciphertext $c$, we split $c$ into two halves, and try to decrypt each half.
As the encryption scheme is authenticated, decryption will only be successful for the half actually encrypted under $k$ except with negligible probability. We then simply output this message.

The CPA security of this scheme easily reduces the the CPA security of the authenticated encryption scheme.
If we need CCA security, it should be enough to add an additional MAC over the complete ciphertext with a third key, and include that third key as part of what you call AP and BP, i.e. the two keys.

The Security of the encryption scheme ensures that given one of the keys you can decrypt only exactly one of the messages.
Furthermore, because the order of the ciphertexts is random, you cannot learn whether your key/message is the first or second one.


XMSS WOTS+ private keys vs XMSS private keys The length of WOTS+ private key is an array of length "len" of n-Byte strings. Meaning, for w=16 and n=32, the len is 72. So the WOTS+ max length of the private key is 72, meaning only 72 messages can be signed.
Now my problem is, when you read about XMSS Keys, it says that the private key is defined by 2^h OTS private keys, h is usually 20 so 2^20 keys. What do I generate first? With the first definition I can only have 72 private WOTS+ keys and the second one extends it to over a milion.
Do I have to ignore the fact of array[len] n-Byte private keys and generate just 2^h WOTS+ keys using the chaining function?

Do I have to ignore the fact of array[len] n-Byte private keys and generate just 2^h WOTS+ keys using the chaining function?

In practice, what we do is follow the recommendations of section 4.1.11 of RFC 8391, and generate all the WOTS+ private keys dynamically as needed from a single secret seed.
The RFC recommends a two step process; you use the PRF function (with the ADR with the index of the WOTS+ key you're retrieving) to generate an n-byte value they denote as S_ots; then for each WOTS+ chain, you run the PRF function again on the S_ots value to generate the starting value for that chain.
And, if you're implementing XMSS^MT, you'll also want to pay attention to section 4.2.6, which adds a third layer to distinguish between different XMSS trees.  I suspect that step isn't needed (the ADR structure already distinguishes that); on the other hand, it's fairly cheap to follow the RFC's recommendations.


Is SRP post-quantum secure? Is SRP-6a post-quantum secure? If it is not post-quantum secure, do any post-quantum secure alternatives similar to SRP-6a exist?

No, since finding $a$ allows offline checking of passwords. $\:$ No, although I can't back this part up.


(How) Can we use HOTP for file encryption? I recently went through the list of available KeePass plug-ins and noticed one that advertises support for HOTP as a means to derive the database key.

Now I trust the developer of this plug-in who is Dominik Reichl, who also signs the KeePass releases, so I doubt this is some sort of KeePass-only feature that won't actually increase file security.

How can we use HOTP to as a factor to derive a key suitable for file encryption?

This is especially puzzling as it claims support for any HOTP client that complies to RFC 4226, which advises to compute the shared-keyed HMAC of a counter and then convert this into a decimal number and I really don't understand how one could leverage this number into a good source for the key.

I had only a quick read through the source, and I am not particularly fluent in C#, so I may have gotten something wrong. That said the process appears to be:

Generate a random encryption key, encrypt the database with it.
Generate (up to six) HOTP tokens, derive a key from those, use that to encrypt the database key.
To read:

Ask for the HOTP tokens, derive the key, check that it matches.
Decrypt the database key, so it can be read.
Generate new HOTP tokens, use those to re-encrypt the database key for  next access.

So by hashing several HOTP tokens you get enough entropy for a strong key – up to ~160 bits if you use the full six tokens with eight decimals each. Additional computational entropy may be added by the iterated hashing process.

By always encrypting the key with a new set of tokens you ensure they are only used once.

The HOTP secret is stored in encrypted form, so it can only be used to derive tokens when a set of matching tokens has been received.


What is the meaning of "trapdoor" in cryptography? I do not really understand the meaning of a "trapdoor" in cryptography, so here are my questions:

What is the meaning of trapdoor and how can I convert a word or string using a trapdoor in cryptography?
Is a hash function considered to be a trapdoor function, or is a trapdoor function some kind of encryption?
What is the result of trapdoor function, a numeric or a string result?
What does trapdoor itself mean? Does it mean a private key is used in a trapdoor function or does it point to the string after transmission?

It would be nice if you could explain with examples.

A trapdoor function is a function that is easy to perform one way, but has a secret that is required to perform the inverse calculation efficiently. That is, if $f$ is a trapdoor function, then $y = f(x)$ is easy to compute, but $x = f^{-1}(y)$ is hard to compute without some special knowledge $k$. Given $k$, then it is easy to compute $y = f^{-1}(x, k)$. The Wikipedia article also contains a straight-forward explanation.

The analogy to a "trapdoor" is something like this: It's easy to fall through a trapdoor, but it's very hard to climb back out and get to where you started unless you have a ladder.

A hash function is not a trapdoor function because it is not reversible. Instead, it's called a one-way function. A one-way function is similar to a trapdoor function in that it's easy to compute both and it's very hard to reverse both, but there is no special key that allows you to reverse the one-way function.

To compare the definitions of one-way and trapdoor functions, I double-checked teaching sources I'm familiar with, including:

Boneh's lecture notes
Wagner's lecture notes
Bellare-Rogaway's lecture notes
The Handbook of Applied Cryptography (PK systems, hash functions)

They all categorize (sometimes implicitly) trapdoor functions as a subset of one-way functions: Trapdoors are a one-way function with the extra restriction that they have a secret for calculating the inverse.

For example: RSA is a one-way trapdoor function, but SHA-1 is just a one-way hash function. Discrete exponentiation is also (supposedly) just a one-way function, since there's no key information about the group that can be used to calculate the discrete logarithm efficiently.

That said, on a pragmatic note I have noticed that common Internet usage often mixes the terms "one-way" and "trapdoor" interchangeably, which no doubt causes confusion.


Can I truncate a CSPRNG psuedorandom number? This might be too broad to apply for all CSPRNG, but it might apply for the general case, I'm not sure. I need this specifically for python os.urandom() and SystemRandom() which get a seed  from /dev/urandom, and on Windows CryptGenRandom(),

Is it possible to truncate or even modify the random number but still retains its randomness. The reason I need to do this is because the OS has nanosleep and the overflowing digits I will need to cut off.

The idea for the security notion of Cryptographically Secure Random Number Generators (CSPRNGs) is that at the very least they are as good as Pseudo-Random Generators (PRG) which is why I'm applying their security notion of Indistinguishability.

This says that the probability that somebody can distinguish a PRG from a truly random sequence is better than guessing is negligible.

Now what you want to is to truncate the output of a CSPRNG (that is, you straight-up discard certain bits from the output). Now assume the result was insecure. As this truncated part would also be output by the actual CSPRNG, you could then "just" use this sub-part of the output and use the weakness we assumed to distinguish the CSPRNG's output from random. Now we assumed this to be impossible, so it can't be that such a weakness as assumed above exists and thus it must be secure.

A similar argument applies if you apply a public bijection on the output or a part of it.


Memory hard key derivation (password hash) using AES encryption I am restricted on a certain environment involving PHP and am currently unable to implement new memory hard hashes such as scrypt (and I am not trying to compete with the likes of scrypt).

My current key derivation is simply an iteration of HMAC (password + salt). But it seems that using AES or other encryption ciphers, one could construct a fairly simple, memory-hard key derivation function using build-in PHP capabilities such as HMAC and AES encryption (assuming PHP is compiled with openssl support).

Pseudocode is:

salt = random (any length between 512bit and several MB)
M[0] = HMAC (sha512, password, salt)

for i=1 to N
    hash = HMAC (sha512, M[i-1], M[0] + i)
    M[i] = AES-128-CBC (iv = substr(hash,0,128), key = substr(hash,128,128), data = salt + hash) // substr lengths in bit

result = M[N]

for i=0 to N
    result = HMAC (SHA512, result XOR M[i], M[N-i])

Because of the second for loop, the entire matrix M needs to be present in memory, which would hopefully make it memory hard. Then one could configure salt size versus N to see what gives the desired results of memory usage and cpu usage within a reasonable amount of time.

I would appear to me that AES related-key attacks are not an issue in this scheme also because of the second for loop which hashes all matrix elements. The purpose of using AES is to obtain a larger randomized text for each array element than a 512 bit hash output would be. Since iv and key are unique and are related only through HMAC hashing, this use of AES would also appear to be secure. Even so, I appreciate your input. Creating one's own crypto is not encouraged, which I understand. Even if I do not end up using this, your feedback would really help me improve my understanding of these matters.

Also, I wonder whether the length of the salt affects the security of the function? I.e. if the salt were to be very long, say several MB, would that make it less safe than if the salt was short such as 512 bit (less reliance of encryption, more HMAC hashes)?

EDIT:

For theoretical purposes and NOT in order to create my own cryptography, based on the comments of otus, it appears that in principle, higher memory-hardness is achieved by a more intense shuffling of the matrix.

Therefore, one could e.g. generate a matrix of a size rounds * x, which is then hashed rounds times, but each hash made up of XOR-ring x*2 matrix values. The example below (PHP code) shows it for x=4 (^ is the PHP XOR operator):

for ($i = 1; $i <= $rounds; $i++) {

    $result = hash_hmac ('sha512',
                $result . ($matrix[$i] ^ $matrix[($rounds+$i)] ^ $matrix[($rounds*2+$i)] ^ $matrix[($rounds*3+$i)]),
                ($matrix[($rounds-$i)] ^ $matrix[($rounds*2-$i)] ^ $matrix[($rounds*3-$i)] ^ $matrix[($rounds*4-$i)]));

}

For 8 rounds, a matrix size 8*4 = 32 would be created, and then hashed with XOR combinations in the loop shown. The output below shows, which matrix index values (the $i in $matrix[$i]) would be combined in each HMAC round:

Computing 1 ^ 15 ^ 17 ^ 31 AND 7 ^ 9 ^ 23 ^ 25
Computing 2 ^ 14 ^ 18 ^ 30 AND 6 ^ 10 ^ 22 ^ 26
Computing 3 ^ 13 ^ 19 ^ 29 AND 5 ^ 11 ^ 21 ^ 27
Computing 4 ^ 12 ^ 20 ^ 28 AND 4 ^ 12 ^ 20 ^ 28
Computing 5 ^ 11 ^ 21 ^ 27 AND 3 ^ 13 ^ 19 ^ 29
Computing 6 ^ 10 ^ 22 ^ 26 AND 2 ^ 14 ^ 18 ^ 30
Computing 7 ^ 9 ^ 23 ^ 25 AND 1 ^ 15 ^ 17 ^ 31
Computing 8 ^ 8 ^ 24 ^ 24 AND 0 ^ 16 ^ 16 ^ 32

One concern there is the question of whether that many XOR operations would create a lot of of collisions and thus somehow security, even though each result is HMAC hashed. It would be interesting to get people's comments on that, with the reasons behind it.

Your key derivation function is not particularly memory hard.

The second loop walks the array in order, so an optimized implementation which an attacker would use can avoid the whole array, keeping only some elements in memory at a time.

For example, you can halve the memory use by only storing the second half of M initially. Then for the first N/2 iterations of the loop you only need to calculate the i'th element from the i-1'th. Then you would recalculate the first half of M instead and continue as earlier. You need about twice the computation for half the memory use, and can extend the tradeoff further. This is much worse (better for the attacker) than scrypt's tradeoffs.

If you use a salt length longer than 512 bits, the attacker can reduce the size of M[i] by only storing the hash value at that iteration during the first loop. They can then derive the whole value when needed in the result loop because it only depends on the hash and salt. This means a memory savings factor of salt length/512 bits for a computational overhead of less than 3x (since they need to recompute the AES twice in the second loop, but none of the hashing needs to be repeated).

There is probably a way to fix these, but the main issue is that you are rolling your own algorithm. Normally algorithms need to face years of cryptanalysis before they are trusted, at least unless they have a security proof reducing them to something already known/believed to be secure.

Instead, you should if at all possible use an existing algorithm, preferably an existing implementation because there are things that can go wrong implementing one yourself. If you want memory hardness, scrypt is the most accepted and widely available algorithm (tradeoffs exist, but they are expensive), though Argon2 which recently won a competition for password hashing algorithms might be an option soon (you will not find implementations for most languages yet).


What is the use of pre-computed points in ECC? I am trying to understand the use of pre-computed points in ECC for ECC signature, verification, key generation, and so on. After searching on the internet, I understand that pre-computed points aid faster execution. However, I am unable to get the complete picture. Can someone help with an example? Also, once the pre-computed points are calculated, are these secrets?

Can someone help with an example?

Ok, here's a simple example; suppose we precompute a table that contained all the points of the form $(a \cdot 256^b) G$, for $0 < a < 256$ and where $b$ be within the scalar we intend to support.
For example, the table (if we support 2 byte scalars) would contain the points $\text{0x01}G, \text{0x02}G, …,\text{0xff}G, \text{0x0100}G, \text{0x0200}G, …, \text{0xff00}G$
Then, to compute the value $0x1234G$, we would look up $0x1200G$ in our table and the value $34G$, and then add them $0x1200G + 0x34G = 0x1234G$; we just computed the point multiplication with a single addition (and some table lookups); using a table without precomputation would use at least 13 point additions/doublings.
It should be obvious how this table can be extended to support longer scalars; if we support 32-byte scalars (appropriate for 256-bit curves), we can do any point multiplication using 31 additions (and a large table).
There are a number of ways to build the table (including methods with much smaller tables and not that much more computation required); I picked this example solely because it was easy to understand.

Also, once the pre-computed points are calculated, are these secrets?

Only if the base point is secret.  As this is most commonly used with the public curve generator point, there is usually no need.
Also, the tables/algorithms can be set up to run in constant time; however that is rather trickier.


Definition of Short Authentication String I am studying for my cryptography final and I passed by the following term: short authentication string. Please, can anyone explain it to me, thank you very much.

The Short Authentication String (SAS) is used in various protocols, but in short, SAS is produced to transfer a long authentication tag into a smaller so that the two users can verbally verify. For example;

In Diffie-Hellman key Exchange, there is always a risk of Man-in-the-Middle attack. To ensure that there is no attacker in the first session, that there are no shared secrets yet, a SAS can be used. After verbal communication, if the values don't match then Man-in-the-Middle attack is detected.

Some Protocols that uses SAS;

ZRTP: Media Path Key Agreement for Unicast Secure RTP
Short Authentication Strings for TLS
Device Pairing Using Short Authentication Strings