**BIND configuration**

Generate a key using the dnssec-keygen utility like this:
   dnssec-keygen -a HMAC-MD5 -b 512 -n USER user.domain.com.

and this will create two files like this:

   Kuser.domain.com.+157+47950.key
   Kuser.domain.com.+157+47950.private

Using the information from the public key add to your dns server configuration the key:

   key user.domain.com. {
     algorithm HMAC-MD5;
     secret "xAw7F/axmVSxsZ+V4LAZnkeYObjOaJjbVKf21Zl4WhxtRHdlhqWSeCdd fIVR6MhC8LSQoim7NfkWD2j7WT5AHw==";
   };

where secret is the value from the public key, that in my example looks like this:

   $ cat Kuser.domain.com.+157+47950.key
   user.domain.com. IN KEY 0 3 157 xAw7F/axmVSxsZ+V4LAZnkeYObjOaJjbVKf21Zl4WhxtRHdlhqWSeCdd fIVR6MhC8LSQoim7NfkWD2j7WT5AHw==

Finally we need to allow update access for the key:

<code>
zone "ec2.domain.com"
{
   type master;
   file "/etc/bind/zone/ec2.domain.com";
   allow-update { key user.domain.com.; };
   allow-query { any; };
};
</code>

**Using nsupdate to update the hostname**

Next we will need to upload the key we created on the EC2 image (later we will save it inside the AMI once all runs well) and test to see if it is working properly.
<code>
cat<<EOF | /usr/bin/nsupdate -k Kuser.domain.com.+157+47950.private -v
server ns1.domain.com
zone ec2.domain.com
update delete test.ec2.domain.com A
update add test.ec2.domain.com 60 A <some_IP>
show
send
EOF
</code>

**Finally automation :-)**

Now we just have to put all the pieces together and using a simple script like this will do the job:
ec2-hostname.sh:

<code |f ec2-hostname.sh>
#!/bin/bash

# you will need to have the key available in the instance in the same dir as this script
DNS_KEY=Kuser.domain.com.+157+47950.private
DOMAIN=domain.com

USER_DATA=`/usr/bin/curl -s http://169.254.169.254/latest/user-data`
HOSTNAME=`echo $USER_DATA`
#set also the hostname to the running instance
hostname $HOSTNAME.$DOMAIN

PUBIP=`/usr/bin/curl -s http://169.254.169.254/latest/meta-data/public-ipv4`
cat<<EOF | /usr/bin/nsupdate -k $DNS_KEY -v
server ns1.$DOMAIN
zone ec2.$DOMAIN
update delete $HOSTNAME.ec2.$DOMAIN A
update add $HOSTNAME.ec2.$DOMAIN 60 A $PUBIP
send
EOF

LOCIP=`/usr/bin/curl -s http://169.254.169.254/latest/meta-data/local-ipv4`
cat<<EOF | /usr/bin/nsupdate -k $DNS_KEY -v
server ns1.$DOMAIN
zone ec2-int.$DOMAIN
update delete $HOSTNAME.ec2-int.$DOMAIN A
update add $HOSTNAME.ec2-int.$DOMAIN 60 A $LOCIP
send
EOF
</code>