More general - what is the hard problem of recovering r from r*p mod q? I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$.  (This is a simplification of an earlier post that had some errors).  It really looks like integer factorization to me; if not, what else would it be?

More specifically, select two prime numbers $p$ and $q$, $q>p$, and a random positive integer $r$, large enough such that $q/p<r<q$.  Publish $q$, but keep $p$ and $r$ private.  Further, assume there are several instances of $r$ for a given pair of $\langle p, q\rangle$ to work with.  Assuming existence of a hardness problem X, such that a polynomial-time solution of X could be reduced to finding either $r$ or $p$ from the integer $$r\times p\mod q$$in polynomial time, what is this problem X?

I am relatively new to this.  I looked at a few hard problems; none of the residuosity or discrete logarithmic problems seem to apply, but I'm hesitant to say that it's integer factorization or RSA in case there is some problem with a stronger assumption that fits.  I want to get a good characterization of the construct so that I may describe it accurately.

Thanks for your help and patience!

When given a single triple consisting of $(p,q,x)$ with $x = r \cdot p \mod q$, then there is no hard problem. It takes one inversion and one multiplication (both in modular arithmetic) to calculate $r$.

If just $x$ is given, then you can choose $p$ and $q$ arbitrarily and calculate a matching $r$ to fullfill $x = rp \mod q$.

If the actual question is about recovering the original values: That's not possible. This is exactly the same situation like only giving some bounds for random values (e.g. $q>x$) and nothing else.


Can two rc4 encoded messages be XORed and decrypted if encrypted with the same key? If I have the following:

E1 = RC4(M1, K);
E2 = RC4(M2, K);

If two different messages M1 and M2 are encrypted with the same key, K, can the key be recovered by doing:

K = E1 XOR E2

I tried XORing the two streams and could not get the key. Does RC4 not work this way?

No.  The key is not used to encrypt the message.  RC4 is a stream cipher.  The key is utilized to generate a one-time pad to encrypt the message.  This is what you have actually done:

E1 = RC4(M1,K) = M1 XOR PAD(k)
E2 = RC4(M2,K) = M2 XOR PAD(k)

E1 XOR E2 => M1 XOR M2

Ergo, RC4 keys are safe for single time use.  You need to concatenate a nonce to the key for multiple use.


How can we sign a contract digitally between two parties? I'm trying to sign a contract with another party, without using handwritten signatures.

I've just read through Applied Cryptography, but there doesn't seem to be a protocol that can solve this problem. Digital signatures simply don't work. Even if the other party signs the contract with his private key and I can verify it using his public key taken from a Certificate Authority, he can claim that he had lost his private key, and an imposer had signed the document.

In fact, he can shamelessly broadcast his own private key anonymously over the internet moments before he signed the document with me, thus securing his "proof" that everyone has his private key at a time before the document was signed. Besides this, there are many other reasons why digital signatures cannot achieve non-repudiation, as elaborated by D.W. in another post.

What alternatives do we have?

How can we make digital signing work?

No.  Cryptography alone cannot solve this problem.

Solving this problem requires a combination of technical (e.g., cryptography, systems security) and non-technical (e.g., legal, regulatory, contractual) solutions.  Even the technical part is not solely a cryptography question; it as much about systems security.


How hard is the Solitaire cipher to crack? Assuming your deck  is completely random and that it is not retrivable, how hard would it be for a casual person to decrypt a message encrypted with the Solitaire cipher?

Of course, it strongly depends on what exactly you mean when writing “casual person”. The cipher algorithm works similar to a shift cipher. As long as the attacker does not know the original order of the cards (of one or more decks of cards), then the cipher should be close to being unbreakable for a “casual person” – assuming that that casual person is someone we could call “an average Joe” and not a ”maths, statistics, or cryptanalytics fan”.

As for cryptanalytic security:

It should be noted that there is a chance the algorithm may repeat numbers since there is some bias (as pointed out by people like  Paul Crowley in his Problems with bruce schneier's "solitaire"). While the probability that several numbers will be repeated consistently is rather low, you might want to take a look at his (and related) analysis nevertheless. After all, “having bias” is what broke RC4s neck too. (Yet, RC4 was used in a completely different context where several KBs of data were encrypted with a single key… which added to its bias becoming a weaknes.)
Also, it should not be ignored that if you encrypt with the same deck order and the same keyphrase twice (or more), then both messages can be solved by dragging probable cribs and expanding the solution… without ever attacking the Solitaire key-generation algorithm itself! This practically means Solitaire has the same weaknesses as an OTP system: key-distribution and user-discipline.

On the other hand, we should remember the Solitaire cipher is nothing but a pen-and-paper cipher so we can surely not expect the same security that cryptographic algorithms like AES provide. If you want to hide some personal information from your neighbour, Solitair will do a perfect job. But if you want to protect your country’s top secret information, I would definitely advise to use something else.


Historical algorithm which is frequency analysis resilient Long ago, I read an article on Wikipedia which described a cipher algorithm, used by the KGB (if I remember well), with the property that all ciphered letters had the same (or nearly the same) probability to appear, without adding symbols to the alphabet of the ciphered text (i.e. unlike how homophonic encryption does). The algorithm was computable by hand.

But I cannot find this article again. Does anyone know the article I mentioned?

You probably mean the VIC cipher.

It can be set up in a way such that the initial substitution that also achieves fractionation through the use of a so-called straddling checkerboard is followed by a transposition or substitution step. These steps make the distribution of symbols in the cipher text more uniform than in the plain text.

An optional subsequent reverse substitution using the same straddling checkerboard leads to a cipher text that contains only symbols of the original alphabet.


Certificate Authority RSA key expiration? My understanding about SSL/TLS for HTTPS is that servers send their certificates to browsers and browser attempt to decrypt them using trusted CA public keys that are already presented in their store. Also our certificates are limited to an expiration date (mostly because of security).

Do Certificate Authorities need to renew their RSA keys from time to time due to security considerations?

To understand why CAs need to rotate their RSA keys less often, let's first investigate why end-users have to rotate their keys / certificate every few years.

There are three main reasons why end-users have to renew their keys / why certificates have a limited life-span.

To keep CRLs somewhat small. Expired certificates don't need to be put onto CRLs because they're invalid anyways, this the CRLs can be "constant-sized". Obviously CAs aren't hit by this because you always have an explicit list of trusted CAs.
To enforce technology renewal. From time-to-time technology changes and becomes potentially unsafe. Certificate renewal usually forces you to upgrade to more secure technologies (like RSA-2048, SHA-2, ...). The CAs are hit by this, but not because of expiry dates but rather because of pressure from the browsers. However they usually tend to have a long grace period where they put their new certs (not neccessarily with new keys) into the trust stores and gradually remove the old certs.
To allow CAs to earn money. When your certificate expires, you have to buy a new one from the CAs which brings them money. So obviously they want to limit certificate validity. Obviously CAs aren't hit by this because renewing CA keys is a lot of work and procedures and thus will be avoided at (nearly) all costs.

So the main reasons why CAs renew their keys seems to be that they have to upgrade key-length and the the main reasons why they have to renew their certificates is outdated hash functions (but in this case they usually keep on using the keys).

Now there are two more reasons why CAs have to renew keys / certs (without being put out of business due to a breach):

Issues related to their root key storage. CA root keys are stored in super-secure HSMs inside of heavily guarded vaults. Depending on the HSM in use, it runs on batteries (while it's not being actively used) and they will run out of power sooner or later. At this point you have to renew keys as well. This happens after five years earliest and depending on their setup may require new keys to be put in the trust stores or just some effort to move the keys into a new HSM (which is possible).
They "screwed up" with the expiry date. Obviously you only want to renew keys / certificates if there's a need for it and sometimes the older CAs just set their expiry date of the root certificates to something like 20 years in the future assuming there would be other reasons meanwhile to renew the certificates. But that usually doesn't happen so they keep the key and just distribute a new cert (with a much longer expiry date this time).


Multi-Embedded Xor for Perfect OTP I am looking for a perfect OTP design, so let's see if this design is good.

There are 2 issues when it comes to a good OTP system, the key and the plaintext, we will use XOR as cypher:

If the plaintext is like a message, then it should be long enough, otherwise it's pointless. What is the point in encrypting "Hello world", or something like that. So it should be a long message, so that it can't be guessed. If the plaintext is a private key itself, then it should be truly random and long as well, otherwise this scheme is pointless. This has nothing to do with the OTP I will talk about, it's just a caveat.
The key is the important part. It has to be truly random, the same size as the message or longer, and used only once, hence an OTP (onetime pad). So if we XOR the plaintext with the key, we get an unbreakable OTP.

The weakest link is probably the randomness of the key. However there is a solution:

Multi-Embedded Xor

What if we XOR it multiple times with different keys, like this:

$$Cyphertext = ( ( ( ( ( (Plaintext \oplus K1 ) \oplus K2) \oplus K3) \oplus K4) \oplus K5 ) .... \oplus K_n$$

So we would just Xor the plaintext n times with n different one time keys. Even if the key is biased or contains low entropy, the Xor function is known for it's de-biasing features, so Xor-ing multiple keys togeter would decrease the bias, and even for a very low quality random key, I think 5-6 rounds are enough, the bias will definitely shrink after 6 rounds to insignificance. But it also adds entropy into the system. By having 1 weak key with unknown entropy, we can have more keys mixed into the system thus increasing the overall entropy of the keys.

Would this be a perfect OTP design?

What if we XOR it multiple times with different keys, like this:
  $Cyphertext=((((((Plaintext⊕K1)⊕K2)⊕K3)⊕K4)⊕K5)....⊕Kn$

This is equivalent to XOR with a single key $K$ where $K = K_1 \oplus K_2 \oplus K_3 \oplus ... \oplus K_N$. As such, it would be no stronger than a regular OTP.

  Even if the key is biased or contains low entropy, the Xor function is known for it's de-biasing features, so Xor-ing multiple keys togeter would decrease the bias,

This is not accurate: Xor is a bitwise operation, and it only operates on 2 values at a time. The bit at position $i$ in word $K_1$ only interacts with the bit at position $i$ in $K_2$. If a bit at position $i$ happens to be biased, and all of the rest of the bits are not biased, then Xor with similarly biased data will not de-bias any of the other bits in the key word.

Put another one, if the adversary knows that the first bit of each $K$ is $0$, then you can Xor as many $K$ together as you want, and the adversary can still be certain that the first bit will still be $0$.

  I think 5-6 rounds are enough, the bias will definitely shrink after 6 rounds to insignificance.

So we can see this is not useful or accurate.

  But it also adds entropy into the system. By having 1 weak key with unknown entropy, we can have more keys mixed into the system thus increasing the overall entropy of the keys.

For our purposes, entropy is the number of secret bits of information the adversary does not know and must guess/obtain if they are to evaluate the desired function. So "unknown entropy" is redundant. We assume the secret key to be unknown to the adversary - that is why it is called a secret key.

Now, there are branches of cryptography that focus on retaining security even when some key bits are leaked, but I don't think they focus on the OTP. This is probably because if your key generation process for the OTP is flawed and produces weak keys, then you would be better off using a better key generation process, rather then trying to compensate for the inadequacy further down the line.

  Would this be a perfect OTP design?

No; The "perfect" one is the regular old, unmodified OTP, which is information theoretically secure. "More"/"newer"/"complex" is not necessarily better when it comes to cryptography.


Can you break a multi language code using Frequency analysis? Let say that I wrote a 26 letter alphabet, each letter of my alphabet represent a letter from the latin alphabet.

I'm writing in 3 languages, only I know which languages.
Grammar is the one from my native language.

Each time I need to write a word I randomly chooses in which language I'm going to write it.

Can you actually break this code using Frequency analysis?

EDIT

example :

abcdefghijklmnopqrstuvwxyz
xzcdnefqghijbkslmaoprtuvwy

The sentence :

this is a cherry tree

becomes :

ceci is a sakura

[fr] [en] [en] [jp]

and once encoded :

cfch gi x oxirax

Yes, we can almost certainly break this, given enough ciphertext.

One approach would be to use a dictionary and use word patterns.  For instance, if the ciphertext word is qddxfozogf, then the plaintext word was probably ammunition.  Notice how the 2nd and 3rd letters are the same; and the 5th and 10th letters, and the 6th and 8th letters?  The word ammunition is essentially the only word that has this special pattern.  One could expect that some fraction of words will be essentially unique, in their pattern of repetition.  With enough ciphertext, you'll be able to uniquely recover one or more of the words, and then the rest of the cipher will be easy to break.

Frequency analysis will also almost certainly be possible.  For instance, the letter q occurs with frequency 0.1% in English, 0.02% in German, and 0.9% in Spanish.  In contrast, the letter e occurs with frequency 14.7%, 17.4%, and 13.7% in English, German, and Spanish, respectively.  Therefore, if you choose uniformly at random between English, German, and Spanish, the letter q will occur in the plaintext with frequency about 0.3%, while the letter e will occur with frequency about 15.3%.  Notice how e is still much more common than q?  This indicates that frequency analysis remains possible.  (Wikipedia has data on the frequency statistics of different languages.)

Digraph analysis (the frequency of pairs of letters, like the pair th or qu) will also almost certainly be possible.

Finally, there are more sophisticated methods for cryptanalysis of simple substitution ciphers, such as hill-climbing.  These methods will almost certainly be effective at ciphertext-only cryptnanalysis.

And the cipher will completely fall apart in the presence of known plaintext (let alone chosen ciphertext).

TL;DR: Your proposal is highly insecure.  Don't use it.


SHA-1 requires utf-8 and reordering of bytes Today I implemented SHA-1 in JavaScript. While doing so I stumbled upon two requirements which are not mentioned in the RFC-3174.

Text is supposed to be utf-8 encoded / one character should be 8 bit long. This makes sense, since the same text should always return the same hash, but I couldn't find anything about it in the RFC. Is there any place where this is documented?
For some reason the bytes for each 32-bit word need to be reversed so the first byte comes last. e.g if we have chunk of 32-bit (reading from left to right).

00110101 00110011 01100110 00001111

the bytes should be arranged like this, before processing them:

00001111 01100110 00110011 00110101

I also couldn't find anything about this in the RFC. Where was this defined and is there a reason why this needs to be done?

Text is supposed to be utf-8 encoded / one character should be 8 bit long. this makes sense, since the same text should always return the same hash, but I couldn't find anything about it in the RFC. Is there any place where this is documented?

This isn't a requirement of SHA-1, but rather appears to be some requirement of the context in which you encountered this implementation.

SHA-1 doesn't assume anything about the bytes in the message; they may be text in any encoding, image data, random bytes, whatever.  However, an actual user of SHA-1 who is hashing text would care about this.  Suppose two applications have the same text string, but one uses UTF-8 internally and the other uses UTF-16.  If each one just hashes its own raw memory bytes they're going to get different results even though their strings, textually, are the same.

  For some reason the bytes for each 32-bit word need to be reversed so the first byte comes last. e.g if we have chunk of 32-bit (reading from left to right).

This is an endianness conversion, so you should familiarize yourself with that concept.  This is in fact a requirement of SHA-1.  FIPS 180-4 says (p. 7):

    Throughout this specification, the “big-endian” convention is used when expressing both 32- and 64-bit words, so that within each word, the most significant bit is stored in the left-most bit position.

The RFC that you link says it this way (which is more confusing, I think):

    The least significant four bits of the integer are represented by the right-most hex digit of the word representation.  Example: the integer 291 = 2^8+2^5+2^1+2^0 = 256+32+2+1 is represented by the hex word, 00000123.

Whether you need to perform the step that you describe is context-dependent.  For example some CPUs are natively big-endian and wouldn't need that step—the bytes would already be in the correct order for the 32-bit operations that SHA-1 performs.  Others are natively little-endian and would need the conversion.  It can also depend on the details of some network protocol or library that you're working with.


Alter plaintext in block cipher AES in CBC mode How can I alter the plaintext before decryption by changing the IV?

I know what the value of the plaintext should be. I also know the value of the IV (initial vector). The IV and the AES block are both 16 bytes long.

What I am trying to do is change what the plaintext will be into something meaningful. "SEND ME THE DATA ENCRYPTED" is the plaintext and "8f6f27b5dbfa2ba8367262bda7154d95" is IV.

I want to change the word "ENCRYPTED". I can change everything before using by changing the IV it but I cannot change it.

This the message encrypted:

IV: 8f6f27b5dbfa2ba8367262bda7154d95
CT: 798e0ff8b06cc27c1591a4088531a64a9b76a9be87a3e944c6e7000f24f5b9f9

So if you consider ASCII encoding you have two plain text blocks: "SEND ME THE DATA" and " ENCRYPTED" + padding (which we will ignore). Note the space before "ENCRYPTED".

Now if you change the IV you will indeed only change the first block. What you should however do is to change the first block of the ciphertext. That is used as vector (not the initialization vector, but the next vector) for the CBC decryption of the next block.

As you can see, each bit or byte that you change will be directly reflected in the plaintext. So if you want to flip a single bit in the plaintext you simply flip the bit at the same position in the previous ciphertext block.

So in the end you may want to end up with something like:

IV: 8f6f27b5dbfa2ba8367262bda7154d95
CT: 798f04f8b06cc27c1591a4088531a64a9b76a9be87a3e944c6e7000f24f5b9f9


Assumption of difficulty of attack in restricted short time As well known, different assumptions of difficulty of some problems are used in provable security. E.g., if some crypto-scheme is breakable only in case the attacker finds preimages for hash function, we say that the scheme is as secure as preimage resistance of hash-function.
Imaging, that some hash function is not preimage resistant in general (e.g. it has not enough length, say only 64 bit). Nevertheless, it's obviously difficult to find preimages in short time (say 10 minutes). And imaging that we're able to construct a reduction that implies that successful attacker is able to find preimages in some short time, e.g. during some short session of protocol (e.g. some online key exchange which is abandoned in 10 minutes in case counter-party doesn't respond ).
In this case, the scheme should be recognized as secure based on 2 assumptions:

party controls time of sessions and discontinues a session after 10 minutes of waiting
hash function is preimage resistant within time 10 minutes.

My question is whether you know some research/papers which use such approach in provable security, i.e. they use such assumptions of form "preimage resistance in small time T", instead of conventional "preimage resistance in acceptable(polinomial) time"?
Concrete problem (preimage resistance or something else) doesn't matter obviously,
I'm interesting only in time-restriction.
And does this approach could be reasonable at all?

One area that tries to address such questions is fine-grained cryptography [DVV]. Here the working assumption is that the protocols should be secure "against adversaries with an a-priori bounded polynomial amount of resources but the honest algorithm requires less resources than the adversaries they are designed to fool". A classical example of such a protocol is the Merkle puzzle, which is a key-exchange/public-key scheme that requires $O(n)$ time/queries for the parties carrying out the protocol but it takes an adversary $\Theta(n^2)$ time/queries.

More recently, there have been attempts at building public-key cryptography where the gap is arbitrary (e.g., $O(n^c)$ vs $O(n^{c+1})$ for any constant $c$) and these rely on computation problems such as the orthogonal vector problem [B+] where there is a gap between computation and verification (and this gap is inherent conditioned on SETH). This has also resulted in an interesting notion of proofs of work called useful proof of work [B+] where the goal is to utilize otherwise wasteful work (as for example in Bitcoin).

You can find a nice overview of the area by Alon Rosen here.

[B+] Ball et al, Proof of useful work, Crypto'18

[DVV]: Degvekar, Vaikuntanathan and Vasudevan, Fine-grained Cryptography, Crypto'16.


Cipher suite priority I've been tasked with defining a list of cipher suites to use.

The requirements for the cipher suites are the following:

Symmetric Algorithm: AES-256
Key Exchange: ECDH P-384, DH 3072-bit, RSA 3072-bit
Key Authentication: ECDSA P-384, RSA 3072-bit
Hash Algorithm: SHA-384

Here is the list I've come up with (in prioritized order):

TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384 (0x00C02C)
TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384 (0x00C024)
TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (0x00C030)
TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384 (0x00C028)
TLS_DHE_RSA_WITH_AES_256_GCM_SHA384 (0x00009F)
TLS_ECDH_ECDSA_WITH_AES_256_GCM_SHA384 (0x00C02E)
TLS_ECDH_ECDSA_WITH_AES_256_CBC_SHA384 (0x00C026)
TLS_ECDH_RSA_WITH_AES_256_GCM_SHA384 (0x00C032)
TLS_ECDH_RSA_WITH_AES_256_CBC_SHA384 (0x00C02A)
TLS_RSA_WITH_AES_256_GCM_SHA384 (0x00009D)
TLS_DH_RSA_WITH_AES_256_GCM_SHA384 (0x0000A1)

Would you say I've made the correct prioritization of the cipher suites? Are any of these ciphers considered weak?

These are all fine and the order seems reasonable as well. It is a judgement call which part you think is most likely to fail. I would use your order of preference for the elliptic curve algorithms. GCM vs. CBC is a case of which you find more likely to be badly implemented.

If the requirements are not enforced upon you, I would consider adding in P-256. It should be as strong as 3072-bit RSA, and it at least used to be slightly more widely supported than P-384 – I have not seen recent numbers though.


Comparing two committed values Given two commitments on different values, Can a third party compare those two commitments to know which one is the higher value?

If there's a trusted third party who needs to do the comparison (and you don't care if the trusted third party knows the committed values), then it's actually quite simple.

Take your favorite public key encryption algorithm; remember that a public key encryption algorithm can be represented by $E_{pub}(x, r)$, where $pub$ is the public key, $x$ is the value being encrypted and $r$ is a random value; this random value makes the encryption nondetermanistic.

Now, have the trusted party generate a public/private key pair, and have him publish the public key.

To commit a value $x$, Alice would select a random value $r$, and publish the value $E_{pub}(x, r)$.  Assuming that $E$ is a secure public key encryption system, no one can recover $x$ without the private key (and we assume that only the trusted third party knows that private key).

The open the commitment $E_{pk}(x, r)$, Alice would reveal the values $x$ and $r$; anyone can verify that those values (along with the global public key) generate the commitment.

And, because the trusted third party has the private key, he can examine $E_{pk}(x, r)$, recover $x$, and check if it is a sane value, and check how it compares to another commitment.


Which Diffie-Hellman Groups does TLS 1.3 support? And should we use TLS 1.3 as a guide? This is a two part question - and I'm asking as someone moving into a security role, who'll need to standardize practices going forward.
(1) I'm curious whether the following 10 different DH Groups are the only groups that TLS 1.3 supports, (2) and as such, are they the only ones that we should be using?
https://tools.ietf.org/html/rfc8446#section-4.2.7
      /* Elliptic Curve Groups (ECDHE) */
      secp256r1(0x0017), secp384r1(0x0018), secp521r1(0x0019),
      x25519(0x001D), x448(0x001E),

      /* Finite Field Groups (DHE) */
      ffdhe2048(0x0100), ffdhe3072(0x0101), ffdhe4096(0x0102),
      ffdhe6144(0x0103), ffdhe8192(0x0104),

Some discussion into what curves should be used has already taken place here, which mentions that secp256r1 and secp384r1 are best.

I've read over the RFCs and this post and understand that there are only 5 ciphersuites that TLS 1.3 supports, 3 of which are mandated for compliance with the standard (there are also 3 mandated Signature Algorithms). I also understand that the Signature Algorithms and the Supported Groups are communicated in other Extensions
(2) To elaborate on my second query: Given that TLS 1.3 was developed over years by experts, and that it only supports certain cypher mechanisms - can we take that to mean that these are the only mechanisms that should be used?
Basically, should we configure any TLS 1.1 and TLS 1.2 connections (web servers, SSL-VPN servers and IKE/IPSEC tunnels) to use/prefer the mechanisms listed in the TLS 1.3 RFC if the software/hardware supports it?

(1) I'm curious whether the following 10 different DH Groups are the only groups that TLS 1.3 supports,

Yes, in the sense that TLS 1.3 only allows groups that are explicitly declared as supported in 1.3. This currently includes not only the groups from RFC 8446, but possibly more recent RFC as well, such as Brainpool curves from RFC 8734.
The TLS supported groups registry lists all the groups, but unfortunately it doesn't distinguish between protocol versions (you have to chase this information down in the RFC given as references). The “recommended” column is specifically about TLS 1.3, but it is neither a minimum supported set nor a maximum safe set (you can have good interoperability even without the full “recommended” set, and the non-recommended set includes both acceptable things such as FFDH and bad things such as 160-bit elliptic curves).

(2) and as such, are they the only ones that we should be using?

You certainly shouldn't be using other groups in TLS 1.3 since they wouldn't comply with the protocol. Your software isn't likely to support other groups in TLS 1.3 anyway.

(2) To elaborate on my second query: Given that TLS 1.3 was developed over years by experts, and that it only supports certain cypher mechanisms - can we take that to mean that these are the only mechanisms that should be used?

No: it's ok to use other mechanisms in older versions of the protocol. Not every mechanism that is safe to use made it into TLS 1.3. Some mechanisms that are safe but don't have any practical advantage (faster, smaller code, smaller message size, etc.) didn't make it into TLS 1.3. One of the goals of TLS 1.3 was to reduce the complexity of the protocol, which means fewer choices.
With TLS ≤1.2, you need to balance security (as in: risk of implementation bugs, known protocol weaknesses, or yet undiscovered protocol weaknesses) with interoperability. (This is true with TLS 1.3 as well, but 1.3 hasn't been along for long enough to have interoperability problems when it goes through at all.) Due to the number of existing options and the diversity of the existing software, there's no single right answer for where to put the balance.

Some discussion into what curves should be used has already taken place here, which mentions that secp256r1 and secp384r1 are best.

That discussion was in the context of TLS 1.2, which didn't support the same curves. There's no reason to reject any of the curves supported in TLS 1.3 except maybe secp521r1, which is susceptible to implementation weaknesses. (As the name hints, secp521r1 involves 521-bit numbers – and yes, it's 521 and not 512. Because this is slightly larger than a multiple of 64, there's a non-negligible chance that certain intermediate numbers will have the most significant word be 0, and insufficiently protected implementations might leak that fact when the number is multiplied because the multiplication will be slightly faster. This leak can be enough to allow an attacker to reconstruct the private key with a moderate number of connection attempts.) Curve25519 is perfectly fine and arguably preferable to secp curves because it's easier to implement securely. Back in 2015 it was not commonly supported in TLS, but in 2021 it's a standard part of TLS 1.3. Curve448 is slower and has no particular advantage (barring yet unkown weaknesses in other curves), but it's ok to use it.
For finite-field Diffie Hellman, don't use groups smaller than 2048 bits. Older versions of TLS allow custom groups, and there's no consensus on whether to make use of that. On the one hand, using standard groups might allow an attacker with sufficient computing power (read: NSA) to precompute a very large number of values which then makes attacks feasible. On the other hand, generating good custom groups is slow and hard, and doing that risks creating vulnerabilities that are easier to exploit, such as letting a man-in-the-middle persuade the participants to use a weak group. This is why TLS 1.3 mandates the use of known good groups.


Can multi-prime RSA be used to create an abuse-resistant lawful interception mechanism? New to site so this may have been asked before: Can multi-prime RSA, i.e. where N is product of three or more distinct primes, be used for secure communication while allowing distinct authoritative entities to decrypt the messages when under a proper court order to do so?

For instance, let $N=p\cdot q\cdot r$, let $(N,e)$ be the public key and let $(N,d)$ the private key as usual. But have the generating algorithm securely send $(N,e,p)$ to, say, the Supreme Court, $(N,e,q)$ to the Executive and $(N,e,r)$ to Congress. Then no one entity alone could decrypt, but any pair could.  Can this or some variation work? Would this require that two-prime RSA be outlawed?

It is also known that multi-prime RSA has a narrower range of exponents vulnerable to the lattice-based reduction algorithm attack. See N. Ojha and S. Padhye "Cryptanalysis of Multi Prime RSA with Secret Key Greater than Public Key", IJNS, Jan. 2014.

That sorts of works, but:

Whatever decrypts will need the full private key, and will be a potential single point of failure.
The system can be secure only if each of $pq$, $qr$, and $rp$ is wide enough to be hard to factor; so if you want to be as secure a 4096-bit RSA, you need a 6144-bit public modulus.
We can achieve the same functionality by using two-factors RSA (thus reducing the size of the public modulus at equivalent security), and Shamir's secret sharing for the private key (or the seed that was used to generate the private key, with the added bonus that the shared secrets can be short enough to be keyed-in).
We can achieve better functionality using two-factors RSA and a private/public key pair per entity, with each file encrypted with secret-key cryptography like AES and a random key, shared using Shamir's secret sharing, with the secret shares RSA-encrypted. That way, the number of autorities necessary to decipher, thresold... can be chosen on a per-file basis; and most importantly, the multiple private keys never need to be brought together.


The Rationale behind NIST's counter/LFSR recommendation on deterministic IV constructions on SP 800-38D The NIST has a "SP 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC". This guideline is a base for AES-GCM from definition to security considerations. ( all bolds are mine)
In section 8.2.1 Deterministic Construction IV

In the deterministic construction, the IV is the concatenation of two fields, called the fixed field and the invocation field. The fixed field shall identify the device, or, more generally, the context for the instance of the authenticated encryption function. The invocation field shall identify the sets of inputs to the authenticated encryption function in that particular device.

and later in the same section

The invocation field typically is either 1) an integer counter or 2) a linear feedback shift register that is driven by a primitive polynomial to ensure a maximal cycle length. In either case, the invocation field increments upon each invocation of the authenticated encryption function.

The distinction of a counter and Linear Feedback Shift Register (LFSR) is clear. A counter can be simply implemented in the CPU registers in construct an LFSR that requires a primitive polynomial and extra code. Selecting/finding a primitive polynomial is not hard today. As listed in this SO answer there is a report from HP list the binary primitive polynomial of low-degree. One can also use Maple, Mathematica, and SageMath to find one.
If everything works correctly, the counter and LFSR can produce unique IV's that are crucial for the security of the AES-GCM. Any (IV,Key) pair use can remove the confidentiality and can cause forgery.
There is one problem that I'm aware of; during the system failures, the last incremented/advanced counter/LFSR value can be lost. If the administrators continue from the last known values this can result in (key,IV) pair reuse. To mitigate either exchange a new key or use random in some part of the IV.
In the comment of the answer of What are the rules for using AES-GCM correctly?
Maarten Bodewes said

Sorry, but I don't understand why you'd need a LFSR specifically rather than a generic DRBG.

and also
Gilles 'SO- stop being evil' said

This is good advice except for the LFSR. A non-cryptographic RNG has no place in crypto code.

and

I wonder why they suggest an LFSR. It's a pity that they don't give a rationale.

So the questions for the AES-GCM are;

What is the rationale of the NIST to suggest counter and LFSR for IV.

Why using an LFSR is not good advice?

In section 8.2.2 RGB-based construction talk about RGB(Random Bit Generator) in two ways

an output string of r(i) bits from an approved RBG with a sufficient security strength, or
the result of applying the r(i)–bit incrementing function to the random field of the preceding IV for the given key

Is there any advantage of RGB against counter/LFSR?

I can't tell whether this is what motivated NIST, but I found a paper that has an argument for LFSR counters in some applications:

Mukhopadhyay, Sourav and Palash Sarkar. 2006. "Application of LFSRs for Parallel Sequence Generation in Cryptologic Algorithms." Cryptology ePrint Archive: Report 2006/042.

Abstract. We consider the problem of efficiently generating sequences in hardware for use in certain cryptographic algorithms. The conventional method of doing this is to use a counter. We show that sequences generated by linear feedback shift registers (LFSRs) can be tailored to suit the appropriate algorithms. For hardware implementation, this reduces both time and chip area. As a result, we are able to suggest improvements to the design of DES Cracker built by the Electronic Frontier Foundation in 1998; provide an efficient strategy for generating start points in time-memory trade/off attacks; and present an improved parallel hardware implementation of a variant of the counter mode of operation of a block cipher.

As I mention in one of the comments to the question, NIST SP 800-38a ("Recommendation for Block Cipher Modes of Operation," 2001 Edition) also mentions LFSRs as an example of an allowable incrementing function for counter blocks (p. 18), so the technique predates both GCM and this paper.
RFC 3686 ("Using Advanced Encryption Standard (AES) Counter Mode With IPsec Encapsulating Security Payload (ESP)," January 2004) also allows the use of LFSR counter blocks. It says LFSR are a common IV generation method (p. 5) and obliquely appeal to similar motivations as Mukhopadhyay & Sarkar for allowing them:

[p. 14] Allows adders, LFSRs, and any other technique that meets the time      budget of the encryptor, so long as the technique results in a unique value for each packet.  Adders are simple and straightforward to implement, but due to carries, they do not execute in constant time.  LFSRs offer an alternative that executes in constant time.

Saying that LFSRs execute in constant time does counterintuitive to us software folks, who are biased into thinking more generally that addition is "simple" but LFSRs "complex."


Multiplication vs exponentiation in pairing based cryptography $$P\in G_1$$$$Q\in G_1$$          $$a,b \in Z_q$$         $G_1$ isadditive cyclic group of prime order $q$
$$e(P^{a+b},Q)------(1)$$
$$e(aP+bP,Q)----(2)$$
(1) and (2) will give the same pairing result $e(P,Q)^{a+b}$.
In (1) and (2), despite of same pairing result, is there difference in terms of security or performance for different operations (exponentiation, multiplication and addition) in $P$?In (1), I don't know clearly about exponentiation is allowed or not with randomly generated $P$ value from additive group.

The problem is that you are comparing apples and oranges. A group has a single operation associated to it. Depending on your notational conventions you either need to write (1) $e((a+b)P,Q)$ and (2) $e(aP+bP,Q)$ if you write $G_1$ additively or (1) $e(P^{a+b},Q)$ and (2) $e(P^a \cdot P^b,Q)$ if you write $G_1$ multiplicatively. The cost of computing $(a+b)P$ or $aP+bP$ depends on your approach to scalar multiplication, but typically the former approach will be more efficient.


How much pre-hashing a password increase security against brute force attack? I am wondering how much hashing a password used as key for a symmetric key algorithm helps preventing brute force attack on crypted text.

Let's assume I want to crypt text A using key B using AES-256. I expect user to input not secure keys, such as: ['apple', '22march', 'newyork'].
So I hash these keys with PBKDF2 using many iterations, and I got the key B. That is long and fixed length key I will use for crypting the text with AES.

AES(TEXT, PBKDF2(KEY))

Would this help preventing brute force attacks?

The attackers should also hash each input (for example from a dictionary, where they'll match 'apple') to get the key B for trying decrypting the text A using AES? Or alternatively, they should trying brute forcing directly the AES crypted text, but the keys are always output from PBKDF2 and so they are really difficult to be cracked.

Would this help preventing brute force attacks?

It would slow down an attacker and prevent them from trying as many password guesses. E.g. if you used 1000 rounds like in RFC 2898, you would reduce the number of guesses by a factor of 1000.

Assuming you count dictionary attacks under brute force attacks, such attacks would definitely not be completely prevented. Simplest passwords like your example of 'apple' could be cracked regardless of which (practical) number you choose for iterations. You can't make the work factor large enough that the attacker can't still make hundreds or thousands of guesses in a feasible time, or you can't yourself use it.

But yes, your use of PBKDF2 makes sense and is essentially the purpose of having it in a key generation context. It's just that there is no way to make as simple passwords as 'apple' secure under any circumstances. (At least unless there's another authentication factor.)


How to deal with a cipher with addition and XORs combined together? I am trying to cryptanalyze a cipher where bitwise XOR and addition mod $2^n$ are combined together. I've been working on it for a long time but with no result - the main difficulty, which I am unable to overcome, is that even though XOR and addition are linear in their own groups, addition mod $2^n$ is non-linear over $\mathbb{F}_2^n$ and vice versa.

Are there any standard methods of dealing with it which I should know about or some fancy theorems that would make things easier?

Note that, for the least significant bit, addition mod $2^n$ and xor are the same.  So if the cipher doesn't include rotation then you can set up a linear equation in the least significant bits of the plaintext, ciphertext, and round keys that holds with probability 1 (if the cipher breaks the state up into two or more distinct parts, like a Feistel cipher, then you need to consider the least significant bits of each part).  That means with a single known plaintext you can extract a single bit of information about the least significant bits of the round keys.

This single bit of information narrows down the possibilities for the least significant carry bits, which enables you to gain one more bit of information about the LSBs of the round keys by observing what happens to the least 2 significant bits of the plaintext and ciphertext.  That narrows down the possibilities for the LSB carry bits even further, enabling you to gain another bit by looking at the least 3 significant bits of the plaintext and ciphertext, and so on.  By progressively narrowing down the possibilities for the round key LSBs, you can gain complete knowledge of those bits (so long as the number of rounds does not exceed the 'part' size of the cipher), and then you can attack the 2nd LSBs using the same techniques.

To illustrate, take this very simple example cipher: $E(x) = ((((x + R_0) \oplus R_1) + R_2) \oplus R_3)$, where the cipher operates on blocks of $n$ bits, "+" is addition over $2^n$, $\oplus$ is xor, and each 'round' key $R_i$ is an $n$-bit independently selected random string.  From this, if $X^j$ denotes the $j$th bit of a given word (zero being the least significant bit) and $P$ and $C$ denote the plaintext and ciphertext respectively, given a single known plaintext the following equation gives you a single bit of information about the four round keys:
$$P^0 \oplus C^0 = R_0^0 \oplus R_1^0 \oplus R_2^0 \oplus R_3^0.$$
Let us suppose that the result is zero.  That means either all four least significant bits of the round keys are zero, or two of them are zero, or none of them are zero - there are eight possible arrangements in total.  If you get two known/chosen plaintexts where $P^1$ is fixed to some value and $P^0$ varies, and look at the resulting $C^0$ and $C^1$, you can narrow those 8 possibilities for the LSBs of the round keys down to 4 possibilities.  In a similar fashion those four can then be narrowed down to two, and then to one, using a few more known/chosen plaintexts.

With the influence of the least significant carry bits known, you can apply the same technique to determine the four $R^1$ bits.  That way you can progressively reveal almost all the bits of the round keys, using relatively few known/chosen plaintexts.

Because of this sort of vulnerability in using only addition and xor, ARX ciphers include rotation (that's the 'R' part of the name).


Using a non cryptographic PRNG for randomized algorithms I want to use randomized algorithms (quicksort, ect...) on a server, but secure pseudorandom generators use a lot of cpu time. But if I use a non-secure one, and the clients figure out the seed, they will be able to force a worst-case scenario. However, the users are never given the seed or output of the generator. The only way I think they can break this is by timing attacks. Will it help if I impose a delay on randomized algorithms e.g. they will be forced to run for 1 second, and if they finish earlier, just wait until 1 second passes?
Also, I can reseed it with a cryptographically generated seed every now and then.

In fact, on a recent enough x86 CPU (I mean 2011 or later, so not exactly bleeding edge), there are AES opcodes that, as their name say, help implement the AES block cipher with hardwired dedicated operations. They are really fast. Thus, a PRNG that simply runs AES in CTR mode (encryption of successive values of a counter) will:

be cryptographically secure; and:
be blindingly fast, actually more so than most non-cryptographic PRNG.

We are talking here about several gigabytes per second. This should be adequate, and even negligible, for most purposes.

If your platform of choice does not have such an hardware implementation of AES, then there still are good cryptographic options, in particular the stream ciphers from the eSTREAM projects.

As an aside, there are several variants of Quicksort, and are not necessarily randomized. The randomized versions of Quicksort try to avoid the tricky cases where the performance degrades from the average O(n log n) to O(n2). Presumably, if there is an attacker, then the attacker will try to force the input to hit that kind of bad situation, as a denial-of-service attack. If you use a non-secure PRNG, then the attacker may indeed analyse the timing information to predict the PRNG output and thus defeat the countermeasure. Enforcing a delay might work only if the delay is such that the sorting is always below the threshold, which means that you made it so that your Quicksort is always slow. In other words, you defeat DoS by attackers by DoS-ing yourself harder. This is hardly a nice situation.

A fast, cryptographically secure PRNG will avoid such situations nicely, and if that PRNG is properly implemented, then its cost will be negligible with regards to the cost of sorting. Alternatively, you might consider other sorting algorithms that have guaranteed O(n log n) performance even in the worst case, in particular Mergesort and Heapsort (Mergesort is usually faster than Quicksort, but requires an extra RAM buffer; Heapsort is a bit slower but in run in guaranteed fixed RAM, contrary to Quicksort).


Encrypt password for oneself on paper Assume the following:

You have to encrypt a file (ZIP-file) containing import information. This file should be password-protected and you want to leave yourself the password encrypted (on paper, maybe bury it somewhere in your yard, hide it behind the walls, you name it). How could you encrypt it so that you might be able to recover it? You might as well assume extreme situations like suffering a stroke (and recovering) or becoming enemy of the state and thus being pursued by government agencies. Apart from a secure physical location (six feet under) it should also be logically secured.

Some thoughts:

tabula recta might work -> how long could passwords be (more than 24 characters?)
the information to decrypt the password should be self-containing -> hinting to things only you yourself know or something similar
or does it make no difference if I buried a flash drive somewhere?

Thank you for your thoughts on this one.

Update 2017/12/31:

I checked the key sharing schemes article on Wikipedia. Actually this is slightly beyond the scope of my question - although I like the idea of splitting the key!

I am more concerned about proper encryption. I would really like to find a way to create a proper key and encrypt a password.

Key management is always an issue, and you could write books about it.

I'd myself create two keys by splitting one off a normal symmetric key. This key I would print out on paper and store in a secure location such as a physical (fireproof) safe. I'd store the other part in another secure location, such as a bank, referring to the bank from the safe (you know where your own safe is, but will you remember the details of the bank?). To decrypt you can re-establish the key and then decrypt the password.

There are literally hundreds of other ways of accomplishing the same thing though. Which one is most secure depends on the situation and threats. In the end this is about balancing convenience and security. You can have a look at key sharing schemes to have some more ideas for splitting and securing keys. If security is a real issue you should be just using keys, no passwords - they are simply too easy to guess or too difficult to remember.

I'd not store the keys on flash - there is too much chance of it losing too much charge. Burying anything is not a good idea at all; somebody may accidentally or purposefully find it and with the amount of trash we generate, it will not be a great archeological find far into the future - please do not bury your electronics. Besides the chance of damage is just too likely when you bury anything.


Can Bitcoin HD public keys be used for symmetric encryption? I asked this at bitcoin.stackexchange.com first, but it seems that this is more of a crypto-question anyway.

I'm interested in using a Hierarchical Deterministic Bitcoin wallet branch as a "shared secret" between two parties. Basically one party could send an index (in plain text) to the other party, along with some sensitive information encrypted (symmetrically!) with the public key along that HD branch.

The recipient could then derive the public key at the sent index, and decrypt (symmetrically!) the sensitive information with that public key. These keys would not be used as addresses or in any bitcoin transactions, nor would any addresses along that HD branch. The HD branch itself is not known outside of the two parties.

Is this (cryptographically) secure?
Would it be better to hash the public keys before using them as an encryption key?
Are there any resources about doing something similar I can use for research?
Anything blindingly obvious that I'm missing?

Thanks!

Is this (cryptographically) secure?

That is hard to say without knowing the exact details of the bitcoin protocol (which I would like to understand better, but don't have the time at the moment). Looking at the document you linked to, the public child key is created as $\text{HMAC-SHA512}(Key = c_{par}, Data = ser_P(K_{par}) || ser_{32}(i))$. This value is split in half. One half is turned into a point. That point, plus $K_{par}$ is returned as the public key. The other half is returned as the chain node. Is this the index of which you speak?

The process looks good, but it is hard to say whether or not it is cryptographically secure without knowing details of how the input parameters are chosen. It all comes down to the entropy of those. If they are high entropy, then the output should be high entropy and so it should be "secure" (you haven't actually defined secure, but I'm assuming you mean that an outsider could not guess/figure out the key).

I would strongly recommend, once you have formally specified your protocol, that you work on a security proof. This will likely be done by reducing the security of your protocol to some other (related) protocol. This would be done by assuming an attacker breaks your protocol then showing some horrible impact this would have on the other protocol. The other protocol could be the HD wallet protocols. That would establish that breaking your protocol is at least as hard as breaking HD wallet.

  Would it be better to hash the public keys before using them as an encryption key?

As the public key is a point on an elliptic curve, I would say yes. In particular, owlstead's recommendation of a key derivation function is on the right track.

  Are there any resources about doing something similar I can use for research?

Not that I am aware of.

  Anything blindingly obvious that I'm missing?

Well, if there is, I am missing it too. The best way to find out about this at this point would be to write up a short white paper on the idea and present it to people familiar with the areas (both bitcoin and cryptography). You could do this by sending it directly to researchers and getting their thoughts, publishing it in a workshop of some sort, etc. Also, make it available online somewhere (e.g., ePrint) and comment on here with a link (I'll definitely take a look). Your white paper should review enough of the basics of the bitcoin protocol and the HD wallet protocol so as to be self-sufficient. This should be a good exercise as I saw on your profile that you are a graduate student.


What is the need of having a key schedule before executing AES Can someone explain to me why does using a key schedule make's AES more secure if instead of calculating and adding your round key's, you just keep on adding the cipher key. ?

Not using separate keys for each AES round would make your cipher vulnerable to slide attacks.
Using two plaintexts M and M' with M' being the result of an AES round after calculating M as input, you can differentiate between those plaintexts by calculating the output of an AES round which takes the ciphertext C as input.

Due to the birthday problem, this attack schould reduce the complexity of breaking the AES to $\mathcal{O}(2^{n/2})$.

Source: Silde attack


Public key decryption mathematical analogy To clarify, I'm talking about digital-signatures, not public key encryption.

When I encrypt something with a private key, then it should be decryptable with a public key, as I've understood how asymetric cryptography works.

So, if 654 * 987 * 123 = 79.396.254, there are countless sums that could lead to that 79 million answer, that explains private key encryption to me, and can be applied to superficially explain how digital signing works.

But how do you verify with a public key, that it was signed with their private key?

I'm looking for the simplest mathematical way to explain this, perhaps using a similar mathematical analogy.

I'm not looking for a super in-depth explanation, but a superficial analogy for it.

Ok, here's a toy example (which really doesn't work) of a simple signature scheme, which you can use as an analogy of a real system:

Suppose the signer Alice picks three integers $b, c, p$, and computes $a = b \times c \bmod p$.  She then publishes $a, b, p$ as her public key, and keeps $c, p$ as her private key.

Then, when Alice wants to sign a message $M$, she computes $S = c \times M \bmod p$, and publishes $S$ as the signature.

So, when verifier Bob gets the message $M$, the signature $S$, and Alice's public key, he verifies whether $a \times M \bmod p$ and $b \times S \bmod p$ are the same; if the signature is valid, then $a \times M \bmod p = (b \times c) \times M \bmod p = b \times (c \times M) \bmod p= b \times S \bmod p\ $, and so equality would hold.

The points I am hoping to make in this analogy:

The signature is not necessarily an 'encoding' of the message
Instead, the signature and the message satisfy some relationship (in concert with the public key)
It's not obvious how to create a signature for a given message with only the public key (actually, my example falls down a bit here)
The private key contains the 'secret sauce' that makes generating such signatures easy

Now, this doesn't work as an actual signature scheme, even with large numbers, because we know how to compute $a \times b^{-1} \bmod p$, which is $c$, however the method isn't immediately obvious to someone new to the field.


Key vs Algorithm when applied to Enigma I've just been reading the Why should I make my cipher public? question and answers on this site.

I understand Kerckhoffs's principle, but I'm unsure exactly how this applies to Enigma - i.e. where the delineation is between algorithm and key.

(I feel I should know, but I haven't quite gotten there.) Here's what I think I know:

The wiring of the rotors & plugboard = part of the algorithm
The starting positions of the rotors = part of the key

Assuming #2 is correct, how would you define the order in which the rotors are set, or which ones are selected - is that merely altering the algorithm?

Your assumptions are partially correct.  The wiring of the rotors is technically part of the algorithm, but because of the era in which Enigma was invented the rotors were kept secret, so discovering the rotor wiring became an initial step in the cryptanalysis of the machine.  The plugboard/steckerboard, however, was changed by the operator every day and its setting was definitely part of the key.

The full key to an Enigma message is made up of everything the operator needed to set in order to encipher and decipher a message.  There are four parts to the key.

Rotor order.  Each rotor had a Roman numeral engraved on it to identify it, and the operator had to install them in the assigned position.  This was set daily.
Ring position. Each rotor had an alphabet ring that could rotate about the rotor, and it had to be positioned correctly before installing the rotor in the machine.  This was set daily.
Letter starting position. Each rotor had to be rotated to display the correct starting letter.  This was set at the beginning of each message.
Plugboard wiring.  This was set daily.

The settings were changed every day.  The operator looked up the settings by date printed on a sheet of paper and would set up the machine for that day, establishing the key.  The starting position of the wheels had to be set prior to each message being sent or received.  If there was a problem or typo during the message, the operator had to start over by resetting the wheels, and retyping the entire message.

I believe the setting sheets were distributed monthly, and the naval versions were printed on water soluble paper so they could be destroyed in the event of imminent capture or sinking; but I don't have a reference for that.

Operating instructions for the machine can be viewed here:  http://www.ellsbury.com/enigma3.htm

An English translation of a manual for the machine can be found here:
http://www.ilord.com/enigma-manual1937-english.html


All fully homomorphic encryptions (FHE) are converted into homomorphic commitments? The GSW one of the FHE scheme is widely used as a homomorphic commitment scheme to build lattice based ABE, homomorphic signatures and NIZK and so on. But I cannot find other FHE schemes to be considered as a commitment scheme such like that.
Is there a special reason why GSW is only one scheme regarded as a commitment scheme? or all known FHE schemes such as BGV are also commitment schemes?

Yes, all known FHE schemes are also commitment schemes (BGV included). The reason why GSW if much more often explicitly described as a commitment is that, unlike the alternatives, it leads to a commitment scheme with very nice property - for example, it gives a dual mode commitment (i.e. it can be perfectly binding or perfectly hiding depending on how exactly the parameters are generated), which is a very useful property (at the heart, to mention one application, of the constructions of fully homomorphic signatures).


why babai rounding technique does not work for finding closest vector using bad basis Given, a basis of the lattice such that the basis not nearly orthogonal(bad basis) babai rounding technique to find the closest vector does not give the desired result. Can any one explain why?

The rounding algorithm, given $\mathbf{t=v+e}$ will output
\begin{equation}
\lfloor\mathbf{t}^t\cdot \mathbf{S}\rceil\cdot \mathbf{S}^{-1}=
\lfloor(\mathbf{v}^t + \mathbf{e}^t) \cdot \mathbf{S}\rceil\cdot \mathbf{S}^{-1}=
\mathbf{v}^t +\lfloor\mathbf{e}^t\cdot \mathbf{S}\rceil\cdot \mathbf{S}^{-1}
\end{equation}
where $\mathbf{v}$ is in the dual lattice. Now, the algorithm works correctly if $\lfloor\mathbf{e}^t\cdot \mathbf{S}\rceil$ becomes zero, which holds as long as both $\mathbf{e}$ and $\mathbf{s}_i$ are short enough (i.e., the basis is good enough)


LFSR for small numbers with large periods I want to generate a few random numbers using an LFSR. However, the LFSR output depends on the number of taps, so for a large period I use large (relative) number of bits. This causes the numbers to be as large as the period. For example, I would like to use a 16-bit LFSR to generate random 5-bit numbers. What is the proper way to reduce the number of bits but still ensure that single numbers don't repeat and that the sequences don't become shorter?

[Edit:]

For degree 5, I am using the polynomial x^5+x^3+1 and the following code:

lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0x0014u);

For n = 16, I am using the polynomial  x^16 + x^14 + x^13 + x^11 + 1

lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xB400u);

Are any of these a problem?

Contrary to what's stated in the question and its comments, extracting any $m\le n$ bits from the sequence of the states of an $n$-bit LFSR still result in a sequence with period $2^n-1$, assuming the state of the $n$-bit LFSR is not zero and its generating polynomial is primitive. Proof sketch: by a fundamental property of LFSR with primitive feedback polynomial, its period has $2^n-1$ states not including the all-zero state. It follows that any bit has period $2^n-1$ with $2^{n-1}$ ones and $2^{n-1}-1$ zeroes.

Further, the sequence is as closely evenly distributed as an $m$-bit sequence of period $2^n-1$ can be: each of the $2^m$ values is reached $2^{n-m}$ times, except $0$ which is reached $2^{n-m}-1$ times. In fact, that's much too evenly distributed to be random.

Hence taking (say) the low 5 bits of a maximal-length 16-bit LFSR will result in a sequence with period 65535, and during that period each of the 32 values will be reached 2048 times, except 0 reached 2047 times. However that's NOT going to make even a passable non-cryptographic RNG: if the LFSR uses the Fibonacci construct, 4 bits of any output directly come from the previous output, and the situation is hardly better with a Galois construct (or not at all, depending on polynomial). For example, using the 16-bit generator in the updated question (which, per the convention I favor, use the polynomial $x^{16}+x^5+x^3+x^2+1$ rather than its reflexion $x^{16}+x^{14}+x^{13}+x^{11}+1$)

#include <stdio.h>
int main(void){
  unsigned x = 1, j = 128, y; // initial sate, number of outputs, output
  do {
    y = x&31;
    printf("%02X%c", y, --j&15?' ':'\n');
    x = x>>1 ^ 0xB400&-(x&1);
  } while(j);
return 0;}

we get this:

01 00 00 00 00 00 00 10 08 14 1A 0D 16 0B 05 02
01 00 10 08 04 02 11 08 14 0A 05 02 11 18 0C 16
1B 1D 1E 0F 17 1B 0D 16 0B 15 1A 0D 16 0B 05 02
11 08 04 12 19 1C 1E 0F 17 0B 05 12 19 1C 0E 17
1B 1D 0E 07 03 01 10 18 1C 0E 17 1B 1D 1E 0F 07
13 09 14 0A 05 12 19 1C 0E 07 13 19 1C 1E 1F 1F
1F 1F 1F 0F 07 13 09 14 1A 1D 0E 07 03 01 10 18
1C 1E 1F 0F 07 13 09 04 12 09 14 0A 15 1A 1D 1E

and it is painfully apparent that the right hex digit of any output is always the previous output right-shifted by 1.

One possible solution to that is to steps the LFSR $m$ times for each output of $m$ bits, collecting 1 bit at each step. One problem is that when $\gcd(m,2^n-1)\ne 1$ the period is reduced by that factor (and the proof of even distribution no longer works).

Rather, I formerly proposed to output y = ((0x6D9B*x+0xDB75)&0xFFFF)>>11. It does improves things, but some of the problem with y = x&31 remains: the distribution of two consecutive outputs is quite poor. Something like y = 0x6D9B*x, y = (y<<4 ^ y)*0xDB75, y = (y<<2 ^ y)>>11 & 31 further improves things, while provably keeping the period and uniform distribution (because, until the >>11 & 31 steps, the transformation from the low 16 bits of x to the low 16 bits of y is a mapping).

Caution: even perfecting that by using an even more complex transformation of output, the resulting sequence is not cryptographically strong, by any measure, and can't be made so without much more state bits.


What exactly is the impact of the hidden subgroup problem on cryptography? I understand my group theory (allegedly), so I can make partial sense of The Hidden Subgroup problem:

  Given a group $G$, a subgroup $H \leq G$, and a set $X$, we say a function $f : G \Rightarrow X$ separates cosets of $H$ if for all $g_1, g_2 \in G$, $f(g_1) = f(g_2)$ if and only if $g_1H = g_2H$.

  Hidden subgroup problem: Let $G$ be a group, $X$ a finite set, and $f : G \Rightarrow X$ a function such that there exists a subgroup $H \leq G$ for which $f$ separates cosets of $H$. The function $f$ is given via an oracle. Using information gained from evaluations of $f$ via its oracle, determine a generating set for $H$.

In English as much as possible, $G$ is a group which means it satisfies certain conditions such as there being an identity and inverse element under an operation. Here, the operation isn't specified. So then we have some set $X$ which does not necessarily have to meet these criteria, and $f$ a function that maps $G$ the group onto $X$.

Cosets e.g. $gH$ are the set of all $H$ operated on by a specific $g$, so $gH = {gh: h \in H, g}$. $Hg$ is the other ordering and exists because groups aren't required to be abelian.

So this splitting function $f$ ensures each coset is mapped uniquely if when the function is applied to the group members it and derives the same result, when applied to the relevant cosets it must also derive the same result. This establishes that each coset does essentially map to a unique set of elements in $X$ if I understand this correctly.

So, the HSP is essentially the task of finding $H$ given $G$, $f$ and $X$ if I follow that correctly.

So, the obvious one-way-problem great-if-you-know-$H$ issue aside, how does the HSP affect cryptography? Specifically, aside from the discovery of the set $H$ in $X$ I see no particular direct use for the HSP, yet I have come across it frequently in discussions on cryptography, particularly with the odd link or reference towards this paper. Finally, am I missing anything, aside from the impacts of cryptography, in my summary of the HSP?

As far as I understand, the HSP is a hard problem such that:

some types of HSP (namely those operating in an abelian group) can (theoretically) be solved efficiently on a quantum computer (assuming one can be built);
many types of public key cryptosystems can be reduced to the HSP: if you can solve the HSP you can break the key.

In particular, integer factorization and discrete logarithm (in any abelian group, which includes elliptic curves) can be reduced to HSP over abelian groups, and thus easily breakable on a quantum computer. This is not really new: Shor's algorithm already does that. It just happens that Shor's algorithm is a special case of HSP.

The interesting part is that lattice reduction can be reduced to HSP over a non-abelian group, for which no efficient algorithm is known yet. So this formalism is actually giving reasons on why lattice-based algorithm may survive in the post-quantum world.

In your summary of HSP, one might add two details: "finding H" really means "finding a set of elements of G which generate H" (i.e. H is the smallest subgroup of G which contains all those elements); and: "given f" means "a black box implementing f is given, and can be invoked repeatedly on any inputs".


Difference between cryptanalysis and brute force attacks I wonder about the difference between brute force and cryptanalysis attack?
as my professor asked us about the difference,
but i searched and found that the brute force is one type of cryptanalysis attacks is that true or there's a difference between them ?
Thanks in advance.

That's a matter of terminology, but generally cryptanalysis and brute force attack are mutually exclusive. Cryptanalysis means attacking a cryptographic system by looking for something clever that the designers of the system didn't think of, for example finding a mathematical relation that makes some computation fasters. A brute force attack is one that doesn't use any intelligence and enumerates all possibilities; cryptography is always vulnerable to brute force attacks, but if properly designed it makes them practically impossible by arranging for the probability of success to be utterly negligible.


Are there any examples of signature schemes with multiple signing keys but one verification key? Need a signature scheme where signer signs with one secret key out of a set of signing keys, but verification can be done using just one verification key.

Maybe you're looking for certificates.  A certificate is a formal signed statement of authority for a user's public key to sign documents.  A certificate is signed by a party called a certification authority whose public key a verifier knows.  A user transmits a message, her certificate, and a signature under the user's private key.  The verifier, knowing only the CA's public key, verifies the certificate with the CA's public key, extracts the enclosed user public key, and verifies the signature with the user public key.  This can be built out of any vanilla signature scheme.

Maybe you're looking for group signatures.  A group of users, and a group manager, gather together to generate keys and publish a public key for the group.  Any member of the group can sign messages on behalf of the group, verified by the group's public key.  The verifier does not ordinarily learn which member signed it, only that someone in the group did, but the group manager can deanonymize signers.  There are a few more security properties; see the article for details and references.  This requires fancy crypto.

Maybe you're looking for multisignatures or collective signatures.  A collective of users gather together to generate keys and publish a public key for the collective.  The collective, or some sufficiently large subset, must all agree to sign any particular message before they can produce a signature that a verifier can verify with the collective's public key.  In an answer to another question yesterday I sketched a simple collective signature scheme out of Ed25519.


Secure enigma machine? The enigma machine had a serious flaw: the letters could not be encrypted as themselves. Is there an online enigma simulator I can try that does not have this flaw, which would likely make it secure?

I think you're looking for the Typex machine.

It was developed by the British and it had the major design flaw of the Enigma machine removed, which was the fixed-point-free permutation, meaning that no letter will be encrypted to itself.

A Typex simulator can be downloaded on Github (released by GCHQ). Unfortunately I could not find an online simulator, but maybe you'll have more luck.


Encoding an element in $r=r'||h(r')$ way We consider a finite field $\mathbb{F}_p$, where $p$ is a large prime e.g. 256-bit.

We have $b$ a fixed element of the field. We encode it as $b'=b||h(b)$, where $h(.)$ is a cryptographic hash function. Assume the output of $h(.)$ is of size 160-bit.
We encode that way to distinguish the element $b'$ from a random element $r$ of the field.

So to check if the element has the above structure we do:

(1) Parse the value: $r=r'||r''$, where size of $r''$ is 160-bit.

(2) check: $h(r')\stackrel{?}=r''$

Question1: How can we show/prove that the random element only with a negligible probability can have such structure?

Question2: Can we reduce the $h(.)$ output size to 80-bit (which is not the standard hash function output size) and set $p$ as smaller prime number (e.g. 128-bit )and prove a random value can have the above structure with only negligible probability?

Citing a paper that use/prove such statement would suffice.

Question1: How can we show/prove that the random element only with a negligible probability can have such structure?

If we assume the random oracle model and have $h: \{0,1\}^* \to \{0,1\}^n$ then we can state that $h(.)$ is equivalent to randomly sampling from $\{0,1\}^n$. Thus for a random element $r = r'||r''$ the probability that $r$ has the structure $r'' = h(r')$ is $\frac{1}{2^n}$ since all $2^n$ possible outputs of $h(r')$ are equally likely. Thus for $n=160$ we have a probability of $\frac{1}{2^{160}}$ which is negligible.

  Question2: Can we reduce the $h(.)$ output size to 80-bit (which is not the standard hash function output size) and set $p$ as smaller prime number (e.g. 128-bit )and prove a random value can have the above structure with only negligible probability?

Sure, the same logic as above can be applied here as well, now with the case $n=80$ and a corresponding probability of $\frac{1}{2^{80}}$ which is still negligible.

Note that the size of $r'$ is not relevant to the probability of a random element having the structure $r'||h(r')$, the probability solely depends on the size of $h(r')$.


Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)? Alice is going to use some existing RSA scheme (employing industry-standard signature or/and encryption with proper padding), which she can't change, or influence beyond her choice of key. In this scheme, all public modulus $n$ are exactly $b$ bits with $b$ even (e.g. $b=4096$); and any odd public exponent $e$ with $3\le e<e_\mathtt{lim}$ is allowed, for some $e_\mathtt{lim}$ at least $n$ (this is common; e.g. PKCS#1v2.1 uses $e_\mathtt{lim}=n$).

Contrary to standard practice, Alice would like her RSA key to have a public exponent $e$ crafted to slow down use by other parties (say, she wants to better resist some denial of service attack starting with sending her an RSA-encrypted message); but she would like to keep her own actions fast when performing a computation normally involving her public key (that includes Alice checking a signature she just generated using the CRT, as customary to guard against the mother of many fault injection attacks).

Towards these goals, Alice can generate her key as follows:

she secretly chooses a random odd $f$ with $3\le f<2^{b/2}$;
she secretly chooses random primes $p$ and $q$ with $2^{(b-1)/2}<p<q<2^{b/2}$, $\mathtt{GCD}(p-1, f)=1$ and $\mathtt{GCD}(q-1, f)=1$;
she computes $n=p·q$;
she computes $e=f+(p-1)·(q-1)$;
she computes $d=f^{-1}\bmod{\mathtt{LCM}(p-1,q-1)}$, or/and $dP=f^{-1}\bmod{(p-1)}$, $dQ=f^{-1}\bmod{(q-1)}$, $qInv=q^{-1}\bmod p$.

Alice's public key is $(n, e)$, made public, and her private key is $(n, d, p, q, dP, dQ, qInv)$. These are usable as customary in RSA. In particular, the construction yields $2^{b-1}<e<n<2^b$ with $e$ and $n$ odd, and thus meets the conditions required for $(n, e)$ to be acceptable in the scheme.

For a user of Alice's private key other than Alice, computing $x^e\bmod n$ for arbitrary $x$ requires over $b$ modular multiplications (more like $3·b/2$ with basic binary exponentiation), rather than $17$ modular multiplications for the customary public exponent of $2^{16}+1$. Thus Alice's goal of making use of her public key slow is largely met.

Notice that $\forall x\in\mathbb Z$, $x^e\equiv x^f\pmod n$ (proof sketch: the equality holds $\pmod p$ using Fermat's little theorem; same $\pmod q$; thus the equality holds $\bmod(p·q)$ as well). Therefore, Alice can use $f$ instead of $e$ when she wants to perform the transformation $x\mapsto y=x^e\bmod n$. Because $f$ is at most $b/2$-bit when $e$ is $b$-bit, this gives Alice a performance advantage of about a factor of $2$.

Question is, does Alice's choice of key create a risk, compared to established practice? And how can we keep (or make) that safe, and maximize the cost of computing $x^e\bmod n$ directly, and Alice's advantage over that?

Update: In particular, how much can we safely reduce the interval for $f$ at step 1? Can we make the binary expression of $f$ sparse to further speed its use by Alice? Can we increase the cost of using the public $e$? How can we use freedom given by $e_\mathtt{lim}$ when that's more than $n$? Notice each of these could improve Alice's advantage.

Update: By using a CRT form of her public key $(n, f, p, q, fP, fQ, qInv)$ with $fP=f\bmod{(p-1)}$ and $fQ=f\bmod{(q-1)}$, Alice gains an extra advantage by a factor of about $2$ (and more should we increase the number of prime factors of $n$).

Update: As pointed in the first comment, Alice must keep $f$ secret as well as $d, p, q, dP, dQ, qInv$, since knowledge of $f$ combined with $e$ reveals $(p-1)·(q-1)=e-f$, wich combined with $n$ is known to allow efficient factorization of $n$. In particular, Alice should be wary of side channel attacks such as these when computing $x^f\bmod n$, which are not to fear when computing the same value as $x^e\bmod n$ (at least when $x$ is public).

Note: AFAIK this is new, and hereby put in the public domain.

I can't see any problems, if you use it as specified (with the performance advantage of a factor of 2).

If you start to narrow the interval too much, you're going to get into trouble.  For instance, one factoring method is to compute $c=b^e \pmod n$ for some known base $b$; then try to compute the discrete logarithm of $c$ to base $b$.  We know $c=b^f \pmod n$, so if $f$ comes from a small range, so we can use some algorithm for computing the discrete logarithm when the exponent is known to come from a small range (e.g., baby-step giant-step or Pollard's rho).  This will reveal $f$, if $f$ comes from too small of an interval. For instance, if you pick $f$ from the range $3 \le f \le 2^{80}$, these algorithms will be able to find $f$.  Once $f$ is known, $n$ can be factored, as $e-f$ reveals $(p-1)(q-1)$ which can be used to extract a factor of $n$.

Similarly, if you choose $f$ to have very low Hamming weight, I think you will again get into trouble.  The baby-step giant-step and Pollard's rho algorithms can be adopted to solve the discrete log in cases where the exponent is konwn to have low Hamming weight, so the same method can be used.

For these reasons, I don't think you're going to be able to get a very large performance advantage.

And, I have to say that I would not bet much of my own money on the security of this scheme.  I believe van Oorschot and Coppersmith have some results on factoring $n$ given partial knowledge of $d$ or $p$. The lesson I draw from those results is: when you start giving away partial information on RSA secrets, RSA can lose a lot of security.  I don't know if that applies to your scheme, but I would be reluctant to use it in a high-stakes situation, and I would be especially reluctant to narrow the interval from which $f$ is chosen.


Signing dynamic data on an embedded system I have built a GPS based on the AVR microcontroller. The GPS is used to log flight data for competitions. The log file is updated 10 times per second. What I'd like to do is to associate a signature with this file so that anyone can confirm that the file was written by the GPS.

This suggests that the GPS should have a private key of some sort internally, and that verification should occur through a public key. However, there are a couple of significant hardware limitations:

The AVR is an 8-bit processor running at 8 MHz. I can keep a running MD5 hash of the file, but there is not enough time between samples to calculate, e.g., an ECDSA signature.
The hardware does not know when it will shut down. When the user turns off the switch, it just shuts down. This means it is not possible to perform the hash/signature once just before shutdown. The signature would have to be updated every time a new row is added to the log file, i.e., 10 times per second.

Something like an HMAC would fit the processor limitations, but not the necessity of public verification. Is there some variant of an HMAC which can be computed using a private key and then verified using a public counterpart?

Thanks for your help!

Signature algorithms of the ECDSA family are amenable to precomputations. Indeed, when you want to sign message m with ECDSA, the process goes thus:

We work in a curve (or a subgroup of a curve) of order $n$ (a prime integer). A conventional generator $G$ is given (a fixed point of order $n$). Private key is $x$ (a non-zero integer modulo $n$) and public key is point $Q = xG$.
Generate (for each signature) a new random non-zero integer $k$ modulo $n$. The integer MUST be selected uniformly in the whole range (this is important).
Compute the point $kG$, extract its $X$ coordinate, and reduce it modulo $n$; this yields the first half of the signature, $r$.
Hash message $m$ and truncate/reduce the hash value into an integer modulo $n$ (let's call it $h$).
Compute the second half of the signature: $s = (h+xr)/k \pmod n$

The point here is that the most expensive part, which is the computation of $kG$, does not actually depend on the message that is to be signed. It can thus be done in advance, before the message $m$ is obtained. A precomputing setup would pre-generate a bunch of values $k$, with corresponding values $r$ and $1/k \pmod n$, thereby reducing the online part of the signature to a couple of modular multiplications and a modular addition. This, however, calls for the following comments:

The process above requires a random $k$, produced with a random generator of cryptographic quality. This is a tough thing to get in practice, especially on embedded systems. Since a failure to use good randomness may expose the private key itself (and such blunders have happened in practice), another mechanism for generating the $k$ value has been defined, called derandomization. In the case of ECDSA, this is described in RFC 6979. However, while this removes the need for a random source, it makes $k$ depend on the input message $m$. As such, it prevents precomputations.
ECDSA, as defined by the relevant standards, operate on "classic" curves, which are not necessarily the fastest curves around. You might want to investigate EdDSA, and especially Ed25519 (application of EdDSA to a specific 255-bit curve). This can be done, but may run into some extra issues:

EdDSA is specified as derandomized, so no precomputations. It so happens that the signature verifier cannot actually know whether the signer was derandomized or not, so you could "re-randomize" the algorithm, which is totally heretic from a cryptographic point of view, and thus possible but fraught with peril.
The actual signature computation uses a hash function invocation, which is defined to be SHA-512. SHA-512 is reasonably efficient... on big desktop and servers, where 64-bit registers are available. Your 8-bit AVR won't like it.

Precomputations can help you only if you have time to precompute. The typical use case for precomputations is paying a toll on a highway or bridge: the signing device on a car has very little time to compute the actual signature (transaction should be completed while the wireless device is in range of the detection apparatus, and that does not last because the car does not slow down), but minutes if not hours to prepare the next signature. In your case, you have a long and potentially unbounded stream of signatures to compute, so it is not obvious whether you have enough time to do all precomputations.

To give some figures, the current record for elliptic curve computations on 8-bit AVR processors is described in this paper; they compute a point multiplication in Curve25519 in about 14 millions of clock cycles. This is substantially higher than your budget (at 0.400 millions of cycles per signature).

Here are some ideas that may help (or not):

"Modern" curves such as Curve25519 are designed under the essential premiss that multiplications are fast. This is true for the CPU in desktop and server systems, and also smartphones. But not on 8-bit AVR. Therefore, they are not necessarily a good choice in your specific case.
I suppose that the value of your signatures is not that high. I mean, you worry about fakes, but a fake log will not yield billions of dollars to attackers. As such, you could probably tolerate a slightly lower level of security. A 160-bit or so curve will provide a security level of about $2^{80}$, which is beyond the current public records in curve breaking. This is technologically attainable, but at a tremendous expense (we are talking billions of dollars here), so it is unlikely to be done merely in order to make fake GPS log (I assume you are talking about drone racing or something similar).
Under these conditions, I would say that among known curves, the fastest one will probably K-163, described in FIPS 186-4. This curve has a special structure that allows faster computations, provided that you apply some weird maths (the Frobenius endomorphism). However, even with the full power of the Frobenius, I fear that it would still not fit the per-signature cost in 400k clock cycles.
The human user is human; he is not that fast. By that, I mean that while you cannot predict when the user will pull the switch, you can still instruct the said user that pulling the switch may lose, say, the last two seconds of GPS logs. Therefore, you could compute one signature every 2 seconds, on twenty lines of logs in one go, instead of doing ten signatures per second. I have just multiplied your CPU budget by 20! And now, ECDSA with K-163 may become a realistic solution.
You might want to consider plugging in a better CPU. In a GPS receiver, chances are that the radio part uses way more power than the CPU, so you could use a more beefy CPU. The ARM Cortex-M0+, clocked at 48 MHz, would draw at most a few milliwatts (including the power for some RAM), and can compute an Ed25519 signature in less than 200ms.

Another, completely different idea, would be to use Lamport's signature scheme. It uses only hash functions and can be very fast. Its main issue is that it is a one-time signature scheme: if you sign two distinct messages with the same private key, then you reveal the private key, and forgeries become easy. However, in your specific case, you could apply it in the following way:

Before a flight, the GPS system generates a new public/private key pair, and exports the public key.
During the flight, the system regularly computes a new signature over the entirety of the log file, and replaces the previous signature. Thus, it only keeps a single signature in its storage system. This uses the fact that the private key is revealed only through showing two signatures; signature values that are never shown are thus not a problem.
The private key is held in RAM only, so it disappears when the system shuts down.

To ease usage, you could envision an hybrid system:

The system has a "permanent" key pair, to use in ECDSA or Ed25519 or a similar system.
When it boots up, it generates a new Lamport public/private key pair.
The public key is signed with the ECDSA/Ed25519/whatever key; the Lamport public key and the signature are then stored along in the log file header.
The running Lamport signature is computed every second or so, as described above.
The Lamport private key disappears upon shutdown.

Combining all of the ideas above makes me think that what you are looking for is possible, but certainly not commonplace. You are in for a big delve in arcane cryptography, and we know, out of experience, that such things are hard, in particular because there is no test for security (you can test for functionality, but you cannot easily know whether what you produced is secure).

So, a fun project, but don't build a business on it.


Is there a point using GCM block chiper with Authenticated DH? I'm delivering shared secret with DH exchange, using a static key for signing and an ephemeral for session, so is there a point using GCM for encrypting the data, or is a simple CBC/CTR block cipher is enough?

Also, I'm not sure what's the point authenticating the encrypted data, since if it gets modified, it will produce garbage at decryption, or if adversary gains the key somehow they will be able to fake the authentication tag too.

Unless you are absolutely sure that you don't need to and that the cost is going to be significant then I would absolutely say you should use authenticated encryption.
One reason is bit-flipping attacks - flipping a few bits at the 'right' point in your encrypted message might lead well to a message that is legal (the classic example is if someone learns your message will be of the form ??<misc secret unknown format stuff>???  Send Bob ???<more unknown stuff>??? then they can xor the 'Alice' section with Bob$\oplus$Eve).

Another example that could well affect you would be a replay attack where an old message is sent again, and because you are not authenticating the messages the server wouldn't realise.  There's a nice reference somewhere to an old computer game that players managed to cheat by continuously replaying the 'Killed Beast' message, but I can't find it at the moment.

You might find this question relevant.


Can we give access to controlled functionality in Fully homomorphic encryption schemes? Homomorphic encryption schemes are PKE schemes with an additional special method Evaluate. Evaluate method takes input any function (as boolean circuit) and encrypted inputs of the function and evaluates the circuit. The results of such function are still encrypted under the public key PK.

Sometimes, it would be too wide of a scope to allow execution of any arbitrary function.

How can one limit FHE schemes to allow only fewer circuits?

This concept is called targeted malleability:

http://crypto.stanford.edu/~dabo/pubs/abstracts/reshom.html

The abstract and introduction of that paper give a good overview of the ideas. In brief, the goal is to ensure that a homomorphic evaluator can only produce a ciphertext by evaluating a function from an "approved" class of functions. It is trivial to achieve this by attaching to the ciphertext a noninteractive proof/argument that it was computed correctly, but this yields a ciphertext whose length is at least linear in the length of the chain of homomorphic operations performed. (This may be acceptable if only a small number of such "hops" are needed.)

The solutions given in the paper instead use succinct noninteractive arguments of correct computation relative to the previous ciphertext in the chain.  This keeps the ciphertext length from growing much, because only one proof is attached to the ciphertext. However, the argument system needs a stronger property of "extractability" (of the previous statement in the chain to be proved) to make this work.


Is there a cryptographic hash function that can be performed with pencil and paper? Imagine I'm signing up for the 99th new web site this month.
I somehow take my secret key (which I have written down on a card in my wallet) and the domain name of the site and feed them both into some algorithm (perhaps a HMAC?),
and type the resulting hash into the "password" field of the registration form.

Later, I'm at the library and I want to log in to that one particular site,
but I don't have my phone and the computers at the library are locked down so I can't install any new software,
so I want to reconstruct that password "by hand".

Is it reasonable to use Kerckhoffs's principle and assume that everyone knows exactly which hash algorithm I'm using, and assume every knows I use exactly the exactly the same hash algorithm and exactly the same secure key for web site all 99 web sites that I've signed up for this month?
It would be nice if somehow, even if the sysadmins for websites 1 through 98 all conspire together and share with each other the "password" I gave each one (and they know the algorithm I'm using), the hash is secure enough that finding the password for website 99 is harder than brute-forcing a random 8-character password.
It would be nice if somehow, even if all 99 sysadmins conspired together and shared the "password" I gave each one, the hash is secure enough the recovering my secret key is harder than brute-forcing a random 16-character password.
The amount of secret information I have to write down and put on a card in my wallet and keep secret should be shorter than simply making up a fresh new random 10 character password for each of 100 websites and adding the domain name and the new password to the card. (Perhaps 256 bits of information is reasonable? Perhaps encoded into 80 decimal digits or 55 lowercase letters or 20 Diceware words?).
I'm in a relatively private cubicle at the library -- I can write stuff on my pad of sticky notes, manipulate my deck of cards, perhaps do some calculations on a 5-function calculator, look up a passage from my copy of "The Good Soldier Schweik", that everyone knows I always carry with me, etc. But not run a computer program. (Let's assume I eat any sticky notes that might leak secret information). This should make it easier than " Are there cryptographic hash functions that can be computed using only paper and pen without leaking any information about the plaintext? " because I can write down secret information.

Is there any pencil-and-paper algorithm that meets these criteria?

I don't think doing this by hand is the right way to do this. Pencil and paper systems are unreliable because humans just aren't as good at being robots as, well, robots! Most of the work in computing a secure MAC is hugely monotonous and a single mistake, anywhere during the process, could completely destroy any security you thought you had.

If your library computer has web access, then it executes Javascript with very high probability. Javascript is enough to conquer this problem.

Just create a static HTML with some Javascript in it. You have two HTML input fields with a single button. When you click, it computes the $HMAC(site,password)$ using SHA-256 or something, then encode the result as printable characters.

There is the problem of key loggers etc, grabbing your master password but they could just as easily covertly film you as you carry out the computation by hand!

There's a limit to the countermeasures that be deployed when the machine is fundamentally untrusted. However, you can mitigate against key loggers by simply making the master password be entered, character by character, via a dropdown box.