Some time ago, with cfengine-3.3.5 clients I started getting this error server side:

Jan  2 10:26:33 serv cf3[7732]:  Private decrypt failed = padding check failed
Jan  2 10:29:15 serv cf3[7732]:  Private decrypt failed = block type is not 02
Jan  2 10:31:47 serv cf3[7732]:  Private decrypt failed = padding check failed 

The clients could no longer authenticate themselves against the server, and became isolated. I was not able to determine reasons of the error, which seems to happen randomly, at any time, even without policies update. Operating system, architecture, ip subnet didn’t matter in occurrence of the problem.

Trying to re-bootstrap clients did not help:

-> This host is: mail
-> Operating System Type is linux
-> Operating System Release is 2.6.32.25lp
-> Architecture = i686
-> Internal soft-class linux for host mail
-> No previous policy has been cached on this host
-> Assuming the policy distribution point at:
192.168.200.2:/var/cfengine/masterfiles
-> Attempting to initiate promised autonomous services...

BAD: Unspecified server refusal (see verbose server output)
!! Authentication dialogue with 192.168.200.2 failed
R: This autonomous node assumes the role of voluntary client
R: !! Failed to pull policy from policy server
R: !! Did not start the scheduler
!! Bootstrapping failed, no input file at
/var/cfengine/inputs/promises.cf after bootstrap

Update 2013-04-10: Still have this issue with cfengine-3.4.2

After testing several fixes from 3.4.x branch, this patch solved the problem:

lastseen: initialize variable, don't propagate garbled digest

When calling Address2Hostkey(address, result) the result would only
be set if the address is known in the lastseen database. However,
some code did not check the return value of the fn() and still used
the result as if it were valid.

Now, just initialize the result to an empty string anyway.

For the record, the error occurs during the initial client/server encrypted challenge/dialog, in AuthenticationDialogue()