Signature security proof in the Random Oracle model As a study case, I consider the BLS signature scheme, but the following question is relevant in the general context of security proofs in the Random Oracle model.

Let us briefly recall BLS signature scheme:

Let $e:G \times G \to G_t$ be a bilinear group scheme. Let $g$ be a generator of the group $G$, and let $a \in \mathbb{Z}^*_p$ be a random field element. We denote by $H$ a function that serves as a random oracle.

Keys: secret key is $a$, public key is $(g, g^a)$.
Sign: compute $m \mapsto (m, \sigma = H(m)^a)$.
Verify: check the equality $e(g, \sigma) = e(g^a, H(m))$.

The authors prove that this scheme is secure (or more specifically - secure against existential forgery under adaptive chosen message attack) by describing an algorithm $\mathcal{A}$ that given a forging entity $\mathcal{F}$ breaks computational Diffie-Hellman in $G$.

  The proof assumes that the algorithm $\mathcal{A}$ emulates the random oracle, meaning that every query by $\mathcal{F}$ to $H$ is actually answered by $\mathcal{A}$. My question is, isn't this a very, very strong assumption?

If instead we assume that the random oracle is some third party that both $\mathcal{A}$ and $\mathcal{F}$ can only query but not affect (like in every real-world use case) than this proof completely breaks.

Also, if we provide a security reduction without this strong assumption, our reduction might be far more efficient.

This was discussed by Coron in 1.

You are actually asking why the random oracle can't just be some uncontrollable ideal random oracle.
In fact Bellare and Rogaway when introduced their Full Domain Hash scheme (FDH) in the seminal works 2,3 used this uncontrollable random oracle to analyze the security reduction for FDH.

The thing about using reductions to prove the security of, let's say a signature scheme, is that the reduction security depends greatly on the probability to break the underlying assumption, let's say the CDH assumption. So ideally, if the reduction enables to break CDH problem with probability 1 it means the signature scheme is pretty much secure as solving the CDH problem.

But what happens if this probability is much lower than 1?  Well, the signature scheme security becomes rather weak.

As Coron mentions in 1, allowing $\mathcal{A}$ to control the random oracle gives a tighter security bound on the FDH signature scheme than the one shown by Bellare and Rogaway.

The main thing about the tighter bound is that it does not depends on the number of queries requested by the forger, but rather only on the number of queries for signatures (which in practice is much lower than the number of hash queries such forger can do). A better bound enables one to use more efficient signature scheme.

To conclude, using a specific hash function does not say that this is an assumption of the model, it is merely a way to make the bound tighter.


Is it considered insecure in an HOTP implementation to publicly provide the next counter? I am working on a project that needs to securely authenticating one or more smartphone clients with a server running on a microcontroller so it has very limited resources.  I have found plenty of lightweight HMAC hashing libraries.  Therefore it seems to me that an HOTP authentication mechanism would be feasible on the limited resources of the microcontroller.

My concern however is with the authentication of multiple clients.  I know that ideally (or so I am told) in an HOTP implementation each client would have its own shared secret key with the server.  However I don't have the resources to have a database of shared secret keys on the microcontroller.

I was wondering if it would be OK to have all clients and the server share the same secret key and for the server to tell any client that requests it what the next expected counter would be.  This would be an unauthenticated request that would do nothing more than provide the expected counter.  The client could then issue an authenticated command with an HOTP code in it (using the provided counter) that would actually perform the desired action.

As per the RFC that defines HOTP each counter would only be accepted once even if the server gave the same counter to 2 clients, in this case the first one in wins and the second needs to get the next counter.

I know this isn't quite ideal, but it is the best implementation I can think of. Security is about balancing weakness with usability or in my case server constraints.  This is for a door unlocking mechanism for what its worth.  I think that my implementation would be at least as good as a typical physical key.

What are the security implications and trade offs here?  Is there a better implementation (HOTP or not) given the constraints of the inability for the server to maintain multiple keys?

RFC 4226, section 7.5 defines two shared key generation schemes: deterministic and random.  I would suggest that you use the deterministic scheme, which only requires the server to store a single "master key":

  "Deterministic Generation

  A possible strategy is to derive the shared secrets from a master
   secret.  The master secret will be stored at the server only.  A
   tamper-resistant device MUST be used to store the master key and
   derive the shared secrets from the master key and some public
   information.  The main benefit would be to avoid the exposure of the
   shared secrets at any time and also avoid specific requirements on
   storage, since the shared secrets could be generated on-demand when
   needed at provisioning and validation time."

Addendum: To also avoid storing a separate counter value for each client, you could still use a shared counter for all clients as you suggest, at least as long as the intended purpose of the server is such that it's unlikely for more than one legitimate client to attempt to authenticate simultaneously.

However, simply sending a counter value to the client and having the client reply with the corresponding one-time password could allow an attacker masquerading as the server to send an artificially high counter value to the client and store the response for later use.  (If the client enforces the monotonicity of counter values, this could also render the client temporarily unable to authenticate until the server's counter catches up with the bogus counter value sent by the attacker.)

One way to avoid this attack, and eliminate the extra round-trip to request the counter, would be to use a timestamp as the counter, something like this:

When the user want to authenticate, the server sends to the server the current timestamp $T$, its client ID $i$ and the one-time password $P = HOTP(K_i,T)$, where $K_i$ is the client's HOTP key.
On receiving an authentication request $(T,i,P)$, the server checks that:

$i$ is a valid and non-revoked client ID;
$T$ is a valid timestamp, and is not too far in the past or the future;
$T$ is greater than the timestamp $T'$ for the previous successful authentication; and
$P = HOTP(K_i,T)$, where $K_i$ is the client key derived from the client ID $i$ and the master key $MK$.

If all these checks pass, the client is allowed access.

Thus, the server only needs to store the master key $MK$, the last successful authentication timestamp $T'$, and possibly list of revoked client IDs.  (This ability to revoke access for compromised clients is one of the main advantages of not sharing keys between clients.)

The valid time window allows for some degree of clock skew between the clients and the server, and should be set to reflect a balance between that and security requirement.

An attacker intercepting the authentication request in this protocol can't really do much: if they pass the request on to the server, the password they just captured becomes useless (and if the client and server encrypt any further communications with their shared secret $K_i$, the attacker can't even eavesdrop on it); if they don't, the client will know something went wrong, and in any case the password will still expire after the limited time window passes (and possibly sooner, if the client tries to reauthenticate and succeeds).

(Obviously, the protocol also needs to protect against brute force attacks, either by implementing request rate throttling as recommended in the HOTP spec, and/or by making the password long enough.  Indeed, if the password need not be human-enterable, one could just as well — and, indeed, preferably — use the full non-truncated HMAC output as the one-time password.)


How to make an AES implementation using lookup tables immune to cache timing attacks? I recently made a very naive implementation of AES using lookup tables, but it's totally unsafe because of timing attacks. I am not interested in using the processor specific instructions for AES, which is used practically, since I wanted to make a cool project with AES ! Is there any way to prevent my AES implementation from being insecure  ?

When it's possible, a solution is to ensure that table lookups at data-dependent addresses are constant-time and without action on the cache, by

Disabling cache (use and loading/invalidation) during such table lookups. That's heavily system dependent, though. Some CPU architecture have special instructions, addressing modes, or mode bits allowing this, or allow to control which addresses can be cached.
And ensuring that there is no other condition causing timing variations in table lookup; I'm in particular thinking of an extra cycle due to internal carry in the addition of base address and index on some CPUs. On many 8-bit CPUs, that means starting the 256-byte table at an address multiple of 256.

It is not quite as safe to:

Flush cache before table lookup, because in some attack scenarios an adversary could examine the cache state.
Fill cache with the full table before use, because in some attack scenarios an adversary or a coincidence could partially flush the cache.

Other techniques aim at making it impossible to measure timing dependencies. For example, we may start a timer before encryption, set to a larger value than the worst-case encryption duration, then wait precisely until expiry of the timer after encryption. With a cycle-accurate timer, and if an adversary can not induce interrupts that make the duration of the encryption vary beyond the maximum forecast, and a host of other conditions, it is conceivable that timing variations in encryption are fully hidden. Beware that this could worsen leaks by other side channels (power, electromagnetic emissions).

None of this is general and portable. Other solutions have no such drawback: they just use no table lookups at data-dependent indexes, replacing them by constant-time expressions or table tookups at data-independent adresses. That can be made portable and reasonably fast when using bitslicing; see answers to this related question.

If speed is not an issue, a slow but simple and quite portable technique goes:

uint8_t lookup(const uint8_t table[256], uint8_t index) {
    unsigned j, r;
    j = r = 255;
    do
        r ^= ((-(index ^ j)) >> 8) | table[j];
    while(j--);
    return (uint8_t)r;
}

This works because -(index ^ j) has bits 8 to 15 each 0 or 1 depending on if  index==j or not, and the indexes in table[j] are not data-dependent.It might be necessary to inhibit a spurious compiler warning or/by inserting 0 before -.

It is also possible to use that (c >> j) & 1 does a lookup at index j in a $k$-entries 1-bit table defined by $k$-bit constant c, in a constant-time manner on CPUs with an at-least-$k$-bit barrel shifter and a compiler that uses it. That combines with the above: we can select among 32 constants each 64-bit according to 5 bits of the index (perhaps unrolling the loop), then use a 64-bit barrel-shifter to extract the 8-bit result according to the remaining 3 bits of the index.


How can the Enigma's plugboard settings be found with partially known plaintext? I don't quite understand the procedure described on wikipedia, is there a generalized procedure you can follow to rule out a pairing on the plugboard?

For example, let's say the cipher text is

XOIWN LUKLV FPHZH VMWPX GLIEV NZTTC EKYEB QJP

And the known plaintext is

ATTACKATDAWN

What would i have to do to find out the original wiring on the plugboard, or which possibilities can we rule out?

There is a much better explanation available. See Graham Ellsbury's page here for full details, and a summary below:

Intuitively, what one does first is to drag the crib (known plaintext) accross the ciphertext and rule out relative positions which map a plaintext letter to itself in the ciphertext (since it is known that the Enigma mapping has no fixed points).

Afterwards, for each hypothesized setting that is compatible with the plaintext ciphertext pair, one iterates the enigma machine according to the setting, until one gets a contradiction, for example, say that in the hypothesised setting X maps to Z. But after a number of iterations, X then maps to G. This rules out the initial hypothesized setting.

This requires automation of the process of checking all these settings in parallel, and that's where the bombe mechanism comes in.

I have condensed the example from that page below:

Example After the crib dragging, there is the possibility that

RWIVTYRESXBFOGKUHQBAISE

is the encryption of

WETTERVORHERSAGEBISKAYA

(since there is no letter mapping to itself in this shift of the crib with respect to the ciphertext), for one of the 60 rotor orders, 17576 rotor positions, 676 Ringstellung positions and 150,000,000,000,000 stecker swappings.

One still needs to find out which setting.

Now numbering the positions, we obtain the table

12345678901234567890123
RWIVTYRESXBFOGKUHQBAISE
WETTERVORHERSAGEBISKAYA

where the number above X and H is 10, that above B and K is 20, etc.

This means we can derive a relationship graph

So, if the crib is correctly matched with the ciphertext, we know that some setting of the Enigma will encode R as W and W as R in a particular position which we will call position 1, the Enigma rotor(s) step and then in the next position, which we call position 2, it will encode W as E and E as W, then the rotor(s) step and then in the next position which we call position 3, it will encode I as T and T as I, and so on.

The linked page then goes through a fully detailed argument as to how the setting hypothesis can be verified or ruled out. This would have been done with the Bombes eventually, though Turing et al worked through this procedure by hand as well.


Digital signature providing a proof of file authenticity How can a digital signature provide proof the authenticity (not integrity!) of a file?

First of all, authenticity and integrity are related especially when it comes to cryptography. The reason is simple: if an attacker can alter the file - void the data integrity - then the file is obviously not authentic / original anymore. Note that data integrity does not disallow replacing the signed file by another file signed with the same private key.

It is required to verify that the signature and file match to provide authenticity. The verification procedure most show that the signature was created by the entity that that was supposed to have signed the file. Usually asymmetric cryptography is used for this, where a key pair is generated by the signing party. The private key is kept by the signing party and the public key can be distributed to parties that need to perform verification.

The private key an be used to perform signature generation over the file. The public key can be used to verify that the file was signed by that particular private key because the public key and private key are mathematically related to each other. Generally the signature generation and verification both have to use a cryptographic hash over the file to calculate a statically sized, computationally unique value to represent the file; this unique hash is used in signature generation and verification rather than the file itself.

The verification shows that the file must have been signed using the private key that is part of the key pair. It is however of vital importance that the public key is trusted to belong to the private key of a particular party. Otherwise an adversary could simply substitute their own key pair and substitute both the public key and signature values. In other words, the signature value can only be trusted once the public key is trusted.

Note that cryptographers generally talk about message authentication. A file is just a persistently and sequentially stored message with a particular name. In cryptography a message can consist of any ordered amount of bits. We don't care how the bits are presented during signature generation / verification, as long as they are present when required.


Applicability of birthday attack to AES brute force Is the following snippet from a recently published cryptography book correct?
EDIT: Expand the snippet from the book to make the context (symmetric key search) more clear.

You can apply this to other cryptographic issues as well. Let's return to the DES algorithm.  Recall that it has 72,057,594,037,927,936 possible keys. To guarantee that you find the correct key, you may need to check all 72,057,594,037,927,936 possibilities.  However, if all you are seeking is a greater than 50 percent chance of finding the right key, you can try $1.774 \sqrt{72,057,594,037,927,936}$ possible keys -- only 476,204,499 possible keys. This is far more manageable.  In fact, again referring to our earlier scenario with DES, if you can attempt 1 million keys per second, you have a 50 percent chance of finding the right key in 7.9 minutes.  Although 1 million keys per second is beyond the capability of your standard personal computer, it is well within the capabilities of supercomputers or even computing clusters.
The birthday paradox is one reason why larger key sizes are necessary
for security.  If we move our attention from DES to an AES 128-bit
key, there are approximately $3.402 * 10^{38}$ possible keys.  Applying
the birthday paradox gives us $1.774 * \sqrt{3.402 * 10^{38}}$, or
32,724,523,986,760,744,567 keys that need to be attempted to have a 50
percent chance of finding a match.  This number is large enough that
it is computationally infeasible to break it through brute-force
methods, even with the birthday paradox.

The citation as now expanded is clearly in the context of key search for a cipher, and grossly wrong, including time estimate to find a DES key with odds 50% with 1 million keys tested per second (that is over 11 centuries where 7.9 minutes is stated). In other contexts, the explanation could be right except for a moderate factor erring straight on the unsafe side, or vaguely related to a relevant phenomenon. In all cases, that's wrong; as well as the estimate of key test rate: one million DES keys per second on a consumer desktop CPU was already feasible circa 1997.

As pointed in comment by the question's author, in the context of key search we need to search half of the key space to find a particular key with odds 50% (baring equivalent keys, and shortcuts to search). The birthday bound is irrelevant. After we searched the number of keys indicated in the citation ($1.774\sqrt n$ where $n$ is the size of the keyspace), our odds of having found the right key (assumed randomly chosen and initially unknown) is the ratio of the number of (distinct) keys tested, to the size of the keyspace; and that's in the order of $1.774/\sqrt n$, which is negligibly small, rather than 50% as stated.

The multiplicative constant for the birthday bound should be $\sqrt{\log4}\approx1.1774$ where the citation gives $1.774$, and uses it, making even the leftmost digit of both birthday bounds stated wrong, and erring on the unsafe side; see final note. Except for that, the explanation would have been right if the issue had been to guard against finding collisions for a one-way function such as $H:\{0,1\}^{128}\to\{0,1\}^{128};\; H(K)=\operatorname{AES-128}_K(0)$.

If we consider the security of a block cipher such as DES or AES in CBC mode, it is correct to invoke the birthday bound for collisions over the block size space; and for AES-128 this is the same as the key space, which makes the order of magnitude of the numbers in the second half of the citation relevant; however in that context the explanation does not justify "why larger key sizes are necessary"; only why larger block sizes are necessary.

As a practical illustration of the relevance of the birthday bound for CBC mode, consider a 40 GiB file, that is suspected to be the result of enciphering with 3DES in CBC mode a movie file directly extracted from a Blu-ray disk (perhaps with a little random added at the end of the file to hide the exact length of the original). The encrypted file is large enough that with odds better than 50%, two enciphered 64-bit blocks are identical. This implies that the eXclusive-OR of the two corresponding blocks in the original is equal to the eXclusive-OR of the preceding blocks in the encrypted file. That observation makes it feasible to demonstrate beyond reasonable doubt the nature of the encrypted file if the original is available, even if we have to decide among thousands of potential originals.

Note: The actual birthday bound for 56-bit (resp. 64-bit and 128-bit) values is 316,058,597 (resp. 5,056,937,541 and 21,719,381,355,163,562,492). That's applying David Brink: A (Probably) Exact Solution to the Birthday Problem (in The Ramanujan Journal, June 2012, Volume 28, Issue 2, pp 223-238), conjecturing that the number of uniformly chosen values among $n\ge1$ at which odds of collision reaches 50% is
$$\left\lceil\sqrt{n\log4}+{3-\log4\over6}+{9-\log^2 4\over72\sqrt{n\log4}}-{\log^2 4\over270n}\right\rceil$$
which in cryptography we tend to approximate with $1.1774\sqrt n$ or just $\sqrt n$, with both erring somewhat on the safe side from the legitimate user's perspective.


Cracking the Beaufort cipher Is there any easy way to crack a Beaufort cipher?

We have a Vigenère table, and are trying to guess the keyword.

Any easier way?

Yes (guessing you are doing the cypher challenge?)

The "Beaufort Decoder" is a really good decoding tool (saves you time), then trial and error keywords. Also, the "Vigenère cracking tool can be used to find the length of the keyword. Paste the texts you're decoding; the number of the column(s) with the most x's is the length of the keyword.


Help defining a shift cipher mathematically For an assignment question, I am trying to prove formally that double encryption with two keys by the shift-cipher encryption function results in a shift cipher as well.
If the Shift-cipher encryption function is defined as:

$E_K(M)= (M + K) mod 26$

and suppose that we let $M = (x_1, ... , x_{m-1}, x_m)$ = an arbitrary but particular message of length m, where each element of M is a is an integer element of $Z_{26}$, and we pass M into the encryption function, resulting in:
$(x_1 + K_1, ... , x_{m-1} + K_1, x_m + K_1) mod 26 = (y_{1}, ... y_{m})$ , where  $1 \leq i \leq m,  y_i \in Z_{26}$ .

Then my question is: what is it that makes $(y_{1}, ... y_{m})$ a shift cipher? And how is this generally expressed formally? When I know this I will be able to show that encrypting $(y_{1}, ... y_{m})$ also results in a shift cipher.

Right now all I can think of is that it is a shift cipher if it is a string where the index of each element is a number from 0-1, that was acquired by adding the index of each paintext element to the index of the key. Can anyone help clarify things for me?

My understanding is given that $E_K(x)=(x+K)~mod~26$ is the character by character encryption of a shift cipher, you want to extend it to words as the function $E'$ given by
$$E'_K(x_1,\ldots,x_m)=(E_K(x_1),E_K(x_m)).$$
If you intended the key $K$ to change per character you can modify.


With public-key crytography, is private-key crytography still useful? It seems that, with public-key cryptography, there is no need to use private-key cryptography. But obviously, both public-key cryptography and private-key are taught in cryptography classes. Can anybody let me know when private-key crytography is useful in practice? If so, can it be replaced with public-key cryptography?

Can anybody let me know when private-key crytography is useful in practice?

Symmetric techniques tend to be significantly faster than asymmetric techniques. Encrypting data with AES and an appropriate mode of operation can yield throughput that is magnitudes of order greater than what the fastest implementations of RSA could possibly deliver. This difference is so great that encrypting any sizable amount of information with only RSA would take a prohibitive amount of time and be unusable in practice.

So symmetric cryptography techniques are useful pretty much everywhere in practice, from encryption of bulk data at rest (e.g. full-disk encryption) to encryption of data in transit (e.g. TLS)

  If so, can it be replaced with public-key cryptography?

You could simply use asymmetric cryptography for everything. But there are much more intelligent ways to do things.

You can, for example, generate a regular symmetric encryption key and use that to encrypt your data quickly, and then use public-key encryption to secure the key. This nets the following advantages:

You can use a new secret key per encrypted message
But you only have to manage long-term control of a single private key, instead of $N$ secret keys for $N$ messages.

This highlights what Public-key cryptography is really good at: Key management.

Using public-key encryption to directly encrypt bulk data won't work out well in practice, because that's arguably not what the tool is supposed to be used for.


Is it possible to split a large AES encrypted string and decrypt the parts one by one? Due to some platform restrictions our decryption algorithm can only handle up to 1 million bytes. The string we receive is larger, having been generated by AES in cipher block chaining (CBC) mode, with PKCS5 padding.

Is it possible to somehow split the encrypted data and decrypt the parts?

Absolutely. The key point is that, whilst in CBC mode, the encryption can be thought of as using the previous ciphertext as the IV - have a look at this diagram from wikipedia:

I assume from what you've said that you have a function that will "do" AES-CBC decryption on large amounts of data, and you wish to use this. So, you simply run:
$$
   D_k^{IV}(c_1\ ||c_2\ ||\dots||c_n\ ) = m_1\ ||m_2\ ||\dots||m_n\
\\ D_k^{c_n}(c_{n+1}||c_{n+2}||\dots||c_{2n}) = m_{n+1}||m_{n+2}||\dots||m_{2n}
$$

That is, wherever you 'break' the flow from the CBC output, you simply use the previous ciphertext as the IV to start the next section.


Brute force encryption keys base on their length I need to clarify if my understanding is correct.

if I am using 4.2 GHz CPU -one core only- that means:

4.2 billions hertz = 4.2 billion operations per second. (about 2^32)

So:

32 bit key : 2^32 \ 2^32 = 1 second

64 bit Key : 2^64 \ 2^32 = 2^32 = 4294967296 seconds = 136 Years

My Questions:

1) Is my way of calculation is correct?

2) In Assembly language : is one line = 1 operation?

Your calculation gives the correct order of magnitude but is not correct.
Different assembly operations take a different number of clock ticks/cycles.
Also note memory access can be expensive, and it makes a big difference which cache layer if any you hit.
To make matters worse there is a difference between an instructions throughput and latency because several instructions can happen simultaneously.
If you really want to do micro optimizations yourself you can look up instruction cost here: http://www.agner.org/optimize/instruction_tables.pdf

For cryptographic operations we usually already have highly optimized code and we can just look up the cost in cycles of various cryptographic primitives. For instance SHA-3 is very efficient and can be implemented with a throughput of ~8 cycles/byte on modern processor.

Just in general you expect single cryptographic function invocations to take on the order of a few hundred cycles in efficient implementations.

In order to make brute-forcing low entropy passwords difficult we usually use tuneable Key Derivation Functions which can be made arbitrarily slow.


Concatenating "words," is it possible to create a key that is indistinguishable from one made in a truly random manner? By concatenating "words" and adding them Modulo 26, can we create a key that cannot be distinguished from one that was generated in a truly random manner?
For example, let's say we use three "words" to create a key (EATED, PIG, ELEPHANTINE), whose lengths are coprime, using Modulo 26 addition:
  EATEDEATEDEATEDEATEDEATEDEATED...
  PIGPIGPIGPIGPIGPIGPIGPIGPIGPIG...
  _______________________________
  TIZTLKPBKSMGIMJTIZTLKPBKSMGIMJ...

  ELEPHANTINEELEPHANTINEELEPHANT...
  _______________________________
  XTDISKCUSFQKTQYAIMMTXTFVWBNIZC...

And sender and receiver have already agreed that they will only use certain values, say the 4th, 19th, and 21st letters of the final string, as the key.  (I, M, X) The rest will be discarded.  Then we use a different set of words and a different choice of values to keep, say the 6th, 11th, and 21st, determined ad hoc beforehand.  The sender and receiver must have shared this information beforehand in a secure manner, of course.
The point is to get rid of the one-time pad and only have a list of words and numbers on you.
Repeat with different sets of three or more words whose lengths are coprime until we have our key, let's say thirty characters long.
Let's say we use a combined dictionary of Mandarin Chinese, Russian, and English words that has a total of 180,000 possible words (Mandarin and Russian are phoneticized).  Let's say we choose each word in a random manner.
Only using a small number of letters from each result is going to create a short key and require effort, but the question is this: would such a key be indistinguishable from one generated in a truly random manner?
I think so--if the words are long enough and coprime to each other and the words were chosen in a manner that was random  i.e., it did involve a TRNG.
Indistinguishable or not?

No. From 3 “words” as in the question, there can't be any fast public transformation (like the one considered in the question) creating a key of more than about 10 letters in A…Z that is indistinguishable from a key made in a truly random manner, in the sense that has in crypto.
Taking the question's numbers, we pick 3 words in a set of 180,000. That's $(180,000)^3$ choices (ignoring the requirement of length being coprime, which reduces the number of choices significantly; and assuming the position of the letters kept is known, or found by trial and error). Whatever deterministic transformation we make of this input, it can't have more outcomes. If the transformation has for outcome 12 letters in A…Z, not all such strings can be obtained, since $(180,000)^3\ll26^{12}$. Given a string of 12 letters in A…Z, it can in principle be tested if it could have been generated by the transformation applied to the input words, or not (at least by enumerating the $(180,000)^3$ choices and applying the transformation). For 12 letters in A…Z chosen "in a truly random manner", the probability is at most $(180,000)^3/26^{12}<6.2\%$, when that's $100\%$ when using the transformation. That's "distinguishable from a key made in a truly random manner", in the sense that has in crypto, if the test "could have been generated by the transformation applied to the input words" is feasible.
For the question's transformation, that test is feasible, and much faster than testing the $(180,000)^3$ possible input words. One way is to consider only the $(180,000)^2$ combinations of two words, deduce what the selected letters must be considering the key tested, and see if that exists in the dictionary. I estimate that such test lasts a fraction of an hour on a single computer.
Even if we used a cryptographic transformation like SHA-256, the test remains feasible, since $(180,000)^3\approx2^{52.4}$ SHA-256 hashes is within reach.
The first paragraph says "more than about 10 letters" rather than "more than 11", because even with 11 letters, we can still distinguish outputs of the transformation from random, with a few example outputs. Problem is that no transformation can make all the $26^{11}$ outcomes of 11 letters equally likely, because $26^{11}$ does not evenly divide $(180,000)^3$. At best, some (41%) 11-letter outputs will have probability $1/((180,000)^3)$, and the others (59%) twice that. Which is distinguishable from true random with a few examples. With 10-letter outputs, we could still pull that trick with some more examples. That's for the best possible fast cryptographic transformation, and is much easier for the question's simple transformation, where we could recognize the output from random based on a large sample of the first few characters of the output keys.

The best crypto has to offer here is a password-based key derivation function such as Argon2, which is a purposely slow hash, and can be used to a generate a key (of any length) that is indistinguishable from random for practical adversaries, given an input with enough combinations (and here, we have $(180,000)^3\approx2^{52.4}$, which is quite respectable if we are willing to wait 1 second for the Argon2 transformation to run on a computer).


80-bit collision resistance because of 80-bit x87 registers? This is just a curious question, and it probably doesn't belong here anyway, and I'm just being bold asking it here.

80-bit used to be considered an adequate level of security, Skipjack and SHA1 were designed to be 80-bit-secure. But why 80 bits? Isn't 96 bits better because it's a multiple of 32 and gives a higher margin?

Does the choice of 80 bits have anything to do with the fact that the 8087 processor has a 80-bit floating-point register as part of the design?

Coprocessors are designed for improved performance in a certain case, and in the case of fixed-width mathematics, I do not believe you would see a performance increase.

I am quite sure that 80-bits is simply because it is 10, 8-bit words, and not that it is targeting the 80-bit registers in a FPU.  Primarily, it would be inconvenient to use an FPU for this case due to the instruction layout.  In the case of Skipjack or a Feistel network in general, I do not know of any easy way to do the block swap without pulling the words out of the FPU back to the CPU to do the swap because the FPU hardware is designed around mantissa functions, not shifts and XORs.  You could use the FPU for intermediate storage, but because the x87 (this is particular case that is very x86 specific), you pull the 10-byte sequence from the stack, which would be more of a cost than just keeping it all in the integer unit.

Another note of security margins and Skipjack, it was designed for a minimally viable VLSI implementation.  If you were going to put something on an IC circa 1996, you'd probably lean toward 80-bits over 88 or 96, or larger.  MPEG-1, 2, 4 etc all had choices that were sub-optimal mathematically but the decoder ICs needed to be viable as a VLSI implementation. At meetings, this is always a constraint that comes up.  At NIST 8114, we've had the discussions but I've never seen these discussions formalized.  In power constrained computing, such as passively powered RFID, I still make engineering choices that are sub-optimal as far as ideal cryptography because bits cost money to make, power to use, and I don't have the luxury of increasing IC costs or power consumption.  Encryption often takes a backseat to economics in the same way that security does to convenience.


Prove that a given encryption scheme is perfectly secret I'm studying for an upcoming test and I can't figure out the following sample question:

  Let $\Pi = (\operatorname{Gen}, \operatorname{Enc},
 \operatorname{Dec})$ be an encryption scheme with key space $\mathcal
 K$, message space $\mathcal M$, and ciphertext space $\mathcal C$
  where $\mathcal K =\mathcal M =\mathcal C = \{0, 1, 2, 3\}$. Algorithm
  $\operatorname{Gen}$ returns a uniformly random key $k$ in $\mathcal
 K$. For any key $k$ in $\mathcal K$ and any message $m$ in $\mathcal
 M$, $\operatorname{Enc}(m)$ using key $k$ is defined as $(m + k) \bmod
 4$. For any key $k$ in $\mathcal K$ and ciphertext $c$,
  $\operatorname{Dec}(c)$ using key $k$ is defined as $(c - k) \bmod 4$.

  a) Prove that $\operatorname{Dec}(\operatorname{Enc}(m)) = m$ using
  key $k$ holds for any key $k$ in $\mathcal K$ and any message $m$ in
  $\mathcal M$.

  b) Prove or disprove: $\Pi$ is perfectly secret.

The formal definition of "perfectly secret" used is:

  An encryption scheme (Gen, Enc, Dec) over a message space $\mathcal M$ is perfectly secret if for every probability distribution over $\mathcal M$, every message $m$ in $\mathcal M$, and every ciphertext $c$ in $\mathcal C$ for which $Pr[\mathcal{C} =c] > 0: Pr[\mathcal{M}=m | \mathcal{C}=c] = Pr[\mathcal{M}=m]$.

In this scheme, keys can be reused.

For every key $k \in \mathcal K$ $$Dec(Enc(m)) \overset{\underset{\mathrm{def}}{}}{=} (Enc(m) - k) \bmod 4,$$ where $$Enc(m) \overset{\underset{\mathrm{def}}{}}{=} (m + k) \bmod 4,$$ so, combining it, we have $$Dec(Enc(m)) = (((m + k) \bmod 4) - k) \bmod 4,$$ which, by properties of modular arithmetic (or, more precisely, congruences), is equivalent to $$(m \bmod 4) + (k \bmod 4) - (k \bmod 4) = m + k - k = m$$
This is actually a great example, as it demonstrates the ultimate elegance of the mathematical definition of security. Encryption scheme $(E, D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is perfectly secret, if for all $m_i, m_j \in \mathcal M, c \in \mathcal C$ $$Pr[E(k, m_i) = c] = Pr[E(k, m_j) = c],$$  where $k$ is uniform in $\mathcal K$. Here is a table of encryptions of $m$ with key $k$ for all $m \in \{0, 1, 2, 3\}$ and $k \in \{0, 1, 2, 3\}$:
$$
\begin{array}{c|lc}
m/k & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 1 & 2 & 3 \\
1 & 1 & 2 & 3 & 0 \\
2 & 2 & 3 & 0 & 1 \\
3 & 3 & 0 & 1 & 2
\end{array}$$
As you can see, for every $m$, $Pr[Enc(m) = c] = 1/4$, thus given encryption scheme is perfectly secure.


Concerns about using a hash to determine if specific input data has already been encrypted A system is used to securely store account numbers.

When an account number is added to the system it is securely encrypted and stored in a database along with the IV and a reference to the encrypted record is returned (so that the encrypted record can be retrieved at a later date).

If a second request for an identical account number is made, rather than creating a new record, the existing reference must be returned to avoid duplicate entries in the database.

Storing a hash of the account number along with the record would provide a means to determine if a particular account number has already been stored, but my concerns are whether there are any implications for the hash being used to identify the account numbers.

I gather that all secure modern-day cryptographic hashes have pre-image resistance (so the hash can't be "reversed"), but if the account numbers themselves come from a limited set then presumably the account numbers could be determined via the hashes by brute force?

Are the ways to protect against this?

Would increasing the number of hash iterations slow down any brute force attempts to the point where the hashes wouldn't be considered a security issue? When selecting iterations to use other than the general size of the iterations (1000, 10,000, 100,000) are there other things to consider... is there any value in selecting a non round number such as 993 hash iterations rather than 1000?

When using a hash as a lookup value like this individual record level salts aren't usable, but I presume using a system specific salt would still be useful (to minimise the use of pre-built rainbow tables?) Would storing the system salt in a different location to where the hashes are stored (i.e. not in the database) offer any value (or is that just security through obscurity?)

Instead of using a hash function, use a pseudo-random function (PRF). Unlike hash functions, which are publicly computable, PRFs use a secret key. HMAC-SHA256 is a widely supported PRF (although usually it's used as a MAC, which is a bit different). Use a different key for the PRF then you use for encryption.

Another possibility is to use a deterministic encryption scheme, such as SIV. These ensure that the only information leaked (asside from plaintext lengths) is plaintext equality: the same plaintext results in the same ciphertext each time, but close-related plaintexts don't result in similar ciphertexts. Unless you're crunched for space in the database, though, there's no real advantage to this approach for your purposes, and implementations may not be as widely available.

To address some of your other questions:

A salt would prevent the use of pre-built rainbow tables, but, depending on the length of account numbers, this may not be sufficient.

Suppose you use 10,000 rounds of a SHA256. If there are 8 digits of an account number that an attacker cannot guess beforehand, bruteforcing all the account numbers requires 10^8 * 10,000 = 10^12 SHA256 calculations. A modern GPU can do 10^9 SHA256 calculations a second. This would result in all the account numbers in your database being broken in 10^3 seconds, which is under 17 minutes.

You might be able to play with the numbers a bit to make things more reasonable, but my advice would be to go with the PRF. Then you don't have to worry about this sort of thing.

I'm assuming that anyone who could steal the PRF key could also steal the encryption key, and therefore am not worrying about this possibility. But you could certainly combine the PRF with a large number of hash rounds to provide some measure of defense-in-depth. If you opt to go this route, consider using bcrypt rather than, e.g., SHA256. Bcrypt is less easily bruteforced on a GPU. Some experts also recommend scrypt for this purpose, but scrypt is new enough that I would be hesitant to rely upon it.

Edit: There's another related (but distinct) disadvantage to using repeated hashing: An attacker who obtains the hashes can easily answer the question, "Does account #XYZ exist in this database?" Depending on what these account numbers and database are used for, this might be a real concern for your users. A PRF does not allow this attack, provided the key remains secret.


What are the dangers of predictable (repeated) plaintext structures? When using a "good", modern cipher (specifically one that provides ciphertext indistinguishability), is it a problem at all if there is some well-known structure in all plaintexts?

For example, consider a simple protocol that transmits many messages that all start with an identical, but secret string. All of the messages are encrypted with a different symmetric key, and the keys are in no way correlated (to either plaintext or previous keys).

Is there a way for an attacker to use his knowledge of the fact that the first n bytes of ciphertext always correspond to the same plaintext? Can those bytes even be decrypted? If so, is there a specific term for that kind of attack/cipher weakness? (Maybe something like "known identical plaintext"?)

My background for asking is section 5 of RFC 4345, which specifically advises against using RC4 in that kind of scenario. I know that RC4 has some known weaknesses regarding ciphertext indistinguishability, and it seems that my scenario is exactly one where those would allow the plaintext to be recovered.

So my question, in other words, is: Do other ciphers like AES share that weakness? If not, does resistance against that weakness, however it is called, follow from the fact that a cipher provides ciphertext indistinguishability?

Well, no, modern ciphers (such as AES) do not share that weakness; they are designed specifically to be secure without any assumption of what the plaintext looks like.  You can encrypt the same message with multiple keys; in fact, you can encrypt the same message a bunch of times with the same key, and the attacker still cannot deduce any information for what the plaintexts look like (or indeed verify that all those ciphertexts did in fact correspond to the same plaintext).

As for specific terminology for an attack that, given a large number of messages, attempts to find some information about them, I have seen the term "statistical cryptanalysis"; I don't know how commonly that is used.

As for resistance to AES with a secure mode to statistical cryptanalysis, one way to derive it is indeed based on ciphertext indistinguishability.  If the cipher mode does provide ciphertext indistinguishability (that is, the ciphertexts corresponding to chosen plaintexts are indistinguishable from random outputs), then any process that gains any information on the plaintexts based on the ciphertexts leads immediately to a distinguisher (as doing the same analysis on truely random outputs can't give any information about the plaintext), and such a distinguisher contradicts the assumption of ciphertext indistinguishability.


Decrypted RSA 64 bit encryption using modulus and private exponent. Got gobbledygook [Verify] As part of an experiment, I was given a .enc RSA (encrypted) file that was most likely generated using openssl. I had the public key, I factored it, obtained the private exponent, and decrypted the .enc file in chunks of 64 bit. What I got as a result, was nonsense hex. I was supposed to get a password or secret key.

What I have so far:

 Factors: 3917781347 x 4215069449
 Private exponent: 9440767265896423601
 Modulus: 16513720463601767803

I have used xxd to extract the hex data from the ciphertext file: xxd -p > enc.hex

This created a hex dump of the file called 'enc.hex'. The contents of this file begin like this:

 7d4554292d7b9f980ed049cea0f968cf438b6fc312cf2028ce5ce2fe9f38
 387b72a01bf6564f25884a2cacd187c2eeccd0cf78c2a74785f18d5e72b5
 270ac3e45b6f7505347b38ec7684b1af206d73ea4a84cd59b50be56d7abf
 74a569868406ab2b17846c9e448fe1392b21dac0b10fbb733536c99e598b
 683be7400a1ad55c42faa171becd803b8b8f4a1fa512a33222ec042486c5
 672f6200d4f00e2994b6d247a44edb6ce90795bde7ccda4433cf6fca8362
 f87c68f9df6418c4f0b8fb9da39a1d173fea2b1466e646f01e2dc7fb0499
 311d35ec75c15c5910b2d3e0c662de0b3b1716bab44faa2a36538bb44f6a
 3c3abd37692cf95fa075b58485ad983533782d7bf51e10c0e3b18ccec972

My Python code:

#!/usr/bin/python
d = 9440767265896423601
N = 16513720463601767803

file = open('enc.hex', 'r')
c = file.read()
n = 16
c = c.replace('\n', '').replace('\r', '')
m = [hex(pow(int(c[i:i+n], 16), d, N)).rstrip("L") for i in range(0, len(c), n)]

f = open('decrypted.hex', 'w')
f.write(''.join(m))
f.close()

Where, 'c' is the ciphertext, 'd' is the private exponent, 'N' is the modulus and 'm' is supposed to contain the plaintext hex bytes.

Output of my python script:

  0x2f2f7656414141410x41414141615155410x41416741414130670x6f414142464a4636
  0x39746d3641414b530x4c3137624e3041410x41424a44414141410x412f365758484676

When I convert this to ASCII, I get nonsense:

//vVAAAAAAAAaQUAAAgAAA0goAABFJF69tm6AAKSL17bN0AAABJDAAAAA/6WXHFv

Also, '2F 2F' is not a Magic Number and does not indicate a file type. As I said, I was supposed to get a password one way or another after decryption.

I have spent weeks over this experiment, and I'm on the verge of crying now if I don't decrypt this and get the password to the next level.

Could someone please quickly verify what I've done is right, and they are getting the same hex sequence after decryption? Here are the files in a tarball:

http://www.filedropper.com/chaltar

Contents:

.enc encrypted file
.uyu (was a hint that .enc is encrypted in RSA 64 bit chunks; you can ignore it)
.pem (a public key from where I extracted the modulus and public exponent)

UPDATE:

I understand what I need to do now, and I know what to expect. However, my Python code seems to be messing up the 64 bit block decryption somewhere near the end as I'm not getting the two '==' signs (3d 3d) at the end after decryption. This is the trail (end) hexdump of my decrypted file:

   002ACD50  33 30 34 31  34 31 34 31   34 31 34 31  30 78 34 31   3041414141410x41
   002ACD60  34 31 34 31  34 31 34 31   34 31 34 31  34 31 30 78   414141414141410x
   002ACD70  34 31 34 31  34 31 34 31   34 31 34 31  34 31 34 31   4141414141414141
   002ACD80  30 78 35 61  35 31 33 64   33 64 34 31  34 31 34 31   0x5a513d3d414141
   002ACD90  34 31 30 78  30                                       410x0

The file unexpectedly ended with one byte (30). Could someone point out what is wrong with my python decryption code above?

I did the procedure myself, and I can confirm that base64 decoding will do the trick; the full decrypted file will have == at the end somewhere. After decoding, the "file" command will reveal the plain text type. The '.uyu' file is quite easy to "decrypt" as well, I noted.


Is it correct to concatenate (pseudo-)random byte values before testing them with the NIST suite or tools like dieharder? Let's assume I have thousands of (pseudo-)random 4-byte values. The values are 4 byte random values which a blackbox device gave me. I got these values by requesting them. In between others might have requested them too (I don't know about that). Now I'd like to test them for randomness. There are tools for this like dieharder or the NIST Statistical Test Suite.

Is it valid to just concatenate the thousands of 4-byte values so that I end up with one very long byte (n * 1000 * 4 byte) stream which I then feed into these tools?

Is it correct that it doesn't matter for the tests how long the individual values (4-byte) were before? (Because the test tool wouldn't know that I had 4-byte values in the beginning, once I concatenated them?).

Edit:
The question is meant as a general question. The actual underlying problem is how to examine seed values for randomness, which I obtained via UDS Security Access (see https://en.wikipedia.org/wiki/Unified_Diagnostic_Services#Services $27).

Is it valid to just concatenate the thousands of 4-byte values so that I end up with one very long byte (n * 1000 * 4 byte) stream which I then feed into these tools?
Is it correct that it doesn't matter for the tests how long the individual values (4-byte) were before?

Yes for both. The fact that others may have obtained (and removed) randomness from the source while it was sampled, or/and that the samples are grouped in some particular way for testing, does not prevent from testing what's obtained. And that can not cause a valid test to fail more often, assuming the source's full output is indistinguishable from random (including for said others trying to make the test pass, or fail).
On the other hand, those same facts could make the test become arbitrarily less capable of detecting some faults. As an extreme example, a source that always repeat each byte that it outputs might become indistinguishable from true random if we sub-sample its output, keeping every odd byte.

The actual underlying problem is how to examine seed values for randomness.

Dieharder or the NIST Statistical Test Suite alone can't give any assurance of that. At best, they can indicate a fail with high confidence, which saves from performing further work (beyond checking that the test was correctly performed/works). If they indicate pass, no other firm conclusion can be reached on that basis alone. It is needed to know how the seed values are generated, and that can't be determined by a test of the seed values.

As a proof that these tests can not validate the fitness for cryptographic purposes of a source of unknown build, consider a RNG with:

a real-time clock keeping UTC time in second, initializing 128-bit register at startup after a delay of 1 second
with the register then repeatedly encrypted using AES-256 and a key to produce the next register value, which concatenated 128-bit values form the bulk of the output, queried over a gigabit Ethernet interface.

This source will pass any black-box testing that does not reject a good generator, including tests scrutinizing power-on, as long as the test does not use AES-256 and the correct key.
But this source is disastrous from a cryptographic perspective. Given the key and when the black box was started, its output is predictable. Given the key and a fragment of a sequence, all the rest can be computed. Some party eating bytes from the source in the background can even decide what another party using the source will get!

As pointed by others, many statistical tests, including some of the DieHarder suite, require megabytes of input. The full Dieharder needs gigabytes.
However, in the context of a cryptographic RNG of proper structure, these tests requiring a lot of input are not needed. The tests that make sense are those on the unconditioned (or lightly conditioned) entropy source, used to seed a CSPRNG. The source is validated by tests which purpose is to ensure that it delivers some entropy. The CSPRNG is validated by examination of its design, and Known Answer Tests. Some monitoring in the RNG should detect a fault in the source and in this case prevent output. The combination might be checked by an extra test of the whole thing, but that's meaningful only if there is some assurance, obtained otherwise, that the overall structure really is the source seeding the CSPRNG, and being monitored.


What's the strategy for future directions in cryptography? Bigger numbers/faster searching, or new methods, say, of factoring? I'm taking a course in cryptography, and I would value any comments. This is not too technical a question, but more about directions or strategy in cryptography. My question is, is public key cryptography, for instance, "just" a question of the difficulty of dealing with large integers? I can understand that factoring a product of two large primes is time-consuming. Is there a basic belief that new methods of factoring might be developed, which will lead to breaking some cyphers, or pushing the number-size requirements ever higher? Or do industry pros look more toward ever-faster, ever-large-number-handling capabilities as the most likely future?

If you're asking about the likely future for public key cryptography, then my opinion is that we are likely to see a transition (gradually over the next number of years) from things such as RSA and DH, and into Elliptic Curve Cryptography.

This is because ECC is just more efficient; we know that we can break RSA and DH in subexponential time; that means that as computers get faster, and we need to make the problems more difficult, the modulii that we need to use for RSA and DH get larger a lot quicker than you would naively expect.  On the other hand, with ECC, the curve sizes don't grow very much at all.  So, instead of going to increasingly large RSA key sizes, I expect that people will gradually transition to ECC (as people become more comfortable with it).

If a new factoring method is found (which, personally, I don't expect), then all that would do is make that transition happen that much faster.

What would be a real game changer would be if someone was able to build a real quantum computer; a large enough one would be able to break RSA and ECC easily.  There are public key algorithms that don't appear to be solvable by a quantum computer (at least, not significantly easier than a conventional one); we'd transition to such an algorithm instead.


Differences between Extractors and Privacy Amplification for Quantum Random Generators We know that for the last step of QRNG: we need to separate quantum and classical noises from each other so we use extractors, after extractor we need privacy amplification step. At this point: if extractor is a strong extractor we can use it as a privacy amplification too. However I could not understand differences between extractor and privacy amplification. If I use the strong extractor for the second time, will I be able to complete my privacy amplification step? What will change in privacy amplification? If what happens, privacy amplification will be completed? Thanks

Privacy amplification (PA) cannot be done at all with only a QRNG (which I take to be a quantum random number generator).  Privacy amplification resides further along the application stack, and requires two co-operating parties (Bob and Alice) and an opponent (Eve) listening in on their quantum channel within their quantum key distribution network (QKDN) :-

Essentially privacy amplification (pink bits above) in QKDNs aims to allow two parties, Alice and Bob, to distil a secure final key from a partially secure bit string. The degree of security (bits) is governed by the Leftover Hash Lemma (LHL), which also can be applied to simple random number generation for regulating the output bias.
The purple rectangle is where true random numbers are generated within a QKDN.  Clearly within a QRNG that would be the end of the story. A randomness extractor may or may not be incorporated into the output stage of the QRNG as they're not always needed. If you did need a randomness extractor, they're used to alter the probability mass function of the quantized signal into an almost perfectly uniform distribution.
That's a lot of stuff, so an example is probably in order.  See High-speed Privacy Amplification Scheme Using
GMP in Quantum Key Distribution, specifically §2.2.


Longer IV generation from a single block IV for ICBC I was reading a question about ICBC here and it mentioned that you would need a $s \cdot n$-bit $IV$ if you would use $s$ "stripes", where $n$ is the blocksize.

Say that we don't like transmit that amount of data, would it then be safe to use the following generation of $IV'$ for ICBC, so we can use an $n$-bit $IV$ again?

$$IV' = \operatorname{CBC}_k(0^n, IV \|  0^{(s - 1) \cdot n})$$

I think it is secure (other than that the amount of data that can be securely encrypted is diminished by the amount of data that is encrypted for
$IV'$, but that's as good as negligible, I suppose).

Of course, we assume the normal CBC conditions regarding unpredictability for the $IV$ in the scheme.

I'm reading the question's suggestion as using $\text{IV'}_0=\text{ENC}_k(\text{IV})$ as the Initialisation Vector for stripe $0$ and for $0<i<s$ using $\text{IV'}_i=\text{ENC}_k(\text{IV'}_{i-1})$ as the IV for stripe $i$.

That's not (CPA) secure, because it allows distinguishing that the plaintext starts with zero blocks: in that case, the second ciphertext block of stripe $0$ will be the same as the first ciphertext block of stripe $1$.

Addition: I do not immediately see an attack¹ if we build the IVs as $\text{IV'}_0=\text{IV}$, $\text{IV'}_i=\text{ENC}_k(\text{IV'}_{i-1})\oplus\text{IV}$. Or this slightly different option, using the question's notation:
$$\text{IV'} = \operatorname{CBC}_k(\text{IV},\text{IV}^s)$$

¹ which is not a conjecture of security.


LWE with secret matrix (Reverse LWE?) I was wondering if there is a version of LWE with secret matrices and public seed vectors? Would it be as hard as the popular definition of LWE?

The LWE assumption tells you that $(\mathbf{a},\mathbf{a}\mathbf{s}+e)$ looks random for a hidden random vector $\mathbf{s}$, a random vector $\mathbf{a}$ and small error $e$.

Invoking the LWE assumption k times, you get that $(\mathbf{a},\mathbf{a}\mathbf{s}_1+e_1,\mathbf{a}\mathbf{s}_2+e_2,\ldots,\mathbf{a}\mathbf{s}_k+e_k)$ is indistinguishable from $(\mathbf{a},b_1,b_2,\ldots,b_k)$ where the $b_i$'s are random values.

So $(\mathbf{a},\mathbf{S}\mathbf{a}+\mathbf{e})$ is indistinguishable from $(\mathbf{a},\mathbf{b})$, and if an adversary has advantage $\varepsilon$ in distinguishing those 2 distributions, there is an adversary that has advantage $\frac{1}{k}\varepsilon$ in distinguishing LWE samples from uniform, where $k$ is the dimension of the vector $\mathbf{e}$.


GGM PRG construction: Why do we need to change keys all the time with underlying PRG When constructing a PRF that has n bit input using the GGM PRG, why do we always have to recursively run the PRG using its previous output as a seed key n times. Instead, why don't we run the PRG n times, and use that as the output.

Any answers would be great. My assumptions is that it has something do with producing independent random blocks, but surely a secure PRG would satisfy this?

Short answer: I'm pretty sure that your suggestion would "work," but I don't think that it would be better than the GGM approach from either a performance or a security point of view.

Long answer: As Mikero suggestions, we have to be careful about the intput and output lengths of the PRGs. So the GGM problem starts with a family of pseudorandom generators whose output length is 1 more than its input length:

$$ G_n : \{0,1\}^n \to \{0,1\}^{n+1} $$

The goal is to produce a family of PRGs with bigger expansion. For the sake of concreteness, let's say that you want a new family of functions that doubles the length of its input:

$$ F_n : \{0,1\}^n \to \{0,1\}^{2n} $$

The GGM construction accomplishes this by using $G_n$ a total of $2n$ times to produce the corresponding $F_n$. It sounds like you want to do things slightly differently. If I understand your question correctly, you want to apply $G_n$ to the input in order to get $n+1$ bits, and then apply $G_{n+1}$ to that in order to get to $n+2$ bits, and so on. Thus, you'll set

$$ F_n (x) = G_{2n-1}(G_{2n-2}(\cdots(G_n(x)\cdots)).$$

I'm pretty sure that you could prove this secure through a simple hybrid argument. However, from a theoretical point of view, I think that I'd prefer the GGM method for a few reasons:

The PRGs with bigger-input-lengths, like $G_{2n-1}$, could be much slower than the initial PRG $G_n$. Remember, each function in the family runs in time polynomial in its own input length.
The hybrid argument will have a rather large error term in the indistinguishability claim. With the GGM approach, you're using $n$ pseudorandom bits each time and you're claiming that they are indistinguishable from $n$ random bits. With your suggestion, things are worse: you're using more pseudorandom bits each time ($n+1$, $n+2$, and so on) and claiming that they are indistinguishable from the corresponding number of random bits.

In practice, it is unlikely that you'd want to use either the GGM construction or your own when building a PRG. However, if for some strange reason you wanted to do so, I think the GGM method is better again, but for a more subtle reason. I'm not sure what initial PRG you'd use in the construction, but I'm assuming it would be something like the assumption "I'm willing to believe that SHA1 is a PRG when used on 159-bit inputs." (HUGE caveat: I'm not suggesting that you should actually make this assumption! It just seems like the most logical way to use a GGM-style approach in practice.) What this really means is that you think

$$ SHA1 : \{0,1\}^{159} \to \{0,1\}^{160} $$

somehow is part of a mythical family of PRGs, even if you don't know what the other members of this family are. Under this assumption, I suppose you could use the GGM construction on SHA1 in order to make bigger PRGs. Your method wouldn't work though, because we don't know the other members from this "mythical family" so we cannot use them in a construction.

Sorry for the long-winded answer; I hope it made sense.


is it correct that for a nbit LFSR (galois algorithm in particular) the maximum number of unique 32byte keys can only be 255? In fact I have more than just the one question as I try to better understand the whole topic.
for a CTF challenge I am currently reading up on LSFR. The code the challenge provides as an example is a 5bit lsfr and it generates from its bit sequences a 32byte long key (8bit to one byte and this 32 times).
So the first and last byte of the key are the same for this particular 5bit case as after 2^5-1 iterations the whole sequence repeats.
Also if I understand the whole logic behind LSFR right I can produce 2^5-1 unique keys only for the 5bit version. (starting with one particular seed e.g. s=1). Also I can have 2^5 different initial seeds. According to my tests this will not produce additional 31 unique 32 byte keys but only the same keys but in a shifted sequence. ok, so here the questions I have.

a) are the above statements as written correct or did I miss something ?

b) if above is correct then I can get up to 255 unique keys if using as minimum a 8bit_lsfr (2^8-1). right ?

c) I will always get a max of 255 unique keys even if I increase the bits of the lsfr as I can only have 255 unique bytes and the byte sequence will repeat. is that correct ?

d) So it doesnt make sense to increase the bits beyond 8 bits or is there another benefit for this particular case that I dont see ?

Thanks for any help in better understanding this in advance.
Best
Zaphoxx

edit: Clarifying what I mean with unique 32 byte key:
when I generate multiple 32byte keys from an lsfr, then I save the generated keys in list and each key is only once in that list. I thought that when running a nbit lsfr the maximum number of 'unique' keys would be 255 but that might not be true and I'll need to recheck that.
maybe someone can clarify that question.

An $n-$ bit primitive LFSR generates the $2^n-1$ unique nonzero $n$ tuples exactly once in a cycle.

Take $n=8$ and your questions all have the answer yes, except the all zero seed will not give any tuple other than the all zero tuple.

However, such an $n$bit primitive LFSR generates all $k$ tuples, for $k\leq n,$ (provided its initial loaading is nonzero)

$$2^{n-k}$$
times if the $k$tuple is not all zeroes, and
$$2^{n-k}-1$$
times if the $k$ tuple is all zero.

So these $k$ tuples are not unique, repeat at pseudorandom times along the cycle, but you do get the all zero $k$ tuple occur naturaly in the scheme.

Example: $n=4,k=3.$ There should be 2 of each nonzero 3-tuple in
a period while the zero 3 tuple should occur exactly once. The sequence below is a primitive LFSR sequence. I have taken $2^4-1+2=17$ symbols instead of 15, so I can examine the 3-tuples starting within one period from position 1 to position 15. I grouped in 5's to make it easy to see positions

00100.11010.11110.00

001 occurs twice, starting in position 1 and 4

010 occurs twice, starting in position 2 and 8

100 occurs twice, starting in position 3 and 14

etc.

000 occurs once, starting in position 15


Example of breaking RSA with CRT I understand that if the same message is sent to 3 people with $e=3$ that even with different public keys, the message can be decoded using the Chinese Remainder Theorem.
I have tried to figure out the steps to do so, but I am unable to actually lay it out even using small numbers. How would one decrypt a message $m$ = 10, for example with $n_1=6$, $n_2=35$, and $n_3=143$, with $e=3$?

We have the three cipher texts $m^3\equiv c_1\equiv 4\pmod{6}$, $m^3\equiv c_2\equiv 20\pmod{35}$ and $m^3\equiv c_3\equiv 142\pmod{143}$. An application of the Chinese remainder theorem tells us that $m^3\equiv 1000\pmod{30030}$, but because $m$ is less than $\root 3\of{30030}$ we know $m^3=1000$. A regular cube root now recovers $m=10$.


Custom AES-128 encryption I have a 16-byte ciphertext, 16-byte key, and 16-byte IV. The key and IV I was able to set myself, and all I know about the ciphertext is that when I decrypt it, it will be human-readable.

I have tried PyCrypto and OpenSSL methods to decrypt the ciphertext with no luck. This is leading me to believe that it may be a custom implementation of AES. My background is not in cryptography so please excuse my ignorance.

Is there a standard way to implement AES-128? Is it uncommon to implement your own version of AES? I'm familiar with the AES algorithm, and it seems like it would be possible to implement your own way of scrambling the bits in the individual rounds.

I also noticed the NIST gives out certifications to individual companies for their AES encryption (ie. Google, Cisco, HP, AWS, etc.). Is this because it's a custom implementation?

Is there a standard way to implement AES 128?

There are several implementation strategies to AES (SIMD-based, plain-C, table-based, side-channel resistant, bit-sliced, AES-NI, ...). The "standard" way depends on your platform and goals, depending on the answer to questions such as "do yo have hardware support?", "do you want constant-timeness", "do you want maximal speed", "how much RAM / code space do you have?", "is your mode parallelized?", ...

  Is it uncommon to implement your own version of AES?

Yes, it is, because there are already so many good open-source implementations, however people still do it every now and then. For example re-implement AES "just for fun" and sometimes they have a different set of optimization goals than all previous implementations like "minimize code-size, work everywhere in C, runs in constant-time".

  I'm familiar with the AES algorithm and it seems like it would be
  possible to implement your own way of scrambling the bits in the
  individual rounds.

No. If your implementation doesn't result in the same encryption and decryption functionality as described in FIPS 197, you do not get to call it "AES", because it's some custom scheme you made up.

  I also noticed the NIST gives out certifications to individual
  companies for their AES encryption (ie. Google, Cisco, HP, AWS, etc.)
  Is this because it's a custom implementation?

The only actual evaluation and certification program that I'm aware of that is run by NIST is the cryptographic module validation program, which well, validates cryptographic modules according to FIPS 140-2. These validations are usually carried out by certified validators (certified by NIST). The modules may use AES but they usually do much more and the main aspect usually is on key management, role management and user authentication, but also of course on the correct implementation of the algorithms, so yes, you can get your AES implementation validated by this program, if it is part of a cryptographic module.


El Gamal Signatures, Need help explanining a step, Where does the "775" come from? Image included I understand all of the previous steps, but I don't understand what is happening to "S2" in that the number "775" showed up.

Where does the 775 come from? I can't seem to get it, and I've tried modding it, but received the wrong answer.

The answer to this is to add the modulo to the a when a is negative. As such, this worked out fine after I added the modulo to the negative number.

Solved!

The question basically is how $300 - 61 \cdot 425 \bmod 880$ can turn into the value $775$, while a calculator returns a different value, likely $-105$.  The difference is that sometimes a remainder is taken to have a value in the range $(-N, N)$ rather than $[0, N)$.

$300 - 61 \cdot 425 = -25625$. So you can say that we're trying to find a value $x \cdot 880 + y =  -25625$. Now is can be $-29 \cdot 880 - 105 = -25625$ to find a value within $(-N, N)$, similar to finding $29 \cdot 880 + 105 = 25625$. $-105$ is then commonly called "the remainder"; it's what you would get if you would perform simple tail division yourself.

However, for cryptographic operations we generally try and perform operations in a group of order $N$ instead, with $N$ possible values in the range $[0, N)$.  so in that case we can take $-30 \cdot 880 + 775 = -25625$, and the result will be $775$, exactly $880$ more than $-105$ in other words. This is commonly called taking the modulus, although this value can also be called a remainder.

So to find the right value within your calculator you can simply add $N = 880$ if the result is negative. A little trick in programming languages is to perform ((X % N) + N) % N, so that an if statement can be avoided. Note though that the + N may cause an overflow for large values of $N$.


Is it feasible to find n hashes that sum up to a given hash? Consider two sets $A=\{a_1,a_2,\cdots,a_n\}, B=\{b_1,b_2,\cdots,b_m\}$;

We can calculate the hash sum of those sets:

$$HASHSUM()=(ℎℎ(a_1)+ ℎℎ(_2)+\cdots +ℎℎ(_))$$ and
$$HASHSUM()=(ℎℎ(_1) + ℎℎ(_2)+ \cdots + ℎℎ(_)).$$

Is it possible that set $$ does not equal the set $$, yet $$HASHSUM()=HASHSUM()?$$
Specifically, if $n$ (not necessarily $m$) is a small number ($<20$).

Let the hash length be $d$. If we consider finite groups, like addition modulo $2^d,$ this problem is well understood. Fix $k=n+m.$ If the vectors are randomly generated and form a list of size roughly at least $2^{d/k},$ there exists a solution with constant probability bounded away from zero. This is because a list of size $M$ contains $$F:=\binom{M}{k}$$ subsets of size $k,$ and thus as
$\{a_1,\ldots,a_n,b_1,\ldots,b_m \}$ ranges over these subsets the function $$f(a_1,\ldots,a_n,b_1,\ldots,b_m):=(a_1+ \cdots + a_n)-(b_1+\cdots+b_m)$$ hits $F$ pseudorandom points from $\mathbb{Z}_{2^d}.$

This is a $F$ balls into $2^d$ bins problem and if $F\geq 2^d,$ the probability that $f$ misses the bin corresponding to  $0 \in \{0,1\}^d$ is roughly $e^{-1}\approx 0.37.$ Taking $M=\Omega((n+m) 2^{d/(n+m)})$ is enough here. However, finding the solution is computationally more expensive.

Wagner (see here ) has a recursive binary tree based algorithm for the $k-$ XOR problem $$x_1\oplus \cdots \oplus x_k=0 \qquad (1)$$ with $k=2^s,$ with time and memory complexity essentially
$$O(k 2^{d/(1+s)}).$$ This algorithm can be applied with addition, and will solve your problem if $k=n+m\geq d,$ since a solution will exist in that case.

Here we have $+$ instead of $\oplus,$ which is not a problem since we can use $-b_i'=2^n-b_i$ and use addition throughout. The upshot is, you need $F\geq d/(n+m).$ So if $d=256,$ and $n=20,$ you need $m\geq 236,$ and you will have complexity $$O(k 2^{d/(s+1)}).$$

Note: For the integer case without modular reduction, this is equivalent to a knapsack problem for which, the best algorithms are of very high complexity. Even though your outputs are in $[0,2^d-1]$ addition means your target set is much bigger. I believe the best complexity for finding a solution (if it exists, no guarantees since there is no finite domain) would then be $O(2^{(n+m)/4}),$ memory and $O(2^{(n+m)/2})$ time, from memory (Shamir Schroeppel?).


Small subgroup confinement attack on Diffie-Hellman I am trying to understand the small subgroup confinement attack on the Diffie-Hellman algorithm. I will present the attack and try to explain why it works.
Small subgroup confinement attack on the Diffie-Hellman algorithm
Let be a group $\mathbb{Z}_p^*$ where $p$ is a large prime and $\alpha$ a primitive root modulo $p$. Let's consider that Alice and Bob want to do a key agreement on the whole cyclic group $\mathbb{Z}^*_p$ using the Diffie-Hellman algorithm. The following sequence diagram illustrates how Eve can perform a small subgroup confinement attack:

By doing this, if $k$ is well chosen, the secret $S$ can be found by exhaustive search.
How to choose the $k$-value
As $p$ is a prime number, the order of $\mathbb{Z}^*_p$ is a composite, so there exist subgroups. Say $\mathbb{G}_w$ is one small subgroup of prime order $w$. So by picking $k = \frac{p-1}{w}$, the secret value $S \in \mathbb{G}_w$ and as it is a small subgroup, $S$ can be found by exhaustive search efficiently.
Why does it work?
In this section I will try to prove that $S \in \mathbb{G}_w$.
We know that $w\text{ | } (p-1)$ so $\exists k$ as $p-1 = w \times k $. Plus we know that $ord(\alpha) = p - 1$ because it is a primitive root modulo $p$ and a consequence of the Cauchy's theorem is that given an element $x$, $ord(x^k) = \frac{ord(x)}{(ord(x) \wedge k)}$.
So in our case we have:
$ord(\alpha^{ab(p-1)/w}) = ord(\alpha^{abk}) = \frac{ord(\alpha)}{(ord(\alpha) \wedge abk)} = \frac{(p-1)}{((p-1) \wedge abk)} = \frac{wk}{ (wk \wedge abk)}$ and we know that $(wk \wedge abk) = k$ because $w$ is a prime number. So we obtain that $ord(\alpha^{ab(p-1)/w}) = \frac{wk}{k} = w$ so we can conclude that $S \in \mathbb{G}_w$.
Could someone approve or disapprove my demo?

The proof provided in the question is correct, but as Chris Peikert pointed out in comments, there is an easier way to prove that $S \in \mathbb{G}_w$:

$ord(\alpha^k) = \frac{ord(\alpha)}{ord(\alpha) \wedge k} = \frac{p - 1}{(p-1) \wedge k} = \frac{p - 1}{k} = w$ so it implies that $\alpha^k \in \mathbb{G}_w$.

As $A^k = (\alpha^a)^k = (\alpha^k)^a$ is a power of $\alpha^k$, it also implies that $A^k \in \mathbb{G}_w$.

In the same way, $S$ is a power of $A^k$ so $S \in \mathbb{G}_w$.


Adding two public keys secp256k1 (the signature scheme used by Bitcoin) has the interesting property that you can add two public keys to get a combined key that requires both private keys to produce signatures for.

Is there another, more widely used public key cryptography scheme with the same property?

Yes.  Discrete-log based cryptosystems (e.g., El Gamal) have a similar property.  It's "multiply", not "add", but that's just because that's the group operation for discrete-log based cryptosystems.

More generally, I suggest you look at threshold cryptography.  Threshold public-key cryptosystems are a class of systems that can achieve the sort of thing you mention.


AES CTR with similar IVs and same key Let's say there is a piece of software that uses AES CTR to encrypt different messages using the same key but with slightly different IVs.

So for example,  a 16 byte IV, the 2nd 8 bytes are always the same, but the 1st 8 bytes are random.

How insecure is this?

I know that you shouldn't use the same IV and key. But do similar IVs have the same vulnerability or a different way to attack them?

As the name suggests, CTR mode works by encrypting a counter (that gets incremented with each 16-byte block) to generate a stream of random bits. That bit stream is then XOR'ed with the plaintext to create the ciphertext. The IV provides the initial value for the counter.

CTR mode is secure as long as the probability of a counter value repeating is negligible. Therefore the scheme you describe is secure under two conditions:

No message is longer $2^{32}$ sixteen-byte blocks long. Since this works out to be 64GB, this assumption is probably safe. (I'm assuming the 32 IV bits that are the same each time are the bits that get incremented with each block.)
The number of messages encrypted under a single key is small.

How small is small? Well, the birthday paradox says that if you encrypt $2^m$ messages, the probability that the random, 64-bit portion of the IV will repeat is at most $2^{2m}/2^{64}$. So if you encrypted $2^{16} = 65536$ messages, the probability of having a repeated counter is less than one in $2^{32}$; i.e., less than one in roughly four billion. In most cases, this is an acceptable risk (although some may consider it high by cryptographic standards).


"hex" vs. "base64" encoding when enciphering Examining different implementations of encryption / decryption  with cipher on Node.js, I paid attention that some implementations use hex encoding:

let encrypted = cipher.update(value, "utf8", "hex");

while other prefer base64:

let encrypted = cipher.update(value, "utf8", "base64");

Questions:

Does encoding choice play a significant role in encryption for a cipher?
From security point of view, can the wrong encoding choice affect the outcome?

Does encoding choice play a significant role in encryption for a cipher?

No.  Ciphers operate on bit strings.  It is far more important to focus on what kind of ‘cipher’ it is and what security goals it provides: you generally want an authenticated cipher like NaCl crypto_secretbox_xsalsa20poly1305 or AES-GCM, and you definitely don't want to reach for the letters A-E-S directly yourself.  Focus on security contracts.

  From security point of view, can the wrong encoding choice affect the outcome?

Not as far as the cryptography is concerned, but complicated encoding methods can pose security problems of their own:

If you apply a base64 encoder/decoder to the plaintext rather than ciphertext you might leak information about the plaintext via timing side channels in a naive array lookup for hexadecimal digits.
If you apply compression to the plaintext you might leak information about it via the length of the ciphertext as a side channel.
If your encoding method is buggy like an ASN.1 parser your application might barf its memory contents out like a bleeding-heart OpenSSL.


Is matrix elliptic curve discrete logarithm problem quantum-safe? I can't be the first one to think of this and there must be a reason nobody design cryptosystem off this problem.
Let's define MECC as matrix of elliptic curve points, and MI as matrix of non-negative integers.
Given a MECC $G$, MI $v$, and MECC $P=v\cdot G$. How would a quantum computer calculate $v$ from $P$ and $G$?

Reasoned it through just now. Given the ultimate generator of the elliptic curve group $G'$

Shor $G$ element-wise to obtain an MI $H$ such that $G=H * (G')$, where $*$ is element-wise multiplication.

Shor $P$ element-wise against $(G')$ to obtain an MI $J$

Calculate $J\over H$ using Gaussian elimination to obtain $v$

Yeah! I defeated myself in a cryptanalysis challenge.


Would a simplified CBC-MAC be safe? Would using the ciphertext of the previous block as key instead of XOR:ing the block and encrypting with the normal key work?

Normally it's done like this:

What if we instead do this:

Seems like it should be more or less the same thing in the end?

I'll assume that you a prefix-free encoding (or fixed-length messages) to solve that problem of CBC-MAC. It's actually very possible that this would be secure since the proof of CBC-MAC pretty much works by showing that the input to each block is random. Thus, it's conceivable that it will be secure when using the result as a key (since it's also random). However, I say just "conceivable" because you would have to formally prove this.

I'll just note that in practice this would be a terrible idea since it would require a new key schedule for every block. That would be really inefficient (e.g., for AES).


Storage of Private Keys I'm building a bitcoin web application that will require all users to be assigned a wallet for adding funds to their account. I plan on exposing the public key to the user (the bitcoin address). Users will simply use their exchange or their bitcoin client to send money to this address and their accounts will be subsequently credited.

I'm wondering what the best method would be for storage of each wallet's private key. Obviously, the web application needs to know it when the user wants to spend the coins. However, in the event of a database breach, the attacker could obviously steal everyone's private keys, and therefore, their money.

Here is my idea and I would like some feedback whether or not it is secure:

I am already using phpass which utilizes bcrypt to salt and hash their password on signup. When a signup occurs, generate a bitcoin key pair, and (MCRYPT_RIJNDAEL_256) encode the private key using the user's password as the encryption key.

Now when users are willing to spend their coins, I simply re-ask them for their password to uncover their private key to the web application. This is a small price to pay for the added security.

If the database is ever breached, the attacker would only see bcrypted passwords and MCRYPT_RIJNDAEL_256 encoded private keys to which he does not know the decryption key.

Update 1: I suppose the public key should also follow the same algos as the private key because a database attacker could replace the public key with one of his own unbeknownst to the user.

By the way, I've already asked this question on Bitcoin Beta SE but with much less emphasis on the specifics and more of just a general best practice question.

About the best you can do is have a master public/private key pair where the public key is stored on your server and the private key is stored offline. When you generate a new private key, encrypt it with the master public key and store that in the database. That way, if a password is ever lost, you can recover the user's private key by using the master private key to decrypt their encrypted private key.


Are Hash Palindromes Possible? I'm trying to figure out whether the following is impossible or merely improbable:

Does there exist an input, I and its hashed value, H, such that:

hash(I) --> H and hash(H) --> I

If not, what prevents it?

TL;DR: The probability of a hash palindrome should be around $1-\frac{1}{e^2} \approx 0.8647.$

I'd like to generalize the question and answer it immediately afterwards.
First of all, let's make the setting more abstract. Say we have a set $M$ of finitely many hash values and denote its cardinality $|M|$ by $m$, usually $M=\{0,1\}^m$.

Then a more general question could be: For any random permutation $H: M \rightarrow M$, how probable is it, that there exists some $x\in M$ such that $\underbrace{H(H(...x))}_{\text{n times}}=x$,
meaning that after $n$ repetitions of $H$ on $x$ the hashed value is equal to the input. We'll have to assume surjectivity of the hash function for now, despite it technically not being accurate. Now that we know what we are looking for let's focus on the case that the $n$-th time is the first time this occurs.

If you are wondering whether $n\geq m$ is possible, there's a section about this at the end of the post, otherwise let's continue with $n < m$.

Case 1:
For simplicty let's look at $n = 1$ first. The question then is equivalent to asking what the probabiliy is, that $H$ has some fixed point or to speak in the language of permutations: $H$ does not produce a derangement of $M$, as there is one value (the fixed point) that is not deranged.

Let's first calculate the probability of a permutation being a derangement.
In general there exist $m!$ many permutations of $M$ and $!m$ of them are in fact derangements, with $!m$ meaning

$$!m=m! \sum_{i=0}^{m} \frac{(-1)^i}{i!}=m!\cdot\left(1-1+\frac12-\frac16+\frac1{24}-\ldots\right)$$.

So we get
$$P(\text{H produces a derangement})=\frac{!m}{m!}$$

Now, as our $m$ get's larger and larger our $n$ does so as well. So I will be assuming that we have large enough values, such as $m=2^{256}$, for both to make the known approximation $\lim_{n\rightarrow \infty} \frac{!m}{m!}=\frac{1}{e}\approx 0.3679$ which results in

\begin{align}
P(\text{H does not produce a derangement})&=\\
1-P(\text{H produces a derangement})&=\\
1-\frac{!m}{m!}&=1-\frac{1}{e} \approx 0.632
\end{align}

So this far, I have not said much more than in Maartens' answer, I just framed it a little bit different.

At this point it's time to let our $n$ increase. I'll reason inductively. We already established, that $n<m$ holds. For notation purposes let's denote the $n$-th repetition of $H$ as $H^{n}$, meaning
$H^{n}(x)=\underbrace{H(H(...x))}_{\text{n times}}$.

Observe, that the first hash not producing a derangement leaves only around $37\%$ of a chance open for the remaining cases to occur. Since those cases are disjoint you can add their corresponding probability.

Case 2:
Now, if the first hash did produce a derangement, what is the probability of the second hash not producing one as well?
As argued before, we get

$P(H^{2}\text{ does not produce a derangement})= P(H \text{ does not produce a derangement})
\\ + P(H \text{ does not produce a derangement})\cdot P(H^{2} \text{ produces a derangement}))=\\(1-\frac{1}{e}) + (1-\frac{1}{e})\cdot \frac{1}{e}= 1-\frac{1}{e^{2}}\approx 0.8647.$

I should mention, that $H^2$ is just another permutation on $M$, meaning that the probability for it to produce a derangement is exactly the same as for $H$.

That much for the start of my inductive reasoning. In the next steps $H^3, H^4 \dots H^{m-1}$ the probablities have to be added in a similar way. This yields the formula

$P(H^{m-1} \text{does not produce a derangement})= \sum_{i=1}^{m-1} \frac{1}{e^{i-1}} - \frac{1}{e^{i}}$. The last telescoping series evaluates to
$1-e^{1-m}$.

The result also mirrors the intuition in the way that not producing any derangement becames less and less likely as we continue to hash our values, thus at some point it is nearly guaranteed to get some hash value back to the input, with the case of $m$ iterations being covered seperately as cycling back guaranteed.

Now, as promised, the argument why $n<m$:
First of all, note that $n$ can't be equal to or greater than $m$. The reason: Let $j$ be any element in $M$. If $\underbrace{H(H(...H(j))}_{m-1 \ times}$ would not have produced a cycle back to any previously hashed value yet, it would have to do so in the next iteration, since all other $m-1$ elements in $M$ were already reached exactly once. This means, that any Hash repeated $m$ times is guaranteed to cycle back to the input.


Purpose of using a=2 in Pollard p-1 factorization method The Pollard p-1 factorization method states if $\gcd(2^{B!}-1,n)=p$ where $p>1$ and $B$ bounds the prime factors of $p$, then $p$ is a prime factor of $n$.

Shouldn't it be $\gcd(a^{B!}-1,n)$ for any arbitrary $a$?
Why are we choosing $a=2$? Is it because it is computationally cheaper to compute powers of $2$? ( left shift ).
Moreover, should $B$ be an upper bound of the prime factor of $p-1$ or an upper bound of the prime factor of $p-1$ along with its powers?

Shouldn't it be $\gcd(a^{B!}-1,n)$ for any arbitrary $a$.

Yes, and your code tries calculates it in the while loop. Note: normally

$$M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$$ only primes which are less then or equal to $B$ constitute to $M$. The pseudocode in your slide includes all numbers $<B$ which is not correct, it must be prime less or equal to $B$.

  Why are we choosing $a=2$? is it because it is computationally cheaper to compute powers of $2$? ( left shift ).

We want a random integer $a$ that is co-prime to $n$, i.e $\gcd(a,n)=1$. If 2 is possible choice as in RSA modulus - $n$ is a product of two odd primes, it will be easy to calculate $\gcd(2^{B!}-1,n)$

  moreover, should $B$, be an upper bound of prime factor of $p-1$ or upper bound of prime factor of $p-1$ along with its powers?

$B$ is a smooth number, and in the beginning, you select any smoothness bound for $B$. From Wikipedia code;

  select a smoothness bound B
  define $M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$
  randomly pick a coprime to $n$ (note: we can actually fix $a$, e.g. if $n$ is odd, then we can always select $a = 2$, random selection here is not imperative)
  compute $g = \gcd(a^M − 1, n)$ (note: exponentiation can be done modulo $n$)
  if $1 < g < n$ then return $g$
  if $g = 1$ then select a larger $B$ and go to step 2 or return failure
  if $g = n$ then select a smaller $B$ and go to step 2 or return failure

So the algorithm in sense an adaptive algorithm. In a failure either you can stop or adjust the smoothness bound.


AES Mix columns bit example I have been given a 4x4 matrix and each entry is an 8-bit long byte. I have been given the 4x4 matrix that I need to multiply each column by of the first matrix by.

$$\begin{pmatrix}2 & 3 & 1 & 1\\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2\end{pmatrix}$$

The method that I have been told to use seems confusing. I have searched around the internet and found many examples with polynomials but I'm not supposed to use this method.

All I have been told is:

Multiplying by 01 does nothing
 Multiplying by 02 corresponds to multiplying the byte by 10 (because 2 is 10 in binary). This
is simply a left shift by one place. If the left-hand bit of the original byte was 1, then XOR the
answer with 100011011.
 Multiplying by 03 corresponds to multiplying the byte by 11 (because 3 is 11 in binary). This is
a left shift, followed by an XOR with the original byte. Again, if the left-hand bit of the original
byte was 1, then XOR the answer with 100011011.

I find the XOR bit strange as well - because that is a string of 9 bits and the bytes are only 8.

Can anyone make sense of this or point me in the direction of a good example?

If you look at the code in the Wikipedia we will see this part of the code;

h = (unsigned char)((signed char)r[c] >> 7);
b[c] = r[c] << 1;
[c] ^= 0x1B & h;

h stores the leftmost bit of c

c is x-or'ed with 0x1b but not with 0x11b  why?

When shifting r left by one, the MSB value is discarded. Before discarding, we hold this value with h.

If h==0 than modulus operation is not required. The 0x1B & h = 0x0 so there is no x-or with 0x1b
If h=1 than modulus operation is required. The 0x1B & h = 0x1B. The x-or with 0x1b is performed.
Note that: it is not x-or with 0x11b it is with 0x1b since we discarded the MSB 1 while shifting. Therefore, there is no need to x-or with 0x11b, x-oring with 0x1b is enough. Now, it is clear that everthing is in Bytes.

A small example;

Here [ ] represents 8-bit.

Let multiply $a = (x^7+x^6+x^3+x)$ by $\{2\}$

binary representation of  $a = [11001010]$
$h = 1 = [00000001]$
$b = a \ll 1 = 1[10010100]$ but everthing is in Bytes, therefore
$b = [10010100]$
$h \wedge 0x1b = [00000001] \wedge [00011011] = [00011011] = 0x1b$
$b \oplus 0x1b = [10010100] \oplus [00011011] = [10001111] = 0x8f$


What Proof of Work does IOTA use? I have some trouble finding valid information about IOTA. Actually I would be nice if there would be a good source.

So my question is:
Bitcoin uses the SHA-256 twice and some "target bits" for hashing it's blocks.

What PoW does IOTA use? Some sort of Hashcash Lite - but how does this work in detail?
Is there also a header with a timestamp and some previous block hash?

IOTA doesn't use proof of work.
IOTA is a tangle, and the consensus is reach based on the information propagation in the network. You can find more information about it here:
https://forum.iota.org/t/iota-consensus-masterclass/1193