One Time Password generation algorithm to ensure data/transaction integrity? Here is my use case:

A user is trying to transfer money to his friend's account. He enters transaction details on banking website. Bank receives it and then
Bank sends transaction details (receiver name and amount) + One Time Password back to the user (may be through different channel : mobile) so that user can verify the transaction details (this is to ensure transaction integrity. ie., no man-in-the-middle attack) and enter the OTP to confirm the transaction.

What is the threat model?

Man-in-the-middle attack. If an attacker (in middle)  modifies the receiver's bank account details with attacker controlled bank account but shows fake transaction summary, the OTP that sent along with the transaction details should become invalid.

What OTP generation algorithm should I use?

   someOTPgenAlgo(transaction details) = OTP.

Now if the attacker changes the receiver bank account details, he also has to find the matching OTP for that modified transaction details Which should be impossible. How do I achieve this? Is following enough ?

someOTPgenALgo(transaction details + some random key ) = OTP

Thanks a lot. Sorry if the question is naive, I am pretty clueless about this

What you're imagining is impossible to be secure.

Basically what you're describing is a message authentication system where a message is MAC'ed and only the MAC is matched against the actual MAC, but it isn't checked whether the message actually generates this MAC, so an attacker could just fake the transaction details and leave the MAC be and the user would enter the MAC and thus accept the transaction.

Now I'm gonna tell you how many banks here in Germany solved the problem.
This assumes you've issued a card with a chip to every customer and keep track of all cards.
If the user wants to make a transaction, he uses his browser to fill in the data. Then the browser takes him to a page where he is either presented with an optical code (not unlike a QR code, but also using time-based patterns) or some data.
The user has to either scan the code or enter the data, into a physically separate device in which the user plugged the card. The data consists of the amount and the last few digits of the recipients account number. Now the device passes this data to the card which basically just performs HOTP but also incorporates the values for amount and recipient in the calculations. This is done after the user verified the correctness of the transaction on the built-in display. Now he's presented with a short code which he has to enter into the browser. The server confirms the calculations and initiates the transaction.

In a more mathyy way, the OTP would look like this:

$$\text{OTP}=\operatorname{BytesToCode}(\operatorname{HMAC-SHA256}_{\text{Card-Server-Key}}(\text{amount}||\text{recipient}||\text{counter}))$$

welcome to the crypto stackexchange :)

I'd suggest using HOTP, effectively it is a derivate of the OATH specification.

effectively both parties share a shared secret and a counter.

For each authentication the client computes OTP = HOTP(transaction + counter). This is often used in banks today. This approach assumes enrolling the OTP device (the bank usually provides the shared password and the initial counter state).

The counter increases with every transaction, so the replay shouldn't be possible. If there's no counter (or the counter is out of synchro), the challenge-response mode could be used. (as well to reset/synchronize the counter)


Perform ENT / Dieharder on raw entropy or on whitenened entropy? In this question about hardware random number generator, a discussion about the following question has been started: In order to test RNG's and entropy's quality, should test suites like ENT and Dieharder be applied on raw entropy or on whitened entropy?

It depends on the goal of performing the test:

If the goal is to test for a problem in the whitening, then the test should be run on the whitened output, of course. If the test fails (more often than predicted by the P-value), the whitening is demonstrated bad. If the test pass, we can deduce nothing cryptographically useful (the source or the whitening could be badly defective, or/and the tested output could be totally predictable by who knows how it was generated). The test is slightly less pointless if the source is replaced with a very low entropy source during the test.
If the goal is to test for a problem in the noise source, then the test should be run on the noise source before whitening. If the test fails (more often than predicted by the P-value), then the noise source is demonstrated not good enough to be used for cryptographic purposes without whitening (but it might still be excellent and perfectly usable with whitening; many if not most good truly raw sources fail Dieharder, some fail ENT). If the test pass, we can deduce nothing cryptographically useful without knowledge of how the noise source is actually operating, and of how the test works.
If the goal is to pass a conformance test, then the rule it to perform things as satisfies the person with the rubber stamp. If s/he does not care, the easy route is to use the whitened output, so that a good whitening is a sufficient way to pass the test, irrespective of the source. I guess that happened (for FIPS 140-1 and -2 conformance, some tests where mandatory and too stringent for most practical sources; reason prevailed and the tests have been removed, yet the tests remain what some suppliers of RNGs brag about).

There is no other rational goal met by solely performing a RNG test on a sequence, when it passes. Repeating the first bullet: if the test is a blackbox test on the whitened output of a source, then a pass indicates nothing cryptographically useful about the source, the whitening, or the combination.

I have assumed the test is at least correct (and in particular, fails with likelihood comparable to its stated P-value when given truly random input), and correctly used. That's more often than not disproved by repeatedly applying the test to the output of a known-good CSPRNG. The test should pass (with occasional failures per its P-value) regardless of the CSPRNG's input (as long as it is arbitrary rather than tailored to the test being tested).

Note: ENT is a terrible test from a cryptographic standpoint, especially for a whitened source. For example, a PRNG that 90% of the time outputs a byte equal to one more (modulo 256) than the previous one, and is random the other 10%, is still considered perfectly OK.

Note: Temperature or process variations, EMI, aging, adversarial influence, or Murphy's law, can ruin a noise source. In cryptographic devices it is thus critical that the proper operation of the noise source is continuously monitored. A technically valid security certification process aims at checking source, whitening, and that monitoring puts the whole device in a safe state (as a minimum: squelches the whitened output) on detection of failure. This goal is antagonist to field reliability, and it is hard to get both.

It may be useful to illustrate how a TRNG works:-

And perhaps more importantly, you have to realise that random means random, or uncertain. It absolutely does not mean independently and identically distributed random numbers (non IID).  A gangster's lucky die with a corner filed off is random.  It is biased yes, but it is nevertheless random as no particular outcome can be predicted with 100% certainty. So it might be used as the analogue entropy source in the above diagram. Similarly you might use a Zener diode or a photon detector for this purpose.

The (digitised) raw data output from the noise source, is called the entropy. If the source is a Zener, the raw might look like the following if viewed on an oscilloscope:-

Notice the asymetry in relation to the little yellow arrow with the "1" in it.  That's the zero reference.  And this is how it looks following digitisation:-

You can clearly see that it's highly biased and correlated, and the values are 10 bit samples. This is the entropy source within a real TRNG on my wall and is very non IID.  It's a standard avalanche effect log normal distribution plus correlation of readings in actuality.  Most entropy sources are non IID, although some get pretty close to IID.  The Quantis laser devices get to > 0.94 bits/bit. It is random at this raw data stage, but not IID as required for the final output of a TRNG. My example trace is conservatively about 1.5 bits /sample entropy, or ~15% purity.

And so to ent /Diehard.  What possible information could be gained by running an ent test on this raw data?  It will fail massively, as it should. Diehard and all other randomness tests will also fail.  Such tests cannot even accept 10 bit worded data.  And the data might be received in ASCII comma separated format or as a Numpy array, further invalidating testing.  The reason is in the name "Randomness Test".  This raw entropy is not even close to IID random, which is the purpose these tests are designed for.

And almost finally, the following is an ent test of the above raw entropy:-

Entropy = 5.840091 bits per byte.

Optimum compression would reduce the size
of this 500000 byte file by 26 percent.

Chi square distribution for 500000 samples is 6926978.44, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 160.3918 (127.5 = random).
Monte Carlo value for Pi is 1.805719223 (error 42.52 percent).
Serial correlation coefficient is 0.286267 (totally uncorrelated =
0.0).

The test has failed. So will all other randomness tests. Even the entropy measurement of 5.84 bits /byte is incorrect as ent is not an entropy measurement tool.  A live source of raw entropy can be found here.  What use running diehard on the linked data that only ranges 50 units at most? It will fail with a string of p = 0s or p = 1s. As expected.

In summary, you check the final output of a TRNG with these tests to ensure that the whole system (including conditioning) works properly. And to a lesser extent, the tests might also pick up a failed entropy source but that is really the purview of Health Tests in the initial diagram.


Why do key fobs/garage doors openers use rolling codes instead of PGP or SSL encryption? Wouldn't they be more secure if they used the same encryption technology computers use for remote access?

I can think of several issues with using PGP or TLS:

Both PGP and TLS require certificate management (unless password based), it would be tricky to get a PKI going for this;
PGP and TLS are overkill for key fobs / garage doors and would put unnecessary strain on the choice of processor and battery;
PGP and TLS require access to a secure random number generator, which is also pretty expensive to put in a key fob.
The TLS handshake requires two way communication;
Both TLS and GPG require intricate implementation of the message protocol (stuff you can do without for a door opener).

Even from a technical standpoint TLS is overkill; you're really just interested in authenticating a command that cannot be replayed. This explains the choice of a rolling code I guess.

Those are the technical reasons. I guess most of the manufacturers aren't that IT savvy either. They might not even know about PGP or TLS. They're more likely to be interested in motor & hinge design and picking the right color for your door.

That said, there's likely some kind of home automation that can

open a door and
uses some kind of transport protocol or message authentication.

I doubt if these two "heavy weight" protocols are used towards the door though.

Every mifare card does the cert handshake just fine with minimal effort... the chip has the crypto in it you load the cert and call it a day... but I am also after a commercially available programmable remote that can do the same. Reset remote so remote generates new private key... hold programming key combo push a button on the receiver to program new remote... remote sends public cert and that is it.... nothing else is really required... if you want 2-way handshake then remote receives receiver's public cert so it would not even talk to other receivers but that is not necessary for this to work.... if anyone knows of an opener that does this let me know.


Autocorrelation in Autokey I know that Vigenère can broken using auto-correlation (as explained at cryptool-online.org). Now my question is: Why does this also work with autokey (tested it using crypttool)?

To prove that I have already put work into this, I have read Simon Singh: “The Code Book”, F.L.Bauer: “Decrypted Secrets”. Though the latter book said in does not work the same way in autokey than it does in Vigenère. Why is there still a maximum of coincidences when the text is shifted by the key length?

In a Vigenère cipher, the $i$-th ciphertext letter $c_i$ is calculated as $p_i + k_{i \bmod \ell}$, where $p_i$ is the $i$-th plaintext letter, $k_i$ is the $i$-th key letter, and $\ell$ is the length of the key.  Thus, the difference between two ciphertext letters at positions $i$ and $j$ is $$c_i - c_j = p_i - p_j + c_{i \bmod \ell} - c_{j \bmod \ell}.$$

Normally, for this difference to be zero, the difference between the key letters would have to just happen to cancel out the difference between the plaintext letters.  When $i \equiv j \pmod \ell$, however, the last two terms cancel out, leaving just $p_i - p_j$, which, since the plaintext typically has an uneven letter frequency distribution, is more likely to be zero than one would otherwise expect.

Now, consider the autokey cipher, where (beyond the first $\ell$ letters) $c_i = p_i + p_{i-\ell}$.  Now the difference between two ciphertext letters is given by $$c_i - c_j = p_i - p_j + p_{i-\ell} - p_{j-\ell}.$$  This time, when $i - j = \ell$, it's the middle terms that cancel, leaving just $p_i - p_{j-\ell}$ $=$ $p_i - p_{i-2\ell}$.

Again, it's a lot more likely for a single pair of plaintext letters to be identical than it is for the differences of two pairs of letters to cancel out just by chance.  Exactly how much more likely depends on details of the plaintext frequency distribution, but the qualitative behavior is quite robust and shows up for most naturally occurring letter frequencies.

Ps. Note that the conditions for this cancellation to occur are different.  For the Vigenère cipher, cancellation occurs whenever $i - j$ is a multiple of the key length $\ell$, producing a characteristic comb-shaped autocorrelation plot.  For an autokey cipher, however, cancellation only occurs when $i - j$ exactly equals the key length, resulting in just a single peak.

It works with autokey system because the key itself have a bias : in the key is much more E than other letters (this is a natural consequence of using a clear text as key).


Does the IV need to be known by AES (CBC mode)? I was thinking about this today and thought I should ask. I think I understand IV's enough to say that they are basically the same thing as Salts when talking about hashes. They are there to improve randomness between messages. If the IV is simple appended, or prepended to the plain text, why does AES need to know the IV to decrypt it? Can't it just decrypt it, drop the first x amount of bytes and then it has the original plaintext or does AES do some special jizz-jazz with the first bytes in the stream?

The initialization vector is XORed against the first plaintext block before encryption in CBC mode, as shown in the Wikipedia article on block cipher modes. After the first block is decrypted, you still have an intermediate value which has been XORed with the plaintext — without this, you have little hope of recovering the plaintext. However, you do not need the IV to decrypt subsequent blocks.

You could perform CBC in a way that would remove the need to know the initialization vector (note: this is not recommended or encouraged, just pointing it out for the novelty). If you use a null IV and use a random value for the first block of plaintext, you can discard this value and only transmit the ciphertext. Note that this actually gains you nothing, because now the ciphertext is one whole block longer!

I agree. For my purposes I've been prepending the plaintext with a block
of random data so that when the receiver decrypts they simply discard the
first block as it was only there to ensure the ciphertext always changes even
if the plaintext payload was the same (not counting the first random block).
This seems to achieve what the initialization vector was doing from the
beginning without the need to send the initialization vector with the
ciphertext. IE it can be ignored.

It is recommended that an Initialization vector be random and used only once meaning it will some how need to be send to the receiver which seems identical to the proposal of generating a random first block of plaintext and discarding it after decryption.


Can you help me understand Format Preserving Encryption? I came across the definition of format-preserving encryption (FPE) as first defined in a seminal paper by Black and Rogaway. Based on their paper, FPE (or prefix cipher) is defined as follows (quoted from Wikipedia):

  One simple way to create an FPE algorithm on ${0,...,N-1}$ is to assign a pseudorandom weight to each integer, then sort by weight. The weights are defined by applying an existing block cipher to each integer.

Can you help me understand the difference between this and monoalphabetic substitution, and what security is offered by FPE?

I cannot understand what is the difference with monoalphabetic substitution and what is the security offered.

A monoalphabetic cipher applies to individual symbols of the plaintext.  But an FPE scheme works on the whole message as a unit.  In the set {0,...,N-1} that you mention, N is the size of the message space—the number of distinct messages, not the number of distinct symbols; each number represents a distinct message, not a symbol of a message.  So for example:

For US Social Security numbers, which are 9 digits, N is one billion, and each number in the set {0,...,N-1} stands for a distinct SSN.
Credit card numbers have 16 digits, but generally the first 6 and last 4 digits must be left in the clear, so the middle 6 are encrypted and N = one million.

But the 10 digits left in the clear are used as a "tweak" to the encryption, so that 123456 in the middle six encrypts to different values for different credit card numbers.

The way FPE works is (ignoring the "tweak" concept that I mentioned above):

You define a bijective function between your message space and the set {0,...,N-1}.  For SSNs, N = 1,000,000,000, and the bijective function just treats the 9-digit sequence as a decimal numeral with its most significant digits padded with zeroes.
The FPE scheme gives you a bijective encryption function that takes a secret key and a number between {0,...,N-1} and outputs another number between {0,...,N-1}.  (It also takes a tweak, but I'm ignoring that for simplicity.)

So to encrypt an SSN you convert the SSN into a number using the function from (1), encrypt that number using the FPE scheme, and convert the encrypted number to an encrypted SSN using the inverse of the function in (1).  To decrypt you use the inverses of the functions.

One of the reasons why FPE scheme is defined in terms of sets {0,...,N-1} for user-chosen values of N is for flexibility; as long as you can define a bijection between your message space and such a set, you can use FPE to encrypt those values.  For example, if you want to apply FPE to a database date field, you can't just read the date's sequence of digits as a number, because some such sequences of digits aren't valid dates (e.g., 2014-54-35), but the encryption could well output the number 20,145,435.  But you can use date arithmetic to represent a date as a count of days since a reference "beginning of time," and then apply FPE using this bijection.

The security offered gets a bit more complex, but at the most basic level it is that the FPE is a pseudorandom permutation on the set {0,...,N-1}.  Imagine a solution where instead of using a cipher, you had a big database where, for each plaintext Social Security number, you stored a unique, randomly chosen sequence of nine digits.  The encryption operation would go somewhat like this.  Given a plaintext P:

Search the database for an entry that has P as its plaintext.
If P is already associated with a ciphertext C, then return C;
Otherwise, set C to some message chosen at random (using a true random number generator).
Search the database for an entry that has C as its ciphertext.
If C is already in the database, go to 3.
Otherwise, store the entry (P, C) in the database, and return C.

FPE's basic security goal, put in simplified terms, is to be no worse than that in practice, from the point of view of an attacker who has doesn't have the encryption key but might have seen a subset of the plaintext/ciphertext pairs.

Note as well that there exist token vault solutions that work like the six-step sketch that I described—a database that associates plaintext with unique random values.  So in another sense, the security goal of FPE is offer comparable practical security but at lower cost and better reliability and performance.

Mono alphabetic substitution ciphers are vulnerable to the following.

It can be cracked using statistical analysis.
Ciphertext for same plaintext will remain the same

Format Preserving encryption is not easy to crack using statistical analysis due to the PRN. As it is not a mono alphabetic substitution, similar inputs wouldn't result in similar ciphertext.


CCA-Security Proof of a particular scheme Suppose to have a scheme that works so:
$\mathcal{P}_k =:\{P_k\colon \{0,1\}^{2n} \to \{0,1\}^{2n} \}$ is a strong PRP family.

Encryption: $\operatorname{Enc}(k,m)=P_k(m\mathbin\Vert r)$, where $\Vert$ indicates the concatenation and $r\leftarrow \$ \{0,1\}^n$ ($r$ is random from $\{0,1\}^n$)

Decryption: $m\mathbin\Vert r={P^{-1}}_k (c)$,  return $m$;

I remember that we can define $G^{CCA}_{\pi,\mathcal{A}} (\lambda, b)$ as follows:

1) $k \leftarrow \{0,1\}^\lambda$

2) The adversary $\mathcal{A}$ choose two messages $m_0,m_1$.

3)$c_b \leftarrow Enc(k,m_b)$, where $b \leftarrow \$ \{0,1\}$. (I denote with $\$$ to say that $b$ is random).

4) Adversary must say what message has been decrypted.
Let's assume that $\mathcal{A}$ have access to both $Enc_k()$ and $Dec_k()$ (CCA-Security) algorithm. So $b' \leftarrow \mathcal{A}(1^{\lambda},c_b)$.

5)$\mathcal{A}$ succeeds if $b'=b$.

We have CCA-security if $\mathcal{A}$ can not do better than guessing, that's for all PPT adversary $A$

$$|Pr[G^{CCA}_{\pi,\mathcal{A}} (\lambda, 1)=1]-Pr[G^{CCA}_{\pi,\mathcal{A}} (\lambda, 0)=1]| \leq \upsilon(\lambda) \in negl(\lambda)$$

How can I proceed by reduction? Can someone give me an help?


Multiple (RSA) public key encryption how to verify others received the same information? Non-deterministic encryption I have an RSA system between multiple parties. Alice takes the targets (Bob and Oliver) public keys and encrypts a message using them and sends it to them. All parties know each other's public keys and the ciphertexts received.

I wanted to verify that all the targets are receiving the same message, so I thought Bob could take Oliver's public key and encrypt the received message(after decrypting with his own private key) and compare it but I'm using non-deterministic encryption, therefore, the ciphers produced are different for the same message and public key.

I know using deterministic encryption prone to attacks so I was wondering if there are any other solutions out there or do I have to risk using deterministic. For reference, I'm using JavaScript and AES for encryption.

How do I verify that Oliver and Bob receive the same message without them having to send it to each other?

As long as you are not wedded to RSA, here's a way that completely solves the problem (and scales to more than two targets).

The general idea is that we do EC-ElGamal in a pairing friendly curve (that is, an elliptic curve that has a computable function $e(X, Y)$ that satisfies the identity $e(aG, bG) = e(G, G)^{ab}$, for any integers $a, b$ (and $G$ is the generator point), and for which $e(G, G) \ne 1$.  The power on the right is typically a multiplicative group of a finite field (which would depend on the curve you're using), that's not important at this point.

In any case, Bob and Oliver would select private keys $b$ and $c$ (I'll use c rather than o for Oliver, because o is too easily confused with 0), and their public keys are $B = bG$ and $C = cG$.

The encrypt, Alice takes the message $m$, and maps it in a way that is both invertable and nondeterministic to a point $M$ (it has to be nondeterministic, otherwise a third party with a guess of $m$ can verify his guess using the $e$ function).  Then, she selects a random value $r$, and generates the two ciphertexts:

$$rG, rB + M$$

$$rG, rC + M$$

(note: each ciphertext can use the same $rG$ value, or use different ones; both varieties work).

Bob and Oliver first check whether all the points in the ciphertexts are actually points in the curve (I'm not sure what can go wrong if they're not, but it's an easy check to do).

Then, Bob can decrypt his received ciphertext $X, Y$ by computing $M = Y - bX$ and then mapping $M$ back to the original $m$.

Bob can then verify that Oliver got the same message by reconstructing $rC$ (using the value $M$ he got during decryption), and then verifying that $e( G, rC ) = e( rG, C )$ (where $rG$ is the value from Oliver's ciphertext); if they received the same message, then both values are $e( G, G )^{rc}$

It depends on the what are you protecting from. If the scenario is that each party does not trust to other one, then there is no solution.

Alice can be in agreement with Bob against Oliver.

Scenario 1: Alice can send message X1 to Oliver and message X2 to Bob, and the message X2 means "pretend you received message X1". If Oliver wants to verify what Bob received (e.g. via hash or similar signature algorithm), Bob will just generate everything needed for X1.

Scenario 2: Alice can generate a random password, encrypt the message with a symmetric algorithm and send it to both Bob and Oliver, or just make this encrypted message publicly available, so that each party sees there is only one message. She sends this password to Bob and Oliver separately encrypting it with their RAS public keys. But again there is no guarantee for Oliver that Alice has not sent some other messages to Bob.


Deterministically combine more than one source of entropy What is the proper/canonical way to do this?
For example, $0 < r1 < 1$ and $0 < r2 < 1$. Presuming uniformly distributed probabilities for the two, combining/averaging them is going to bias very quickly towards $0.5$.
The specific use case I have is a game/simulation I'm programming. An entity has a random number it was given that's specific to it; Their individual behaviours also have random numbers associated with them. For the purposes of most behavioural calculations, I only use the behaviour random number, but for a few I want to incorporate the entity's random number. Simply averaging them will result in less randomness.
Desired Outcome : Deterministically combine more than one source of entropy
So “Entity A” may have a small random number, and so most of its attributes are skewed small. It's behaviour random number happens to be big, so most of its behaviour attributes are skewed large. When combined the two random numbers deterministically result in $n$, and so some of its behaviour attributes skew towards $n$.
RE: Off-Topic
My question is not specific to game development. The particular use case is. How do cryptographers deterministically combine sources of entropy? I assume they have uses case for this outcome.

Set $r = r_1 + r_2 - \mathsf{floor}(r_1 + r_2)$. One (possible) advantage of this approach is that the result will be uniformly random in [0, 1] even if only one of $r_1$, $r_2$ is uniformly random. (Assuming the two values are independent.)

In Python you can also express this as

r = (r1 + r2) % 1.0

If you just want to combine them, you can just add them. You will get an even distribution between 0 < r < 2. An alternative is to get the bytes of the floating point numbers, and XOR them. The result may not be a valid floating point number however. You may also convert the floating point numbers to a string, with arbitrary precision that suits you, and hash them together. Either hash(r1) + hash(r2), or hash(r1+r2), or hash(hash(r1)+hash(r2)), where + is  Javascript concatenation for strings. There are public hash libraries for SHA, BCrypt, etc.


Is it safer to use timestamp in REST authentication? I am working on a personal project to build a REST authentication system which authenticate clients via three parameters:

apikey = example-apikey-34433
hash = examplehash-notarealhash-a34io4oehosseesr
timestamp = 2000000000

Every client has a unique apikey and secret key, stored in a database.

Hash is a SHA256 hash of the secret key + timestamp. This is to generate a unique authentication hash for every request.

Would this be secure against brute forcing? Because when a client can supply any timestamp, is it true that multiple hashes can be correct?

Wouldn't it be better to just rely on the apikey and (plain text) secret key? Or do you know a better way to do this?

Might need some clarification, but it sounds like you are wondering how to 'salt' the hash. First if you intend to concatenate the secret key with anything else, the standard way to handle this is a HMAC. A common way to handle this is PBKDF2:

https://en.wikipedia.org/wiki/PBKDF2

Basically this does a secure combination of secret codes and the timestamp/salt. While the user can supply the timestamp, the probability that they could guess a timestamp that gives the same hash is very unlikely.

So PBKDF2 with a timestamp salt may be what you're looking for. Good Luck!


Can you distinguish encryption methods from the output? Suppose that you see all IP communication packets between two computers for a day, as they pass through a connecting router, and this amounts to 10MB. You additionally know that all data transmission follows the standard "RSA-1024 plus AES-128" protocol. To be even more specific, suppose you know only one computer is doing RSA decryption, which computer that is, its specific "public key", and that the RSA decryption is only done to re-initiate the AES key after the other computer is (instantly) rebooted.

Could you look at the 10mb and get any information about whether the computer was rebooted?

I wonder if these pseudo-random streams could be "hashed" in some way to help...e.g., maybe 0.03 bits of information is revealed ("Because of this abnormal X-X-X data series in the stream, there is a 60% chance it was rebooted, instead of the normal 50%.").

I know that any revealing (even a tiny part of a single bit as useless as the rebooting of a computer) is against the goal of this encryption, so I ask in a rigorous way for those familiar with these protocols and their outputs. I truly wonder if there isn't some blatant unencrypted "I need to login from scratch, please!" signal in the standard protocols. When a computer loses its AES key, they could be blatant to help the server, or they could rely on the server to use AES first, conclude it's gibberish, and then try RSA. I'm guessing the latter is done, but hoping for confirmation here.

To answer my own question, I do believe that 0.03 bits would be reasonable, mainly due to the timing of the packets. RSA encryption/decryption takes longer, so delayed responses correlate with a reboot (please notice I'm ignoring the actual power-down time and wrote "instantly rebooted" in the problem statement to focus just on the cryptography).

Note: We need more information on the protocol to confidently answer this, but I know nothing beyond the AES and RSA algorithms.  This is why I ask the question.  So, if you must, please just assume the server URL is "https://whatever.ext" or choose a common reasonable protocol.

Well, with standard protocols (TLS, SSH, IPsec), there really is a blatant unencrypted "I need to login from scratch, please!" message.  That's because when they first come up, they don't share keying material with the peer, and so they can't encrypt any messages.  Instead, they perform some sort of key exchange process using nonencrypted messages, and those messages are easily distinguishable.

Now, I suppose it would be possible to define a protocol where this initial message would be indistinguishable from an encrypted message.  However, the details would appear to be rather finicky (you'd have to worry about message timing and message length), and probably end up being expensive.  In addition, reboots are not actually instantaneous, and when you are rebooting, you obviously can't send out any messages.  I can't think of any scenario where the effort would be worth the cost.

The security of two encryption schemes does not imply that you cannot distinguish their ciphertexts. (In fact, it may be even possible to decide which public key a ciphertext has been encrypted with.)

Consider the following:
AES ciphertexts are simply bitstrings of a certain length.
RSA ciphertexts on the other hand are elements of $\mathbb{Z}_N^{*}$.
In general when you have an AES ciphertext, there will be bistrings that would not decode to valid elements of $\mathbb{Z}_N^{*}$.

As an example consider the RSA modulus $11\cdot13=143_{10}=10001111_2$.
Now, if we would see the bitstring $11000000_2=192_{10}$ we would immediately see, that this can not be an RSA ciphertext, because even though, the bitstring has the correct length, it decodes to $192 > 143$ and therefore not to a valid element of $\mathbb{Z}_N^{*}$.

There are ways to get around that, such as Admissible Encodings, but general, it is possible to distinguish two encryption schemes based on their ciphertexts.


Could the Enigma algorithm be classified as a Feistel network? The Enigma algorithm is a encryption method that was developed (I believe) by the Germans in WWII. It went a little something like this:

When a letter was typed on the keyboard of the Enigma machine, it was first sent through the first rotor, which would shift the letter according to its present setting. The new letter would then pass through the second rotor, where it would be replaced by a substitution according to the present setting of the second rotor. This new letter would in turn pass through the third rotor, again being substituted accordingly. Next, this new letter would be bounced off of a reflector, and back through the three rotors in reverse order. The trick that made Enigma so powerful for its time though, was the spinning of the rotors. As the plain text letter passed through the first rotor, the first rotor would rotate one position. The other two rotors would remain stationary until the first rotor had rotated 26 times (the number of letters in the alphabet and therefore, one full rotation). Then the second rotor would rotate one position. After the second rotor had rotated 26 times (26X26 letters, since the first rotor has to rotate 26 times for every time the second rotor rotates), the third rotor would rotate one position. The cycle would continue like this for the entire length of the message. The result was a shifting shift. In other words, an s could be encoded as a b in the first part of the message, and then as an m later in the message. This principle of the shifting rotors allowed for 26X26X26 = 17576 possible positions of the rotors.
In order for the recipient to decode the message, they would need to know the initial settings of the rotors, and then put the cipher text through the machine to find the plain text. The Germans devised a system by which all of the recipients would set their rotors to predetermined settings according to the date. Each clerk had a book detailing the settings for each day.

Although (I believe) a true Feistel involves splitting into two halves (which doesn't happen here) and where one old half == other new half after a round of encryption, could this algorithm be classified as a Feistel network?

Enigma is not a Feistel cipher. A "Feistel cipher" is a block cipher with a specific structure, namely the whole business with the two halves, the combination of one half with a (one-way) function of the other half and a reversible operation (e.g. XOR), and the swap. See the Wikipedia page which has nice schematics.

So considering Enigma as a kind of Feistel cipher is like considering a salmon as a kind of chicken: yeah, it has no beak, no feathers, no legs and no wings, but could it be a called a chicken ? Strangely enough, I tend to answer no to that. Even though both the salmon and the chicken are edible. But being edible is not sufficient to grant chickenness. Similarly, being a symmetric cipher is not sufficient to grant Feistelness.

It seems to me the Enigma could have been made a Good Deal more Secure (if not unbreakable) by a few basic modifications.

They could have used irrational numbers (eg Pi-although nobody should even THINK of using That one-Too Obvious) for the changing of the wheels.
Or-they could have used public key encryption based on prime factoring for the initial positioning of the rotors.
Heck-they could even have used a Block Cipher Stecker Board, with words instead of letters (although that would have been Cumbersome.)


Periodicity of hash functions Consider the naive hash function: HASH = INPUT % 4. This function is periodic in the sense that if we call it with sequential numbers 0, 1, 2, 3, 4, 5, ... the produced hashed sequence will have periodicity of four: 0, 1, 2, 3, 0, 1, 2, 3, 0, ....

My question is whether modern cryptographic hash functions, such as SHA256, are periodic in this sense? In other words, are there some integers 0 <= n and 0 < k such that HASH(n + b) = HASH(n + b + ak) for all integers b in [0, k - 1] and all positive integers a? For example, will the sequence SHA256(0), SHA256(1), SHA256(2), SHA256(3), ... be periodic after some point?

One of the purposes of Hash function is, of course, to make collisions unlikely (both of the deliberate and undeliberate kind). With periodicity this would be broken. However, to avoid collisions in practice, we only need that n and/or k are (very) large and unknown. Has it been proven that no n and k exists?

(This question was previously asked on Stack Overflow.)

What you're actually looking for is called the cycle length most of the time in cryptography.

For a random mapping $f:\{1,2,\ldots,k\} \rightarrow \{1,2,\ldots,k\}$ the cycle length is expected to be $\sqrt{\pi k/8}$ and the tail length is expected to be the same.
If you want more details and some fancy illustrations, the Handbook of Applied Cryptography (PDF) has them.

If you model a cryptographic hash function as a random mapping (which you do most of the time), then you'd expect a cycle length of $\sqrt{\pi 2^n / 8}=\sqrt{\pi}\cdot 2^{\frac{n-3}{2}}$ which is $\approx 2^{127.325748064736}$ for $n=256$, which is the case for SHA-256.

So the TL;DR is:
No it has not been proven that no such $n,k$ exist, but chances are that they exist and range in the area of the values I showed above, which are of no practical relevance as of today.

statrting with any and every hash , iterated rehash of  hash must end in a cycle . It may be 2^256 long but it must end in a cycle. short cycles are very valuable as they may make bitcoin mining easy. each indiviual part of the hash algorithm may have its own cycle, predicting a cycle length for the amalgam of all the parts, likely around the product of all the cycle lengths for all the parts.


Which is the simplest cryptographic algorithm which is close to commercial-level security? An algorithm is simpler than another if

It is easier to explain to a noob with basic high-school math knowledge.
It is easier to securely self-implement by an intermediate programmer (Yes I know one should never 'roll their own' but this is just a metric of comparing simplicity)
Can be done by hand & paper more easily (not necessarily that it can practically be done on paper, but that it is easier to do on paper if one were to take the pains to do so)
Involves lesser steps.
Any other factors that don't immediately come to mind.

To give an example with popular ciphers, by these criteria RSA is simpler than AES.
The point of this question is maybe find out about some very clever albeit less popular/unheard of cryptographic algorithms that are at or quite close to real commercial-level security while still being incredibly simple.
To use simpler words, the requirements are much above Caesar cipher but much below AES, in terms of complexity.
A question on the most secure hand ciphers inspired this question, except there are no such limitations of not having computational/calculational power here, but similar/stricter restriction on complexity. The idea is to test the limits of simplicity that cryptography can reach while still being done right.
Perhaps symmetric ciphers would be ideal for the criteria of simplicity. However, obviously, any cipher is to-the-mark if it is simple and secure enough.
Edit 1 : The criteria listed above are in order of importance, i.e, the 1st is more important than the second and so on.

I would say MiMC is the simplest block cipher with plausible security. The idea is to cube the state, add a random constant, and repeat. This is typically done in a large prime field, but it is trivial to implement field arithmetic in any language with big integer support. Here's a Python implementation:
def mimc(x, p, k, constants):
    x = (x + k) % p
    for c in constants:
        x = (x**3 + k + c) % p
    return x

Notes:

x is the input.
p is the (prime) order of the field.
k is the block cipher key.
constants is a list of r random field elements, where r is the number of rounds. (The paper uses r - 1 constants, since adding one in the final step does nothing for security, but it doesn't hurt either.)
The authors recommend r = ceil(log(p)/log(3)).
The field must be one in which cubing is a permutation, which holds if gcd(3, p - 1) = 1.

You question is quite broad

cryptographic algorithm

What kind of task shall this algorithm solving?

symmetric encryption, like AES
asymmetric, like RSA
key-exchange, like Diffie–Hellman
hash function, like sha256
quantum-theoretical-encryption-algorithm, like something new from the IACR
quantum-key-exchange algorithms, like one used across EU already...
steganography, like spies used
signing algorithms, like used in PGP/GPG schemes
pseudo-random numbers algorithm, like used mostly everywhere in crypto as sub-algo

And probably 10+ fields in crypto, little bit minor...
When you are comparing RSA - easier than AES - you are comparing "Hammer" and "Saw", it is used for different things, this gives different environment for algorithm and of-course - stream encryption little bit harder than just generate private & public keys...
What is better "Blue-Color" or "Cold-Ice-Cream"?
You could say, sha256 easy than ECC - Elliptic-curve cryptography, but this is two completely different targets. It is like to say "ZIP file format" ( an archive ), and all algorithm inside it, easier than Bitcoin's block-chain algorithm... is it easier? or they are equal? Or perhaps, block-chain is so popular - because it is one of the easiest algorithm on the Earth?
One-time pad - will be easiest one to understand than anything you could met, methinks. But would it be easy to handling two big secret books containing one big secret key??? I'm not sure... Are you ready to physically meet with your counter-part to give em copy of your one-time pad. And thereafter - like you said, on the paper, encrypt e-mails - symbol-by-symbol...
So, we could separate categories

easiest in handling
easiest in understanding
easiest in coding

.... and somehow connected to cryptography, hash, key-exchange, stream,  no-matter..
I think the answer on this question will not satisfy your researching.


Are the following functions pseudorandom? Given a PRF $F $, such that for each $k \in \{0,1\} \ ^ n$ , $F_k:\{0,1\} \ ^ n \to \{0,1\} \ ^ n$ , is the function defined by $W_{k_1,k_2}(x) = F_{F_{k_1(0 \ ^n )}}(x) || F_{k_2}(x)$ also a PRF?

I'm almost sure the answer is yes.
I'm trying to assume $W$ is not a PRF and conclude that $F$ isn't either but I dont see how.

Let F be as in (1). Now $H_k(x) = F_k(x) || F_{F_{k}(1 \ ^ n)}(F_{F_{k}(1 \ ^ n)}(F_{k}(x)))$.
I think $H$ is not a PRF.
The polynomial distinguisher I thought about is the following:

$D$ on input $1 \ ^ n$ and orcal asses $O$ , asks for $O(1 ^ n)$ and writes $O(1 ^ n) = \alpha || \beta$ for $\alpha,\beta \in \{0,1\} \ ^ n$.
Now $D$ checks if $\beta = F_{\alpha}(F_{\alpha}(\alpha))$. if yes, outputs 1 otherwise outputs 0.

If $O=H_k$ then $D$ outputs $1$ so $Pr(D \ ^ {H_k()}(1 \ ^ n)=1 ) =1$.
If $O=h$ for a truly random functon then $D$ outputs 1 iff $F_{\alpha}(F_{\alpha}(\alpha)) = \alpha$ for $\alpha$ which is a random number in $\{0,1\} \ ^ n$.

I want to say that $Pr(F_{\alpha}(F_{\alpha}(\alpha)) = \alpha) = v(n)$ for a negl. func. and this will conclude the proof but i can't find a way to prove it. someone can help?

Thanks for the help.

Okay, so now that we've agreed that generalized pseudorandom functions can be of variable length :-D, I'll slightly rephrase your question to meet the definitions I'm working with, and then prove (1).

Given a pseudorandom function $F = \{F_{n}\}_{n \in \mathbb{N}}$, such that for each $k \in \{0,1\}^n$ , $F_k:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, is the function defined by $W_{k_1,k_2}(x) = F_{F_{k_1(0 \ ^n )}}(x) || F_{k_2}(x)$ a generalizable pseudorandom function?

Assume by contradiction that $W$ is not a generalizable pseudorandom function,
then there exists a probabilistic polynomial time (PPT) oracle machine $M'$ and a
polynomial $p(\cdot)$ such that for infinitely many $n$'s,

$$\big|\text{Pr}[M'^{W_{k_1,k_2}}(1^{n}) = 1] - \text{Pr}[M'^{H'_{n}}(1^{n}) = 1]\big| > \frac{1}{p(n)}$$

where $k_1,k_2 \xleftarrow{\$} \{0,1\}^n$ and $H' = \{H'_n\}_{n \in \mathbb{N}}$ with $H'_n$ uniformly distributed over the set of all functions mapping $n$-bit strings to $2n$-bit strings.

We will use $M'$ to construct a PPT oracle machine $M$ to distinguish $F_k$, where $k \xleftarrow{\$} \{0,1\}^n$, from $H = \{H_n\}_{n \in \mathbb N}$, where $H_n$ is uniformly distributed over the set of all functions mapping $n$-bit strings to $n$-bit strings. On input $1^n$, $M$ first queries it's oracle $\mathcal{O}$ with the string $0^n$ and records the result as $k' \leftarrow \mathcal{O}(0^n)$. $M$ then uniformly selects $k'' \xleftarrow{\$} \{0,1\}^n$. Next $M$ runs $M'(1^n)$ and serves as its oracle, returning $F_{k'}(x)||F_{k''}(x)$ whenever $M$ queries with input $x \in \{0,1\}^n$. Whatever output $M'$ returns to $M$, $M$ outputs itself.

If $\mathcal{O} = F_k$, then

$$\text{Pr}[M^{F_k}(1^n) = 1] = \text{Pr}[M'^{F_{k'}||F_{k''}}(1^{n}) = 1] = \text{Pr}[M'^{W_{k_1,k_2}}(1^{n}) = 1]$$

since how we chose $k'$ makes our experiment identical from the point of view of $M'$ to when it's interacting with the oracle $W_{k_1,k_2}$. If $\mathcal{O} = H_n$ we have $\text{Pr}[M^{H_n}(1^n) = 1] = \text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^n) = 1]$. Now, $M'$ is a black box, and was not "designed" to distinguish $W_{k_1,k_2}$ from $F_{H_n(0^n)}||F_{k''}$. That said, we can intuitively see that $F_{H_n(0^n)}||F_{k''}$ should not be distinguishable from $H'_n$ because of our assumption that $F$ is a pseudorandom function. We will now formalize that notion.

Assume that there exists a polynomial $q(\cdot)$ such that for infinitely many $n$'s

$$\big|\text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^{n}) = 1] - \text{Pr}[M'^{H'_n}(1^{n}) = 1]\big| > \frac{1}{q(n)}$$

We can then use $M'$ to construct a PPT oracle machine $M''$ to distinguish $F_k$ from $H_n$. We denote the oracle of $M''$ by $\mathcal{O}'$. On input $1^n$, $M''$ selects $k''' \xleftarrow{\$} \{0,1\}^n$ and runs $M'(1^n)$, acting as its oracle by returning $\mathcal{O}'(x)||F_{k'''}(x)$ for any query $x \in \{0,1\}^n$ that $M'$ makes.

If $\mathcal{O}' = F_k$, then

$$\text{Pr}[M''^{F_k}(1^n) = 1] = \text{Pr}[M'^{F_k||F_{k'''}}(1^n) = 1] = \text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^n) = 1]$$

where the last equality follows because $k$ was chosen uniformly at random and $H_n(0^n)$ is a uniformly distributed random variable over the outputs on input $0^n$ of every function mapping $n$ bits to $n$ bits, and $k'''$ and $k''$ were both chosen uniformly at random. In the case $\mathcal{O} = H_n$ we have $\text{Pr}[M''^{H_n}(1^n) = 1] = \text{Pr}[M'^{H_n||F_{k'''}}(1^n) = 1]$. We must now go just one layer deeper before deriving a direct contradiction, and prove by contradiction that $M'$ cannot $H_n||F_{k'''}$ and $H'_n$.

Assume that there exists a polynomial $r(\cdot)$ such that for infinitely many $n$'s

$$\big|\text{Pr}[M'^{H_n||F_{k'''}}(1^{n}) = 1] - \text{Pr}[M'^{H'_n}(1^{n}) = 1]\big| > \frac{1}{r(n)}$$

Since the first $n$ bits of the output of the two oracles should be uniformly distributed, they cannot provide any useful information to $M'$ to make its decision*. Then $M'$ must be able to distinguish $F_{k'''}$ from the second half of $H'_n$ with more than negligible probability. Since this is equivalent to distinguishing $F_k$ from $H_n$, it contradicts our claim that $F$ is a pseudorandom function.

Now we unfold the argument. Since $M'$ cannot distinguish $H_n||F_{k'''}$ and $H'_n$ with more than negligible probability, this contradicts our assumption that $M'$ can distinguish $F_{H_n(0^n)}||F_{k''}$ from $H'_n$ with more than negligible probability. If that assumption is wrong, then $M$ distinguishes $F_k$ from $H_n$ with only negligible difference in probability from that the which $M'$ distinguishes between $W_{k_1,k_2}$ and $H'_n$. By our hypothesis, this is non-negligible, but because we assume $F$ to be a pseudorandom function, no such $M'$ can exist. Therefore, we conclude that $W$ is a generalizable pseudorandom function.

* You could prove this more rigorously by remembering that polynomial-time unpredicability and pseudorandomness imply each other. Then show that you can replace $M'$ with a PPT oracle machine $M'''$ that never reads less than $n+1$ bits of its input (or more than $2n-1$) before guessing a bit, and that the probability that $M'''$ guesses correctly is no less than $M'$.

I started writing a long proof, but then I remembered pseudorandom functions are length-preserving, so neither of these functions is a pseudorandom function. That said, they might be pseudorandom generators.


Is a collision attack possible on MD5 if message is known partially Is it possible to find $m'$ such that $\operatorname{MD5}(m'||m_1)=\operatorname{MD5}(m_1||m_2)$ if I know $m_2$ and $\operatorname{MD5}(m_1||m_2)$? Is this a collision or a preimage attack?

Also in this case is it possible to find $m'$ and $H$ such that $\operatorname{MD5}(m_1||m')=H$ if I know $\operatorname{MD5}(m_1||m_2)$ and $m_2$?

Basically a message like $(M,\operatorname{MD5}(M||m1))$ is sent from server to client (only client and server know $m_1$). So is there an attack in this scenario?

If you have $\operatorname{MD5}(m_1||m_2)$ and you know $m_2$, and want to find $m'$ such that $\operatorname{MD5}(m'||m_2)$ reaches a known, predetermined value, then you must break MD5's preimage resistance, or at least second-preimage resistance.

This would be true even if you knew $m_1$: if you know $m_1$, then the problem becomes: find $m'$ such that $\operatorname{MD5}(m'||x) = y$ for two given values of $x$ and $y$ ($x = m_1$ and $y = \operatorname{MD5}(m'||m_2))$ in your presentation). Since $y$ is the result of MD5 on a known entry, this problem is a second-preimage attack with an extra constraint on the result. MD5 is still quite robust against second-preimage attacks, so this cannot be done with existing knowledge and technology.

Not knowing $m_1$ cannot help: if the problem is already hard with knowledge of $m_1$, then it cannot be easier without knowledge of $m_1$.

The explanation above is the general case. In some cases it can be quite easy: for instance, if $m_2$ happens to be equal to $z||m_1$ for some value $z$, then $m' = m_1||z$ would be a solution.

If you have $\operatorname{MD5}(m_1||m_2)$ and you know $m_2$, then you can trivially compute $\operatorname{MD5}(m_1||m')$ for any $m'$ which begins with $m_2$, followed by the MD padding, followed by arbitrary contents. This requires knowledge of the length of $m_1$ (but not its contents). For details, look up the length extension attack.

md5 is a one-way hashing function remember? Which means:

cipher = md5(plain)

If you know cipher you cannot possibly get plain by reversing md5. Which means:

plain != md5(cipher)

So s it possible to find m3 such that md5(m3+m1)=md5(m1+m2) if I know m2 and md5(m1+m2)

The answer is absolutely not possible. Why you asking?
Simple because if you know md5(m1+m2) and m2 it doesn't mean you know m1 or m3 which is the collusion value of m1 in your case.

This not to be confused with symmetric keys encryption, where this scenario is very possible!

If your encryption key for a session-1 is K1 and encryption key for session-2 is K2 and so on.. It is possible to retrieve plain text if you REUSE the key twice as follow:

cipher1 = plain1 XOR K1
cipher2 = plain2 XOR K1

now XOR both ciphers and see what happens:

cipher1 XOR cipher2 = (plain1 XOR K1) XOR (plain2 XOR K1)

Notice how K1 XOR K1 = 0...0000 which makes our cipher = plain1 xOR plain2 which leads to plain text retrieval by guessing one value and trying to figure our the second.


How is it possible to parallelize a hashing function to crack an iteratively hashed password? Suppose I have an algorithm that relies on multiple iterations of a hash function like SHA1 to slow down an attacker trying to bruteforce a hash.

digest[0] = hash(password + salt)
for i in 1..r:
    digest[i] = hash(digest[i-1] + password)

The final digest[r] is then used as the hash. How does this compare to a more standard implementation like PBKDF2 or bcrypt?

This website states:

  simply iteratively hashing the hash of the password isn't enough as it can be parallelized in hardware and executed as fast as a normal hash.

Is there any truth to this statement? Since every iteration of the hash function is dependent on the previous, how could this be possible?

The bit about parallelization is not for hashing one password. But the attacker, by definition, has a lot of passwords to try, and these can be computed in parallel, provided that the function maps well to whatever parallel architecture the attacker would like to use. In the case of the multi-SHA-1 method you describe, it maps very well on GPU. Note that the same can be said about PBKDF2, which is why I tend to recommend bcrypt, which is more resilient to GPU.

Although I do not immediately see any obvious problem with your SHA-1* function, it has the generic issue of being homemade and of not having been investigated thoroughly by dozens of cryptographers during several years. Therefore I would not trust it.

PBKDF2 salts each hashing stage with a new value and the uses a mix of all stages. It also does several thousands rounds of this hashing. This makes it impossible to build rainbow tables for, while in your case custom rainbow tables can be built if the salt value is known.


The security of adding random noise many time pad In may application, I have a series of real number $\{v_1, v_2, \ldots, v_N\}, v_i\in\mathbb{R}$. To protect them, I add a random noise $r\in\mathbb{R}$ to each themselves like one-time-pad encryption scheme. But due to some more requirements of optimization we only want to generate and use a random noise $r$ instead of generating one time pad. Is this model is secure and which level of security can I obtain?

Too tricky for a comment...

Conceptually, your scheme is 110% information theoretic secure, as it's a one time pad($ \downarrow $). But since we tend to use octet based computer architecture these days, $  \mathbb{Z}  $ is more appropriate.

Note 1. Ensure $ |r| \ge |v| $.

Note 2. Don't want to patronise, but the one time pad is thee most contentious and misunderstood aspect of cryptography ever invented. Especially on this forum. Is $r$ truly random or just pseudo-random? It's worrisome that I read 'generate' in a kinda algebraic context...


When does a multiple Vignere cipher become intractable? Multiple Vignere ciphers do not repeat the key until the message gets longer than the LCM of the cipher lengths.  Are messages shorter than that safe?  If not, what is the attack strategy?

I believe there is a known plaintext attack which has an algebraic solution if the message is longer than the sum of the cipher lengths.  Are messages shorter than that safe?

Are messages shorter than the longest key in the set of ciphers safe?

Yes, if you know the key lengths and have a sufficient amount of known plaintext, you can easily recover the keys (or at least something equivalent to them) using linear algebra.

How much is "a sufficient amount"?  Well, to fully recover all the key characters, you would need to solve as many linear equations as there are characters in all the keys combined, and would thus need at least that many ciphertext/plaintext character pairs to get a unique solution.

However, in general, some of those equations will be redundant, because multiple Vigenère encryption has equivalent key(set)s.  This implies that a) you cannot, in general, fully recover the original keys, but b) you can generally recover an equivalent set of keys with less known plaintext than the combined length of all the keys.

The exact amount of redundancy will depend on the key lengths.  As an extreme example, encrypting a message with two keys of length $a$ and $b$, where $a$ is an integer multiple of $a$, is obviously equivalent to encrypting it with a single key of length $a$.

More generally, adding a constant to all characters of one key and subtracting the same constant from all characters of another key obviously won't change the result of the encryption.  By choosing suitable constants, we can transform any set of keys to an equivalent one where (e.g.) the first character of each key except one is zero.  So, in general, a set of $n$ keys with total length $\ell$ can have at most $\ell - n + 1$ non-redundant characters, and thus finding an equivalent keyset requires at most that many known plaintext characters.

(Of course, that's assuming that each ciphertext/plaintext character pair actually contributes to the solution.  Depending on where the known pairs are located in the message, this may not always be the case, either.  For example, trivially, two ciphertext/plaintext character pairs separated by a distance that is divisible by the least common multiple of the key lengths will be encrypted with the same key characters, and thus knowing them both won't provide any more information about the key than just knowing one of them.  On the other hand, I would conjecture — but cannot prove off the top of my head — that a sequence of $\ell - n + 1$ consecutive ciphertext/plaintext character pairs should always be sufficient to find an equivalent keyset.)

If all the key lengths are coprime, I believe $\ell - n + 1$ ciphertext/plaintext character pairs is also the minimum number needed to fully determine the key set (up to equivalency).  Otherwise, fewer should be sufficient.

Also, yes, if the message is no longer than the longest key, and that key is fully random, independent of the other keys and used only for one message, then the system is equivalent to a one-time pad, and thus provides perfect secrecy.

Essentially, this is because just encrypting the message with that one key is sufficient to provide perfect secrecy, and anything else we do with the message cannot compromise that.

In fact, since Vigenère encryptions commute with each other, we can always arrange them so that the encryption with the long random one-time key happens last.  Thus, we can treat the result of all the other encryptions as the plaintext input to a one-time pad scheme, which of course perfectly conceals its input.  Thus, nothing about any of the other keys matters in any way, as long as at least one of the keys satisfies the criteria (randomness, independence, length, non-reuse) for being a secure one-time pad.

Nova is wrong.  You cannot attack the cipher you describe with traditional Vigenere attacks.  There is no known (practical) attack on your cipher (trust me, I've looked everywhere).

EDIT: It was recommended that I explain why this is true.  Well the traditional attacks rely on comparing portions of ciphertext separated by a distance equal to the length of the key.  Obviously this cannot be done if the key is longer than the message.


Does decryption with a wrong key creates a new encryption? I'm wondering if decrypting with a wrong key is the same a encrypting in a different way.
For example if I encrypt the message "hello" with Caesar cipher with key = 3 it will give the message "khoor" but if I decrypt it with key = 2 the result will be "ifmmp". So we can say, decrypting a message encrypted with Cesar cypher will be the same as encrypting the encrypted message with -wrongKey.
But in a general way, if I decrypt a message with a wrong key, do I encrypt the encrypted message in a different way?

In general this is a moot point, as modern encryption schemes are designed so that the recipient knows if they have used the correct key or not. It is an interesting question to ask about encryption primitives, like a block cipher. Put more precisely, you are asking whether there is always a $k_3$ such that
$D_{k_2}(E_{k_1}) = E_{k_3}$
This is essentially asking if encryption forms a group, and in general the answer is no. See e.g. Is Triple-DES a group?. There are notable exceptions. You've seen that Caesar cipher is one, and Vigenere is another.

Generally, as mentioned in the comments, if you use an authenticated cipher with an independently chosen key, then decryption will fail with very high likelihood, and can therefore not be considered encryption. It's the same thing basically with padded modes such as CBC. If you'd use it with padding then the decryption will fail with high probability (although once in ~256 is not as high as you would expect with an authenticated cipher).
On the other hand, with CTR mode and most stream ciphers, encryption = decryption by definition (XOR of a key stream with the plaintext / ciphertext). And for block ciphers (which, by themselves, are not semantically secure), you can use them in both directions. In that case yes, your premise is correct. Note that this answer disregards how the nonce or IV is handled (it can e.g. be established out of band).
I'll not go into asymmetric ciphers much; lets us please agree that encryption with a private key is usually not possible.
So it entirely depends on the cipher scheme.


Using date stamp down to milliseconds / ticks as a salt? As I understand it, the salt is used to ensure that a hash of two of the same strings results in a different hash.
The salt is often stored with the hash, either prepended or as a separate field.
As this just needs to be "different" for every input, would using something like:
DateCreated.ToString("yyyyMMddHHmmssffffff")
To get a number string down to the millisecond - If you can guarantee that you'd not have two requests in the same millisecond. This would be unique per record and provide the means to change the hash.
As an example, if I run a basic hash:
 using (HashAlgorithm algorithm = SHA256.Create())
                return algorithm.ComputeHash(Encoding.UTF8.GetBytes(inputString));

If my input string is BabySharkDoDoDoDo - every time this is hashed, I'll get the same result: 567d01ee59d062ff75435033b4c2593058aed5b5ccca0f29ba92b22c13e084b3
So, to make sure each entry to my shark database is unique, I prepend the inputString with DateTime.ToString("yyyyMMddHHmmssffffff") - so my input to the hash becomes 202104132059471235487BabySharkDoDoDoDo and each time I get a unique hash.
So I can check the input is valid, if someone enters the right record and the string BabySharkDoDoDoDo I need to store the salt, either with the hash or in the separate column.
So, the salt is known to the attacker - always the case right? So making a super strong salt, with crazy random entropy to then go and store it right next to the data it's salted makes me think, is this wasted effort? Or theatre to seem great but really all you need is a unique piece of data to provide the salt?
If I go for it and create a 128 bit salt, from a crypo library, Rijndael or similar - sure it's unique (hopefully), but I then go and prepend it to the saved hash - right? Otherwise, I can never check the hash against a known input.
A timestamp down to the millisecond or tick would also be unique and serve the same purpose?

You're going out of your way to create more work for yourself, and introducing a vulnerability. It's not necessarily a huge vulnerability, but why bother?

To get a number string down to the millisecond - If you can guarantee that you'd not have two requests in the same millisecond.

You cannot have such a guarantee, not without doing very complicated things.

If your server is fast enough, it may take less than one millisecond to serve a request. Even if it doesn't now, maybe it will after a hardware upgrade.
Clocks are not always accurate. Just because you have a function GetCurrentTimeInMilliseconds() doesn't mean that it has millisecond accuracy.
The time can go backward if the clock is adjusted. Or if you use the local time rather than wall-clock time.
If you have multiple threads running on multiple processors, they will, from time to time, happen to serve a request at exactly the same time, no matter how much resolution your clock has.
If the same code is running on multiple servers, it's the same thing: they'll all be generating the same number at the same time.

Depending on the purpose of the salt, repeating a value may or may not be catastrophic. For a nonce or IV in encryption, it is often catastrophic. For password hashing, the attacker only has a small advantage if the salt is rarely repeated.

then go and prepend it to the saved hash - right? Otherwise, I can never check the hash against a known input.

Yes. This applies no matter how you generated the salt.

So making a super strong salt, with crazy random entropy to then go and store it right next to the data it's salted makes me think, is this wasted effort? Or theatre to seem great but really all you need is a unique piece of data to provide the salt?

You don't need “crazy random entropy”. You just call GenSecureRandom() or whatever your function to generate cryptographically secure random bytes is called. This is less complicated than the date-based approach you propose!
Even better, when hashing a password, the password hashing library should take care of generating the salt. But if you're stuck with an old API that requires you to do the work, then just generate a random salt of the length stated in the documentation of the library or of the password hashing algorithm. This is the simplest method.

As I understand it, the salt is used to ensure that a hash of two of the same strings results in a different hash.

In short yes.
Remember, the hash functions are not producing unique outputs per input. This can be simply seen by the pigeonhole principle. The input of the hash functions are arbitrary binary strings and the output is fixed length of $b$.
$$H:\{0,1\}^*\to \{0,1\}^b$$
Therefore the collisions are inevitable and the generic cost of finding one is $\mathcal{O}(2^{b/2})$ with 50% probability by the birthday attack.
Therefore, even with the salt (prepended or appended) the collision will be the same.

This would be unique per record and provide the means to change the hash.

Yes, we expect that cryptographically hash functions have avalanche property so that with changing 1 bit we expect that the output bit flips with 50% probability.

So, the salt is known to the attacker - always the case right? So making a super strong salt, with crazy random entropy to then go and store it right next to the data it's salted makes me think, is this wasted effort? Or theatre to seem great but really all you need is a unique piece of data to provide the salt?

Yes, we assume that the attacker has the salts.
Entropy is the property of the process not a property of strings. We prefer the word strength like the password strength.
Without the salt hash functions (as in hashed passwords) have a generic pre-image attack case; Rainbow tables to find the pre-image. These tables speed up the search if more than one search is going to be performed. The salt simply kills the Rainbow tables, since the attacker needs to build one table per salt. Therefore, with the salt they become useless.
To prevent the reuse of the salt one should prefer 128-bit salt value and this is a recommendation of the NIST.

If I go for it and create a 128 bit salt, from a crypo library, Rijndael or similar - sure it's unique (hopefully), but I then go and prepend it to the saved hash - right? Otherwise, I can never check the hash against a known input.

Thanks to Microsoft RijndaelManaged, we are still seeing the Rijndael around. Rijndael was standardized as AES with some changes like the fixed block size 128 and key sizes as 128,192,256 where the middle size is used by nobody!
A block cipher is a family of permutations and if you fix a key, then you will get a permutation. Then for each user you can encrypt user ID, 1,2,3, etc., or their unique some other information. In this way, the salt will be different per user.
For a different server, select a new random key.

A timestamp down to the millisecond or tick would also be unique and serve the same purpose?

Yes, as long as there is no multi-process and resolution of the time ticks are good enough you can use it. Too many ifs?
If the time has subject to change or the resolution is not enough then/or better use /dev/urandom to get a 128-bit salt value.
If you are using multiple servers then you can use an additional pepper string to separate the domains of the servers.


Can adding bad entropy to good entropy, make a system insecure? For example,

If I needed to generate a random number. I use a good source of entropy to generate r.

Then I add values a, b and c whom are generated from bad entropy such that new entropy = r + a + b + c

How would the overall entropy look like?

The plus sign means to add and not concatenate. I believe that if we concatenated, then this would lead to an overall bad entropy because if we assume that each a,b,c,r each contribute 64 bits to 256 bits of entropy. We would in reality only have 64 bits of good entropy from r. This is my intuition with concatenation.

If you have a variable with maximal entropy, and you combine it with an independent variable with less entropy using Xor or modular addition you will still have maximal entropy.

If you have two independent variables with low entropy and you combine them in the above fashion the result will be a variable with more entropy than either the original ones

If however the variables are correlated all bets are off. Even combining two maximal entropy variables may result in 0 entropy (constant variable ) when adding/xoring them.

How would the overall entropy look like?

If you sum algebraically, entropy $H$ is related to the variance of any variable $X$, and so for $N$ independent  variables:-

$$ H \sim   \operatorname{Var}\left(   \sum^N X_i    \right)    =      \sum^N \operatorname{Var}\left( X_i    \right)     $$

Which means the total entropy is approximately related to the sum of the individual variances, as       $  \sim \operatorname{Var}(a)   +   \operatorname{Var}(b)   +   \operatorname{Var}(c)    +  \operatorname{Var}(r) $.  If you're assuming that $a,b,c$ have low entropy (say couple/three bits), it won't make much of a difference compared to the 64 bits of $r$.

Whilst not using the same sample spaces as your example, the following is what happens to the entropy distribution when several dice are summed:-

Your input distributions will be uniform as the dice, just with three small and one much larger.  The resultant convolution will be a slightly non uniform distribution.  But it won't distort as far as the normal approximation in the diagram of four dice.

It makes it difficult to calculate the resultant summed entropy this way as there is no simple closed form probability equation. Consequently we tend not to do it this way.

It's also very inefficient way to convolve entropy inputs, and not done as we aim for a maximal entropy uniform distribution. Crucially you can see that   the per die increase in min. entropy $(-\log_2{(p_{\text{max}})})$ is dropping logarithmically in relation to the number of dice, and  $H_{min}$ is the conservative estimate of $H$ we use for system security. So you'd face diminishing returns in $H_{min}(r)$ as you add more variables to $r$.

We actually would  instead concatenate the variables as $ a||b||c||r $, ignore fixed bits and preserve their entropies.  The final entropy would be the summation of the individual entropies. Just remember that this is entropy, not a uniform distribution or any sort of cryptographic key. Those require further work such as randomness extraction with hash functions or perhaps a key derivation function.


Distributed Shamir's secret sharing Wikipedia on its page for Shamir's secret sharing scheme provides a python implementation that applies the idea. This algorithm will generate a (k, n) threshold scheme so for example we could split a secret in 6 parts and we would need only 3 of them to recreate it.

But isn't the idea of this scheme to be used by a number of various agents that each one will generate only a part of the key and share it? This way each agent can then create the secret key by combining the parts he will receive.

What would be the proper way to make this algorithm distributed and not generating everything in one computer?

Each participant can create his own random k,n secret sharing and send one share to each other participant.
Each participant can then add up his sub-shares to get his final share.

Due to linearity the resulting is also a valid shamir secret sharing.

This produces a random shared secret. If there is something you want to protect with it, we need to ask who knows it initially?

Each user $i=1,\ldots,n,$ could randomly generate a share $K_i$ of the right bitlength to give the desired security and transmit hers share to a trusted third party, $T.$

$T$ could generate the secret as, say,
$$
S=H(K_1\oplus \cdots\oplus K_n)
$$
with a hash function and then use Shamir(n,t) to generate the shares and distribute to the users $i.$

Note that it would be less secure to generate shorter shares and have the TTP concatenate them before hashing.


What can I do if I get private key of signing algorithm in Digital signiture I am confused in digital signature. what is use of encryption with private key and decryption with public key. Using public key we can decrypt the signature then what is use of private key privacy. Explain in detail.

When talking about digital signatures, the private key is what proves the authenticity of the signature, precisely because it is private.

The use case proceeds like this: I choose a private and public key pair. Because I chose it, only I know both keys. I then send a message and sign it by using my private key, typically by encrypting a digest, hash, or checksum of the message with the private key, so that it can only be decrypted with the matching public key.

I publish my public key for others to verify my signature with.

The receiver then manually computes the same digest of the message, decrypts the signature I sent along with it using my public key, and compares the two. If they are identical, the only way that is possible is if I am indeed the person who has the private key and published its matching public key. Otherwise, I would not have been able to properly sign the message without my private key.

This works because it is exceedingly difficult to compute the private key from the public key, so much so that it would take a very long time even on a supercomputer.

You might ask at this point, why is the signature an encrypted digest or hash of the message? If the message differs in any way (was tampered with or intercepted, as with a man-in-the-middle attack), the digest won't match whether it's decrypted correctly or not. So tampering with the message necessarily invalidates the signature, because it's a digest of the message itself, proving it's the same message sent by the person who signed it.

I leave an example of RSA signature creation and verification process (note that other signature schemes will work in other way):

Sender computes the hash of the message that's going to be sent.
Sender signs the hash of that message with his private key. We call this signature a digital signature.
Senders sends to the receiver the message along with the digital signature and his public key.
Receiver verifies the digital signature deciphering it with sender's public key and obtains the original hash computed over the message.
Receiver computes the hash of the message and compares it with the obtained hash.

Now, if both hashes match then we know:

Message has not been altered or modified.

The message belongs to the sender since we have deciphered the digital signature with his public key, that means he signed it with his private key.
Take a look at PGP. It is a mix of this scheme including symmetric-key encryption.


How is public key cryptography used for digital signature? In public key cryptography, there are two different keys used for the encryption and decryption of data . I am wondering how it is used for digital signature

Aleksander's answer is very close, but there is one key difference between encrypting and signing a message.  When you create a digital signature, you are not encrypting the whole message.  The intent is only to validate that the message was indeed sent from you, not to prevent others from reading the message.

To sign a message, first a cryptographic hash is created.  This is a calculated string that provides a unique "fingerprint" for your message, that anyone can reproduce on the other end to validate that the message received is the same as the message sent.  This hash, rather than the message itself is what is first encrypted by the recipient's public key, then your private key, then it's appended along with the message as the signature and sent to the recipient.

The recipient must then use the sender's public key first, then their private key to decrypt the hash.  Once they have the received hash, the last step is to create their own hash of the message, and compare the two.  If the hashes match, the signature is valid, and everybody is happy!

Here's a great explanation: http://www.cs.utsa.edu/~bylander/cs1023/signature-encryption-example.html


Getting inverse of a transposition key I'm new to security stuff and I have some questions about the keys of transposition cryptography.

If I'm given the encoding key to a transposition cipher, how do I get the decoding key for it? I tried googling but couldn't find any steps on the calculation for it. For example, on several crypto-related websites there are these nifty tools where, when I enter 4 3 1 6 2 5 I would get 3 5 2 1 6 4… but why and how?

The key is obtained by taking the encryption steps in reverse.
For example, let's encrypt the word "United" with that 4 3 1 6 2 5 key.
The first step is to take the 4th letter, a "t" and make it the first.
In the decryption, this first ciphertext letter must go to the 4th place again.
So the fourth step in the decryption, must be to look at what is in the first position - a "t" - and put that back in the fourth place again. Indeed we see in the decryption key that "1" is the value its fourth member.
By continuing these steps, you can derive the inverse key.

Here is a little code snippet that does the calculation.

static int[] inverse_key( int[] key )
{
    int[] inverse_key = new int[ key.length ];
    for ( int i = 0; i < key.length; i++ )
    {
        inverse_key[ key[ i ] - 1 ] = i + 1;
    }
    return inverse_key;
}

The "-1" and "+1" in the code are because arrays in most programming languages are 0-based; they do not relate to the actual algorithm.

Let $E_i$ be the transposition cipher associated with the first encryption, and $D_i$ associated with the second one. You only need to garantee that $D_{E_i}=i, \forall i$. Now let's see the magic happening:

$E_3=1$ and $D_1=3$.

Wooow it works!


Post-quantum authenticated encryption It is well-known that the Grover's algorithm reduces cryptographic strength of symmetric ciphers to a square-root - e.g. AES-256 becomes only 2128 strong.

However, these statements are always made about the raw block ciphers. How about GCM-AES256, CCM-AES256 and the like? The MAC tag in GCM is at most 128 bits. Does this mean GCM is not post-quantum secure, even if I use AES-256? What mode of operation that gives me authenticated encryption also gives me post-quantum security?

UPDATE

So I have found some interesting papers, namely:

Secure Signatures and Chosen Ciphertext Security
in a Quantum Computing World
Quantum-Secure Message Authentication Codes

GCM uses Carter-Wegman MAC, and per the second paper (p. 18): This MAC is not, in general, secure in the quantum setting. But the authors (Dan Boneh and Mark Zhandry) do give an example of a modified CW-MAC that is secure in quantum settings. So I guess that rules out the GCM mode, but what about CCM and others?

I am not sure whether the construction of MAC is the only issue in authenticated crypto, or the MAC tag space as well.

This [Carter-Wegman] MAC is not, in general, secure in the quantum setting

This is true; however we need to ask "what is this setting, and is it a realistic one?"

This setting is one where the adversary can ask queries that are composed of a superposition of quantum states, and the oracle returns the superposition of the answers.  In other words, the oracle (that is, the device with the MAC key that computes the MAC) must compute the answer without any decoherence in the quantum state, and the messages to and from the adversary must also not have any decoherence.  As far as we know, any significant amount of computation without decoherence must be done using Quantum Error Correction (to adjust for the decoherence that just occurs naturally), this effectively means that the device with the MAC key must be a part of the quantum computer (but, for some reason, the attacker doesn't look inside the device and just extract the MAC key).

I would argue that this is not an attack model that we need to worry about, if we're just creating devices that exchange messages, and are worried about someone building a Quantum Computer.

We do need to worry about Grover's algorithm, which given a function $F(x)$ with an unknown $n$-bit input, find an $x$ where $F(x)$ is a specific value in $O(2^{n/2})$ time.  However, the attacker can't take advantage to try to compute a 128-bit MAC tag; because, in addition to the tag that the attacker is searching for, the algorithm also has the key as the input, and the attacker doesn't know that.  Grover's algorithm could be used to attack the key itself; we can prevent that from being a possibility by using a 256 bit key.

Actually, a post-quantum security is truly achieveable in a cipher-combo only. So - take a look at AES-finalist-candidates, like Serpent, and use it too or just it, but in 512 bit keys. Here is the starting point for you : enter link description here


Stateless hash based public key cryptography? Merkle-Winternitz signatures based on fractal hash trees are an attractive alternative to other post-quantum cryptographic schemes, in particular since they are conceptually simple, the security properties are easily understood and they are easy to implement correctly.

However, all schemes based on Merkle trees appear to be stateful, in the sense that the signer must keep track of the number of signatures already generated, and because some optimizations make it significantly impractical to generate several signatures in parallel. This is a huge minus e.g. for server authentication, where the same key might have to be used for several connections in parallel.

Furthermore, stateful private keys are vulnerable to server crashes if the private key state is not immediately persisted (which further increases stalls from serialized signing). Randomized schemes (such as DSA/ECDSA), or schemes based on trap door functions rather than one way functions (such as RSA) do not have these problems.

Does there exist any public key scheme based solely on hash function that does not require a stateful private key?

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say).  Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message.  As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a collision is unlikely.

It takes some extra work to make this work.  In particular, if your tree used only hash functions, then to precompute the public key, you'd have to do $2^{80}$ work to populate the entire tree -- no good.  So, in fact we do a multi-level tree where the entries at one level are used to sign a subtree the next level down (signed, using Merkle-Winternitz signatures).

For more details on how to make this work, you can see, e.g.,  https://www.imperialviolet.org/2013/07/18/hashsig.html or https://www.cdc.informatik.tu-darmstadt.de/reports/reports/BDKOV07.pdf.

This does increase the size of signatures and the amount of computation needed a bit, but if you want a stateless scheme, it might be viable.

Here's something similar but completely different: a “one-way” cryptographic hash function which is regressible when combined with the function's parsed trapdoor index. That is to say, the hash function is the file and the trapdoor table file is the key! The trapdoor table generated is approximately 60% larger than the original file but eminently compressible.

unitambo.wordpress.com/spreadsheet-model/
unitambo.wordpress.com/one-way-function-with-trapdoor-table-pre-print/

(Disclaimer: website and crypto by me, Phill Somerville.)

Quoting http://www.cs.ucla.edu/~sahai/work/web/1998%20Publications:

  One-way functions imply trapdoor functions. Our first result, given in
  Theorem 1, may seem surprising at first glance: we show that one-way functions
  imply trapdoor functions. We present a general construction which, given an
  arbitrary one-way function, yields a trapdoor (non-injective) one-way function.
  /Crypto_Bellare1998.pdf


Can I hash a secret key and used the hash as key ID? I am using AES-CBC to provide confidentiality for protocol messages. I want to allow the receiver to know the secret key by using a key ID. For this I hash the secret key to generate a key ID. Every time the sender wants to send a message, the sender appends the key ID to the message to allow the receiver to bind the key ID with a secret key.

Is hashing the secret key to generate a key ID a secure mechanism?

I would do it a little differently so there is less of a relationship between the ID and the key

Encrypt a block of all 0s with the key; $X$ = $E_k(0_{128})$

Hash X; $H$ = SHA256$(X)$

Truncate the hash to 32 bits (8 hex characters)

Encrypting a block of 0s and truncating is generally how a key check value is generated, as block ciphers are designed to resist key recovery, the intermediate hash step is there for extra security, so you are not exposing a known ciphertext value.

I would not consider a direct key hash safe, some software may use that internally, and you do not want that exposed

Hashing does not provide confidentiality, and theoretically your scheme is broken.

PS: This is exact and correct answer to the OP question, and I will not delete it.
Please downvote to show your cryptographic illiteracy.


Is it fair to assume that SHA1 collisions won't occur on a set of <100k strings I'm building a system that has to take file paths, and generate a unique name for each one. I'm planning on using SHA1 as the hash function.  My question is: do I have to deal with possible collisions (2 different paths producing the same SHA1 value) or can I assume it won't occur?

The chance of a collision in such a set is approximately $ \frac{1/2 \cdot n^2}{2^{160}} $, which for n=100k evaluates to about $ 3.4 \cdot 10^{-39} $. So it is fair to say, such a collision won't occur accidentially.

AFAIK nobody has ever found a SHA-1 collision The only concrete SHA1 collision to date was Google's on February 23rd, 2017 (found here). Collisions become likely once you generate about $2^{80}$ or $10^{24}$ hashes.

If cryptoanalysis advances, an attacker might be able to create inputs that deliberately collide. Currently, however, there is no known way to do this efficiently. Of course, this only applies if your application needs to protect against deliberate collisions; many applications only require protection against accidental collisions. If you need protection against deliberate collisions, I'd prefer SHA-2 over SHA-1.

If you are not multi-threading, you could create unique file names by taking the current timestamp in nanoseconds and using that. Or you could use a millisecond-resolution timestamp and concatenate that with some quick hash. As a cryptographic hash the SHA-1 seems like an overkill if you use this method and you might get away with some simple CRC32 check sum, but if you want to be on the safe side you can use MD5 which is a cryptographic hash but faster than SHA1.

These methods kind of assume that the system clock is never turned back on accident or on purpose, or that the name generation process is only ran once.


Nonce reuse resistance I read this article and I think the approach outlined there is very interesting for one of our use case.

We use ChaCha20 Poly1305 (via Sodium crypto_aead_chacha20poly1305_encrypt_detached) to encrypt the data, which is typically 8 kb in size. We use this because this way the mac + nonce can fit in the available space we have in the page header, using XChaCha20 (and random nonce) is not possible because of the amount of space they would take.

The data is pages in database, and each page may be modified multiple times over the lifetime of the database.

I'm trying to figure out what the best way to handle nonce / key management in this case.

Currently we generate a random nonce per page and then increment the nonce every time the page is modified. To avoid the case where a random nonce / increment is reused, we also derive a new key for each page (via crypto_kdf_derive_from_key, where the subkeyid is actually the page number).

This seems fine, but it require us to do quite a bit of work every single time.

Note that we use

The article above seems to indicate that using the hash of the data that we encrypt as the nonce will help avoid the problem with nonce reuse, since if that happens, it will be identical data & nonce, so you can't XOR them together to find anything meaningful (but can find if they are repeating).

If this is a valid option, that would give us the option of having a single key for all the pages, and a nonce based on the hash of the data and avoid the need to carefully manage the nonces.

Assuming this is the case, can we use any hashing algorithm (we already do checksum with XXHash64, or do we need a cryptographic hash to use)?

The scheme you propose certainly leaks plaintext repetitions to an attacker since the same plaintext is always encrypted to the same ciphertext. You typically don't want this and it can be disastrous if the attacker knows some of the messages.

If you are absolutely sure that leaking repetitions is no problem in your case, you can use an authenticated encryption scheme with nonce-misuse resistance. Note that not all authenticated encryption schemes have this property. If you use a scheme with nonce-misuse resistance, you can even use the same nonce (say $0...0$) for all messages, so you don't need the hashing trick. If it is not, a hash function that is not collision resistant does not make it secure because an attacker can find different messages that hash to the same value, so you will end up using the same nonce for different messages. I don't know whether ChaCha20 Poly1305 together with a cryptographic hash function provides nonce-misuse resistance, but unless this is proven somewhere (or at least some other evidence is provided), you should not assume it.


PGP double encrypt instead of signing? So, maybe this is a dumb question, or maybe it's something someone's already done and it's really common, but whatever, here goes:

Why do we sign a message with our private key and then encrypt it with our contact's public key, instead of encrypting our message with our private key and then encrypting it again with our contact's public key?

Wouldn't the latter be better?

In general, the high-level idea behind the Digital signatures is what you mention (Convincing the verifier about owning the secret key). We have to be careful in the Encryption schemes we care about the confidentiality and the message keeps secure against the malicious users while in the Signature schemes the authenticity matters and the message is public.

Let show what is the difference between the RSA encryption scheme and the RSA signature scheme.

  RSA encryption scheme:

Setup:

Selects two large prime number $p$ and $q$.
Compute $n=pq$ and $\phi=(q-1)(p-1)$.
Selects $1<e<\phi$ such that $\gcd(e,\phi)=1$.
Calculate $d$ such that, $d\cdot e = 1 \mod(\phi)$.
Then the pair of public keys are $(n,e)$ while the secret key is $d$.

Encryption:

For a message $m$ compute $c=m^e \mod(n)$.

Decryption:

For a given ciphertext $c$ a valid receiver who owns secret key $d$ can compute $m=c^d \mod(n)$.

  RSA Signature scheme:

Setup:

Selects two large prime number $p$ and $q$.
Compute $n=pq$ and $\phi=(q-1)(p-1)$.
Selects $1<e<\phi$ such that $\gcd(e,\phi)=1$.
Calculate $d$ such that, $d\cdot e = 1 \mod(\phi)$.
Then the pair of public keys are $(n,e)$ while the secret key is $d$.

Signing:

For a message $m$ compute $sig=m^d \mod(n)$ and issue $(m,sig)$.

Verification:

For a given pair of message and signature, a verifier by taking the pair of public keys can check $sig^e \mod(n)\stackrel{?}{=}m$.

As you can see, both approaches follow the same idea but in signature schemes, we use keys conversely. But we never use the term of Encryption with a secret key for the Digital signatures because the main point for the encryption is confidentiality of the message while in the signature the message has to publish with the signature.

The RSA signature is just an example while we know this scheme is forgeable if the adversary owns two valid signatures and multiplying them to get a third valid signature.


Will compression help defeat single letter frequency attack against a mono alphabetic substitution cipher? Alice has a long message to send. She is using mono alphabetic substitution cipher. She thinks that if she compresses the message it may protect the text from single letter frequency attack by Eve. Does the compression help? Should she compress the message before the encryption or after the encryption? Defend.

Will compression help defeat single letter frequency attack against a mono alphabetic substitution cipher?

What user466720 said about ciphertexts being uncompressable is applicable to modern ciphers such as AES. It does not apply to monoalphabetic substitution ciphers, since such a cipher does not change the entropy of the data.

Per fgrieu's comment, you should assume that the attacker knows whichever compression algorithm is used.

Compression, unlike the monoalphabetic substitution cipher, does change the entropy of the data. When a monoalphabetic substitution cipher is applied to the compressed data, the encrypted data will therefore have the same entropy as the compressed data. As such, an attacker will not be able to conduct a frequency analysis on this data. That is because they do not know what the entropy is (which is a requirement of performing frequency analysis).

If you were to apply the cipher, then compressed the encrypted data, the attacker could decompress the encrypted data, and then perform frequency analysis on the decompressed data, assuming they can figure out the compression algorithm used. This is a fair assumption to make, since no aspect of the compression algorithm is secret and their specifications are freely available to all people.

The procedure for doing this is:

plain text $\rightarrow$ compression $\rightarrow$ encryption $\rightarrow$ cipher text

Since the cipher text is not compressible, we do compression before encryption. The secret key of a mono-alphabetic substitution cipher is not effected by this compression. So compression does not avoid single-letter frequency analysis, and mono-alphabetic ciphers can be easily broken by frequency analysis.


Noisiest RF band for random number generation I've been looking into the difference between PRNGs and proper RNG techniques. One that I particularly like is the idea of tuning a radio to a certain frequency and bandwidth and just listening to the noise. Every so often (or continuously) pick a sample out of the noise and build a random number out of the samples.

There are a few obvious frequency ranges to avoid for this purpose:

Actual AM/FM radio stations (very predictable, not noisy at all)
TV stations (as above)
Protected RF bands (government, cellular, etc)

Based on noise-generating natural (and digital) phenomena, my question is: what frequency ranges are likely to be the noisiest and thus carry the most entropy for the purpose of a true random number generator?

This is not likely to be a good method to generate random numbers -- at least not on its own, without significant additional analysis.  You need a source of random numbers that is not only noisy, but also unpredictable to an adversary.  It's not clear that radio will meet that need.  If you listen on a FM band, an adversary who is nearby can also listen on the same FM frequency and will likely see something very similar to what you see, so will have a huge leg up in predicting the numbers you generated.

Bottom line: don't try to roll your own random-number source.  It's better to use a time-tested scheme, like a crypto-strength hardware RNG, or /dev/urandom, or a similar crypto-strength scheme.

Use the entire RF spectrum to create a number. As long as you can get a variable (zero to one) formula demodulation scheme. Multiply the percent by the encryption spread number.