Can't set attributes on instance of "object" class

So, I was playing around with Python while answering this question, and I discovered that this is not valid:

o = object()
o.attr = 'hello'

due to an AttributeError: 'object' object has no attribute 'attr'. However, with any class inherited from object, it is valid:

class Sub(object):
    pass

s = Sub()
s.attr = 'hello'

Printing s.attr displays 'hello' as expected. Why is this the case? What in the Python language specification specifies that you can't assign attributes to vanilla objects?

_{For other workarounds, see How can I create an object and add attributes to it?.}