changing base

One of the things one learns in communications courses is how to reason with such as power, spectral density, rates per unit bandwidth, and… overall… how to invoke a very “engineering-oriented perspective” focused on ‘signal spaces’ and associated geometries.

The thing one learns AS SOON as one embraces quantum computing models is that it is the “change of basis, stupid!”. Only those who know the key (i.e. the required set of ordered basis changes) can distinguish a signal set from a random noise sequence. One is not in the business of ciphering. One is in the business of making things indistinguishable.

Typically, we learn that any signal set can be reformulated into various bases. In particular, one eventually learns HOW useful it is to use the fourier basis…as the basis for one function. This is like taking the typical world view of the globe drawn from the US/UK perspective and now looking it with Moscow or Beijing at the center. It looks different!

One of the reasons in the electronic engineering world one counts weight bits (the number of 1) is to ensure that the power associated with 1 bits is “discrete”. But, since we are counting weights, we might as well consider spectral issues in general – which is where the fourier basis ideas got us, anyway.

So, now consider JUST how many non-zero amplitudes there are in the spectrogram. Consider THESE values much like the 1’s in the common-basis. They represent the “support” of the function, in its fourier basis; aping in some ways how a particular frequency band “supports” electronic engineering signals under the sampling theorem.

Now, we recall how in quantum key agreement protocols folks exchange instructions – which pauli matrices to use, to flip bits in each of the several bases. That is, we are using basis change to confuse (or rather deny) the eavesdropper.

Even in the classical world, we can be changing basis, by changing the fourier coefficients – presu/ming that ONLY legitimate parties know how the basis changes.

Posted in crypto

PingFederate ws-trust server – sampleSTSClient_WSE3

In our last memo, we made a few lines of code talk to the ping federate server using the ws-trust protocol. Ping Identity itself supplies an “enhanced client” and demo program  for doing the same thing. Let’s make it work – doing the simplest of PRACTICAL things.

First compile the sampleSTSClient from the Ping Identity supplied “dotNet ws-trust library and sample App” distribution. Use visual studio 2012 express and run the compiled build in the single stepping debugger. Now copy from the distribution’s bin/ directory its XML subdirectory and associated content files. Copy this set of files to the bin/ directory created within the source directory of the project – created as a resulting of compiling, above. A little XML reader in the program will read “unit test” descriptions from files, to be named via arguments on the command line. For example for sending a username token over SSL, we changed the XML\Prms_UN_SSL.xml file as follows:

image

We changed the URLs (to use https), domains names to localhost, ports to 9031 (SSL), and the name of the appliesTo parameter field to the actually name of the already configured SP partner of the IDP to be doing token minting for us. (This is a required fix, note.)

To orchestrate the debugging, etc configure the debug tab –  using e to identify that one wants the “enhanced” mode unit test and a file of testing parameters – relatively named.

image

The enhanced client is configurable. So, we duly add a line to configure the ignoring of the default set of client-side SSL trust exceptions handling:

image

We get as client side output a success case – in the sense that a minted token is obtained and then printed to command window – having been minted by PingFederate in the very same demo setup as earlier trials.

image

Simple. Not worthy of a moment’s attention by a websso engineer, of course. Also, to be 100% ignored “as years out of date” by current standards architects arguing about this year’s blob format – and probably to be actively scorned (as not being in vogue with the latest thinking). But, when building _confidence_ in a programming team trying to APPLY or RUN websso systems as COMMODITY infrastructure… its absolutely golden. 

Know the likely gotchas; know how to configure around them; and know how to diagnose so one doesn’t walk into walls that seem insurmountable except by “experts”. Then you defeat expert-itis (and all the dogma that typically goes with it). Then, you retain your independence. You can focus most of your effort on your app that is applying websso vs. arguing about websso protocols themselves.

Posted in pingfederate

PingFederate 6.10.1.6 ws-trust username token trials

The Microsoft ws-trust features of WCF makes life hard – if all you want to do is simple username token versions of ws-trust security – swapping one token for another. WCF wants one to wrap even the act of accessing an STS service itself invoke an instance of ws-trust (forming a bilateral secure channel, over which a RST is sent). This all gets in the way – as so many elements of procedure have to be perfectly specified.

So lets’ document how we made the PingFederate solution do something simple (and quick). All we want to do is have a web services client in an ASP.NET page – hosted in the cloud – make itself a username token, use a local STS service to convert that into a saml token, and then send said token in a SOAP header to a WCF web service that is to interpret the inbound token as part of its access control decision making.

Let’s try to just get a soap-ready saml token minted. First, we use the demo web application supplied for the username token toolkit – to give us “something that works”.

First, install and configure the ping federate server. Simply follow instructions; and then install the “username token” demo web application (into the jboss instance hosting the PF application, too).

image

image

The issuing process works out of the box:

image

Per instructions, paste the “extracted security token” content into a notepad file. Use this file with now a validate “request type”. Don’t forget to change the service url fields value – replacing “idp” with “sp”. Though we could be asking our (SP-side) STS to issue another (binary or saml format) token given the saml token provided as input, here recognize we just want the SP-STS to issue a yes/no answer concerning the validity of the inbound token. Hence, we invoke the  validate verb on the SP-STS endpoint.

Since the token signing certificate in the uploaded PingFederate data zip expired in 2012, correctly the STS will return a (negative) verification message – which will raise the associated exception.  So, update the certificate. Create a new signing credential with attached certificate and assign it to the  ISP-STS’s outgoing “SP connection” – so its used for signing the IDP-minted token. Export the cert to a file, too. Import it into the “IDP Connection”, so the SP-STS can verify  many token signature referencing the certificate. Note that when using the web application that now a “valid” report result is issued (vs. an invalid report) upon invoking the validate method.

Now install visual studio 2012 express. Also install Ping Identity’s  “.NET toolkit for ws-trust” – which provides two client-side programming libraries that wrap the raw Microsoft-provided “WSE3” libraries. Update the library references in the various build-able projects. Obviously, also download and install WSE3 2012 edition, from Microsoft’s site.

Using the existing unit test project for the libraryies as our baseline, we started with a simpler test – aiming simply to repeat from our programmed client what we just did from the client built into the username token kit’s web application.

image

Here are a few gotchas to work around – to do JUST that. They are good teachers – showing one how to diagnose issues and solve them with new configuration. All PRACTICAL skills.

We used client side code listed in the library’s help file (see below). It’s configuration doesn’t quite sync with the settings the demo of Ping Federate for username tokens has …for potential clients.So, We made some modifications to the client-side code to align things with those demo settings (see above). We changed the URI domain names (obviously); and then we removed the need for our own client to cite basicAuth credentials to gain access to the server endpoint of the layer 4 transport channel. (I.E. Let’s remove all that which is not needed, since the Ping Federate demo did not happen to require transport-entity authentication.) Obviously, we keep the username and password parameters (!) supplying values for the layer 7 token into which the username and password values are inserted are named fields.

image

On running the code down to the IssueToken method, the log file of the ping federate server indicates no change – no message is “handled” that is. And, a client-side exception is raised – indicating that the transport channels https/SSL tunnel could not be established (probably because Ping Federate is using a self-signed SSL cert, or because the CN field in the cert does not match what is expected by the client, given the local socket’s report).

We added a new requirement  to the client side configuration (allowing the Client to so configure WSE3 so as to ignore certain SSL transport layer errors due to certificate/naming issues):

image

As a result , we can now form a demo-grade https connection between the client and the PingFederate server. Over https the expected request is now both sent and received:-

imageimage

The message response emitted by PingFederate  server over the reverse https channel causes the client library code to raise an (associated) local exception:

image

Using the PingFederate console, we augmented the list of user/passwords that the username token password processor can recognize – obviously adding our own “user/password configuration element” to the IDP’s token processor instance.

image

Modifying the code to cite the new username/password combination, we do now get a back the desired SAML (signed) token :

image

 

whose id aligns with the log file in pingfederate – recording its output message:

image

image

The log nicely aligns with the client side records – having parsed (and presumably verified the signature of) the returned token.

image

But, at least something works now works, and we have a clearer mental model on what the library does, what  role WSE3 continues to play, what ping federate does in hosting token processes, what the token generator does, and how to configure it all in reality. And it works in a manner that just naturally expresses the protocol one is trying to invoke.

Presumably, we can now go about configuring a WCF service that can process the inbound token.

Posted in pingfederate | 1 Comment

decoding dot Net claim rights

image

http://msdn.microsoft.com/en-us/magazine/cc948343.aspx

Decoding Microsoft security is almost as hard as decoding Tunny speak. But, we can remember that different teams get involved – and that gives us a hint. Folks building the TCB of the OS are different to folks building distributed systems using a few libraries OUTSIDE the security policy of the TCB.

In the original dotNet model of Claims, we see the TCB concept – code and classes projecting the OS’s reference monitor’s (security) types and type theory.

First, you describe the token you would like – in the form of a claimset. Each claim has name and value. But, the user of this descriptor also makes a meta-statement about each claim – that he has the “right” to assert it – either as an “identity claim’ or “I possess this property” claim. For example, I may have the right to assert a mere ‘property’ of my identity that: my purchaseLimit is 5000. I may also have the right to assert a given claim as being the fundamental (unique) “identity claim” itself. IN short, properties go on the SAML authorization statement claimbag, whereas the identity claim goes in the subject name field

The way the TCB comes into the picture is that windows users already have a security token (issued by the TCB) attached to their thread. Before the descriptor of new tokens can be induced to mint a new blob (now in the SAML blob format say), the TCB may check one’s assertion rights – enforcing the correctness of the to–be-asserted claim types/values. Its pre-validating, if you will, converting from the (valid) TCB token (and its content) to the form of a “SAML token”.

Once a receiver  gets a hold of the SAML token, it may verify it (using some or other confirmation procedure). Typically, this is not a TCB-based method – since the token  in its SAML form – is NO LONGER under the control of a (distributed) TCB.

Now , in the WIF model of claims, all this TCB-ness gets hidden. One gets simple descriptors, token makers, callback verifiers – suitable for layer 7.

Posted in ADFS, SAML

interpreting Tunny text

 

image

http://www.alanturing.net/turing_archive/archive/t/t03/TR03.php

I find it really hard to tie such abstract description with what folks are doing with pen and paper, with depth information, to find wheel patterns.. Lets try to assign interpretations, though.

The notion that a probability can be a LLN score is straightforward. We can be counting chars or bits of chars on a tape and thus forming relative proportions; which the LLN curve turns into deciban scores.

The notion that we have conditional probability is also straightforward, as is the notion of odds. We are interested in a world we have two hypothesis. One is the null case, – and it’s the one we are interested in – being the needle in the haystack. It’s the key! that makes the stats for that keyed function stand out from random Y.

In the sense of lesbesgue integration, we also want a notion of limits – in which we squeeze the horizontal band around a particular probability value. This means that several parts of the curve are “selected” – and contribute likelihood measures. These are the periodic contributions a given bit on a given Chi wheel makes, to (an impulse of) Y. The collection of these is a “depth”.

We can be imposing the interval e around a particular value = 1/2 or the maximum likely probability value (given the depth evidence). We then squeeze it.

We have the notion that we don’t know the key (i.e. the wheel bits); which have unknown a priori values in the conditional relation between wheel bits and Y/Cipher. We do have the world for a given Chi wheel’s pattern of bits that it contributes a particular bit to a given char of Y. Obviously, 4 other Chi wheels contribute bits to that Y, too. But, in probabilistic sense these only contribute measures in a gross statistical sense (in that all Chi wheels periods treated together have their combined signature). IN these sense the other 4 bits in a given Y char are witnesses – of an “unreliable” sort – because they did not actually ever see the bit from the Chi wheel we are focussed on. They saw it only from afar – because they are in an overall relation to the reliable witness. 5 wheels taken as 1 of compound period likewise do relate to compound evidence.

A sequence of depths – each value of which is a sample d from Y at the period of the Wheel – form a series – in the sense of a markov chain (for that wheel bit). We have a series of reliable witnesses (to each of which there are upto 4 unreliable witnesses, too). IF we assign a characteristic measure to a given reliable witness, then for some fractional base value for the “custom LLN”, one has k “atomic measure values” conjugated by the characteristic measure for the wheel bit (in evidence space). In the LLN space, one can just add the scores, or multiply them

Ok. 98% bullshit, but its hard! Folks are using sampling rationales and advanced limits – but actually speaking in parables.

Posted in colossus

from hamming weights to symmetric computing models

image

John Savage

http://cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation.pdf

note the use of the ripple counter adder. Feels a long time ago that we wrote https://yorkporc.wordpress.com/2011/03/05/double-ripple-to-skipjacks-lfsrs/. No idea what the skipjack reference in the title was about though (given the content!).

Posted in early computing

lets project to a 2 T/bps io rate for cryptanalysis

image

http://arxiv.org/pdf/cs/0504020.pdf

image

http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2012/20120822_LDPC%20Tutorial_Module2.pdf

SO the FPGA you buy in the supermarket is happy to do, per unit, 300Mbps.

1970 –  1 rack at total 2Mbps (for 2**6 states)

1990 – 8192 VSLI units, at 1Mbps per unit. (or is it a combined 1Mbps for 2**14 states)?

2010 – 1 FGPA with 9000 LUTs, with 300Mbps

so if NSA puts 8000 FGPAs in a room, this presumably gives it 8k * 0.3G = 2.4 Tbps

Now that’s going to produce some heat. So stuff it in a school bus sized satellite, and operate in orbit. Its going to require some power – so obviously have some solar arrays. Now, one has to make rad-hardened chips of course, in NSA’s own fab using the same kind of low-intensity radiation process that I used to see applied to process make frequency or power-sensitive cut-out chips.

Now with that kind of rate, one doesn’t need an uplink with that capacity – of course- merely to offload work tasks. One launches that when one want to double one’s processing power (during some war period, for example); or get raw video codec capability to the mobile theater of operations.

Now, would the backbone bus of the satellite itself be wireless!? at least between units of a 100 chips, say? Why not?.. given its got spread spectrum jamming countermeasures builtin?

Now the point here is not IF – but that its commodity. So, now project forward 20 years ahead, and see what folks are doing with non-commodity technology (at horrendous cost). Well, obviously 1 order of magnitude of difference gives 20Tbps – just for cryptanalysis purposes.

so how hard would it be to get 8000 laptop PC with wireless-N to cooperate – reusing the wireless card for cryptanalysis? Well, since there are easily that number of laptops in the DoD, presumably it’s a minor task to leverage the office PC for cryptanalysis, since its probably only operating a 802.11b data rates anyways 99% of the time.

can one imagine the US, given broadband always on connectivity, requiring that home PCs “cooperate” to the ‘national grid’ (of cryptoanalytical capability)? why not? Well I suppose the answer is that any nation could then do it.

Might be better to stuff the FGPA in the “smart meter” on the home, so it can double up as a spying point on the citizen AND provide “LUT resources”. My home now got its own smart meter, last year. Of course, I had no say in its installation….

Of course, everyone has a digital TV box too

image

http://arxiv.org/pdf/cs/0504020.pdf

Presumably, that 10**15 or a 1000 terabits/s is a cumulative number.

Posted in crypto, early computing

From Turing H matrix to Tanner automorphisms

image 

image

image

image

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.48

Tanner et al’s paper makes it much clearer what Turing was alluding to – in his On Permutations manuscript.

For 2 generators, and 2 ring sets of varying number but constant size that combine to fully map the periodic space, we can now see why Turing used his own version of the following diagram:

image

image

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.48

The labeling of the rows of the matrix in the manner outlined by Tanner et al as rows also maps onto his “cosets” – only one of which impacts a particular factor given it’s the parity equation for that local factor.

Posted in coding theory

1996-era NSA flash; quantum coding

Now I look back at (missed) signals, I can see now that certain of those engineers who left NSA to “start a career” outside government (as part of the internet bubble of the late 90s) just happened to land in the flash business – or rather that world of DRM-enabled flash controllers that were supposed to enable the likes of a “militant” Sony to find a trusted point on the PC (through which to deliver controlled content).

The nature of magnetic media is that it’s a probablistic material, per se; and has been since the late 1940s when the first magnetic drum memory came out (presumably after having been applied to the likes of the next generation colossus, replacing the paper tape as the medium for cipher depth information). These days, the semi-conductors that make up high-density NAND flash has similar physical properties – in which the material itself is dynamic (and probalistic).

We can assume that NSA was not only looking at high-density storage (for the obvious application), but at the material  properties itself as a “unique” computing platform, specialized to ciphering/cryptanalysis. And that means in deterministic computing (vs the stored program computing).

If we liberally assume that a national security agency had 20 years ago for $10,000 a chip what we have now (for $10 a flash chip from the supermarket), lets have a look what “todays research” might tell us – about 20 years ago. And, assume the bullshit about MIT/Gallager forgetting capacity-reaching coding is just that – a deception/misdirection ruse.

First lets assume one has a unique “controller” design , in the flash chip. Its not just a small intel-type die handling IO. Rather, its tuned up for the nature of the silicon used for memory. Think of it as a giant parallel processor, handling a megabit array. As always, one has to break down the problem in n smaller “local” functions – so as to leverage the parallelism and scale the computing method.

image

image

http://www.comm.ss.titech.ac.jp/~kenta/doc/ISIT2011_CSSNB_slide.pdf

What’s interesting is JUST how fast we shifted  – to quantum coding.

Now, if we look BACK to a “more obviously” quantum world of memory, we only have to look back to the first effective RAM: the williams tube, of course. As the article implies, the nature of the process is inherently “quantum”:

image

http://www.oldcomputers.arcula.co.uk/bhist7.htm

Posted in coding theory

practical LDPC in flash; Turing decibans

image

http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2012/20120822_LDPC%20Tutorial_Module1.pdf

There is just something practical about the material above. Where-ever one sees math arguments about metrics and measures and inner products, realize that the curve above is just translating a simple probability into a particular scale (LLR).

The whole ban/decibel/odds issue becomes rather obvious (and one doesn’t need a genius mentality or obsequious British attitude to WWII crypto history). If you just think like with Lesbesgue integration (i.e. horizontally vs. vertically) the range of probability from 9/10 down to 1/10 is a range of 40 dB on the LLR scale.

image

http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2012/20120822_LDPC%20Tutorial_Module1.pdf

If n1 sends -10 decibans, it is indicating about 0.3 probability (i.e. 0.2 bias from the mean, towards 0/false). Makes the description of “colossus wheel breaking” rather easier, no?

Be interesting to try and think WHY the tunny description was so convoluted. May be because the notion of odds wants to contrast the probability when the hypotheses vary : 0 against 1. They were “Thinking” more in terms of the conditional probability of a bigram of 2 bits, that is, wanting to tease out the marginal distribution.

 

image

http://www.alanturing.net/turing_archive/archive/t/t07/TR07-011.html

As the Tunny text says, folks worked with crude sign-excess metrics (rather than the magnitude of the soft-evidence, directly). The flag plays the role of the initial APP, form the LDPC channel’s coding. It is soft-decoding, however; but with excess of signs playing the role of the likelihood ratio.

concerning Modern colossus “chips” (i.e. flash and graphic chips):

image

http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2012/20120822_LDPC%20Tutorial_Module2.pdf

Posted in colossus

klein groups, xor’ing complex numbers, quaternion units, quantum instructions; DES The Decoder

The article at https://yorkporc.wordpress.com/2011/09/08/bigger-klein-groups-using-tunnys-addition-square/ makes an interesting observation, circa 1945. Things tend to be rather recursive – whether it’s the representing the elements of the Klein group using bit patterns from the Tunny era, or representing the Walsh-Hadamard transform as an in-place (1945 digital storage-friendly) butterfly process.

Complex numbers are also fun, since its just a funky point – with 2 components. If computing, its an array (of 2 elements). If you have two complex numbers, guess what you have 4 terms (just like the klein group).

Now what’s interesting about the klein group is that the relationship between the 4 terms is not like 1,2,3 and 4. Its rather more like a tensoring of 2 bits (each obviously with 2 possible values). When considering bit values, think more like 1945 (where the typical valve circuit has +300v, 0, and –270v lines). That is (in computer science vs. EE conventions) 0/false is –1, and 1/true is +1. So Xor (or bit flipping) is the operation of multiplying either by –1.

Now it just so happens that the quaternion group has (-1,1) as its units. The interesting thing about quaternions is that their nature – in the text book 0- is such that they are rather like the “group presentation” relations – that define a cayley graph. Oh, and being a non-commutative group, one needs a binary oscillator to round out the notion of universal commutability for graph/subgraph relations and all manner of other things to do with isomorphisms in category theory. The unit bit-oscillator (0,1), (true,false), or (-1,1) – who cares – nicely fits the bill.

Now from complex number and quaternions we easily get to quantum computation – where we remember the every basis has its bit flip – whether it’s the computable basis or the phase-space basis (or any other!). What’s more, the pauli matrix representation just happens to have 4 operators (including identity) – which one can think of a generic instruction set – gene-sequencing bit-flips (in different bases) or even (for the klein ab term) a multi-flip (in two different bases)!

If you are a Turing machine (or just a Turing, since it’s the same thing), you might want to be generating instruction sequences. If you insist that they relate to circle-free (cayley) graphs, your “decoder” might be better though of as an “instruction execution” machine – for multi-phasic bit flipping, for some unitary basis.

Bit flipping is interesting when decoding – particularly in a data flow architecture like that for DES – where bit flipping (i.e. xor) is the only operation one has.

.

Posted in DES, early computing

colossus/tunny mutual information for wheel breaking

In the article at https://yorkporc.wordpress.com/2013/03/05/free-groups-colosssus-forgetful-functors-categories-erasures/ we stated our core ideas on how colossus-era wheel-breaking processes related to LDPC convergence, during sum/product algorithm convergence. In the latter, our mental model is one of a particular hilbert-space filling curve – where the curve is a tree whose branch growth(s) seek out the space of the incoming vector of APPs trying to maximise the mutual information of terms and thus best-fit the evidence. Of course, a side-effect is identification of the wheel bits – whose mutual constraints guide the heuristic search.

If you like, the process of adaptive-search is similar to the process of hugely expanding the number of neurons and their inter-neuron connectivity – in the first 3 months  of post birth life. In this process, potential neuron connectives from newly manufactured neurons have to compete to survive and occupy a particular space – having better adapted to (a) being an effective element of the  visual processing for one of the eyes (say), or (b) having better learned/adapted to the fact that mom approaches the crib from from the left (say). The amount of usage made of the winning connective reinforces its use (and thus directs its survival). Or as someone else wrote

image

image

http://www.jstor.org/stable/40180239

http://www.personal.psu.edu/faculty/e/c/ecb5/Courses/M475W/Readings/Week06-IntoTheTwentiethCentury-10-8/Supplementary/What%20Turing%20did%20after%20he%20invented%20the%20Turing%20maching.pdf

In the case of Tunny (or hagelin!) wheel breaking, we can view a round of rectangling as equivalent to a round of belief propagation in LDPC decoding. Since the actual computation of the apparently-parallel processing performs by decoder nodes are/is actually serialized, there is thus a tree-based ordering to the computation – reflecting which combination of possible sum/product terms in the ever-expanding algebraic-tree best model the mutual information of the incoming APPs. But if Tunny and LDPF are analogues, what are the Tunny-era parity checknodes?

One has to remember that a wheel pattern in Tunny was constrained to have certain legal forms by the designers of the ciphering units. These wheel pattern “rules of formation” can serve the semantic role attaced to parity constraints. Just as for an LDPC individual APP per decoding symbol’s bit and its APP, one can look at any one Tunny-era wheel bit as coming into a fit with its particular depth information. But, moreover, we can look at “bigrams” of neighboring wheel bits. Just as in in LDPC where any any (typically neighboring) lambda-number of symbol APPs have edges in the constraint graph to a common parity check node, so we can look at the rightmost neighbor of any 1 wheel bit as its parity checknode. Similarly, for the left neighbor of the same wheel bit (which thus has two neighbors – one to the left and one to the right, allowing for ring wrap-around). Thus there IS an edge graph from any of the wheel bits treated as intrinsic information to (2) parity check nodes – to which extrinsic information will be sent, by round-based message-passing. By definition, any 1 parity check node ( the right wheel bit, say) has two incoming incoming edges – since the right wheel bit receiving initial information from X is the left wheel bit of some Z also with initial information.

So, essentially we have a (2,2) bipartite graph in Tunny, where the wheel bits double up as parity check nodes.

On a sidenote, its interesting to also see in DES the keybits form the key schedule playing the role of the parity checknodes – treating DES also as a derived LDPC/Tunny-like a convergent process..

Posted in colossus

free groups, colosssus, forgetful functors, categories, erasures

If we assume that Colossus era cryptanalytical attack on Tunny was an early form of the belief-propagation algorithm, let’s state the obvious parallels with modern theory.

To each wheel bit, when wheel breaking, Colossus cryptographers would assign confidence measures. If there was insufficient confidence, the bit would be viewed as an erasure.

Lets assume that wheel breaking is a BP decoding. As such, the goal of finding a covering bi-partite graph by message passing is to model the conditional probabilities using a tree. One is performing a kind of mean-graph convergence.

Now trees and free groups are related. In category theory of course, sets are the bastard child rather than the prodigy. One would much rather be dealing with manifolds of space as domains/ranges, with a space-time process to connect them. But the free group being a forgetful functor, in the group/set sense, does map onto the idea of creating sets of erasure channel – erasing the noise to leave the faithful structure in the form of the graph that corresponds to the functions that the graphs’s nodes support and map onto R.

On some sense, we see Turing/Newman using their topology understanding to create a detector for the tunny distance signatures, to find those wheel bits that most nearly model the generators of the linear part of the tunny machine in a consistent and faithful manner.

Posted in colossus | 1 Comment

DES design criteria

From http://www.ciphersbyritter.com/RES/SBOXDESN.HTM#Kam79

If one assumes that the graph-inducing flows of the DES transposition aim to (i) project from the least bit, (ii) project from the last bit, and (iii) bias the production of paths that accumulate late, then it makes sense that one would protect DES by ensuring the reverse s-box shows maximal non-linearity (and thus distance between elements/vertices analyzed/labeled now as a G64 field

image

It also makes sense that the s-box “registers” are not acting alone, particular given the nature of the expander graph, seeking to make state dependency on keybits subject to belief propagation minimization (i. uncertainty is minimally affected by a round)

image

Let’s not assume that the s-box design knowhow was specific to DES’s particular flow-graph, in its final form. At the same time, the following is very “intuitive”

image

We have to remember the NIST claims about DES – that ultimately the nature of the problem they saw themselves as measuring was whether an attack DES was as hard as brute force search.

Posted in crypto

density evolution, and stability condition

image

image

http://arxiv.org/abs/cs/0511100

The description of q-ary LDPC reminds of Colossus (theory). In colossus one “parity expressions” (i.e. run) was computed at a time – using a short wheel run. FThe parity expression was the “character class” that defined the run. (search for all cipher positions where the character is in class C, and count one). Then from those counts the “weight of evidence” could be computed. Practically, folks just ran every possibility (in O(n2)). Theoretically, they remarked how they COULD have been using convolution of each message (i.e. each 5-bit char of the cipher tape) computed using the fourier transform. AS they remarked in 1945, Fourier transforms can be easy to compute, in certain cases – exploiting dyadic forms and sign/magnitude thinking.

in LDPC, we see each parity expression implemented by one (q-ary) checknode as “one colossus run”. Does that mean then that one should see a series of (user-selected) colossus as a series of LDPC condition nodes? .. in which certain char classes “combine” to tease out the posterior measures more effectively than other run-sets?

What is most interesting about the paper is the way in which reasoning associated with message component permutation  due to “edge labels”

Posted in coding theory, colossus

balanced gray codes; fractal bifurcation

image

image

Balanced Gray Codes – The Electronic Journal of Combinatorics

the reflected gray code, with bit position 5’repositioned to the middle, was used in the attach on Tunny. From the spectral map, the trained eye could see from the patterns of ordering errors in the spectral relations which setting of which tunny wheel (1 per bit position) was not correct.

In the world of ciphering on the other hand, looking for “suitable” binary functions for use in s-boxes requires for countering differential cryptanlaysis that 1 bit change of input does not lead to an approximation cue in the output differences – by virtue of 1 bit change (in i) inducing a 1 bit change in every possible j, for some code word. Furthermore, back to spectral ideas an ordering of the weight partions of the codewords constrains the paths the random particle follows through the graph to those that induce the weight-production avalanche – a fractal bifurcation.

Posted in coding theory, crypto

higher commutators, 1944

image

http://www.ams.org/journals/bull/1944-50-03/S0002-9904-1944-08081-6/S0002-9904-1944-08081-6.pdf

Turing’s 1938 work at Princeton on approximating lie groups with discrete groups can be seen as a payoff for his American grant; and we can now see it had clear links to cryptanalysis and decoding theory (think Sigsaly). Princeton’s role in national security research is obviously long standing.

Turing’s work showed how to use coset representatives in the kernel of decoder, working to minimize the distance squared in certain groups (what we now think of as QAM). One has to remember that valve amplifiers of the day implement continuous functions. On the other hand, rotor machines more clearly map onto groups – or at least those groups for which the conjugate is the same as the normal product.

Baer more clearly outlines the distinction between normal and characteristic: being about inner automorphism (conjugation, in the enigma and sigaba rotor sense) vs all automorphisms. Back in 1938, Turing is concerned specifically to leverage both factor groups and the group formed by the product of coset representatives, note.

Posted in coding theory, early computing, enigma

weight, distance, bent’ness, non-linearity and a field full of 100MHz FPGAs

image

image at

http://www.srccomp.com/techpubs/docs/NPS_BentFunctionsFastWalshTransform_1210.pdf

charting non-linearity against weight (distance).

Posted in crypto

strong law of large numbers, group version

image

image

See http://arxiv.org/pdf/0904.1005v2.pdf

Assuming Natalia Mosina is a she, this co-authored paper is rather different in tone to her PhD thesis. But, in general its topic is complementary and supportive to our work to comprehend all that Turing was discussing in his On Permutations manuscript (and why he was discussing it).

image

composite of other authors’ works. My annotations.

whereas Turing used

image

http://turingarchive.org/viewer/?id=133&title=28

g(a) is played by image and k(a) is played by the atomic probability measure image(a functional form of relative frequencies) .

Obviously, both forms have the notion of distance. Assume g-bar is played by k-mean.

Notice how the partition function is based on a weight/distance ordering relation.

Posted in coding theory, crypto

cryptome’s pointer to Google SSL

image

See http://www.imperialviolet.org/2013/01/13/rwc03.html via cryptome

Langley makes the detailed point that if you take a higher end motor in an expensive car, designers can argue whether or not swapping one material for another in the fuel injection components may or may not improve driver performance (by 10E-19 points). And  indeed, basic science is acheived by the search for such rare elements.

But, there is no point fixing such rare improvements if the road is full of potholes, the typical driver also on the same road as you in your super high-power crypto-enabled car is not wearing his glasses, or the funding for roads from road taxes got diverted to pay for the police officers’ $150k a year pension plan – part of their compensation for the public service of doing traffic control (and seeing lots of screams as folks are pulled out of wrecks) for 30 years.

In short, commodity crypto is different problem to military crypto. There is no point applying research methods suited to the latter to the former.

Now the author gets this, clearly, but fails to state how to approach the shift in thinking.

Remember, governments aim to spy; and thus are perfectly happy to rig the infrastructure so the “usual” quality of crypto results. One doesn’t have to try that hard; all one has to do is give good crypto to generalists and prevent them from ever improving their skills and knowhow; so engendering on average trickle-down crypto. That is, broken crypto; broken (as the author says) when failing to be intended to act as a definitive “cryptosystem” – in which all parts interlock at equivalent levels of assurances.

Posted in rant

from 1920s mean-sets to RSA; and back to enigma menus and weighted edges

image

http://www.gbv.de/dms/tib-ub-hannover/663263735.pdf

 

Turing is known to have wanted, in circa 1939, to multiply two numbers in such a manner that its computationally infeasible to know one of the factors (without special knowledge). The phrase infeasible means: its takes longer than the time-value of the information being ciphered; an example being the submarine will on a certain positional line of subs at 9am – all spread out along said line hat acts as a probabilistic dynamic-search pattern for some wandering Atlantic convoy. Ignoring the storage-value of the information distinct from the time value (the possible positions of subs “next week” is some averaging function of “now stale” time-information from last week), note now that to a Turing multiplication does not necessarily mean its computed in the real space. A “long number” MIGHT be a long series of random variables, and multiplication MAY mean conjugation.

It was interesting to see Hodges (a math type) try to deflect modern UK audiences on this, in his book that discussed the historical context of the crypto idea. Hodges seems to fail to appreciate just how much Turing is fascinated with such as Hiesenburg groups (and the associated principles of operator co-variance and uncertainty), how much a fellowship study on the guassian error function just happens to align with with 1920s theory of mean sets on cayley graphs, etc, and asymptotic properties of long sequences of random variables

So, in short, an enigma rotor is inherently a conjugation mechanism. When you apply 1 rotation R operator (associated with the first letter ‘a’) to a U set of permutation cycles, you conjugate all of U (by a). Rotate again, you conjugate UR by ‘a’, too – which is the same as conjugating U by ‘b’ (i.e. URR). Using publickey terminology, if s is a secret-key (that which you conjugate U by, i.e. the number of core rotations) then some published public key (some number w and w-conjugated-by s) can be used much as they are used ARCHITECTURALLY in RSA.

So did the Americans (i.e. Diffie) really invention the “concept” of public key crypto?

now, if one has a rather large graph stored in NSA’s petabyte of RAM set for each bit in an RSA key, can the RSA math be modeled as a mean set?

lets remember

image

https://yorkporc.wordpress.com/2011/09/26/enigmatic-graphs/

which is variant of the principle of considering the difference between a sample average and the theoretical average (of a mean set).

Now to be fair (unlike an American propagandist), don’t we recall the 1930s US signals corp, when working with polyalphabetic mechanisms, requiring the daily indicator to be set and the operator thereafter to rotates then mechanism n times using a particular zero key (to compute a checksum, that is compared to a table)?

Posted in early computing, enigma

complex vs real values (even for complex fields)

image

http://turingarchive.org/viewer/?id=133&title=28

In his On Permutation manuscript discussing certain topics of Group-based crypto, Turing’s first mental model was to use complex-valued functions (as in QAM). As we learned from Galagger’s MIT open course on modulation/coding, one can be reasoning in a 2d complex plane yet be embedding it all in a real Euclidean “value” plane. It can be quite profitable to do this, as we shall see, when one works  with computing machines that are doing computations with specifically discrete algebraic expressions.

This is not the first time Turing has considered groups, group-centric averages, means (of groups) and complex-valued functions. Citing J.v. Neumann…

image

http://turingarchive.org/viewer/?id=467&title=02

…Turing has considered not only how well a particular (finite) sequence of N terms can be summed and distanced form the average to form a classical limit statement but how summing a finite process can be contrasted with a mean based on integrating a continuous variable.

In the context of the on permutations analysis, what would the difference have been if it had been considering complex-valued outputs? Well, in modern terms, what Turing was doing was mixing coding with modulation (he didn’t see them as different processes, being a pure mathematician). With a complex space to represent a probability measure (for converging/limiting sets, treated asymptotically), he would have more obviously had the tools for distinguishing those correlations that are tractable only in common vs. the quantum protocols.

Now that we have references for “limiting distributions” from finite state machines specified as cayley graph, Let’s review the basics of graph theory and generators – as Turing would have been taught them. Particularly, lets focus on complex cases of generators, involving the quaternion group.

concerning

image

http://www.jmilne.org/math/CourseNotes/index.html and the link pdf specifically

image

The cyclic group leads to enumeration of a bi-infinite series of elements. It also obviously indicates that a single generator can do all this.

The dihedral group introduces the use of two generators (s and r). But, it goes on to use a constructed generator “t”, as in

image

pdf 

we get back to the idea of cyclic group that is, where a couple of operators (in a product) are an object to the nth power. What is also interesting is that the constructed group characterizes “rotor” machine rotation (as in generating the Friedman table) if you look at no-s as “=” and s as “-“. Look at s as sign, that is.

Now we get to probably why Turing chose in his On Permutation’s manuscript to use the quaternion group as his example:

image

pdf 

Here we see a little of representation theory – putting the group dynamics into the form of matrices (in my klutzy and very simplistic way of thinking about abstract math).

Having constructed a group from the a and b terms (bound by their defining relations), the point is that a 2-dimensional general linear space is formed, taking complex inputs. That is, we have matrix math (with complex numbers as the matrix elements). We can also have rotor-based calculators – as alternative forms of computing culture, too (avoiding matrices).

But, we get to see some more “advanced math” on display. Distinct from groups and matrices, we see the “algebra” H introduced (as 4-term expressions); simply as defined. But, more than that, the map from the generators a/b to the “generators” i/j moves us into a 2-dimensional machine/matrix, working over the complex inputs, over the specifically real field R-algebras. Of course, Turing’s manuscript pointedly used i and j as “generator” having earlier (in the same paper) made lots of references to a and b (as terms of words generated by rotor arrays).

We now understand, furthermore that specifically free groups have a particular argumentation role to play, in the reasoning class encompassing Turing’s manuscript topic. Once one is able to see the rotor machine as a generative calculator (doing group-based crypto), it is the strong laws of numbers ( in their group variant) based on the uniformity-measure from free group theory that allows Turing to discuss the asymptotic properties.

More modern re-workings on the topic of group-based crypto seem to give us what we need to understand Turing’s 1930s era reasoning about limiting distributions, as he argued with domains of definition. We can think of domains of definitions in that environment as choice of partitions of the various named states of the state machine (group elements, that is). There too, he needed to argue that either all terms were involved in contributing atomic measures, or none were contributing (giving zero). Since cosets are just a way of specifying a partition (of the state space, as we would call it now), we can now the thinking behind most of his manuscript. Furthermore, quotient groups are one way of forming up a particular regime of cosets, particularly when the quotient uses a free group as the denominator.

image

pdf 

So its fun to see a good-old 1930s rotor crypto machine as something more than merely doing ciphering. It’s rather more general, in computer science terms.

Posted in coding theory, early computing, enigma

conjugation, inner aut, and center

image

http://en.wikipedia.org/wiki/Inner_automorphism

The above gives us a really intuitive understanding of what Turing cared about, in the enigma-era, when looking at automorphisms.

First, the term“inner automorphism” just means ‘conjugation’ – which is just what happens when the enigma rotor rotates (in a world of fixed coordinates). This gives us the friedman square, of course.

once we now that the inner auts themselves form a group, its quite intuitive that one forms a ratio – of this group (denominator) to the group of all automorphisms (numerator). i.e. A / IA. One does this in order to measure – in a proportion sense – e.g. 10/7 – how much the overall group has commutative properties (and how much does not…)

We also get a highly intuitive understand of the notion of center – its just the notion of a group identity identity ‘bumped up’ –  to subgroup level thinking. If we need to be doing group operations on subgroups and thus we need a concept of identity, now we have it!

Posted in coding theory

Finding Turing’s group-theory textbook

image

http://en.wikipedia.org/wiki/Free_group

as a student and then tutor of logic in1935ish and given the dominance showin in his paper on computable numbers, Turing would be familiar with the Banach-Tarski paradox – and all the apparatus that goes with it, moreover. That apparatus is the “programming language” of groups, using set theory notation. As any computer science student knows, the first automata programs one learns to “design” are built in graph notation, from which one then codes up the Turing machine’s Instructions (where states and cycles within the graph become configuration within the machines “configuration space”).

Posted in early computing

bad day with certs – haha

image

http://blogs.msdn.com/b/bharry/archive/2013/02/23/bad-day.aspx

I know its evil to laugh at other’s misfortune. but when you have told folks for years what not to do (and there is always a reason not to do anything about it), you eventually just laugh.

So NSA (engineering method) did me a favor. I didn’t get to see what it produced, but I did get to meet the people (govt or contractor). And you could smell the quality – in engineering terms. You could also smell the limits (particular if you have learned to work with govt-employed product manager and seen the inherent limits that they work under and think in – due to the way Federal govt work culture is organized).

The very first lesson from NSA ”culture” was: crypto is about keying, keying and more keying (did I say keying, yet)? There is nothing else, of much importance (and that includes the math). Everything from analysis to signals collection comes down to the keys. So get the keying right.

Certs are keying. They are not done right in commodity systems; mostly because everyone cut corners. Generalist Americans are bad at certs, in the same way they are bad at math. The reasons are the same (its not cool to be good at math/certs; cos some dick might open his big mouth and starting posturing – to cover up his own inabilities).

Posted in certs

multiple VHDs for san copy in SCVMM

Yet again, SCVMM becomes frustrating. Suddenly, something that was san-copy-able became not.

image

The apparent cause is this. you must have one VHD per original LUN. Do not put (1) another VHD into the same iscsi target partition. Only then can the various mechanism set up the differencing disks, back on the iscsi target server.

Sigh. how hard would it have been to issue a warning, for such a noticeable case!?

Oh Well. We Found it. And a rationale that holds water. When you get blocked on SCVMM, go do some crypto puzzles – which actually make rather more sense. Then your mind gets in the right gear, for figuring system center.

Posted in system center

old man cryptome’s following (inferred)

image

what the chart does not say is (and its possibly due to my article being crap) is that almost none of the readership do any follow through (to links, for example).

This suggests the site has essentially entertainment value. Folks channel surf.

Personally, I find cryptome’s use of interlacing themes interesting; and the topics he likes are similar to my interests (trust, dupery, and the general way that propaganda is used to create a nice docile citizenry.) Right now, America public seems to be being put back in their historical role of hating folks from the East; with lots of demonization, etc. So much for American exceptionalism, 2013 era.

Though is has little or nothing  to do with Cryptome, its also fascinating to see the by country distribution :

image

Posted in rant, Uncategorized

M-209 solution, 1944 (then) Empire of Japan

So we know that the might efforts of the UK solved enigma (and enigma indicators – a rather harder problem). And various James Bond legends were born; all revolving around the sheer magnitude of that unique achievement (which shortened the war by… yada yada ). But, we are learning that the equivalent of enigma (the American/hagelin M./209) was also subject to the same class of attacks by at least 2 axis powers, now, including WWII-era Empire of Japan. This is not entirely surprising to us (at this point of our understanding of crypto principles). What is unknown is what kind of machinery the Japan military was using (which is the interesting part of the story).

image

via cryptome

Of course the typical American is still misled, 50 years later, to believe otherwise (that only “enemy” codes were broken, or breakable).

What would be interesting would be to get via targeted search the OLD records of what the US knew about its own vulnerabilities about its own machines as known from either its own analysis or post-war intimidation, torture or other shakedowns of rival crypt analytical services staff.

Its pointless asking the UK, being so wrapped up in the james bond myth, 50 years of now old men talking about what they pretended to do in the war (while actually acting as cannon fodder), and general national self-delusion on topics of crypto or signal capture.

Posted in crypto, early computing

1940s revisited–probability on graphs for crypto; Turing’s Q for limiting distributions

image

PROBABILITY ON GRAPHS AND GROUPS- THEORY AND …

Concerning historical timing, we have thought for a while that Turing’s “On Permutations” manuscript was written about 1939 – in that period after which Turing is known from records to have been on GCCS training courses and therefore learned basic GCCS-terminology;.such as uprights and beetles. It is this period where he is, from Hodges book, “sent back” to Kings seeking to use the academic process to learn what he can via the research method. And this means writing a paper and floating its ideas with academics via this traditional means of academic argumentation. In  hindsight and on looking at the content, we we can see that he has already figured that there is a world of analysis that links up constraints, axiomatic probability, and group theory. Be they Turing bombe’s enigma-era menu constraints (of a partial covering graph) or the Colossus run-constraints, one sees a general consistency of though concerning “strategies for search”.

Since the argument in the manuscript has to meet rough academic standards required of a King’s Fellow, this driver alone would account for some of the rather pedantic form of the manuscript. Furthermore the timing aligns with Turing’s own known topics of study in 1936-38 – group theory and axiomatic logic (of course), as studied in the first years of his Princeton work or taught by Turing in Cambridge Tipos teaching. (I bet Turing was a terrible teacher.)

Since there are still academic considerations at stake, Turing still has to meet academic rigor. On looking at the form of the rigor, there is one outstanding area that we still struggle with. It concerns how to connect up his use of certain math argumentation with the reason why he thought it so necessary (to use the Q function, representation theory, and domains of definition).

Perhaps we can study the following (happenstance on similar topics as Turing was studying 60 years prior) to help us understand WHY the argument element was perceived as so necessary. Once we understand it in this modern place, Perhaps we will have enough language decoding skill to see the cues in Turing’s choice of phasing (that would be recognizable to a 1930s Cambridge Don audience) that might confirm that the reasons that were driving Turing’s writing were the same as are driving this author’s writing: that one wants to prove (for limiting distributions in Turing’s case) that either the results is 0 or the result is not – in which case all the graph elements have contributed to the non-zero result. This is a spectral result, of course, and one (for Turing’s case) of fiddling around with cosets;-

image

PROBABILITY ON GRAPHS AND GROUPS- THEORY AND …

Posted in crypto

Turing Mechanism

image

image

image

A Thesis

Its tempting to think of concatenated codes, where the inner code is the activator and the outer code is the inhibitor. One is producing distance, the other is distributing it into an extended field.

 

image

 

image

See http://dspace.mit.edu/handle/1721.1/4303

Posted in coding theory, non linearity