An Easy Defence against Dan Kaminsky's DNS attack

So Dan Kaminsky's attack really isn't that sophisticated after all. It's not a birthday attack --- per request (on unpatched servers) it still requires throwing 2^15 spoofed packets at the server before the real reply arrives for a reasonable expectation of success. Getting that many packets on target in time is difficult. The weakness is in the way recursive (i.e. caching) name server accepts in-baliwick glue records thrown at it for any domain that kind-of looks like it belongs. Each potential in-baliwick name becomes a potential point of attack so there is a very broad front for a mass spoofing session to attack. Each point could alone reliably defend against many packets but with a small chance of failure across a very broad front a storm of packets still leads to a quick failure (about 2^16 points of request and spoofed packets to match). However, by making a recursive name server instead throw away those in-baliwick responses and only accept glue when it (subsequently) is actually asking for the A record for an in-baliwick name-server a mass attack is suddenly collapsed to a single and more easily defended attack.

SPF records for

I just added SPF records for my domain. I added a neutral "?all" as the last condition so hopefully my mail delivery wont be any worse than before --- I strangely doubt that however, and cringe to learn I put a one week lifetime on these records --- what was I thinking? Some mail I sent to Japan, through the otherwise reliable Google Apps, seems to be going astray so I was hoping a little added SPF spice might improve its chances of arriving. Fool I am.

Cheap Copies vs Copyright

Copyright came into existence when making copies was expensive, and in its very successful application until this century has remained expensive. Physical publishing of books is becoming cheaper all the time as a result of improvements in xerography but still the initial outlay in hardware required to achieve the lowest costs per page are still significant. Copyright in these situations encourage investment that mightn't occur otherwise; not because copying is cheap for any unauthorized reprints but because it is expensive for the authorized ones and the publisher wants to assure a return on his investment before he makes a significant outlay in printing hardware. The same can be said for optical disks which are cheap individually but mass production requires the use of extremely expensive priniting facilities. The marginal costs of an optical disc are almost nothing but the vast initial costs must be amortized over all optical discs in order for their manufacture to be profitable. A strong copyright regime made such investments easily warrented.

Digital Squatters

The Canada government wants to gut our property law and entrench digital squatters rights to wealthy American Oligarchs in all our personal electronic devices, be they computers, music players, televisions, book-readers for the blind, telephones, mapping and positioning devices, ... --- in short, anything containing electronics that will be manufactured in this century.

Delimited Continuations

Delimited continuations are best thought of as the difference of continuations. Anywhere where one continuation encloses another (i.e. running from one point you reach the second) leads to a well defined difference. Consider a simple subroutine as such a difference, between the entry point to the subroutine and the exit point. In high level languages the exit point of a subroutine is the end of the block or an explicit return statement wholely equivalent to the final statement in a program. So consider a subroutine as if it were a program itself; the entry continuation runs the subroutine and then stops; the exit continuation simply stops. The difference between them is the body of the subroutine followed by some undefined behaviour. When you call the subroutine you provide the context necessary to fully define the thread of execution. The return continuation is implicit and the resulting code is well structured, modular and readable.

Invoking a delimited continuation behaves just like a subroutine call and not like a jump. The return context is necessary to fully define the thread of execution and is provided implicitly at the point of invocation. It is as easy to use such a delimited continuation in as modular and readable way as any subroutine. Capturing a delimited continuation as a first-class value in a high level language involves some new control structures. In Scheme we can define these control structures directly using macros, and then hide call/cc for common use. In other languages we may add only delimited continuations as first-class values. Using the end of a program as the second part of difference it can be seen that delimited continuations encompass ordinary continuations as a special case, so no expressive power is lost in using delimted continuations only.

Delimited Continuations

I've become enamoured of delimited continuations. For the unenlightened, continuations in a high level language are equivalent to addresses you can shove into a program counter in a machine language --- i.e. a continuation is a jump target and is used for looping and for subroutine calls. In an assembly langauge you can create these addresses either as branch labels or using a opcode like `call' or `jsr' which pushes the current address into a register or onto the stack and then branches to a subroutine. Both the jump to the subroutine and the return address saved are continuations but the return address has the interesting property of being generated dynamically and saved as a data word. High level languages dont usually let you meddle with the flow of control like you can in an assembly language, but a few like the Scheme which support first-class continuations do, and the results can be incredibly powerful and just as unreadable as assembly language.

Scheme is a dialect of lisp and to handle the functional (lambda calculus) nature of the language continuations need to take a single argument to pass on the value that all lisp expressions (and hence all jump targets) must return. The call/cc command gives access to the continuation in the roundabout way of lambda calculus by realizing a lambda expression with the return continuation of call/cc expression.

(define (sgn x)
    (lambda (return-sgn) ; `return-sgn' is just a variable bound to the continuation
      (if ( x 0) (return-sgn +1))
      (return-sgn 0)
      (explode) ; we never explode

Here is a simple Scheme procedure that returns the sign of a number. Continuations are unnessesary to achieve this simple result but it demonstrates the basic idea of continuations; they are first-class objects that can be stored in a variable (here I used the variable name `return-sgn') and in calling them you never return to the point of invocation. Continuations can also be aggregated into arbitrary data structures of any scope, may be invoked anywhere whatsoever, perhaps repeatedly to create loops. They can be called from deeply nested recursive procedures jumping out from the recursion in one step and conversely you can jump into a deeply recursive procedure from a previously saved continuation. Trying to follow the thread of execution can cause your brain to explode. Gotos are wimps when it comes to the obfuscation you can achieve with first-class continuations.

Delimited continuations are a refinement that go some way to improving the structure and readabilty of the code over what you would get when using the undeliminated variety.

So, I'm an Idiot. How not to Learn Haskell

I've just come to the realization that two months of haskell progress in my regatta scoring programme was a waste of time. I was porting from python so I couldn't escape from the imperative mindest. My problem was I needed to analyze some racing results and compute results progressively proceeding from raw data, through a sucession of refinements, until finally being able to compute overall results. This was too messy to hand around piece by piece so I needed an overall record to contain the data as it was computed. This was my downfall. Because I was generating the data progressively, later computations depending on earlier ones, I was assuming that to define the overall computation in a purely functional way the declarative form would have to mirror the data flow. I saw myself as having to pass a record with undefined fields from function to function, adding fields and passing the more defined record onto later computations. Consequently I decided I would have to use a monadic approach to emulate the imperative style. This would avoid the unecessary duplication and bookkeeping of the purer approach.

Dell Canada is selling machines with Ubuntu

I'm tempted. They are quite nice core 2 machines with everything on the motherboard. No weird drivers needed as far as I can tell. Intel video which is a plus for someone who likes to compile their own kernels. The price isn't bad but it isn't much cheaper than the XP machines which are usually discounted from their advertized price.

Forall --- forget about it

Using forall as a quantifier is very confusing. It implies predicate logic and, while I am sure there is a formal system of types, it is not a predicate logic. Here forall represents "don't care" or "I'm not looking inside anyway so why should I care". There is still a one-to-one mapping between the type formalism and model. Not at all the same concept as universal quantification which models as "all these possibilties". There is one function which treats that data as a black box. If dynamic dispatch is needed for instances of a class the calling function doesn't need to know about the details, even if the runtime has to add dispatch code (that haskell 98 would never need).

Efficiency in Haskell

I constantly worry about efficiency in my haskell code. Lazy evaluation helps here. Many algorithms that look like they loop repeatedly are actually linear because of haskell's laziness. Recursive string manipulations that return concatenated strings are usually linear despite strings being represented as linked lists. Laziness helps you avoid needleesly higher order implementations but has its own costs in memory allocation. Haskell's own Show class implements conversions to strings using a tail recursive showsPrec function instead of a lazily concatenating strings.


Subscribe to Matt's Blog RSS