Half a croissant, on a plate, with a sign in front of it saying '50c'
h a l f b a k e r y
We are investigating the problem and will update you shortly.

idea: add, search, annotate, link, view, overview, recent, by name, random

meta: news, help, about, links, report a problem

account: browse anonymously, or get an account and write.



intelligible One time Pads

How to use one-time-pads safely in the jurisdiction of an unreasonable law
  (+3, -2)
(+3, -2)
  [vote for,

I recently posted a different idea on the same subject - please bear in mind that this one is different. Also please read the entire idea before even thinking of mentioning truecrypt.

I'm also aware this idea is rather long - I've tried to explain every stage thoroughly to avoid misunderstandings, although I feel I may have still glossed over some details.

In the UK, at the moment, users of computers can be required to decrypt any file they own. See first link for preliminary form. One can only avoid jail by decrypting the file or by proving that one does not have the key in their possession. Proving the negative is hard to do. (Have you ever forgotten a password? If so, any files which use that password are now a liability.)
Regardless of how incredibly awful this law is, in the meantime those of us in the UK have to live with it.

Now, one time pads (OTP) are an encryption system for transferring information with the interesting property of being proveably secure, provided certain conditions are met. No other cryptographic system can make such a claim.

An OTP is effectively a mask of random data which will encrypt a file of up to the same size.

Requirements for security of a OTP:
A pad must be composed of random data.
A pad must be used only once. A pad must be kept secret. If the pad is compromised, so can the message be. (It is in effect a large password or 'key'.)

The Achilles heel of the OTP system is that the pads must be transferred to the recipient. This can be assumed to be secure by arranging for it to be done ahead of time. For example, when you meet your friend in person, you supply them with a CD of OTPs. They copy this to their computer, destroy the CD and can use the pads for secure communication with you. Generally pads are securely destroyed after use, to prevent reuse.

Unfortunately, the first requirement opens up a worrying legal liability in that a user may be required under the RIPA law to decrypt the OTP file - which is impossible since it is random data. Thus we are at a legal risk if we want to enjoy the nice property of having guaranteed secure communication.

Whenever RIPA is mentioned some people seem to immediately jump to mentioning truecrypt. This is a program which is supposed to provide 'plausible deniability' by letting one keep more than one message in the same file. However, it is my belief that using it instead opens one up to 'plausible guilt'. Unless one has used all the space available, and can reveal all keys, it can always be claimed that there is space available for further messages to be stored.

The way of making OTPs safe is to make sure that they are themselves 'intelligable'. If the data makes sense on its own, then you cannot be asked to decrypt it further. The way I propose to do this is to generate large 'background' bitmap images using any source of 'true' randomness. For example, a vector flower may be drawn at slightly varying sizes, colours and different angles at random positions. A whole range of different aesthetic images may be generated by tweaking conditions such as the colours, sizes, and vector shapes involved. Thus, many OTPs can be generated.

Each image file is then seperately compressed as aggressively as possible. The idea here is to remove the 'non-randomness' of the series of bits due to similarity of adjacent pixels. The compressed file constitutes an intelligable OTP.

I want to be explicit here - this is a potential weakness in the system. If the compression is not 'perfect' then this potentially opens a window to decrypting the message. However, if 'true' randomness is used in the creation of the image, then theoretically most of that data is still present in the image after compression - although it may not be completely retrievable. The amount of bits of randomness is known, and if one assumes a fraction of this is present (to allow for obscuring effects and sub-pixel data-loss), then the available data-space can be determined, and passed on (using the filename of the image inside the compressed file).

To use an intelligable OTP, the number of bits of randomness is read, and the header and meta-information of the compression file are of course stripped. The remaining bytes are then combined together using a reliable hashing scheme to yield 'decent' random bytes. These bytes can then be used to encode the message.

At both ends of the information transfer, a system is required by which OTPs are recorded. A small hash plus unique number is used to identify them when they are checked in as available for communication, and this is preserved after they are used (and then securely deleted).

Thus if the police intercept a message in transit and demand you decrypt it for them, you will have hard evidence that the key is no longer in your possession, if it no longer is.

One nice side-effect of this system is that your OTP files can be hidden in plain sight. It should be possible to keep them in a folder in your pictures directory - "My wallpapers". And even for them to be displayed at random as your desktop wallpaper. However if this is done then it is essential for cryptological security that you don't copy the files elsewhere. And also, if you become too attached to any particular backdrop you'd need to tell your friend, as otherwise when a message arrives you might need to delete it.

Note - in practice, OTPs are rarely used.

[1] in the usual sense - actually my other idea might help - but some people think that this would be cheating.

Loris, May 06 2009

Section 47 notice requiring disclosure of key (preliminary) http://www.fipr.org...sampleGAKnotice.htm
Excuse me while I stamp on your face forever. [Loris, May 06 2009]

UK police can now force you to reveal decryption keys http://www.theregis...ryption_keys_power/
An accused person [...] might genuinely have forgotten it but struggle to convince a court to believe him. [Loris, May 07 2009]

intelligible OTPs might look a bit like this http://dryicons.com...ro_flower_frame.jpg
probably larger, with more, smaller flowers, and perhaps more colour variation [Loris, May 07 2009]

Regulation of Investigatory Powers Act 2000 http://www.opsi.gov...ukpga_20000023_en_1
the enemy [Loris, May 08 2009]

Steganogrphy per Wikipedia http://en.wikipedia.../wiki/Steganography
[theircompetitor, May 09 2009]

magic numbers - in cryptography http://www.mail-arc...t.edu/msg00301.html
no back doors here - move along [Loris, May 09 2009]

Give us the passwords or rot in a cell http://www.theregis...ripa_jfl/page4.html
First person in UK jailed for refusing to decrypt. A schizophrenic, not a terrorist. Only 21 Quest is surprised! [Loris, Nov 24 2009]


       Zeno: Oh hello.   

       Constable Loris: I have permission to search your house, you criminal!   

       Zeno : Ok come in.   

       Constable Loris: HoHoHo what's all this then? I'll have to ask you to open up the safe sir! Could very well be the incriminating evidence is in there!   

       Zeno: I refuse to give you the key.   

       Constable Loris: Oh ok well that's allright then, bye.   

zeno, May 07 2009

       As your one-time-pads are still random, you are doing nothing more than saying: 'but sir! the seemingly random data is describing subtle (and obviously random) alterations in this here picture of a flower, that is incredibly dull, because it can be compressed to just about nothing (in fact, the .dul file contains either the word 'flower', in which case it is this flower, or the word 'house' in which case it is, lo and behold! - a car.). this subtle alterations make the dull image of a flower a dull noisy image of a flower, which is exactly the thing i would have lying around.'   

       You could say this about current OTPs already.
loonquawl, May 07 2009

       [21Q] is right - the link doesn't say anything Kafkaesque about needing to prove you don't have a key, all it does is set out penalties for not providing a key to decrypt data, but there would have to be a trial and it would rest on ordinary, everyday evidence so you might be expected to have a private key corresponding to your PGP public key, or you might be expected to have a key for traffic between you and someone else which had been going on for some time, or you might be expected to have a key which covert surveillance showed you being given, etc... My experience of this area is that it's one in which people with a bit of cyptography knowledge love to jump to extreme conclusions, but actually most scenarios have a 'real-world' parallel - e.g. you have a massive safe in your house but claim to have no key for it and no way of unlocking it - looks suspicious, doesn't it?
hippo, May 07 2009

       21Quest there are other unreasonable laws too, they're not mentioned because the idea doesn't address them.   

       Yes, you do get a trial before you have have to go to jail... that's not the issue. Of course, you may well spend time locked up before the trial - which you don't get back if found not guilty.
I know I didn't provide a link to the full law description, but it's boring and turgid - you wouldn't read all that. But the linked document does say that you MUST supply the key ("This notice can only be complied with by disclosing a key ..."). The important point about the law is that it changes "innocent until proven guilty" to "guilty until proven innocent". I've provided an extra link which spells out the issue. It's not just me.

       I don't have a problem with the police getting warrants to look at things and then doing so. You're just being stupid zeno. But to take the parallel of the real-world safe - it's more like this:   

       Policeman: We think there is a hidden compartment in this item of furniture although we can't find it. Show us how to open it.
Suspect: That wardrobe doesn't have a hidden compartment.
Police: We still think there is. Refusing to give us the requested information is a crime that you are guilty of, come with us quietly please.

       So stop saying that the law doesn't do this, because it does. It doesn't really matter if the law has already been abused, the issue is whether it could be.
Try and look at the idea itself now, won't you?


       loonquawl, it's true that the files contain randomness - they wouldn't be suitable for one time pads if they didn't. But they're stored on harddisk as a folder of compressed images (I don't know where you got the idea of single words of text from). The idea is to incorporate randomness in such a way that it's obviously not storing information - or at least, not in a way which can be recovered. I just quickly trawled the net and found an image a little bit like my proposed output, see link.
Loris, May 07 2009

       [loris] the single word idea was given to me by your insistence on //compressed as aggressively as possible// and the well known compression algorithm for books : compress a whole book to a few numbers by stating its ISBN.... Randomness is incompressible, therefore the files would be as big as a OTP with a little data added to contain the actual picture. As to the linked picture: This picture would be incredibly tiny if given in a vector format (and incredibly non-noisy), so far so good. now you add the noise... So you now have a CD with lots of very compressable pictures (compressable if they were not as noisy as they are...). If you comnpress a noisy picture with .jpg, by the way, you loose the noise...
loonquawl, May 07 2009

       loonquawl first:   

       //As to the linked picture: This picture would be incredibly tiny if given in a vector format (and incredibly non-noisy), so far so good. now you add the noise... So you now have a CD with lots of very compressable pictures (compressable if they were not as noisy as they are...). If you comnpress a noisy picture with .jpg, by the way, you loose the noise...//   

       You misunderstand. You seem to do that a lot, and it's starting to feel like you're doing it deliberately.
The file would be rendered to a bitmap, as is clearly stated in the idea. Random numbers are used to determine the positioning, rotation, size, colour &c of a vector image, which is then drawn to the bitmap, to create a 'desktop wallpaper' image. Repeat many times. We *do*not* directly draw random data to the bitmap as pixels - because that would be obviously recoverable information. But for randomly positioned, sized &c vectors drawn onto a bitmap, much less information can be reliably recovered, and it is decidedly non-trivial, so they can't accuse you of the pad itself being a message as easily. I wouldn't use jpeg format for the file, by the way - that random image off the net happened to be one, but that's just a red herring.

       The point about compressing aggressively is that we want to get rid of the ordered information as adjacent pixels are more predictable - compressing does this. I didn't specify what exactly because there's a range of options, and I don't know what would work best. It could be done using pngcrush, or by encapsulating in a zip file at maximum compression level, we want it to be as good as possible to minimise storage and the need for hashing when the file is used.
Loris, May 08 2009

       21 Quest:   

       //It doesn't change "innocent until proven guilty" to "guilty until proven innocent". Nowhere in that Section 47 link did it say anything about having to prove you don't have it.//   

       [first sentence] It does. [second sentence] It doesn't because it doesn't cover the possibility that you don't have the key at all.   

       //If they feel strongly enough that you're lying about it, then you get a trial. In the trial, they have to produce evidence that you *have* the key and that you're *deliberately* withholding the key to convict you. That's the way a trial works, and this law doesn't say anything about changing trial procedure.//   

       That's how the law is supposed to work. You know, that "innocent until proven guilty" thing I've been banging on about. But unfortunately this law changes that.   

       You've forced my hand - please find a link to the incredibly turgid law, all 14 pages of it. Enjoy reading it (I know I didn't).
(Incidentally the 'section 47' seems to have become 'section 49' by the time the bill became law.)
One relevant section is this:

       ::53 Failure to comply with a notice
::(2) In proceedings against any person for an offence under this section, if it is shown that that person was in possession of a key to any protected information at any time before the time of the giving of the section 49 notice, that person shall be taken for the purposes of those proceedings to have continued to be in possession of that key at all subsequent times, unless it is shown that the key was not in his possession after the giving of the notice and before the time by which he was required to disclose it.

       ::(3) For the purposes of this section a person shall be taken to have shown that he was not in possession of a key to protected information at a particular time if—   

       ::(a) sufficient evidence of that fact is adduced to raise an issue with respect to it; and   

       ::(b) the contrary is not proved beyond a reasonable doubt. ::   

       You see that 3(a) clause there? That means that you need to provide 'sufficient' evidence that you don't have a key. That means proving your innocence. Which give the term "guilty until proven innocent". In the case of a password you'd forgotten - how would you go about providing that evidence?   

       Admittedly in this section it says that you have to have been 'shown' to have previously had a key - but that's shown, not proven. My impression (IANAL) is that this is a significant distinction - and language elsewhere in the act seems to support this. It talks, for example, about having 'reasonable grounds' for starting the process off by serving the notice. The police consider many things reasonable grounds - for example, walking past them in a confident way, or refusing to undergo a voluntary search.
In practice, I can see it being easily assumed that if you have an encrypted file, you must have had the key to it.

       ////Users of encryption technology can no longer refuse to reveal keys to UK authorities after amendments to the powers of the state to intercept communications took effect////   

       It seems to me that you misunderstand how that sentence applies. It's from an online newspaper article, and obviously been rendered into easily understandable to the layman terms (as opposed to lawyers).
It doesn't (and isn't supposed to) compress the entirety of that legal act into one sentence.

       // They're going to have a pretty solid case built up long before they ever approach you directly. [...]
You're looking at this law in the absolute worst-case scenario, but the fact is law enforcement doesn't have the time, manpower, or inclination to start kicking random people's doors in and demanding access to random encrypted files in their computers. They're going after people who have been in contact with known criminals who are already under investigation.//

       Well, perhaps. But then again, if they had a solid case they wouldn't need to decrypt your files would they? This law was proposed for the case where they *don't* have other evidence.
When you combine that with the fact that such investigations may spread to people who communicate with people who communicate with the original suspect, and you've got a recipe for disaster.

       Maybe I am looking at the law as it's worst case scenario. But so what? Laws should be written such that they don't permit dubious usage. This Act (which covers many things) clearly hasn't been - it wasn't debated in the commons, but rushed through; the government promised that it would only be used in crucial cases of counter-terrorism. So what happens next? Local councils are using it to spy on people putting out their rubbish, or to see if schoolchildren are going to the right school.
You shouldn't even rely on trusting the government (if you do trust them) - unless you are also happy trusting any and all potential future governments.
Loris, May 08 2009

       Forgetting the motives, this idea is essentially baked - a friend and I used to encrypt files by using "intelligible one time pads" as you put them. It was just a simple XOR encryption, but the key selected was a legitimate file, usually several megabytes big.   

       Another thing we used to do was hide information in bitmap files' colour depth. Split the data, and insert it as the last bit (or last two or more bits) of every colour byte. You could fit a surprisingly large amount of data into an image without noticeable loss of quality.
mitxela, May 08 2009

       [loris]: i'm sorry if i seem deliberately obtuse, and the discussion is drifting into technical territory (you link a jpg as example, i point to the shortcomings of jpg, you say it's not about jpg...) that is not at the heart of my critique...   

       Your idea as i understand it is hiding an OTP (noise) in whatever way in non-noise (picture, sound, metadata). This is Steganography, and relies on the principle being secret (not, as in cryptography, the principle being known). My criticism is the following: There is a law stating you have to provide keys for every lock found on your person. You propose using a very safe kind of lock, which requires a rather intricate key. For being able to send strongboxes to your friends, you first provide them with a bunch of keys. To prevent inquiry as to those keys, you make them look like flowers. Now this is a totally wondeful idea, as long as you do not make it known, because from that point on, people having heaps of flowers in their backyard will be scrutinized...   

       I did not mean injury to you, and apologize if you felt attacked - i simply wanted to point out that this particular kind of Steganography is not all that practical.
loonquawl, May 09 2009

       Loris, as others have pointed out, this kind of approach -- of hiding data within images -- is called steganography. That methodology does not really dictate the method of encryption used, if any -- it simply describes the technique. I've posted a link
theircompetitor, May 09 2009

       RIPA Section 22(2)(f) : The government can phone tap and watch your internet traffic to assess tax due to the government.   

       Well so long as its in the interests of national security. The others in a)-h) are a bit of a laugh too.
bigsleep, May 09 2009

       Okay, loonquawl - no offense meant, none taken.   

       Regarding whether this is steganography - I'm not sure whether it is or not. I mean, I know what steganography is. But does an OTP which will be used in future count as a message? I don't think it really matters - let us suppose that it does. This isn't really the purpose of the idea. If it does happen that the police assume your collection of OTPs are merely pictures, it's a bonus. - Certainly one I'd do my best to maximise, but not the core of the plan.
You can see that I also specified that the system tracks OTPs, and retains a record of their use. That would be counterproductive if the system were purely steganographic. This system is really for the innocent to 'prove' that they're complying with the law.

       The idea is really to have something which is demonstrably not a message in itself. I've got an analogy: When creating a cryptographic system, often numbers are required to initialise state in some way, or something like that - these are called 'magic numbers'. But they can give rise to the suspicion that they are chosen specifically to create a backdoor in the system. To avoid this the usual approach is to choose digits from fundamental constants like PI, which are beyond reproach. But for OTPs we can't do that. So we need some other form of evidence that our pads are not messages. That's where I'm coming from, anyway.   

       21 Quest - you're obviously not a lawyer, but you do really need to pay more attention to sentences and the words in them. Section 53(3) says that you can show that you're not in possession of a key by (a) providing sufficient evidence unless (b) the prosecution can prove the contrary.

       This means that if the prosecution really can prove you have a key, then your evidence raising reasonable doubt isn't good enough.
It does not mean that they have to prove that you have the key under all circumstances. If you can't provide sufficient evidence to raise reasonable doubt, you are assumed by default to retain the key.

       Also, 'shown' does not mean 'proven'. To "show" something is merely to non-rigerously demonstrate that it is possible.
Loris, May 09 2009

       //The idea is really to have something which is demonstrably not a message in itself.//   

       I'm sorry, I must be missing something. But isn't every steganographic message accomplish exactly that? In the Wiki example, they have a winter forest landscape that becomes a picture of a cat. Surely that would cover your idea?
theircompetitor, May 09 2009

       21 Quest, since you asked /so/ politely:   

       GCSE Maths 2tier-higher for AQA B, Speed, Gordon and Evans. Published by Collins (C) 2006. ISBN 0-00-721573-8. It's a Maths book at a fairly basic level. (GCSEs are the last stage of compulsory education in the UK).   

       P592: [asterisks indicate original emphasis]
::One of your earlier activities in geometry may have been to draw a triangle, to cut off its corners and to stick them down to *show that* they make a straight line. <diagram>
::Does this prove that the interior angles make 180 degrees or were you just lucky and picked a triangle that worked? Was the fact that everyone else in the class managed to pick a triangle that worked also a lucky coincidence?
::Of course not! But this was a *demonstration*, not a proof.

       This isn't a legal definition, of course - but it is clear that the term isn't a synonym of 'proof' in normal usage.
It's pretty easy to pick holes in your example, by the way. Many of the other examples are clearly /not/ 'prove'. Term 10 says in legal documents it means allege! Not only that, but the definition you cherry-pick in full is:

       ::to prove; demonstrate: His experiment showed the falsity of the theory. ::   

       It's possible to prove a theory wrong with a single experiment or example; it's not sufficient to prove something right!   

       Not a peep on the main body of my post I note - you know, the bit which blew your insulting denial that the law becomes 'guilty until proven innocent' out of the water.   


       //I'm sorry, I must be missing something. But isn't every steganographic message accomplish exactly that? In the Wiki example, they have a winter forest landscape that becomes a picture of a cat. Surely that would cover your idea?//   

       I don't really understand what your asking here. You might well have missed something.
With steganography, one hides a message - encryption is not necessarily involved.
A one time pad encrypts a message, and must be random (unguessable) data. However, it itself looks like an encrypted message, as there is no way to distinuish 'random' from 'encrypted'.
My proposal here is not to hide a message, but to make it clear that there *isn't* a hidden message.

       I actually looked quite hard at that tree/cat image, as it occurred to me that this might also be a way of showing that there wasn't a hidden message - by putting together a whole set of very blatent messages. Suppose that one had several photos - one could take the top bits from each one and merge them together. However, I'm not sure this would be sufficient. If one discards the original photos it may be claimed that you've inserted coded data at a low intensity. While if one retains them, they become the source of suspicion.
With my proposed system, one would be dealing with blocks of colour, and could attempt to avoid any process which introduced suspicious-looking signals. (Although I'm not entirely convinced this would be sufficient.)
Loris, May 09 2009

       I think it's a minor triumph that I managed to remain as civil to 21 Quest as I did thoughout this conversation, so it's probably for the best he's given up.   

       I am happy to continue discussing this with anyone else.
Loris, May 10 2009

       Your restraint is admirable.
I would discuss this with you if I could. Alas.


       I could whip up a Lawyer/one-time-pad joke though if pressed.   

       A few words on the Patriot Act -   

       I have always been of the opinion that any government should have the means to exert absolute control, yet exert said control to the minutest degree required to maintain the safety of the citizens. Filtering digital communiques for words like "bomb" or "Jihad" is, in my opinion, a perfect application of said philosophy. These "moderators", if you will, have neither the time nor the inclination to read your private emails for a good time.   

       That, and can you really expect privacy of information you are broadcasting non-directionally through EM radiation?
MikeD, May 10 2009

       //I have always been of the opinion that any government should have the means to exert absolute control, yet exert said control to the minutest degree required to maintain the safety of the citizens.//   

       That's interesting.
I have to say I disagree though. Where power is available, it does tend to be used. Absolute power corrupts absolutely, and all that. I'm in favour of a system of checks and balances.
Loris, May 10 2009

       //Absolute power corrupts absolutely//   

       Only AC power can corrupt absolutely, it provides the necessary degaussing effect.
bigsleep, May 10 2009

       I have the same worries as you do re: Privacy. I think the RIPA, and similar, are abominations and generally unconsitutional, whichsoever constitution you are obligated under. The right to privacy exists for all.   

       This process fails under the assumption that "random" images are random. Truely random strings exhibit an H (character entropy) of zero, courtesy of CE Shannon, over any metric. Obviously the problem of determining random from "random" images is hard, see L van Hahn's Captchas.   

       Still this is better than your last, but still not good.   

       I applaud your intentions, just not your implementations.
4whom, May 12 2009

       //This process fails under the assumption that "random" images are random. Truely random strings exhibit an H (character entropy) of zero, courtesy of CE Shannon, over any metric. Obviously the problem of determining random from "random" images is hard, see L van Hahn's Captchas.//   

       It may fail on the randomness requirement - but it isn't obviously so, since the image isn't used directly. Firstly it's compressed - remember that perfectly compressed data is indistinguishable from random. Secondly, since the compression wouldn't be perfect, there's scope for using a hashing algorithm to remove the remaining order. The goal would be to produce a random string - in the Shannon uncertainty sense.   

       Presumably you mean Luis von Ahn regarding CAPTCHAs.
Loris, May 13 2009


back: main index

business  computer  culture  fashion  food  halfbakery  home  other  product  public  science  sport  vehicle