What are linear and non-linear elements in cryptography? I was reading this answer, How secure is XOR for encryption, and it stated that XOR's aren't good for securing messages as they are linear in Nature. And therefore should be paired with some non-linear elements like Substitution box to provide strength to the encryption.

My question is, what are linear/Non-linear elements, in context of cryptography? And what are advantages and disadvantages of each over the other.

A mathematical function $f$ is linear if it is of the form $f(t) = c + g(t)$ where $c$ is a constant and $g$ has the property that $g(a + b) = g(a) + g(b)$.  (Strictly speaking, in math one usually considers only $g$ to be linear and $f$ to be merely affine, but we don't make that distinction here.)  We also say that a function $\phi(s, t)$ of two arguments is bilinear, or again just linear, if for each $s_0$ and $t_0$, the functions $t \mapsto \phi(s_0, t)$ and $s \mapsto \phi(s, t_0)$ are linear.

  Exercise. Prove that the function $(s, t) \mapsto s + t$ is bilinear.

If we're talking about real numbers, like 0, −3, 1/48, $\pi$, etc., linear functions are of the form $f(x) = mx + b$ for constants $m$ and $b$, which you may recognize as the equation of a (nonvertical) line.  But we don't have to talk about real numbers; we can consider integers too, or even the remainders of integers after dividing by 2 (‘modulo 2’), where $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, and $1 + 1 = 0$.  The linear functions in this case are still of the form $f(x) = mx + b$, but the only two possible values for $m$ and $b$ are 0 and 1, so there are only four such linear functions.

We can also do addition and multiplication of polynomials, or of matrices of higher dimensions.  Each space has its own notion of linear functions, defined in terms of that space's notion of addition.  Linear functions are easy to compute—and easy to invert, or at least partially invert: in spaces where we have a notion of division (like rational numbers), we can recover $x$ from $f(x)$ by $x = (f(x) - b)/m$; in other spaces, like matrices, we have easy algorithms like Gaussian elimination to solve linear systems.

Suppose you have a string of bits, say 10110 or 00111.  One way to interpret the bits is an integer, in this case 22 or 7 (in decimal).  Another way is to interpret the bits as a polynomial with coefficients modulo 2, in this case $x^4 + x^2 + x$ or $x^2 + x + 1$.  If we add these in their respective spaces and convert back to a string of bits, we get different answers:

\begin{gather}
  22 +_\mathbb Z 7 = 29 \longrightarrow \mathtt{11101} \\
  (x^4 + x^2 + x) +_2 (x^2 + x + 1) = x^4 + x + 1 \longrightarrow \mathtt{10011}.
\end{gather}

  Exercise. Why did the $x^2$ term disappear?

Here I have labeled the integer addition operation as $+_\mathbb Z$ and the polynomial modulo 2 addition operation as $+_2$.  We could also write both sides of the equation as a string of bits; when we use $+_\mathbb Z$ and $+_2$, we may get different answers, as strings of bits:

\begin{align}
  \mathtt{10110} +_\mathbb Z \mathtt{00111} &= \mathtt{11101} \\
  \mathtt{10110} +_2 \mathtt{00111} &= \mathtt{10001}.
\end{align}

  Exercise. Is there another name for $+_2$?

  Exercise. Find two bit strings $s$ and $t$ such that $s +_\mathbb Z t = s +_2 t$.

Although $+_\mathbb Z$ is linear (or, more precisely, bilinear) in integer addition, it is not linear in polynomial modulo 2 addition—in other words, although, e.g., $t \mapsto s_0 +_\mathbb Z t$ is linear over $+_\mathbb Z$ meaning it is of the form $t \mapsto c +_\mathbb Z g(t)$, specifically with $c = s_0$ and $g(t) = t$, this function is not of the form $c +_2 g(t)$ for any $c$ or $g$.  Conversely, $+_2$ is linear in polynomial modulo 2 addition but not in integer addition.

In other words, xor is linear in polynomial modulo 2 addition, but not in integer addition; conversely, integer $+$ is linear in integer addition, but not in polynomial modulo 2 addition.  When you combine the two—e.g., consider the function $(u, v, w) \mapsto (u +_\mathbb Z v) +_2 w$—the result is a function that is nonlinear in both spaces, which means it does not admit any neat algebraic simplification or inversion like $(f(x) - b)/m$ or Gaussian elimination.  This in turn means that cryptanalysis can't take advantage of neat algebraic simplification or inversion, and so may be much harder.

Xor is linear because its answers are predicted and they’re 4 possible outcomes of this. So this can be broken or breached by brute force of some other techniques.
On the other hand, non linear operation includes linear plus other s-boxes techniques which is based on some finite-field inverse and some shuffling.


Standard serialization format for libsodium-based messages Does anyone know of a standardized serialization format which can be (or already is) widely used for encrypted messages? For a variety of reasons (mostly complexity, age and poor support across a lot of languages) we don't want to use OpenPGP for this case.

The use case is fairly simple, we want to create "stateless" (from the server's perspective) authorization token across a wide variety of our web-based applications, without having to implement an OAUTH-handshake as users transition from application to application. The applications are written in a variety of languages, some .NET, some Java, some Node.js, and Python.

It seems a reasonable, modern solution to this problem is to use libsodium's crypto_secretbox_easy to authenticate a user and then encrypt a message of the form:

{identity: 'someuser@example.com', expires: '2015-02-27T09:45:35.886Z'}

...and send it to the client for cookie storage. Assuming secure configuration of keys in all the various applications, we could use the libsodium variants for each platform to authenticate a user based on this encrypted and authenticated token.

The problem, of course, is how to format the message? I need to transmit the nonce as well, but that isn't part of the output of crypto_secretbox_easy, and nothing I've found during research seems to indicate there is a standard serialized message format for use with libsodium. Lots of people are rolling their own.

So, is it safe to use a general cross-platform message serialization library such as MessagePack to transmit a message of the form:

{nonce_value: 0x44ec53c1235daa22d3e0322931ce2d2c47ece2a5ae46a00e,
secretbox_message: 0xa3ce9f0edb35a058eaf90d87f871ecdf6fb7f88ec547f377fdb27780716e1904ab8663dbce724d1bfcc7ee1f40108400}

I know enough about crypto to know "there be dragons" when inventing your own protocols, and assembling crypto primitives naively has repeatedly shown to be disaster. So if there is a standardized and secure way of doing this sort of encrypted and authenticated messaging (other than OpenPGP) I would of course like to use that. If there isn't a modern standard for this task, I ask:

do you think my proposed construction is secure?
are there any reasons that general structured serialization libraries are unsuitable for use in cryptographic protocols? Looking at various PGP, TLS, and PKCS specifications, it seems this wheel gets re-invented quite a lot, and I don't quite understand why.

Any serialization library that can efficiently encode binary data can be used, and MessagePack is an excellent choice for this purpose.


Is F' a pseudorandom function when F is composed with G, a pseudorandom generator? If $F$ is a pseudorandom function, is $F'$ also a pseudorandom function in the following:
$$
F'_k(x)=F_k(G(x)) \space \space \text,
$$
where $G$ is $a$ pseudorandom generator?

Also, does the other directions holds (i.e $F'_k(x)=G(F_k(x))$)?

Certainly yes.
Proof
A pseudorandom function must produce pseudorandom output for any given input. So, any seed value will provide a pseudorandom output. However, this might not work if the function has a limited input domain (list of possible inputs) causing incompatibility with the two functions. In your case, $F$ should be able to process the input provided by $G$, and vice-versa for the second case.
Proof of concept
Let $F$ be a hash function, say SHA-3, and $G$ be AES-CTR, Then:
Case 1, $F'_k(x)=F_k(G(x))$: AES-CTR would generate a pseudorandom sequence which would be hashed by SHA-3, and, needless to mention, cryptographic hash functions are supposed to produce strong pseudorandom output, regardless of what the input is.
Case 2, $F'_k(x)=G(F_k(x))$: The hash digest of $x$ produced by SHA-3 will be used as a seed for AES-CTR, and, once again, block ciphers are also meant to produce strong pseudorandom output regardless of the input.
Verdict
Both the implementations suggested in the Proof of Concept section explain how $F'$ acts as a pseudorandom function. It is important to know that the security and quality of pseudorandomness is highly dependent on the outer function, $F$ in case 1, and $G$ in case 2, as it's output is what determines the required. The underlying function will only work as an internal state generator, where the state could have been anything, not necessarily pseudorandom.
So, building a PRNG by chaining two different PRNGs (as you did in your post) will surely work out.


Academic breach revealed too late Do you know if is has already happened (since 1980), that someone (academic or not) has "broken" (even in a weak sense) some cryptographic assumption, but has chosen to not first publish and directly attack some security system of the physical world?

I'm really considering the cryptographic/algorithmic level, not a human mistake in which someone didn't use the appropriate standard according to the academic world.

ps: I'm not asking about exploits which are still unknown (it would be an absurd query)

In 2004, Xiaoyun Wang's team first publicly reported collisions in MD5, and in 2007, Marc Stevens, Arjen Lenstra, and Benne de Weger reported a chosen-prefix collision attack on MD5.

Around the same time, the governments of the United States and Israel developed the the Flame malware to sabotage Iran's nuclear program.  Part of the scheme involved forging a Microsoft code-signing certificate using MD5 so that they could sign malicious software without leaving a trail pointing back to themselves.

While studying Flame in 2012, Marc Stevens discovered that the creators of Flame had used an independently developed chosen-prefix attack on MD5 (paywall-free preprint).  We can presume it is independent because if the creators knew about the attack devised by Stevens' group, why would they bother to develop a different way to do the same thing?

Given the $12B market in exploits, obviously it has. Many, many times.  I don't have details of the originators of the exploits, but clearly they exist as the lucrative market is summarised in this Finding flaw in cryptographic protocol answer. You may be able to get to the underlying maths/electronics if you follow the above link(s) deeply enough. These are proper breaks/exploits that generate results, and not in any sense weak.  That's why corporations/agencies pay for them.

As for using "good" standards, well that only applies to simple stuff like not using electronic code book constructs, unless warranted.  Once you get in to the realm of iPhone 11's and the Signal protocol, there is no good standard as those are innovative designs in constant flux. And given the 2nd Law of Thermodynamics (entropy and causality), side channel attacks are impossible to nullify.

Of course it they didn't publish and used or banked the break secretly, we might never know.


RSA: Decrypting message with public key and private key I am trying to decrypt a message which its ciphertext in Hex A3 BB 05 00.
The original plain text is 8 bits and it is encrypted by a 32 bits RSA key.

I have successfully found the public key is $(e=947,n=2671079)$ and the private key is $(d=713604)$.

Then, I try to convert the Hex string to integer 00 05 BB A3 (Little Endian) $=375715$.

Finally, I calculate $C^d \mod n = 375715^{713604} \mod 2671079 = 544824$.

  Calculate in python: C**d % n

My problem:

1) what does $544824$ mean? Is it the original plain text or I need to further converting this number?

2) The plain text should be 8 bits, why the result I get is larger than 8 bits?

thanks!

Your ciphertext is A3 BB 05 00

In RSA, the ciphertext is always larger than the original data. In this case, the keys are 32 bits, which is 4 bytes, and A3 BB 05 00 is four bytes


How many RSA keys before a collision? I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a high chance of collision? I believe GUID would suffer from that problem as many bits are reversed for date/time (and GUID version) and isn't meant to be used in that way.

Would RSA suffer from collisions if many keys were to be generated in the same moment? Is the amount of possible keys known? I know RSA is based on prime numbers and small numbers are to be rejected. I’m sure values above a certain amount of digits/bits are rejected because software may not be able to support those large values?

So: How many RSA keys before a collision? And if you would try to make many at the same time, would that give you a high chance of collision?

Collisions of RSA keys should never happen for realistic key sizes and good random number generators.

Assume a 1024 bit RSA key; the primes from which it has been derived are about 512 bit. If we assume every 500ths 512 bit number is a prime, and we assume the most significant bit of the 512 bit number is set, we still get about $2^{500}$ or $10^{150}$ different primes. If you apply the birthday problem to these numbers then you would expect RSA keys to have a prime in common about every $2^{250}$ or $10^{75}$ key generations. Identical RSA keys are even more rare.

This is large enough to never happen in practice. Unfortunately bad PRNGs which cause collisions do happen in practice, but you can't translate this into probabilities.

I've neglected a few small factors within the calculations that should not have a significant impact on the outcome.

GUID collisions are a bit more likely. V4 GUIDs are random, except for 6 reserved bits. So there are $2^{122}$ different V4 GUIDs. It's possible to get collisions if you create huge, but achievable amounts of GUIDs if you have a huge system dedicated to creating random GUIDs. The creation of a collision is  very unlikely to happen in a normally sized system, where GUIDs are only a part of the overall security system.

It shouldn't matter in theory that you create many RSA key pairs at the same time, as long as you seed your PRNG with enough entropy. But if you seed badly - so that there isn't much entropy in addition to the system time - then random extraction at the same moment can be a problem. One of the most common randomness related questions in C# is why two instances of System.Random created in quick succession return the same sequence. If the random sequences used for RSA key pair creation are the same, then the RSA key pair will be identical as well.

Now the standard key size for RSA is recommended of 2048 bits. This is large enough to never having a collision in practice, where brute force is 2^{2048}. Even if we consider some attacks that allow to break it with half the key size or in birthday attack, this number is quite secure. However, larger the key size, more overhead and lower efficiency.


Do ciphertexts leak information about their algorithmic creators? If an adversary holds thousands of encrypted files that were encrypted with the same cipher, can he determine which cipher method had been used on the files?
Assume that the adversary has no prior knowledge about the encryption environment.

Details:
Let's say I have a encryption program that allows me to select 1 out of 5 well established and well implemented encryption algorithms. I use that program to encrypt thousands of file, using always the same block cipher, while following proper cryptographic procedures (e.g. use different passwords every n files encrypted). The files are stored off-site, and an adversary gets a hold of the files. I wonder if by selecting a less common algorithm, e.g. Serpent, I would increase the workload of the adversary by factor of 5, or encryption algorithms do leak some information, some recurring properties, that will help the adversary to identify the encryption method I had used?

A good block cipher should be indistinguishable from a random permutation (otherwise it is considered broken). A consequence of this is that two good block ciphers are indistinguishable from each other (with at most a doubling of the adversary's advantage).

In your scenario, it means that finding a way to succeed in learning which algorithm has been used implies finding a cryptanalytic attack on at least one of the algorithms you are considering.

[Note that this answer disregard any implementation flaw in your program that would leak the algorithm being used.]

Yes, they do. For example, suppose all of the files where a multiple of 8 or 16 bytes. That would be good evidence of a block cipher. Or, suppose only the characters A-Z appear in the encrypted file. That could indicate that it's a cipher like Enigma.

You can rarely say for certain, but you can often infer information. This isn't a great defense, though. To try the top 40 ciphers when cracking your files slows down an attacker, but only as much as if you had one extra character in your password.

And, of course, there are alternate ways of inferring what cipher is used. For example, if someone connects over the internet on port 22, they are probably using SSH. Further, they are probably using the latest version with default settings. Going back to filesystems, there are programs which can identify Truecrypt containers fairly accurately.


What is the difference between OTR and Signal protocols? The Signal Protocol is a relatively new secure messaging protocol that was recently implemented in Signal, WhatsApp, and several other messenging apps.  According to Wikipedia, the Signal protocol is an evolution of the OTR protocol (https://otr.cypherpunks.ca/otr-wpes.pdf).

One of the major new features of Signal is that it allows for asynchronous messaging (i.e. both participants need not be online at the same time).

What are the other important differences between these protocols? Are there any instances in which OTR would be better suited than Signal?

Check out the blog post by Whisper Systems regarding the triple ratchet of OTR verses the double ratchet of Signal. Also, a prior article about synchronous versus asynchronous messaging is worth the read. Both of those should answer all of your questions.


Has SHA256 been broken by Treadwell Stanton DuPont? In a recent press release issued by Treadwell Stanton DuPont, the claim is made that their research laboratories have successfully broken all 64 rounds of the SHA256 hashing algorithm. They further claim that they achieved this milestone a year ago (late 2018).

  "While we have successfully broken all 64 rounds of pre-image
  resistance," said Seiijiro Takamoto, Treadwell Stanton DuPont's
  director of newly formed Hardware Engineering Division, "it is not our
  intention to bring down Bitcoin, break SSL/TLS security or crack any
  financial sector security whatsoever."

How credible is this claim in the wider cryptographic community?

[Update, 2019-09-12: Upon being exposed, and/or after taking advantage of market manipulation by their fraudulent announcements, the scam artists of Treadwell Stanton DuPont have retracted their claim, with more meaningless waffling technobabble about ‘laboratory equipment flaws’ and ‘ambiguous results’—yet they are still selling the same snake oil!  I leave the commentary below as a record of their fraud, including magic market prediction oracles they continue to hawk as well.]

[Update, 2019-09-18: Now the scam artists of Treadwell Stanton DuPont are just straight up asking for donations, perhaps because the world pointed out they don't actually have anything to sell but they still want to take your money and haven't found a productive way to contribute to society in exchange for it.]

  How credible is this claim in the wider cryptographic community?

It is balderdash by scam artists trying to bamboozle people into buying fintech snake oil, using meaningless technobabble (plus quantum!), a virtual office address on Wall Street, and a slick-looking web site with sleek gadget photos and impossible claims about market prediction.

There is no merit to this claim.  If they actually had this capacity, they could easily demonstrate it by showing a SHA-256 collision, or a message whose SHA-256 hash is all bits zero.  Since they are running an elaborate fraud, rather than doing cryptography, obviously they cannot do this.  But for fun, and to make an indelible record on the web for the chumps who at least have the good sense to search the company's name, let's take a look at these scam artists.

From the press release, archived in case anyone tries to memory-hole it to evade prosecution for fraud.

  "While we have successfully broken all 64 rounds of pre-image resistance," said Seiijiro Takamoto, Treadwell Stanton DuPont's director of newly formed Hardware Engineering Division, "it is not our intention to bring down Bitcoin, break SSL/TLS security or crack any financial sector security whatsoever."

Seiijiro Takamoto does not appear to exist on the web outside the fraudulent press release issued by ‘Treadwell Stanton DuPont’.

  Up to now, it was thought impossible to use the output of the hash function to reconstruct its given input.

They don't seem to be clear on what a preimage attack does.  (If the input is longer than the output, what a preimage attack finds is almost certainly not the original input but another one with the same output.)

  In accordance with its disclosure policy, Treadwell Stanton DuPont won't be saying exactly how they did it — because once the proof-of-concept is out, anyone with enough computing power will be able to produce a SHA-256 collision, rendering the algorithm both insecure and obsolete.

They can't keep their story straight about whether it's a preimage attack or a collision attack.

From their web site, archived:

  While the exploit won’t be detailed here, it does take quite some computing power to achieve, overlapping into the quantum computing realm. So much, in fact, that combinatorial optimization is used, along with a fully connected/coupled 32,768-bit scale, 256-bit gradation solution space, which translates to a maximum of 1.158x1077 gradations of large-scale, precision parallel processing.

wat

  Remember: this is not brute force.

False.  This is a brute force assault on hapless victims by a barrage of technobabble.

  It is not our intention to bring down Bitcoin, which is why only 25 PHAEDRA A3497 and 25 PHAEDRA A3487 Compute Nodes will ever be constructed. Even though preliminary design, manufacturing specification and initial construction work has already begun, it will likely be 12 months before the first compute nodes are delivered to clients, worldwide.

The fraudsters are creating the illusion of scarcity to scare chumps into giving them money as soon as possible, and setting a deadline that gives them plenty of time to walk off with the money and find another scam.

  PHAEDRA A3497 will start shipping around mid-October 2020 at a rate of one per week. PHAEDRA A3487 will follow suit starting around mid-November 2020. Shipped on a first come, first served basis (S&H not included), if you have secured a place amongst any of the two lists (10 BTC and 6 BTC respectively), you can still climb to a higher rank by submitting or resubmitting an accumulative higher bid.

It's first-come-first-served, except if you pay more you can skip the queue!  But you have to pay in BTC, it seems.  I'm sure this is for principled reasons about evil central payment processors like ‘Visa’ who could be capriciously subverted by the judicial overreach of a court order about fraud, and certainly not because BTC transactions are irreversible.

  Timeline:

  Founding.  Treadwell Stanton DuPont is created to research and develop stock market prediction algorithms using artificial intelligence neural networks.

Curious that they waited until 2017 to register their domain name, nine years after their scam was founded.

Their main web page, amazingly, manages to be worse:

  There's only one proven method to beat the stock market: accurate, precise and timely world-class stocks and securities forecasting. It's like having an oracle at your beck and call. Like clockwork, know what's going to happen beforehand, every single time and take the guesswork —and risk— out of wise stock market investing.

In principle there could be a cryptanalytic attack on SHA-256, but the market will be deterministically predictable only when birds like me hang out with airborne pigs.

Here's another product with their name on it, the NEBULA6 SSE Stock and Securities Forecasting Neural Net platform, sold—as a 100 USD brochure—on eBay:

  If you're a sophisticated investor, hear this: Even your initial investment appreciates over time! Treadwell Stanton DuPont accounts are scarce and highly sought-after, and only a few dozens are available (it's free to register). Their value will SKYROCKET in the next, upcoming months, with many standing in-line for a chance to grab an account. ABSOLUTELY NOTHING TO LOOSE! This is a NO-RISK, ZERO LOSS, FAIL-SAFE, FOOL-PROOF investment! EASY TO USE: Even a total newbie who knows next to nothing of the stock market can get up and running in LESS THAN 15 minutes! TSD does not sell securities - they offer extremely accurate stock forecast charts with a degree of precision previously unheard-of, that has until now been the domain of some of the biggest and most established financial players (aka large investment banks).

I'm ready to line up outside their virtual office at 30 Wall Street which is so exclusive anyone on the web can rent it and make my millions!

Maybe they broke into the cryptobabble fintech space because the sketchball eBay fintech predictimacator market was too smart and got wise to them too fast.

Well, I'm not quite buying it. Just because we don't want our bitcoin investment going up in smoke doesn't mean we have to hide our heads in the dirt and pretend it's not happening. Am I the only one noticing strange details in their retraction? "We are being forced...", "...all sectors can still sleep quietly tonight", "specially appointed cryptographers and observers". Anyone notice the upper right image too? Bitcoin chart tanking just to recover with the judge gravel? Center image with the eye of providence and the dollar? Really?


RSA-4096 vs AES-256 for secure chat application? Which of these two methods suits better the implementation of a secure chat application? In this context, chat will be limited up to 150 letters for one message.
I would prefer RSA because what I know RSA is really secure if it is used for small text and also if I will use groups it is easy in RSA because of public key distribution. Specially for chat application where user can write very small letters message I don't know if AES will be good for security.
AES is better in performance specially if I will compare 256 bit vs 4096 bit. RSA will be slower for encrypt and decrypt. But my goal is to have strong secure chat and not super fast chat.
What would be the more apt method?
I will use this chat only for sending message, e.g. no attachments, etc.

RSA and AES do not oppose, and often are rightly used together in hybrid encryption. RSA can do things that AES can not, like allowing encryption to designated recipients, or allowing anyone to check that a message is not altered or from a different person than is apparent. Using AES or other form of symmetric encryption is a must when encrypting more than few hundred characters.

To choose a cryptosystem, you must first define your goals. Secure chat is not nearly precise enough. Confidentiality? Integrity? Proof of origin? Central registry of participants? How is registration and loss of keys handled?

Disclaimer:  The below answer is to the question-as-asked, rather than seeking to address the use scenario in the question.
Double crypt
You want to double-crypt; use AES or RSA, then the other.  AES is super-fast on modern computers, so using both is basically as fast as RSA alone.  So if you're not confident about either one, you may as well use both.

Encrypt your messages using RSA, then AES.

Decrypt your mesages using AES, then RSA.

Or, you can flip the order:

Encrypt your messages using AES, then RSA.

Decrypt your mesages using RSA, then AES.

RSA's way too slow for most uses, so this isn't a scheme most programmers would consider without a good reason.  Plus, there's a lot that you're not doing (e.g. message authentication, protecting against replay attacks, inserting randomness into the messages), so it's probably open to some pretty easy attacks despite both RSA and AES being pretty strong individually, and even moreso together.
But, for the question as you've asked it, it's the way to go.


When using DES, how large would the key space be if we only use letters as characters? Would it be safe? Or is it susceptible to brute force attacks or something else?

A DES key is 56 bits. If we assume letters are ASCII encoded and take 8 bits each this means a DES key of only letters would be 7 letters long. Given that there are 26 letters in the roman alphabet we would have $26^7 \approx 2^{33}$ possible keys, or if we allow uppercase and lowercase, $52^7 \approx 2^{40}$ possible keys. Both keyspaces can quickly be enumerated with modern hardware and can easily be brute forced.

If the intention is to stuff as many letters into a 56 bit DES key as possible, then you can get 11 (and a bit) in if you ignore case. You can decode the ASCII values to reduce the bits necessary to represent the characters.  Then 56/log(2;26) = 11.9.

So your key space would be 26^11 or 51.7 bits. That's almost full strength DES, but still  low for today's attack hardware. And of course DES is deprecated.


How to sign with RSA safely? what should I do to make my RSA signatures secure? If "plaintext RSA" is not secure, is there some sort of "RSA on steroids" I am not aware of? Could anybody tell me what is it?

I read a Wikipedia article "Digital signature". In the "History" chapter we can see:

  ...Soon afterwards, Ronald Rivest, Adi Shamir, and Len Adleman
  invented the RSA algorithm, which could be used to produce primitive
  digital signatures (although only as a proof-of-concept – "plain"
  RSA signatures are not secure

I searched for "rsa signature is not secure" but didn't find anything legible. Does anybody know why are RSA signatures are not secure and how can I make it secure by not doing "plain" signatures? Are there any tricks? The thing is that recently I implemented RSA in my code for my project and was so excited to see that I can sign and verify things with RSA...

The main modern standard RSA-based signature scheme is RSASSA-PSS in PKCS#1 v2, also standardized as IETF RFC 8017 (v2.2, obsoletes v2.1 in RFC 3447).  This is a variant of PSS proposed and analyzed by Bellare and Rogaway in 1996.

Beware: RSASSA-PSS as standardized by RSA, Inc., in the early 2000s, around the same time as Dual_EC_DRBG,* is vulnerable to collisions in the underlying hash function by virtue of using $H(r \mathbin\Vert H(m))$, instead of $H(r \mathbin\Vert m)$, which would have required of $H$ the much more modest security property (enhanced) target collision resistance.  This vulnerability to collisions led to a technique for practical HTTPS certificate forgery by academics, and to a different technique for certificate forgery used in an international incident of industrial sabotage by the United States and Israel against Iran.

If you need to get code running right now and for some reason you need to use RSA, that's the practical answer.  If you need to get code running right now but you don't actually need to use RSA, use Ed25519 instead—except for verification speed, it is an all-around faster, safer, and compacter signature scheme.

If you are studying existing code or an existing protocol that was not designed by a competent cryptographer, and you are wondering whether it uses a state-of-the-art signature scheme, you should expect it to use either RSASSA-PSS or PKCS#1 v1.5 signature.  If it doesn't, your eyebrows should be raised and whoever designed it has some justifyin' to do.

If you are intellectually absorbed by the wonders of the world of cryptography, or if like me you're a bone-eating vulture who likes blathering at strangers on the internet about things you've learned, then you should also know about full-domain hash, which was discarded essentially for political reasons among cryptographers but is easy to implement and instantiate with modern XOFs like SHAKE256, and Rabin–Williams signatures, which are more efficient with a tighter security reduction.  But make sure you know what you're trying to achieve before you go down that rabbit hole!

* I have no evidence to support a connection here, but coincidences like these are remarkably good at playing evidence in games of charades at parties.

When talking about "plain" RSA, it is referencing standard RSA without any sort of random padding. https://en.m.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding talks about this OAEP type of RSA. Problems with the plain format include that it is malleable and deterministic. OAEP solves these problems.


How to verify the claim of entropy available made by Linux 4.5? The Linux kernel has an entropy source and it estimates its amount of bits in the device /proc/sys/kernel/random/entropy_avail.  How can I verify that this number makes sense?  I did the following experiment.  The system in question is:
# uname -rvmpio
4.15.0-1050-aws #52-Ubuntu SMP Thu Sep 12 19:56:00 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

The following program prints the number of bytes of information available in each second as claimed by the kernel.
$ while true; do cat /proc/sys/kernel/random/entropy_avail; sleep 1; done | awk ' { t += 1; s += $0; print "t =",t,"sum =",s/8, "avg =", s/t/8, "now =",$0/8 }'
t = 1 sum = 86.375 avg = 86.375 now = 86.375
t = 2 sum = 174.625 avg = 87.3125 now = 88.25
t = 3 sum = 175.875 avg = 58.625 now = 1.25
t = 4 sum = 179.75 avg = 44.9375 now = 3.875
t = 5 sum = 186 avg = 37.2 now = 6.25
t = 6 sum = 186.875 avg = 31.1458 now = 0.875
[...]

The following program consumes /dev/random as much as possible and estimates how many bytes of information is practically available at each second.
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>

int main() {
  int r, bs; char b[512];
  unsigned int t = 0, n, sum = 0;
  fcntl(0, F_SETFL, fcntl(0, F_GETFL) | O_NONBLOCK);
  while (1) {
    n = 0;
    while ( (bs = read(0, b, 512)) != -1) n += bs;
    t += 1; sum += n;
    printf("t = %3d, sum = %3d, avg = %.4f :: just read %d bytes\n",
           t, sum, (float) sum/t, n);
    sleep(1);
  }
}

Here's how to compile and run it:
$ make p
cc     p.c   -o p
$ ./p < /dev/random
t =   1, sum =  20, avg = 20.0000 :: just read 20 bytes
t =   2, sum =  20, avg = 10.0000 :: just read 0 bytes
t =   3, sum =  20, avg = 6.6667 :: just read 0 bytes
t =   4, sum =  26, avg = 6.5000 :: just read 6 bytes
t =   5, sum =  26, avg = 5.2000 :: just read 0 bytes
t =   6, sum =  26, avg = 4.3333 :: just read 0 bytes
t =   7, sum =  26, avg = 3.7143 :: just read 0 bytes
[...]

Keeping the file system in high activity (while true; do find /; done), we get a certain number of bits being produced at regular intervals.  Running p first to keep entropy production being consumed as much as possible and then checking out the estimate by the kernel, it seems these two numbers do not quite converge, but they are roughly close.  After 100 iterations, I get the following values:
$ while true; do cat /proc/sys/kernel/random/entropy_avail; sleep 1; done | awk ' { t += 1; s += $0; print "t =",t,"sum =",s/8, "avg =", s/t/8, "now =",$0/8 }'
[...]
t = 100 sum = 1534.12 avg = 15.3413 now = 7.625
t = 101 sum = 1537.88 avg = 15.2265 now = 3.75
^C

$ ./p < /dev/random
[...]
t = 100, sum = 2002, avg = 20.0200 :: just read 0 bytes
t = 101, sum = 2014, avg = 19.9406 :: just read 12 bytes
^C

It seems therefore that Linux 4.5 underestimates its amount of entropy --- assuming I'm the only consumer.  This assumption is probably false, but perhaps I am not too far from the truth.  My verification finds about 5 bytes over the estimate of the kernel.

You can't, and you're not the only consumer. The operating system rips you off. It uses true randomness to prevent attacks by shoving code into random places. And randomly sequencing it's network traffic. But here's the thing...

“We have to remember that what we observe is not nature in itself but nature exposed to our method of questioning.”

-Werner Heisenberg
and that's compounded with the concept of the observer effect.
Essentially what the kernel does is quantize various external events via a made up second order differential algorithm. There's a write up in Documentation and Analysis
of the Linux Random Number
Generator but essentially it comes down to temporal quantization of hardware events as :-

And so,

It seems therefore that Linux 4.5 underestimates its amount of entropy

Yes.  That's the conclusion of all of the academic works I've seen on /dev/random. It's essentially the least signification digit of system time when something happens. But, the problem is that it shouldn't take 160 PDF pages to convince us of randomness. My concept of Open Entropy dictates that it should be screaming right up in your face without funky science.
With delicacy, what's your real question?

Nothing in this post relates to Micro$oft operating systems.

If this is important to you, build your own entropy source. It's not difficult considering the 2nd law of thermodynamics. Get a diode.

There's a dangerous and hugely misunderstood  meme out there that suggests /dev/random = /dev/urandom without appreciating the role of time. $(\epsilon, \tau)$ and the left over hash lemma  is everything.


Cryptography system that limits the length of the encypted message I have two devices which communicate via sms.

This communication should now be encrypted.

The devices can only send messages with the lenght of 160 characters.

So i am looking for an encryption system which can limit the length of the encypted message to 160.

Is there such a cryptography system?
Which system that meets this requirement is the safest?

As encryption scheme that could only encrypt fix length message is a important essence in cryptography, e.g. one-time pad.  Block cipher is a better example, e.g. AES is a popular block cipher whose block size is 128 bits.  While given such block cipher who could only encrypt 128-bit string, you can construct encryption scheme that encrypt arbitrary length string.

The security of the encryption scheme is not determined by the length of message but by the length of the key.  For example, AES has variant using 128-bit, 192-bit, 256-bit key.  AES-256, who use 256-bit key, is considered to be safer.

Finally, for ultimate security, you should use one-time pad.  One-time pad is information-theoretically secure which means the most powerful adversary can not break the cipher.  The disadvantage is the key could be only used once.  You could store multiple keys in your devices.  10MB space could store more than 60000 pre-shared keys, which sustain 60000 secure SMS message.


What are the differences between a digital signature, a MAC and a hash? A message may be accompanied with a digital signature, a MAC or a message hash, as a proof of some kind.

Which assurances does each primitive provide to the recipient?

What kind of keys are needed?

These types of cryptographic primitive can be distinguished by the security goals they fulfill (in the simple protocol of "appending to a message"):

Integrity: Can the recipient be confident that the message has not been accidentally modified?
Authentication: Can the recipient be confident that the message originates from the sender?
Non-repudiation: If the recipient passes the message and the proof to a third party, can the third party be confident that the message originated from the sender? (Please note that I am talking about non-repudiation in the cryptographic sense, not in the legal sense.)

Also important is this question:

Keys: Does the primitive require a shared secret key, or public-private keypairs?

I think the short answer is best explained with a table:

Cryptographic primitive | Hash |    MAC    | Digital
Security Goal           |      |           | signature
------------------------+------+-----------+-------------
Integrity               |  Yes |    Yes    |   Yes
Authentication          |  No  |    Yes    |   Yes
Non-repudiation         |  No  |    No     |   Yes
------------------------+------+-----------+-------------
Kind of keys            | none | symmetric | asymmetric
                        |      |    keys   |    keys

Please remember that authentication without confidence in the keys used is useless. For digital signatures, a recipient must be confident that the verification key actually belongs to the sender. For MACs, a recipient must be confident that the shared symmetric key has only been shared with the sender.

The longer answer:

A (unkeyed) hash of the message, if appended to the message itself, only protects against accidental changes to the message (or the hash itself), as an attacker who modifies the message can simply calculate a new hash and use it instead of the original one. So this only gives integrity.

If the hash is transmitted over a different, protected channel, it can also protect the message against modifications. This is sometimes be used with hashes of very big files (like ISO-images), where the hash itself is delivered over HTTPS, while the big file can be transmitted over an insecure channel.

A message authentication code (MAC) (sometimes also known as keyed hash) protects against message forgery by anyone who doesn't know the secret key (shared by sender and receiver).

This means that the receiver can forge any message – thus we have both integrity and authentication (as long as the receiver doesn't have a split personality), but not non-repudiation.

Also an attacker could replay earlier messages authenticated with the same key, so a protocol should take measures against this (e.g. by including message numbers or timestamps). (Also, in case of a two-sided conversation, make sure that either both sides have different keys, or by another way make sure that messages from one side can't sent back by an attacker to this side.)

MACs can be created from unkeyed hashes (e.g. with the HMAC construction), or created directly as MAC algorithms.

A (digital) signature is created with a private key, and verified with the corresponding public key of an asymmetric key-pair. Only the holder of the private key can create this signature, and normally anyone knowing the public key can verify it. Digital signatures don't prevent the replay attack mentioned previously.

There is the special case of designated verifier signature, which only ones with knowledge of another key can verify, but this is not normally meant when saying "signature".

So this provides all of integrity, authentication, and non-repudiation.

Most signature schemes actually are implemented with the help of a hash function. Also, they are usually slower than MACs, and as such used normally only when there is not yet a shared secret, or the non-repudiation property is important.

Hash = A result of a mathmatical function that is difficult to reverse engineer.
The result of applying hash to a text is a long code.
Examples of hashes: MD5, SHA1.
The length of MD5 code is 128 bits, the length of SHA1 code is 160 bits.
With a hash: You cannot revert back to the original message. But the same message will always give the same hash. So if you receive a message along with a hash. You an always calculate your own hash. If the 2 hashes match it means the message is the original one, if not, the message has been tampered with.
The important thing about a hash is that a minor change to the message makes a huge difference to the hash code.
This means that a hash assures the integrity of the message.
Encryption (you didn't ask but it's important in the context) = You replace the text of a message in a way that is impossible or at least very difficult to decrypt, unless you have the key. If you combine the key with the encrypted message you get the original message.
This means that an encryption assures the secrecy of a message.
There are 2 types of encryption: symmetric and assymentric.
The symmetric is faster but less secure. It uses only 1 key for encryption and decryption. Both the sender and the receiver need to know the key and keep it a secret.
The risky part in the symmetric encryption is sending the key from one to another, because there is only one key and if compromised the whole conversation is compromised.
Examples: AES, DES.
The assymentric is slower but more secure. It uses 4 keys, each user has 2 keys, one for encryption and one for decryption, these 2 keys are mathmatically linked. The encryption key is the public key while the decryption key is the private key. A public key can only be decrypted by it's matching private key.
The public key, as the name suggests, is not a secret, the owner of the pairs of keys can post his public key on his website or whatever for anyone to pick, and in fact he has to in order to receive encrypted messages that can only be decrypted with his private key. It's like an address or mailbox. The private key, as the name suggests, must be kept a secret. If the owner of the pairs of keys has his private key compromised, then anyone can know what messages he received. Best thing to do in that case is generate a new pair of keys.
To communicate with assymentric encryption, exchange public keys. Unlike symmetric encryption, you can do this in the open, nobody can read your messages if he only knows your public keys.

If you want to send a message, use the public key of the other person to encrypt the message and send it to them, only they will be able to unlock the message with their private key and read it.
If you are to receive a message, the other person must have used your public key to encrypt your message, that means only your private key can decrypt the message.

Examples: RSA, DSA.
Of course, most of the time this is done automatically by e-mails or other forms of messaging. You may have communicated with assymentric or symmetric encryption already without manually encrypting and decrypting a message.
Now, in digital signature the opposite is done. You don't encrypt with the other person's public key but with your own private key. Because of this, anyone can use your public key that is out in the open to decrypt that message. How is this a signature? Because only you had access to your private key, which means that if decrypted only you could have sent that message.
This doesn't only create authenticity, but also integrity of the message and non-repudiation. Why as latter 2 as well?
Because what the digital signature actually encrypts with the private key is a hash of the whole message that you are sending.

If your message is: "Hello there, General Grievous!" a hash is used for all this text that generates a code, that code is then encrypted with your own private key.
The one who receives your message, uses your own public key to decrypt the signature, then he gets a code. He applies the same hash algorithm (for example MD5 pe SHA1) that you used to the whole message, you should mention what hash algorithm you used in the message, and if the hash result he got matches the code/hash result that he got after decrypting your digital signature with your public key, it means not only that the message was sent by you, since you are the one who owns your private key that encrypted the digital signature, but also that the message he received is the original one you meant to send, since its hash matches the hash in the signature. Because of the signature, you cannot deny the authenticity of the message and of yourself.

But how can you make sure that the public key you send in the open cannot be tempered with, or have someone make a public key of their own and claim it's your key? That way they can decrypt the messages that are meant to you, and you can't. That is where digital certificates come in. Digital certificates make sure that the public key posted in your name is indeed your public key.
Digital certificates include information about the public key, information about the identity of its owner called the subject and the digital signature of an entity that has verified the certificate's contents, a 3rd party called the issuer. If the signature is valid, and the software examining the certificate trusts the issuer, then it can use that public key to communicate securely with the digital certificate's subject.
Why can't you just make a simple hash to guarantee the integrity of the message? Because an attacker can take your message, create a new one, and then make a new hash then send them to the receiver. The hashes will match and there's no way the receiver can tell whether he got that message from your or an attacker. Where as in the case of digital signature, the attacker doesn't have your private key to go that extra mile of asymmetric key encryption. He can encrypt it with his own private key, but then the receiver won't be able to decrypt it with your public key and will realise that signature is not from you.
But what if you want to ensure the integrity of the message but not necessary the authorship of the message and you just want the messages to work faster? You're not at work or in a public institution, you talk to a friend and none of you cares about the legal bindings of making sure the message is from each other. That's where HMAC comes in, unlike digital signature, the HMAC encrypts the hash of the message with a symmetric key.
Being encrypted with a symmetric key, the authorship of the message cannot be tracked back to you, because you're not the only one who has access to that symmetric key. The receiver also has the same key and he could have made that message himself. Of course, they are the only 2 people that have access to the symmetric key, so unless one of them compromised the key, the message that you received, if you know that you're not the one who wrote it, you can be sure that it came from the other person who has the symmetric key.
The H in HMAC stands for hash and the MAC stands for message authentication code, meaning a code that guarantees data integrity as well and authenticity, by allowing the viewers who posses the secret key to detect any changes to the message content. A MAC usually has 3 parts: a key generation algorithm, a signing algorithm and a verifying algorithm.
In short:
Digital Signature = Hash of the message is encrypted with the private key of the sender.
HMAC = Hash of the message is encrypted with the symmetric key.


Using ECDSA keys for encryption I know that ECDSA is used for signature only, but I wonder if I can use the public/private Elliptic Curve keys for encryption too.

I have ECDSA SSH public keys and I wonder if I can use them to encrypt data that only the matching machine could decrypt, writing the proper software.

Pointers welcomed.

Of course you can use Elliptic Curve cryptography to do public key encryption, that is, a method with a public key and a private key; anyone with the public key can encrypt, but only someone with the private key can decrypt.

One way would be to use the Integrated Encryption System.  It's does most everything for you (allowing the encryption of arbitrary sized plaintext efficiently, and throws in an integrity check as well).

However, in your case, I do see two potential pitfalls:

If all you got is some software that verifies an ECDSA signature, I don't know how that could be used to generate ECIES ciphertexts - or any other type of ciphertext.  Something that verifies a signature may only produce one bit of output ("it verified" or "it didn't"); it does not need to export any of its internal computations.  On the other hand, if you do have something that does a 'point multiplication' - and you don't mind putting together everything else ECIES needs to run - this may not be an issue for you.
I also wouldn't recommend you use their existing ECDSA keys with that scheme; it doesn't look like it should cause any weaknesses. I  mean that I don't believe that an attacker could send them a 'ciphertext' that, if they decrypt it and reveal the plaintext, that it would enable the attacker to generate an ECDSA forgery; I don't believe that someone could ask for a specific message to be signed, and use that signature to decrypt an ECIES-encrypted message); it however still makes me nervous.  Good crypto hygiene says to use a key for only one purpose (unless there's a proof somewhere that it is safe for both uses).

Instead, if possible, I would suggest that the devices create a separate encryption key; generating EC public/private key pairs are cheap.

In order to encrypt with ECC you have to take a look at El-Gamal.
As mentioned above, ECIES is a common way to do it but it is based on symmetric keys and it forces both sides to agree on the key while the idea with PKI encryption is that one can publish his public key so anyone can send data that can be read only by the publisher.


Assistance Cracking Classical Cipher Below is the cipher text I am trying to break and as you can see its rather short which is why I am having so much trouble.

WOYFN ZCMSH VUVTG BFUTW ABTZP FHIMF TFOSU UXFQC HKVKG MPUUQ
MHRXI OVBRZ EPJYF KKVJW GEIOV HUKEB JUNSM THIMF TFKUB ULMMQX

What I know about this ciphertext:

Key is 6 characters long and repeats (Given by the person who encrypted it)
There is a single character missing from the start of the ciphertext! (Also given)
It uses a simple cipher I believe a vigenere cipher.
Friedman IC: 1.143 (kappa-plaintext: 0.4396) which is why i think its a vigenere cipher

I have spent many hours on this but to be honest im not very good at breaking these codes.

My problem that iv run into is that once I break the cipher into its sections they are all very short and hence frequency alaysis fails.

I would really appreciate if someone could either confirm or find the crypto system being used as well as any more information about how one would find the plaintext + key or better yet find the key itself and explain how you manage it with such a short piece of ciphertext

Edit: There was some debate as to the validity of this question so here is some more information from my attempts:

Streams:

?ZUUZFUKUXZKEKSFU IC = 3.6833 (kappa-plaintext: 1.4167)
WCVTPTXVUIEKIEMTL IC = 1.1471 (kappa-plaintext: 0.4412)
OMTWFFFKQOPVOBTFM IC = 2.1029 (kappa-plaintext: 0.8088)
YSGAHOQGMVJJVJHKM IC = 1.3382 (kappa-plaintext: 0.5147)
FHBBISCMHBYWHUIUQ IC = 1.5294 (kappa-plaintext: 0.5882)
NVFTMUHPRRFGUNMBX IC = 0.9559 (kappa-plaintext: 0.3676)

These numbers don't look good. they are almost all drastically off normal distribution for any language.

The main point to my question is:

Does Vigenere Seem like a reasonable fit (given those streams are correct)?
Is it possible to use that analysis in any way? I cant see how it can be effective with only 17 characters per stream. Most letters frequencies are 0.
What other ciphers are possible? How could I identify that they are in use?

I am happy to provide more information I am just not sure what else is useful.

I don't know the solution, but since you say you're only asking for hints, here's a few that occurred to me:

If this is a Vigenère cipher, the missing character at the beginning should not matter (much): if you encrypt a message with the key FOOBAR and drop the first letter of the output, you can decrypt the resulting ciphertext with the key OOBARF.
As ewanm89 notes, the obvious way to attack a Vigenère cipher, after you've determined the key length is $n$, is to write it with $n$ letters per row and attack each column as if it were a Caesar cipher.  There are automated tools for doing that, such as pygenere; they may not always give the correct answer for very short messages, but yours looks long enough that they should at least have a decent chance.
The most notable feature I see in your ciphertext is that the string HIMFTF occurs twice, at offsets 26 and 86.  That does strongly suggest that the key length may be a divisor of 60; alas, 60 has lots of small divisors (including 6, which you believe the key length to be), so that doesn't really give that much information.  It does at least rule out 7, 8 and 9 as likely key lengths.

I can confirm that this can be solved as a Vigenere cipher. The decoded message reads [c]ongratulations on solving the puzzle we hope you enjoy computer and network security and the wargames puzzles good luck.


Showing the decrypted sum of encrypted values Is there a system that would allow to encrypt values with one or more keys, sum the encrypted values, and reveal a key which could only decrypt the sum.

Essentially would be able to show encrypted values where anyone could verify the sum by adding all of the encrypted values, then decrypting it.

There is a recent line of work that does exactly this; it is called functional encryption for inner-product. It allows to encrypt a vector of integers (from some exponent space $\mathbb{Z}_p$) so that one can generate secret keys that do only allow to decrypt a given inner product between the components of any such encrypted vector.

There is a simple construction under DDH, and under LWE. The construction from the Paillier cryptosysem is way more involved and was presented at the CRYPTO conference in august this year.

For the DDH-based variant, the intuition is simple: encrypt your vector with different keys, but the same random coin each time (id est: $E((m_1, \cdots, m_n);r) = (g^r, h^r_1g^{m_1}, \cdots, h^r_ng^{m_n})$, where $g$ is a generator of some group where DDH is hard, and each $h_i$ is $g^{s_i}$ for some secret key $s_i$). The secret key to decrypt an inner product with $a_1, \cdots, a_n$ is just $\sum_i s_i a_i$.

Here is the original article: http://eprint.iacr.org/2015/017. If you want to look into the more advanced constructions, I suggest looking the papers that cite this one.

EDIT: I forgot to mention, the DDH-based instantiation has the same drawback that the additive variant of ElGamal it relies on, which is that a discrete logarithm must be performed on $g^{\sum_i a_i m_i}$ at the end, so it works only when $\sum_i a_im_i$ remains small (say, less than $2^{30}$). If the messages can be large, then the LWE-based or the Paillier-based instantiations must be used.

Interesting simplistic construction is shown. There are far more advanced methodologies. The question references summing encrypted values etc. "Summing" encrypted values in of itself, in my view (ideas I have) is not the only "manipulation" of encrypted values that may be done to reveal key(s) to decrypt the "non-sum manipulation". Noting also references to vectors which can be expressed in n-space.


Zero-Knowledge proof with the paillier cryptosystem For a paillier cryptosystem how can I perform a zero-knowledge proof?

Given a set of values:

0001
0010
0100
1000

This would be for use in a voting system where we want to ensure we where given a value from the set of acceptable ballots without knowing which if the values where selected.

I have found some information suggesting it is possible but I can't find a succinct set of steps or explanation for how this could be accomplished.

Found an implementation here: https://paillier.daylightingsociety.org/Paillier_Zero_Knowledge_Proof.pdf


The effect of truncated hash on entropy Suppose I have a 128-bit random binary string (128 bits of entropy), then I hash it using SHA-256, then I take the first 128 bits of the output hash. Does the taken bit string still have (almost) 128 bits of entropy or the entropy is reduced to 64 bits? (I mean another 64 bits of entropy probably lies in the second 128 bits of the output hash).

I am confused because in the definitions of cryptographic hash functions that I have read in the past it was said that if one bit of input is changed then every bit of the output changes with a probability of $1/2$. It seems from this we can deduce that our truncated output still has (almost*) the same entropy as the input. Is that right?

*: I added 'almost' to mean ignoring the possible hash collisions.

Expected entropy in the output of a random oracle

The expected entropy in the output of a $h$-bit random oracle fed with random $h$-bit input is close to $h-0.8272$ bit, for even moderate $h$ (e.g. at least $32$). As $h$ grows, that expected entropy becomes arbitrary close to $h-\eta$ bit with
$$\begin{align}\eta&=\frac 1{e\ln(2)}\sum_{i=1}^\infty\frac{\ln(i+1)}{i!}\\
&=0.82724538915300508343173\dots\text{bit}\end{align}$$
where the sum is given by A193424.

Proof, where I'll be using $a\approx b$ as a convenient shorthand for $\displaystyle\lim_{h\to\infty}\frac a b\ =\ 1$

For a particular distribution implemented by the oracle, let $n_j$ be the number of output values appearing exactly $j$ times among the outputs for all inputs. The exact entropy $H$ for that particular distribution can be computed from the $n_j$ by applying the definition of entropy, giving
$$\begin{align}H&=\sum_{j=1}^{2^h}n_j\;\frac j {2^h}\;\log_2\left(\frac{2^h}j\right)\\
&=\frac h{2^h}\sum_{j=1}^{2^h}j\;n_j\;-\frac 1{2^h}\sum_{j=1}^{2^h}n_j\;j\;\log_2(j)\end{align}$$
where we have (by merely counting what all inputs lead to)
$$\sum_{j=1}^{2^h}j\;n_j\;=2^h$$
thus
$$h-H=\frac 1{2^h}\sum_{j=1}^{2^h}n_j\;j\;\log_2(j)$$
For fixed $j$ and as $h$ grows, by counting of the possibilities, we can establish that for random distribution, odds that any particular value is reached $j$ times is $\displaystyle\approx\frac 1{e\;j!}$. Thus for fixed $j$ and as $h$ grows, the expected $n_j$ is $\displaystyle\approx\frac{2^h}{e\;j!}$.
In the exact expression of $h-H$, all the terms in the sum are non-negative. To obtain an asymptotic of the expected $h-H$ when $h$ grows, we can thus replace $n_j$ by its expected value, and obtain that when $h$ grows the expected value of $h-H$ is $\displaystyle\approx\frac 1 e\sum_{j=1}^\infty\frac{j\;\log_2(j)}{j!}$.
The stated result follows by defining $i=j-1$, and removing the sum's first term, which is zero.

I've been unable to locate a source; the closest I found is an empirical derivation of $\eta$ to 4 decimals by Andrea Röck: Collision Attacks based on the Entropy Loss caused by Random Functions, WEWoRC 2007, slides; with more in her thesis.

My first empirical derivation was using a program which draws $2^h$ pseudo-random $h$-bit values and counts how many values are reached how many times; for $h=35$ (the largest I could do with 20GB RAM), three runs gave:

             run 1                run 2                run 3
  0  12640123427 36.79%   12640183855 36.79%   12640308584 36.79%
  1  12640408212 36.79%   12640365800 36.79%   12640104651 36.79%
  2   6320124091 18.39%    6320013534 18.39%    6320174710 18.39%
  3   2106681541  6.13%    2106762262  6.13%    2106726749  6.13%
  4    526645276  1.53%     526674914  1.53%     526679947  1.53%
  5    105334156  0.31%     105325000  0.31%     105330269  0.31%
  6     17561277  0.05%      17551924  0.05%      17556150  0.05%
  7      2507918  0.01%       2508727  0.01%       2505282  0.01%
  8       313971  0.00%        313943  0.00%        313406  0.00%
  9        34748  0.00%         34553  0.00%         34755  0.00%
 10         3424  0.00%          3542  0.00%          3546  0.00%
 11          291  0.00%           287  0.00%           292  0.00%
 12           31  0.00%            24  0.00%            24  0.00%
 13            4  0.00%             3  0.00%             2  0.00%
 14            1  0.00%             0  0.00%             1  0.00%
 15+           0  0.00%             0  0.00%             0  0.00%
entropy   34.172763 bit        34.172758 bit        34.172751 bit

Application to the question: the entropy for the output of SHA-256 truncated to its first $128$ bits when fed a random $128$-bit input is about $127.173$ bit, down from very close to $128$ bit before truncation (see final note). The truncation does not halve the entropy, because the halves are not independent. The right line of thought is that SHA-256 truncated to its first $128$ bits is a fine $128$-bit hash, and behaves like a random oracle.

Note: if we consider a random function from $\{0,1\}^{128}$ to $\{0,1\}^{256}$, most likely there is a small $k$ (most often $0$ or $1$, sometime $2$, rarely $3$ or more) such that $k$ outputs have exactly two corresponding inputs, $2^{128}-2k$ outputs have exactly one, and $2^{256}-2^{128}+2k$ outputs have none (odds that any output is reached three or more times are negligible).

Therefore, in this most likely case, the entropy on output of that function when fed a random $128$-bit input is $-k\;2^{-127}\log_2(2^{-127})-(2^{128}-2k)\;2^{-128}\log_2(2^{-128})$, that is $128-k\;2^{-127}$.

The best model we have for SHA-256 (not truncated) for $128$-bit input is a particular function chosen at random among functions from $\{0,1\}^{128}$ to $\{0,1\}^{256}$, thus we can conclude the entropy for the output of SHA-256 when fed a random $128$-bit input is likely exactly $128-k\;2^{-127}$ for $k\in\{0,1,2\}$, which is very nearly $128$ bit, down to about the 37th decimal places.

Remember that a hash function does not create entropy (it can make it very hard to detect a lack of entropy though).  Therefore, if the input has 128-bits of entropy, the output has 128-bits of entropy as a maximum.  If the output size is 256 bits, then each output bit has $0.5$ bits of entropy.  Taking $1/2$ the output bits will cut the entropy in half.

To be on the safe side (due to loss from collisions and such), it is safe to assume that the output is only $0.85 \times$input entropy.

To get a good understanding of what NIST requires associated with this topic (truncated output of functions on entropy) read NIST SP 800-90B.


How can I convert numbers into prime numbers? I'm working with one-way accumulators, but I'm not knowledgable in cryptography. Is there an easy peasy way to hash numbers (or whatever) into prime numbers?
Obviously I'd like it to be collision resistant and all that, but this project is huge, I'm alone and I'm confident someone else in the field will pick up from there.
Also, primality tests are linear in n or what?
Thanks

Thank you for your answers but I think I found a better method.

Take the hash of your input $h(x)$, preferably with random oracle approximation
Sample the interval $[2^kh(x), 2^k(h(x)+1)]$ and pick only primes, for each of them
Hash it with an universal hashing function $f$ until you find that $f(p)=h(x)$
Write to memory: $H(x)=p$

Done!

notes:

The random oracle makes collisions infeasible
Universal hashing gives high density of primes with high probability (there is a theorem out there but the principle is that, for a given prime, I have multiple hash outputs, so the probability that one of them is my input increases. See: Gennaro et al. - Secure hash-and-sign signatures without the Random Oracle, lemma 2)

Misiec´s conjecture:

Let

$$x= \frac{1}{n \cdot n^{\frac{1}{2} + n \cdot 2 \cdot i}}$$

if $n$ is a prime number then the $\sin(x)=x$, and if not the number is not a prime number.

Even though the conjecture does not hold true the $x$ value obtained turns a non-prime number into a complex prime number.


When is an RNG a CSPRNG, a CSRNG, or a TRNG? In a recent answer to a question about CSPRNGs, it was stated that…

Nondeterministic algorithms where there is no such requirement, and ideally could be replaced by a true random generator. Example: operating system random generators, where the practical solution has been to compose a deterministic pseudorandom generator with a physical noise source, to yield output that is both nondeterministic and pseudorandom.

This got me thinking that this could potentially lead to further confusion due the terminologies used, so I decided to wrap this into a question to have a place to point people to…

Can an RNG which relies — among other things — on a non-deterministic physical noise source still be called "pseudo" random?
If, where do we draw the line between a CSPRNG and a CSRNG?
And where do we place a TRNG in this picture? Or is a CSRNG always a TRNG and vice versa, making every other (cryptographically secure) RNG a CSPRNG even when non-deterministic physical sources are part of the RNG?

EDIT
It would be nice if your answer would include some pointers to according references that underline your explanation(s). After all, a trustworthy reference can replace a thousand opinions and related discussions.

There seems to be a lot of confusing terminology here. Let me define everything to the best of my knowledge.

RNG: Some mechanism that produces random numbers.
CSRNG: An RNG that is safe for cryptographic use.
PRNG: An RNG that is a deterministic algorithm based off of a seed.
TRNG: An RNG that is based off of some unpredictable physical process.
CSPRNG: A PRNG that is safe for cryptographic use. (Assuming the seed is picked correctly)

I've never heard the term CSTRNG, but I could imagine it meaning a TRNG which is cryptographically secure. In general conversation, this is redundant because TRNGs are assumed to be cryptographically secure regardless. Even though it is not explicitly defined that way.

  Can an RNG which relies — among other things — on a non-deterministic physical noise source still be called "pseudo" random?

Depends how the noise source is used. If the source is used as a seed for a PRNG, then it is in fact pseudo, since most of the randomness is "made up" by the algorithm.

If every bit of output is influenced by a different bit of input, then it can be considered a TRNG.

  If, where do we draw the line between a CSPRNG and a CSRNG?

From my understanding, a CSPRNG is a subset of CSRNG.

CSRNG means Cryptographically Secure Random Number Generator. It may be pseudorandom, it may not. The only requirement is that it is safe for cryptographic use.

CSPRNG means Cryptographically Secure Pseudo Random Number Generator. This has the same requirements of a CSRNG (hence it being a subset), with the additional requirement that it be some sort of deterministic algorithm that accepts a seed.

  And where do we place a TRNG in this picture?

The best description I've ever heard of a TRNG is an RNG based off of physical noise that has a mathematical basis for how every bit is based off of a different part of said physical noise. (Paraphrasing)

  Or is a CSRNG always a TRNG and vice versa

I could trivially make a TRNG by recording my voice and using the bytes from the recording as randomness without any processing. That isn't cryptographically secure, making it a TRNG but not a CSRNG. This isn't common because a TRNG that isn't good for cryptography is a waste of money for the most part.

However, there are CSRNGs that are TRNGs (See: random.org).

They are separate categories with separate requirements. They do overlap, but they do not depend on each other.

  making every other RNG a CSPRNG even when non-deterministic physical sources are part of the RNG?

A PRNG with a seed derived from a TRNG is still a PRNG. This is actually how a lot of random entropy is generated quickly. It isn't efficient to generate megabytes of entropy using physical sources. (Have you ever tried generating a public/private key pair using /dev/random? It's harsh) It's usually done by using physical sources to seed a CSPRNG, which does the heavy lifting.

Also, there are a lot of RNGs that are not CSPRNGs. Xorshift, LFSR, ARC4Random (when it was based off of RC4), and Mersenne Twister to name a few. These algorithms have biases or other problems that render them bad for cryptograpic use. However, they still output numbers that seem random to the naked eye.

I simply categorise them mathematically, based on entropy flow.  So you can have three types.  The categorisation relies on two kinds of entropy, output or deterministic and input or non deterministic.  Some of this explanation will still be contentious as there are various definitions of entropy between the information science and cryptography disciplines.

Entropy in << Entropy out

This is the typical pseudo random number generator.  A seed formed from true entropy initialises the generator, which then streams (almost) infinite amounts of deterministic and therefore repeatable entropy. This might be a linear congruential generator like Java's Random(), an AES + counter based generator or an RC4 + SHA1 monster like Windows' CryptGenRandom.  Clearly  a linear congruential generator is easily reversed and therefore insecure.  So you might call it simple a PRNG.  If secure and irreversible, then it's a CSPRNG.  With the same seed /input entropy, the output is entirely deterministic and therefore repeatable.

Entropy in < Entropy out

This is a grey area where creations like /dev/random and some of the hyper fast beam splitters live.  They're all hardware based.  Raw hardware collected entropy is not clearly measured in these devices.  In the case of /dev/random it's formed around non deterministic input entropy measured in jiffies.  Not really SI units of measure.  Similarly some beam splitters use AES based randomness extraction without a clear separation of entropy collected from the optical process, and the entropy arising from instrumentation noise which might be 25% of the signal.  Being hardware based, raw entropy is biased and in these cases inadequately assessed so secure cryptographic functions are used to whiten the output.  Hence these devices are somewhere between a CSPRNG and a TRNG.  Their output is non deterministic, but greater than it should be for the amount of entropy flowing into the system.

Entropy in > Entropy out

This is the most secure type of generator.  And also the slowest. They output a smaller amount of entropy than collected making them impossible to invert.  For this reason alone, there is no concept of a cryptographic ally secure random number generator.  They are naturally secure. This also means that cryptographic extraction functions needn't be used.  Any TRNG using a block function like AES is automatically in danger of falling into the previous category due to block size issues.  Simple matrix multiplication /compression extractors can be used on these generators with total security. You can if you so wish use hashes of all sorts, either cryptographic or not but only for the purposes of entropy compression. Their output is entirely non deterministic and never repeats.

To specifically answer bullet point one, yes you can call it pseudo.  This is the point I was making for the second category (Entropy in < Entropy out).  You an also call it a TRNG and people do, specifically devices like the Intel random number generator.  It produces (allegedly) non deterministic output, yet there is much more output than expected from just a weird and under detailed phase oscillator.  It is possible to stretch the raw entropy just like a key stretching function does. So this category is a bit of TRNG and CSPRNG mixed together.  Hence the confusion.


Is Discrete Logarithmic assumption enough to design a secure searchable encryption scheme? I have a basic question in my mind which is "Can we develop a scheme based on Discrete Logarithmic (DL) assumption only? "

Most of the "Searchable Encryption" schemes use assumptions like Decisional Bilinear Diffie–Hellman (DBDH) in their formal security proofs, (e.g. "Protecting Your Right: Verifiable Attribute-Based Keyword Search with Fine-Grained Owner-Enforced Search Authorization in the Cloud" by  Sun et al. SE). Can the formal security proof of my designed scheme be based on DL assumption only?

If you only use the group in a black-box way (meaning, if you wish to rely on the discrete logarithm problem on an arbitrary group), we do not know of any encryption scheme (searchable or not) whose IND-CPA security reduces to the discrete logarithm problem. What we can do from the discrete logarithm problem directly is quite limited. In particular:

you can design a commitment scheme whose binding property reduces to the discrete log problem, this is the famous Pedersen commitment scheme.
The key-recovery security of the ElGamal encryption scheme (i.e. the hardness of computing its secret key given only its public key) reduces to the discrete logarithm assumption.

However, in some specific groups, it is known that the computational Diffie-Hellman assumption is equivalent to the discrete logarithm assumption - this was shown by den Boer in this paper.

Furthermore, we know how to construct advanced types of encryption schemes from the computational Diffie-Hellman assumption. For example, using the Goldreich-Levin harcore predicate and the ElGamal encryption scheme, one can construct an encryption scheme whose IND-CPA security reduces to CDH. IND-CCA secure cryptosystems from CDH where given in this paper.

Very recently, in a breakthrough result, Garg and Döttling have shown that identity-based encryption can be obtained assuming CDH only.

In a follow up to the previous paper, this result was extended to anonymous IBE. Furthermore, it is known that encryption with keyword search can be constructed from anonymous IBE - see this paper. Combining all of the above, this gives you a CDH-based searchable encryption scheme.

All these schemes are secure under the discrete logarithm assumption when instantiated in the groups identified by den Boer. However, it should be noted that the dlog-based keyword-search scheme obtained this way is extremely inefficient and only of theoretical interest.

It is also known that sufficiently powerful quantum computers will break the assumption that discrete logarithms cannot be solved in polynomial time, raising doubts about the future security of systems based on it.


Is TrueCrypt's multiple/cascading encryption safe? Is TrueCrypt use of cascading encryption safe?  Is it useful?  TrueCrypt is arguably one of the most popular and widely used encryption applications in use today, yet it seems to use a very unconventional scheme.

The software offers cascading encryption, where the user can specify either double or triple encryption using any combination of AES, Twofish, and Serpent.  Unusually, multiple-encryption is performed on each block, before moving on to the next block, as opposed to encrypting all the data and then encrypting the resulting ciphertext.

After having spent a lot of time reading through crypto.se, the consensus seems to be that multiple/cascading encryption offers little (or perhaps no) extra security, and some even argue that if may be weaker than just following a standard protocol (although the latter rarely seems to be substantiated by any reasoning).  However, in Bruce Schneier's Applied Cryptography (considered by many to be a quintessential text on cryptography), he advocates the use of multiple encryption (albeit cautiously, and with some caveats).  See sections: 15.7 Cascading Multiple Block Algorithms, 15.8 Combining Multiple Block Algorithms, and 17.11 Cascading Multiple Stream Ciphers.

Another example of going against this consensus would be the Tahoe-Lafs 100 Year Cryptography Project, which has been recommended on crypto.se. Their protocol involves encrypting with AES in CTR mode and then encrypting the output with XSalsa20.

So my question is, is TrueCrypt's use of multiple/cascading cryptography reasonable, and why?

Cascading cipher gives a sense of security; and one that is technically justified with respect to the possibility that a weakness in one of the cipher would allow recovering the encrypted data. That's Bruce Schneier's argument, and it made sense in an era where DES, the then leading cipher, was a closed design, clearly deliberately weakened by a small key, giving rise to the fear that is was also deliberately weakened otherwise (which turned out not to be the case).

On the other hand, the more serious threats facing systems like TrueCrypt are not a weakness of the cipher; they include compromise of the software, compromise of the hardware running the software, compromise of the key (by eavesdropping, guess of the passphrase, rubber hose cryptanalysis, recovery from hibernation file or RAM memory..), analysis of changed sectors.. These risks are hard to mitigate, and in the opinion of many (including me), much more likely to materialize than cryptanalysis of AES, for at least decades even if we consider AES-128. And further, technological progress likely will enable a guess of the passphrase by brute force sooner than a cryptanalysis of AES.

Cascading ciphers has at least one obvious drawback: performance is lowered. Often it matters, sometime it does not, e.g. when enciphering a key. In my opinion, compared to AES, cascading might only improve practical security by a side effect: making it harder to verify a guess of the passphrase (that would be the case in a system where the only way to check such guess is to turn the passphrase into keys, decipher something using the cascade of ciphers, and check that it makes sense).

So all in all, I would think of cascading a cipher in addition to AES only as a way to damp paranoia or indicate an extra level of care, like telling to someone knowing little about cryptography: for the cold storage of your all-important master keys, you could use a Truecrypt volume on a USB stick, perhaps even with cascaded ciphers; and most importantly, strive for the integrity of all the hardware and software used!

Addition following comment asking how to do cascading (of block ciphers) properly. My answer to that would be that if one uses cascading:

That might be considered in the key-stretching phase (turning the user's passphrase into the key of the bulk cipher), where cascading is useful, because it makes construction of a device that successfully brute-force passphrases significantly harder/more expensive/less likely. Cascading is useful in key stretching because when a cascade of encryptions is iterated, a fast implementation must be fast on each of the cascaded ciphers, which is a very serious problem in a password cracker using ASIC or FPGA; search FPGA password for some interesting links. Beware however that speed optimization of the legitimate implementation for each of the cascaded cipher iterated in the key-streching phase is important for security (because we need to push the number of iterations as high as feasible), when it is immaterial to security in the bulk-encryption phase.
At least the first cipher in the cascade (the one in contact with the plaintext during bulk encryption, or to a lesser degree the one in contact with the passphrase during key stretching) should be implemented in a manner protecting from any likely side-channel attacks, including timing and unwanted emissions (for an illustration of that later danger in a slightly different context, see this).
When the key must be secret (in particular the key used for bulk encryption), the cascaded ciphers positively must use different keys (e.g. extracted from a wide derived key); otherwise using a cascade could well turn out to enable an attack if any of the ciphers turns out to leak its key through a side channel.

Truecrypt's use of cascaded ciphers definitely follows 3; I can't tell for 2, and the most important 1.

If there is a logger malware in the computer, not a keylogger, the cascading cipher should be weakened, because the application will know the specific way the cipher encrypted something. Reverse mathematic operations maybe discover the password. Cascading ciphers are secure, and have chances that not even a Quantum computer will break it. Here i only say that cascading ciphers are not the fast, as like only using the standard AES, but it is not so slow.


Are there any advantages in using proprietary encryption? Proprietary software generally relies on the fact that in keeping the encryption algorithm private, it gets an extra layer of security implying "Security through Obscurity." Obviously this phrase has been hotly debated and surely is only acceptable if discovering the mechanics of a proprietary algorithm doesn't actually reduce it's security.

Is there any other reason you would use a proprietary encryption since my research has proven there to be many more disadvantages than advantages!

Yes, there are advantages to the attacker.

Using a well vetted encryption algorithm provides a better assurance of security. There may be cryptographic algorithm flaws and/or coding mistakes.

As noted, relying on the algorithm being private just adds a layer of false security.

Obscurity can work if your application is, indeed, obscure.  If you're Microsoft, that won't work.  If millions of dollars depend on the security, that won't work either.

But don't make up your own encryption algorithm - chances are it'll be easy to break.  Instead, modify an existing encryption algorithm that's already good.  For instance, use AES but swap the 2nd and 7th bytes in each 16-bit block.  Or swap the 2nd and 7th byte in the KEY.  Then, you've got the security of AES, but it's not off-the-shelf AES.


Slow one-way pseudo-random permutation? I'm looking for a slow one-way pseudo-random permutation; or in other words a block cipher $E_K: P\in\{0,1\}^b\mapsto C\in\{0,1\}^b$ with moderate block size $b\approx 64$ bits, wide key $K$, indistinguishable from a random permutation for one not knowing $K$, and additional characteristics:

encryption $E_K$ is controllably slow according to a parameter $c$, similar to the iteration count parameter in PBKDF2; an additional memory size parameter $m$ as in Scrypt would be nice;
there is no efficient decryption method even knowing $K$, ideally so that the least costly method to decipher ciphertext blocks $C_j$ would be to try and (slowly) encipher candidate plaintext until finding a match. Update: Otherwise said, there should be a security gap as wide as possible between decryption and encryption, expressed as a ratio of work; and that should remain sizable when the cost of encryption is raised using parameter $c$.

Is there some established (or arguably secure) construct for that? One idea is outlined in this interesting answer to a related question (but unfortunately, the one-wayness obtained using a permutation polynomial seems dubious).

Update: I'd also be satisfied with a slightly expanding injective function, e.g. $E_K: P\in\{0,1\}^b\mapsto C\in\{0,1\}^{b+1}$.

Updated example application: 2-D barcode cards (or other kind of write-once memory cards) are issued to individuals with data including a unique serial number $S$ of $s=32$ bits (sequentially assigned, thus largely guessable from another $S$), and other data $Q_S$ (which we assume has sizable entropy). The serial number is used for some initial purpose, and (interpretations of) regulatory requirements protecting individual's privacy prevent from storing that identifier for purposes unrelated to the initial purpose. Nevertheless, merchants would like to lawfully reuse the same cards in an existing loyalty application, identifying cards with an identifier of small size, and able to work off-line (at least, as a backup). We thus want to transform $S$ and $Q_S$ into a short digest (practically public), computable from $S$, $Q_S$, and a key $K$, that remains unique to a given card (as $S$ is); the digest should leak no information about $S$ and $Q_S$ without access to $K$; and, inasmuch as possible, the confidentiality of $S$ and $Q_S$ should be preserved from an attacker knowing digest and key (thus easing the requirements on secure storage and use of the key). Notice that a truncated MAC would not match the "remains unique to a given card" requirement.

With a function as in the question, we could use as digest $E_K(S||R_S)$ where $R_S$ has $b-s$ bits, and is obtained, say using Scrypt, from $Q_S$, $S$, and $K$. Notice that encryption slowness in the forward/encryption direction is necessary to prevent checking guesses of $S$ and enumerated $R_S$; and even more slowness (ideally, next to $2^b$ times as much slowness) is required in the backward/decryption direction, in order to prevent deciphering of the digest. Notice that either attack would reveal $S$, and also allow forged cards misappropriating the same $S$ and digest as the original, if not the same $Q_S$.

The main difficulty in designing what I asked, is coming up with a permutation over a relatively small set, that is easy to compute in the forward direction, but convincingly much more difficult to invert. The least unsatisfactory I have so far is based on the discrete logarithm problem in $\mathbb Z_p$. If $p$ and $(p-1)/2$ are primes, and $g\in\{2\dots p-2\}$ with $g^{(p-1)/2}\not\equiv1\pmod p$, then
$$P:\begin{cases}
 x\mapsto g^x\bmod p& \text{if } x\in\{1\dots p-1\}\\
  0\mapsto0
\end{cases}$$
is a permutation of $\{0\dots p-1\}$ which is easy to compute, but markedly harder to invert. At least, the problem is well-studied, with the best known algorithms the index calculus algorithm and some specialized GNFS variants. Bad news is that the problem is workable for 530-bit $p$, and here I'll be stuck with $p$ like 80-bit (for $b=64$ and other realistic parameters).

It seems possible to build a slow one-way pseudorandom permutation over $\{0,1\}^b$ from such $P$, while keeping about the same security gap (ratio of work in backward to forward direction) as in $P$. I sketch such a construction below. Again this is not fully satisfactory, for the above (family of) $P$ does not have a high-enough security gap, given the order of magnitude I can use for $p$. I badly need a better $P$ !!

Update: The best attacks on $P$ require a heavy pre-computation, then can go from $P(x)$ to $x$ at comparably low cost. I have tuned the following to account for that fact.

The construction requires an expected $c_0\cdot c_1$ evaluations of the above $P$ with $p\approx c_0\cdot2^b$, and forces an adversary trying to brute-force the forward direction to mobilize about $m\cdot2^m$ bits of memory for each few instances run in parallel. Realistic parameters could be $b=64$, $c_0=2^{12}$, $c_1=2^{12}$, $m=20$.

Derive from $K$ a pseudo-random $g$ in $\{2\dots c_0\cdot2^{b-1}\}$ ;
Derive from $K$ an arbitrary permutation $M$ of $\{0,1\}^m$, stored as $2^m$ words of $m$ bits of memory;
Repeat for $c_1$ rounds (identifier by round counter $r$) the following keyed permutation of the current $b$-bit state $s$:

derive from $K$ and $r$ a pseudo-random prime $p$ in range $\big[{3\over4}\cdot c_0\cdot2^b\dots{5\over4}\cdot c_0\cdot2^b\big]$, such that $(p-1)/2$ is prime and $(g^{(p-1)/2}\bmod p)=p-1$ (note: it is advantageous to perform the later test right after insuring that $p$ and $(p-1)/2$ have no small divisors);
Repeat

If $s<\big\lfloor p/2^m\big\rfloor\cdot2^m$ (which is, most of the time)

Replace the low $m$ bits of $s$ with their image through $M$;

If $s\ne0$ (which is, most of the time)

Replace $s$ with $g^s\bmod p$;

Until $s<2^b$.

Note: $s$ temporarily grows to at most $b+\big\lceil\log_2({5\over4}\cdot c_0)\big\rceil$ bits.

For each round, the repeat..until iteration is expected to be executed about $c_0$ times, with an exponential distribution. Increasing the number of rounds $c_1$ makes the runtime more predictable, and less likely that pre-computations for inverting $P$ can help an attack. Each iteration requires one memory lookup, and $\epsilon\cdot\log_2 p$ multiplications $\bmod p$ (we can have $\epsilon\ll1$ with some pre-computation).

(Optionally, the construction could end (or/and start) with some conventional $b$-bit block cipher using key $K_d$ derived from key $K$, perhaps TDES for $b=64$ (with additionally one bit of $K_d$ devoted to making the resulting permutation odd or even, by conditionally swapping output values $0$ and $1$). This, combined with use in other steps of permutations not chosen from $K_d$, convincingly insures that the overall construction is indistinguishable from a random permutation for one not knowing $K$).

I have a 128-bit block cipher that can be modified to fit your requirements (possibly).

It is an AES variant with a 16x16 matrix multiplication that operates on the entire state instead of the standard 4x4. ShiftRows is maintained but not necessary for diffusion. The matrix is its own self inverse. The s-box has been replaced with one that has a more complicated algebraic properties. The key schedule uses Keccak with c=1024,r=576, and generates round keys with a squeeze operation with 448 bits of output ignored. The key size and round counts are specified up to 512-bit keys.

In the standard form it is slow because of the large matrix multiplication, but in 32-bit and larger systems table lookups can be used (with about 64KB of memory for the tables) that combine the matrix with the sbox. The decryption process is simple, using the same "equivalent inverse" method that AES uses. The design can be shrunk to 64-bits using an 8x8 matrix, or extended to 256-bits using a 32x32 matrix.

In order to modify it to meet your requirements, additional rounds could be a parameter to slow it down. The ease of decryption part can be solved with using a non invertible MDS matrix. Additional slowdowns can be made by changing the round count of Keccak when generating round keys. Brute forcing a key with a 96-round Keccak based key schedule will be hundreds, if not thousands of times slower than AES.

Since this is a permutation, all unique inputs are guaranteed to produce unique outputs with a given key. With a non invertible matrix there should be no efficient decryption. With parametrized round counts and flexible key sizes, in addition to its design, it should be as slow as you want it to be on all platforms. The design should make its pseudo-randomness equal to or better than AES at a given round count (for a 128-bit block anyway). All of your requirements except for configurable memory requirements should be met.

Round function pseudocode modified since decryption not required

AddRoundKey 0
for i = 1 to Rounds
  Sbox(state)
  MatrixMultiply(state)
  AddRoundKey i
next i

16x16 MDS matrix modulo 0x11B (not tested for noninvertibility but sure looks it)

5C E8 9C 6C 77 0C 0E F7 47 79 5C CE A4 FA 80 B5
E8 2C 23 A9 08 70 5F 43 6B 15 84 29 32 5E DA 4E
9C 23 5F 41 87 FA 37 AF CA E4 79 24 85 42 2D DC
6C A9 41 EB C7 E0 BD E2 71 4E 27 93 9F 62 33 53
77 08 87 C7 48 15 1C 5B B5 6B B7 99 D3 52 D3 86
0C 70 FA E0 15 CE 24 72 B1 D4 DB 98 EE DA A2 5A
0E 5F 37 BD 1C 24 91 D5 75 35 A1 86 5A AF B3 87
F7 43 AF E2 5B 72 D5 6A 0E 54 AA 3D 6D CA F3 F7
47 6B CA 71 B5 B1 75 0E 86 8A 64 5E 44 EA AC DD
79 15 E4 4E 6B D4 35 54 8A 83 6E B3 CC F5 BD 49
5C 84 79 27 B7 DB A1 AA 64 6E 1D 2F 04 10 B8 74
CE 29 24 93 99 98 86 3D 5E B3 2F DA F1 DF B4 69
A4 32 85 9F D3 EE 5A 6D 44 CC 04 F1 3C 2D 87 6C
FA 5E 42 62 52 DA AF CA EA F5 10 DF 2D B6 41 62
80 DA 2D 33 D3 A2 B3 F3 AC BD B8 B4 87 41 7A D5
0E 1F EE BC C4 F7 48 81 F7 48 DE 4D 57 C4 A3 A4


Is signing a plaintext sufficient? If I have N bytes of plaintext, does signing it with my private key prove (to holders of my public key) that I have signed that exact plaintext messages?

i.e. could an attacker use the plaintext and signature to generate another plaintext which would also verify?

Or do I need to hash the plaintext to provide message integrity?

A signature algorithm should - in general - be thought to contain the hashing method as parameter. Take for instance RSA / PSS. RSA / PSS includes the  EMSA-PSS-ENCODE operation. Here the hash function to use is an option to the algorith.

Step 2 is:

  Let mHash = Hash(M), an octet string of length hLen.

where M is the message to be signed.

"Or do I need to hash the plaintext to provide message integrity?" is therefore a question that is non-sensical for most signature definitions. RSA has deprecated modes that directly sign a message (with message recovery) but those are generally not used. ECDSA is also defined for use with a hash function and EC crypto cannot easily "encrypt the message" with the private key for signature generation.

As you have found out, Signature dsa = Signature.getInstance("SHA256withECDSA"); uses SHA-256 as an option to ECDSA. The hashing will then be performed internally.

Sometimes hash value or intermediate hash value is used as input for signature generation. This can be useful when the device that performs the private key generation is limited in hashing bandwith. E.g. for a smart card you may not want to send all the data to the smart card - sending just the hash is much more efficient.

Assuming your signature scheme is non-malleable, it is sufficient to encrypt the message using your private key.

The purpose of using digest is to reduce the size of the data to be encrypted. The digest used in such case should be cryptographically secure.